×

Predicting nonlinear pseudorandom number generators. (English) Zbl 1136.11316

Summary: 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.

MSC:

11K45 Pseudo-random numbers; Monte Carlo methods
94A60 Cryptography

Software:

NTL
PDFBibTeX XMLCite
Full Text: DOI

References:

[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. · Zbl 1323.68561
[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. · Zbl 1059.11044
[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. · Zbl 1123.94330
[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). · Zbl 1178.68220
[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. · Zbl 1062.94545 · doi: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. · Zbl 0667.94006 · doi: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. · Zbl 0673.94009 · doi:10.1007/BF02252875
[8] Gustavus J. Simmons , Contemporary cryptology, IEEE Press, New York, 1992. The science of information integrity. · Zbl 0784.94019
[9] Wun Seng Chou, The period lengths of inversive pseudorandom vector generations, Finite Fields Appl. 1 (1995), no. 1, 126 – 132. · Zbl 0822.11054 · doi: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. · Zbl 0912.11056 · doi: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. · Zbl 1006.11081 · doi: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. · Zbl 0790.11058
[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. · Zbl 0654.10006 · doi: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. · Zbl 0993.94547 · doi: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. · Zbl 0837.05001
[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. · Zbl 1063.65005
[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). · Zbl 1116.14307
[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. · Zbl 0922.11113 · doi:10.1007/BFb0024458
[19] Antoine Joux and Jacques Stern, Lattice reduction: a toolbox for the cryptanalyst, J. Cryptology 11 (1998), no. 3, 161 – 185. · Zbl 0919.94011 · doi: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.
[21] Ravi Kannan, Minkowski’s convex body theorem and integer programming, Math. Oper. Res. 12 (1987), no. 3, 415 – 440. · Zbl 0639.90069 · doi: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. · Zbl 0581.94008 · doi: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). S. V. Konjagin, Letter to the editors: ”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; MR 80k:10013a], Mat. Sb. (N.S.) 110(152) (1979), no. 1, 158 (Russian).
[24] Hugo Krawczyk, How to predict congruential generators, J. Algorithms 13 (1992), no. 4, 527 – 545. · Zbl 0784.65006 · doi: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. · Zbl 0747.94011 · doi: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. · Zbl 0488.12001 · doi:10.1007/BF01457454
[27] D. Micciancio and S. Goldwasser, Complexity of lattice problems, Kluwer Acad. Publ., 2002. · Zbl 1140.94010
[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. · Zbl 0980.94010 · doi: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. · Zbl 1006.94531 · doi: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) Lect. Notes Stat., vol. 106, Springer, New York, 1995, pp. 87 – 120. · Zbl 0893.11030 · doi: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. · Zbl 1076.65008
[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. · Zbl 1030.11072
[34] V. Shoup, ‘Number theory C++ library (NTL)’, version 5.3.1, available at http://www.shoup.net/ntl/.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.