Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 

 

Predicting nonlinear pseudorandom number generators


Authors: Simon R. Blackburn, Domingo Gomez-Perez, Jaime Gutierrez and Igor E. Shparlinski
Journal: Math. Comp. 74 (2005), 1471-1494
MSC (2000): Primary 11H06, 11K45, 11T71, 94A60
Published electronically: July 27, 2004
MathSciNet review: 2137013
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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.
  • 2. 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
  • 3. 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.
  • 4. S. R. Blackburn, D. Gomez-Perez, J. Gutierrez and I. E. Shparlinski, `Reconstructing noisy polynomial evaluation in residue rings', J. of Algorithms (to appear).
  • 5. 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, 10.1007/3-540-45682-1_3
  • 6. Joan Boyar, Inferring sequences produced by pseudo-random number generators, J. Assoc. Comput. Mach. 36 (1989), no. 1, 129–141. MR 1072416, 10.1145/58562.59305
  • 7. Joan Boyar, Inferring sequences produced by a linear congruential generator missing low-order bits, J. Cryptology 1 (1989), no. 3, 177–184. MR 1007218, 10.1007/BF02252875
  • 8. Gustavus J. Simmons (ed.), Contemporary cryptology, IEEE Press, New York, 1992. The science of information integrity. MR 1205128
  • 9. Wun Seng Chou, The period lengths of inversive pseudorandom vector generations, Finite Fields Appl. 1 (1995), no. 1, 126–132. MR 1334630, 10.1006/ffta.1995.1009
  • 10. Don Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology 10 (1997), no. 4, 233–260. MR 1476612, 10.1007/s001459900030
  • 11. 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, 10.1007/3-540-44670-2_3
  • 12. 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
  • 13. 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, 10.1137/0217016
  • 14. 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, 10.1007/3-540-46513-8_3
  • 15. 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
  • 16. 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.
  • 17. 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).
  • 18. 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, 10.1007/BFb0024458
  • 19. Antoine Joux and Jacques Stern, Lattice reduction: a toolbox for the cryptanalyst, J. Cryptology 11 (1998), no. 3, 161–185. MR 1633944, 10.1007/s001459900042
  • 20. Ravi Kannan, Algorithmic geometry of numbers, Annual review of computer science, Vol. 2, Annual Reviews, Palo Alto, CA, 1987, pp. 231–267. MR 921497
  • 21. Ravi Kannan, Minkowski’s convex body theorem and integer programming, Math. Oper. Res. 12 (1987), no. 3, 415–440. MR 906415, 10.1287/moor.12.3.415
  • 22. Donald E. Knuth, Deciphering a linear congruential encryption, IEEE Trans. Inform. Theory 31 (1985), no. 1, 49–52. MR 786369, 10.1109/TIT.1985.1056997
  • 23. V. S. Konjagin, The number of solutions of congruences of the 𝑛th degree with one unknown, Mat. Sb. (N.S.) 109(151) (1979), no. 2, 171–187, 327 (Russian). MR 542556
  • 24. Hugo Krawczyk, How to predict congruential generators, J. Algorithms 13 (1992), no. 4, 527–545. MR 1187200, 10.1016/0196-6774(92)90054-G
  • 25. 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, 10.1090/psapm/042/1095554
  • 26. 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, 10.1007/BF01457454
  • 27. D. Micciancio and S. Goldwasser, Complexity of lattice problems, Kluwer Acad. Publ., 2002.
  • 28. 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, 10.1007/10722028_4
  • 29. 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, 10.1007/3-540-44670-2_12
  • 30. 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) Lecture Notes in Statist., vol. 106, Springer, New York, 1995, pp. 87–120. MR 1445782, 10.1007/978-1-4612-2552-2_5
  • 31. H. Niederreiter, `Design and analysis of nonlinear pseudorandom number generators', Monte Carlo Simulation, A.A. Balkema Publishers, Rotterdam, 2001, 3-9.
  • 32. 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
  • 33. 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.
  • 34. V. Shoup, `Number theory C++ library (NTL)', version 5.3.1, available at http://www.shoup.net/ntl/.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11H06, 11K45, 11T71, 94A60

Retrieve articles in all journals with MSC (2000): 11H06, 11K45, 11T71, 94A60


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
Email: igor@comp.mq.edu.au

DOI: http://dx.doi.org/10.1090/S0025-5718-04-01698-9
Received by editor(s): August 14, 2003
Received by editor(s) in revised form: February 6, 2004
Published electronically: July 27, 2004
Article copyright: © Copyright 2004 American Mathematical Society