Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Predicting nonlinear pseudorandom number generators
HTML articles powered by AMS MathViewer

by Simon R. Blackburn, Domingo Gomez-Perez, Jaime Gutierrez and Igor E. Shparlinski PDF
Math. Comp. 74 (2005), 1471-1494 Request permission

Abstract:

Let $p$ be a prime and let $a$ and $b$ be elements of the finite field $\mathbb {F}_p$ of $p$ elements. The inversive congruential generator (ICG) is a sequence $(u_n)$ of pseudorandom numbers defined by the relation $u_{n+1} \equiv a u_n^{-1} + b \bmod p$. We show that if sufficiently many of the most significant bits of several consecutive values $u_n$ of the ICG are given, one can recover the initial value $u_0$ (even in the case where the coefficients $a$ and $b$ are not known). We also obtain similar results for the quadratic congruential generator (QCG), $v_{n+1} \equiv f(v_n) \bmod p$, where $f \in \mathbb {F}_p[X]$. This suggests that for cryptographic applications ICG and QCG should be used with great care. Our results are somewhat similar to those known for the linear congruential generator (LCG), $x_{n+1} \equiv a x_n + b \bmod p$, but they apply only to much longer bit strings. We also estimate limits of some heuristic approaches, which still remain much weaker than those known for LCG.
References
  • M. Ajtai, R. Kumar and D. Sivakumar, ‘A sieve algorithm for the shortest lattice vector problem’, Proc. 33rd ACM Symp. on Theory of Comput., ACM, 2001, 601–610.
  • P. H. T. Beelen and J. M. Doumen, Pseudorandom sequences from elliptic curves, Finite fields with applications to coding theory, cryptography and related areas (Oaxaca, 2001) Springer, Berlin, 2002, pp. 37–52. MR 1995326
  • S. R. Blackburn, D. Gomez-Perez, J. Gutierrez and I. E. Shparlinski, ‘Predicting the inversive generator’, Proc. 9th IMA Intern. Conf on Cryptography and Coding, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2898 (2003), 264–275.
  • S. R. Blackburn, D. Gomez-Perez, J. Gutierrez and I. E. Shparlinski, ‘Reconstructing noisy polynomial evaluation in residue rings’, J. of Algorithms (to appear).
  • Dan Boneh, Shai Halevi, and Nick Howgrave-Graham, The modular inversion hidden number problem, Advances in cryptology—ASIACRYPT 2001 (Gold Coast), Lecture Notes in Comput. Sci., vol. 2248, Springer, Berlin, 2001, pp. 36–51. MR 1934514, DOI 10.1007/3-540-45682-1_{3}
  • Joan Boyar, Inferring sequences produced by pseudo-random number generators, J. Assoc. Comput. Mach. 36 (1989), no. 1, 129–141. MR 1072416, DOI 10.1145/58562.59305
  • Joan Boyar, Inferring sequences produced by a linear congruential generator missing low-order bits, J. Cryptology 1 (1989), no. 3, 177–184. MR 1007218, DOI 10.1007/BF02252875
  • Gustavus J. Simmons (ed.), Contemporary cryptology, IEEE Press, New York, 1992. The science of information integrity. MR 1205128
  • Wun Seng Chou, The period lengths of inversive pseudorandom vector generations, Finite Fields Appl. 1 (1995), no. 1, 126–132. MR 1334630, DOI 10.1006/ffta.1995.1009
  • Don Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology 10 (1997), no. 4, 233–260. MR 1476612, DOI 10.1007/s001459900030
  • Don Coppersmith, Finding small solutions to small degree polynomials, Cryptography and lattices (Providence, RI, 2001) Lecture Notes in Comput. Sci., vol. 2146, Springer, Berlin, 2001, pp. 20–31. MR 1903884, DOI 10.1007/3-540-44670-2_{3}
  • Mary Flahive and Harald Niederreiter, On inversive congruential generators for pseudorandom numbers, Finite fields, coding theory, and advances in communications and computing (Las Vegas, NV, 1991) Lecture Notes in Pure and Appl. Math., vol. 141, Dekker, New York, 1993, pp. 75–80. MR 1199823
  • Alan M. Frieze, Johan Håstad, Ravi Kannan, Jeffrey C. Lagarias, and Adi Shamir, Reconstructing truncated integer variables satisfying linear congruences, SIAM J. Comput. 17 (1988), no. 2, 262–280. Special issue on cryptography. MR 935340, DOI 10.1137/0217016
  • Guang Gong, Thomas A. Berson, and Douglas R. Stinson, Elliptic curve pseudorandom sequence generators, Selected areas in cryptography (Kingston, ON, 1999) Lecture Notes in Comput. Sci., vol. 1758, Springer, Berlin, 2000, pp. 34–48. MR 1767726, DOI 10.1007/3-540-46513-8_{3}
  • Martin Grötschel, László Lovász, and Alexander Schrijver, Geometric algorithms and combinatorial optimization, 2nd ed., Algorithms and Combinatorics, vol. 2, Springer-Verlag, Berlin, 1993. MR 1261419, DOI 10.1007/978-3-642-78240-4
  • J. Gutierrez, I. E. Shparlinski and A. Winterhof, ‘On the linear and nonlinear complexity profile of nonlinear pseudorandom number generators’, IEEE Trans. on Information Theory, 49 (2003), 60–64.
  • F. Hess and I. E. Shparlinski, ‘On the linear complexity and multidimensional distribution of congruential generators over elliptic curves’, Designs, Codes and Cryptography (to appear).
  • Nicholas Howgrave-Graham, Finding small roots of univariate modular equations revisited, Cryptography and coding (Cirencester, 1997) Lecture Notes in Comput. Sci., vol. 1355, Springer, Berlin, 1997, pp. 131–142. MR 1660500, DOI 10.1007/BFb0024458
  • Antoine Joux and Jacques Stern, Lattice reduction: a toolbox for the cryptanalyst, J. Cryptology 11 (1998), no. 3, 161–185. MR 1633944, DOI 10.1007/s001459900042
  • Ravi Kannan, Algorithmic geometry of numbers, Annual review of computer science, Vol. 2, Annual Reviews, Palo Alto, CA, 1987, pp. 231–267. MR 921497
  • Ravi Kannan, Minkowski’s convex body theorem and integer programming, Math. Oper. Res. 12 (1987), no. 3, 415–440. MR 906415, DOI 10.1287/moor.12.3.415
  • Donald E. Knuth, Deciphering a linear congruential encryption, IEEE Trans. Inform. Theory 31 (1985), no. 1, 49–52. MR 786369, DOI 10.1109/TIT.1985.1056997
  • V. S. Konjagin, The number of solutions of congruences of the $n$th degree with one unknown, Mat. Sb. (N.S.) 109(151) (1979), no. 2, 171–187, 327 (Russian). MR 542556
  • Hugo Krawczyk, How to predict congruential generators, J. Algorithms 13 (1992), no. 4, 527–545. MR 1187200, DOI 10.1016/0196-6774(92)90054-G
  • J. C. Lagarias, Pseudorandom number generators in cryptography and number theory, Cryptology and computational number theory (Boulder, CO, 1989) Proc. Sympos. Appl. Math., vol. 42, Amer. Math. Soc., Providence, RI, 1990, pp. 115–143. MR 1095554, DOI 10.1090/psapm/042/1095554
  • A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI 10.1007/BF01457454
  • D. Micciancio and S. Goldwasser, Complexity of lattice problems, Kluwer Acad. Publ., 2002.
  • Phong Q. Nguyen and Jacques Stern, Lattice reduction in cryptology: an update, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 85–112. MR 1850600, DOI 10.1007/10722028_{4}
  • Phong Q. Nguyen and Jacques Stern, The two faces of lattices in cryptology, Cryptography and lattices (Providence, RI, 2001) Lecture Notes in Comput. Sci., vol. 2146, Springer, Berlin, 2001, pp. 146–180. MR 1903893, DOI 10.1007/3-540-44670-2_{1}2
  • Harald Niederreiter, New developments in uniform pseudorandom number and vector generation, Monte Carlo and quasi-Monte Carlo methods in scientific computing (Las Vegas, NV, 1994) Lect. Notes Stat., vol. 106, Springer, New York, 1995, pp. 87–120. MR 1445782, DOI 10.1007/978-1-4612-2552-2_{5}
  • H. Niederreiter, ‘Design and analysis of nonlinear pseudorandom number generators’, Monte Carlo Simulation, A.A. Balkema Publishers, Rotterdam, 2001, 3–9.
  • Harald Niederreiter and Igor E. Shparlinski, Recent advances in the theory of nonlinear pseudorandom number generators, Monte Carlo and quasi-Monte Carlo methods, 2000 (Hong Kong), Springer, Berlin, 2002, pp. 86–102. MR 1958848
  • H. Niederreiter and I. E. Shparlinski, ‘Dynamical systems generated by rational functions’, Proc. the 15th Symp. on Appl. Algebra, Algebraic Algorithms, and Error-Correcting Codes, Lect. Notes in Comp. Sci., vol. 2643, Springer-Verlag, Berlin, 2003, 6–17.
  • V. Shoup, ‘Number theory C++ library (NTL)’, version 5.3.1, available at http://www.shoup.net/ntl/.
Similar Articles
Additional Information
  • Simon R. Blackburn
  • Affiliation: Department of Mathematics, Royal Holloway, University of London, Egham, Surrey, TW20 0EX, United Kingdom
  • Email: s.blackburn@rhul.ac.uk
  • Domingo Gomez-Perez
  • Affiliation: Faculty of Science, University of Cantabria, E-39071 Santander, Spain
  • Email: gomezd@unican.es
  • Jaime Gutierrez
  • Affiliation: Faculty of Science, University of Cantabria, E-39071 Santander, Spain
  • Email: jaime.gutierrez@unican.es
  • Igor E. Shparlinski
  • Affiliation: Department of Computing, Macquarie University, Sydney, NSW 2109, Australia
  • MR Author ID: 192194
  • Email: igor@comp.mq.edu.au
  • Received by editor(s): August 14, 2003
  • Received by editor(s) in revised form: February 6, 2004
  • Published electronically: July 27, 2004
  • © Copyright 2004 American Mathematical Society
  • Journal: Math. Comp. 74 (2005), 1471-1494
  • MSC (2000): Primary 11H06, 11K45, 11T71, 94A60
  • DOI: https://doi.org/10.1090/S0025-5718-04-01698-9
  • MathSciNet review: 2137013