Recovering zeros of polynomials modulo a prime

Gómez, Domingo; Gutierrez, Jaime

doi:10.1090/S0025-5718-2014-02808-1

Recovering zeros of polynomials modulo a prime
HTML articles powered by AMS MathViewer

by Domingo Gómez and Jaime Gutierrez PDF

Math. Comp. 83 (2014), 2953-2965 Request permission

Abstract:

Let $p$ be a prime and $\mathbb {F}_p$ the finite field with $p$ elements. We show how, when given an irreducible bivariate polynomial $F \in \mathbb {F}_p[X,Y]$ and an approximation to a zero, one can recover the root efficiently, if the approximation is good enough. The strategy can be generalized to polynomials in the variables $X_1,\ldots ,X_m$ over the field $\mathbb {F}_p$. These results have been motivated by the predictability problem for nonlinear pseudorandom number generators and other potential applications to cryptography.

References

L. Babai, On Lovász’ lattice reduction and the nearest lattice point problem, Combinatorica 6 (1986), no. 1, 1–13. MR 856638, DOI 10.1007/BF02579403
Simon R. Blackburn, Domingo Gomez-Perez, Jaime Gutierrez, and Igor E. Shparlinski, Predicting nonlinear pseudorandom number generators, Math. Comp. 74 (2005), no. 251, 1471–1494. MR 2137013, DOI 10.1090/S0025-5718-04-01698-9
Simon R. Blackburn, Domingo Gomez-Perez, Jaime Gutierrez, and Igor E. Shparlinski, Reconstructing noisy polynomial evaluation in residue rings, J. Algorithms 61 (2006), no. 2, 47–59. MR 2281416, DOI 10.1016/j.jalgor.2004.07.002
Johannes Blömer and Alexander May, A tool kit for finding small roots of bivariate polynomials over the integers, Advances in cryptology—EUROCRYPT 2005, Lecture Notes in Comput. Sci., vol. 3494, Springer, Berlin, 2005, pp. 251–267. MR 2352192, DOI 10.1007/11426639_{1}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, 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
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}
Jean-Sébastien Coron, Finding small roots of bivariate integer polynomial equations: a direct approach, Advances in cryptology—CRYPTO 2007, Lecture Notes in Comput. Sci., vol. 4622, Springer, Berlin, 2007, pp. 379–394. MR 2423860, DOI 10.1007/978-3-540-74143-5_{2}1
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
Domingo Gómez, Jaime Gutierrez, and Álvar Ibeas, Attacking the Pollard generator, IEEE Trans. Inform. Theory 52 (2006), no. 12, 5518–5523. MR 2300710, DOI 10.1109/TIT.2006.885451
Martin Grötschel, László Lovász, and Alexander Schrijver, Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics: Study and Research Texts, vol. 2, Springer-Verlag, Berlin, 1988. MR 936633, DOI 10.1007/978-3-642-97881-4
Jaime Gutierrez and Álvar Ibeas, Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits, Des. Codes Cryptogr. 45 (2007), no. 2, 199–212. MR 2341883, DOI 10.1007/s10623-007-9112-3
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
Ellen Jochemsz and Alexander May, A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants, Advances in cryptology—ASIACRYPT 2006, Lecture Notes in Comput. Sci., vol. 4284, Springer, Berlin, 2006, pp. 267–282. MR 2444641, DOI 10.1007/11935230_{1}8
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, 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
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
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
Daniele Micciancio and Shafi Goldwasser, Complexity of lattice problems, The Kluwer International Series in Engineering and Computer Science, vol. 671, Kluwer Academic Publishers, Boston, MA, 2002. A cryptographic perspective. MR 2042139, DOI 10.1007/978-1-4615-0897-7
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
Igor Shparlinski, Cryptographic applications of analytic number theory, Progress in Computer Science and Applied Logic, vol. 22, Birkhäuser Verlag, Basel, 2003. Complexity lower bounds and pseudorandomness. MR 1954519, DOI 10.1007/978-3-0348-8037-4
Joseph H. Silverman (ed.), Cryptography and lattices, Lecture Notes in Computer Science, vol. 2146, Springer-Verlag, Berlin, 2001. MR 1903881, DOI 10.1007/3-540-44670-2
Serguei A. Stepanov, Arithmetic of algebraic curves, Monographs in Contemporary Mathematics, Consultants Bureau, New York, 1994. Translated from the Russian by Irene Aleksanova. MR 1321599