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
DOI: https://doi.org/10.1090/S0025-5718-04-01698-9
Published electronically: July 27, 2004
MathSciNet review: 2137013
Full-text PDF

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. Beelen and J. Doumen, `Pseudorandom sequences from elliptic curves', Finite Fields with Applications to Coding Theory, Cryptography and Related Areas, Springer-Verlag, Berlin, 2002, 37-52. MR 2004d:11066
  • 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. D. Boneh, S. Halevi and N. A. Howgrave-Graham, `The modular inversion hidden number problem', Proc. Asiacrypt'2001, Lect. Notes in Comp. Sci., vol. 2248, Springer-Verlag, Berlin, 2001, 36-51. MR 2003h:94022
  • 6. J. Boyar, `Inferring sequences produced by pseudo-random number generators', J. ACM, 36 (1989), 129-141. MR 91g:68035
  • 7. J. Boyar, `Inferring sequences produced by a linear congruential generator missing low-order bits', J. Cryptology 1 (1989) 177-184.MR 90g:94012
  • 8. E. F. Brickell and A. M. Odlyzko, `Cryptanalysis: A survey of recent results', Contemp. Cryptology, IEEE Press, NY, 1992, 501-540. MR 93k:94009
  • 9. W.-S. Chou, `The period lengths of inversive pseudorandom vector generations', Finite Fields Appl., 1 (1995), 126-132.MR 96i:11087
  • 10. D. Coppersmith, `Small solutions to polynomial equations, and low exponent RSA vulnerabilities', J. Cryptology, 10 (1997), 233-260. MR 99b:94027
  • 11. D. Coppersmith, `Small solutions of small degree polynomials', Proc. Intern. Conf. on Cryptography and Lattices, Lect. Notes in Comp. Sci., vol. 2146, Springer-Verlag, Berlin, 2001, 20-31. MR 2003f:11034
  • 12. M. Flahive and H. Niederreiter, `On inversive congruential generators for pseudorandom numbers', Finite Fields, Coding Theory, and Advances in Communications and Computing, Marcel Dekker, New York, 1993, 75-80. MR 94a:11117
  • 13. A. M. Frieze, J. Håstad, R. Kannan, J. C. Lagarias and A. Shamir, `Reconstructing truncated integer variables satisfying linear congruences', SIAM J. Comp., 17 (1988), 262-280.MR 89d:11115
  • 14. G. Gong, T. A. Berson and D. A. Stinson, `Elliptic curve pseudorandom sequence generators', Proc. 6th Workshop on Selected Areas in Cryptography, Lect. Notes in Comp. Sci., vol. 1758, Springer-Verlag, Berlin, 2000, 34-49. MR 2001j:94032
  • 15. M. Grötschel, L. Lovász and A. Schrijver, Geometric algorithms and combinatorial optimization, Springer-Verlag, Berlin, 1993.MR 95e:90001
  • 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. N. A. Howgrave-Graham, `Finding small roots of univariate modular equations revisited', Proc. 6th IMA Intern. Conf on Cryptography and Coding, Lect. Notes in Comp. Sci., vol. 1355, Springer-Verlag, Berlin, 1997, 131-142. MR 99j:94049
  • 19. A. Joux and J. Stern, `Lattice reduction: A toolbox for the cryptanalyst', J. Cryptology, 11 (1998), 161-185.MR 99c:94031
  • 20. R. Kannan, `Algorithmic geometry of numbers', Annual Review of Comp. Sci., 2 (1987), 231-267. MR 89a:11131
  • 21. R. Kannan, `Minkowski's convex body theorem and integer programming', Math. Oper. Res., 12 (1987), 415-440.MR 89c:90078
  • 22. D. E. Knuth, `Deciphering a linear congruential encryption', IEEE Trans. Inf. Theory 31 (1985), 49-52. MR 87c:94040
  • 23. S. V. Konyagin, `On the number of solutions of a univariate congruence of $n$th degree', Matem. Sbornik, 102 (1979), 171-187 (in Russian). MR 80k:10013a
  • 24. H. Krawczyk, `How to predict congruential generators', J. Algorithms, 13 (1992), 527-545.MR 93g:65013
  • 25. J. C. Lagarias, `Pseudorandom number generators in cryptography and number theory', Proc. Symp. in Appl. Math., Amer. Math. Soc., Providence, RI, 42 (1990), 115-143.MR 92f:11109
  • 26. A. K. Lenstra, H. W. Lenstra and L. Lovász, `Factoring polynomials with rational coefficients', Mathematische Annalen, 261 (1982), 515-534. MR 84a:12002
  • 27. D. Micciancio and S. Goldwasser, Complexity of lattice problems, Kluwer Acad. Publ., 2002.
  • 28. P. Q. Nguyen and J. Stern, `Lattice reduction in cryptology: An update', Proc. 4th Intern. Symp. on Algorithmic Number Theory, Lect. Notes in Comp. Sci., vol. 1838, Springer-Verlag, Berlin, 2000, 85-112.MR 2002h:94064
  • 29. P. Q. Nguyen and J. Stern, `The two faces of lattices in cryptology', Proc. Intern. Conf. on Cryptography and Lattices, Lect. Notes in Comp. Sci., vol. 2146, Springer-Verlag, Berlin, 2001, 146-180.MR 2003d:94082
  • 30. H. Niederreiter, `New developments in uniform pseudorandom number and vector generation', Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Lect. Notes in Statistics, vol. 106, Springer-Verlag, Berlin, 1995, 87-120. MR 97k:65019
  • 31. H. Niederreiter, `Design and analysis of nonlinear pseudorandom number generators', Monte Carlo Simulation, A.A. Balkema Publishers, Rotterdam, 2001, 3-9.
  • 32. H. Niederreiter and I. E. Shparlinski, `Recent advances in the theory of nonlinear pseudorandom number generators', Proc. Conf. on Monte Carlo and Quasi-Monte Carlo Methods, 2000, Springer-Verlag, Berlin, 2002, 86-102. MR 2003k:65005
  • 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: https://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

American Mathematical Society