# zbMATH — the first resource for mathematics

Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. (English) Zbl 1159.94369
Summary: Lattice-based signature schemes following the Goldreich-Goldwasser-Halevi (GGH) design have the unusual property that each signature leaks information on the signer’s secret key, but this does not necessarily imply that such schemes are insecure. At Eurocrypt ’03, M. Szydlo [Lect. Notes Comput. Sci. 2656, 433–448 (2003; Zbl 1038.94558)] proposed a potential attack by showing that the leakage reduces the key-recovery problem to that of distinguishing integral quadratic forms. He proposed a heuristic method to solve the latter problem, but it was unclear whether his method could attack real-life parameters of GGH and NTRUSign. Here, we propose an alternative method to attack signature schemes à la GGH by studying the following learning problem: given many random points uniformly distributed over an unknown $$n$$-dimensional parallelepiped, recover the parallelepiped or an approximation thereof. We transform this problem into a multivariate optimization problem that can provably be solved by a gradient descent. Our approach is very effective in practice: we present the first successful key-recovery experiments on NTRUSign-251 without perturbation, as proposed in half of the parameter choices in NTRU standards under consideration by IEEE P1363.1. Experimentally, 400 signatures are sufficient to recover the NTRUSign-251 secret key, thanks to symmetries in NTRU lattices. We are also able to recover the secret key in the signature analogue of all the GGH encryption challenges.

##### MSC:
 94A60 Cryptography 94A62 Authentication, digital signatures and secret sharing
##### Software:
NTL; FastICA; NTRU; NTRUSign; McEliece
Full Text:
##### References:
 [1] M. Ajtai, Generating hard instances of lattice problems, in Complexity of Computations and Proofs. Quad. Mat., vol. 13 (Dept. Math., Seconda Univ. Napoli, Caserta, 2004), pp. 1-32 · Zbl 1071.11041 [2] Alon, N.; Spencer, J. H., The Probabilistic Method (2000), New York: Wiley, New York [3] Babai, L., On Lovász lattice reduction and the nearest lattice point problem, Combinatorica, 6, 1-13 (1986) · Zbl 0593.68030 [4] Consortium for Efficient Embedded Security. Efficient embedded security standards #1: Implementation aspects of NTRUencrypt and NTRUsign. Version 2.0 available at http://grouper.ieee.org/groups/1363/lattPK/index.html, June (2003) [5] Frieze, A.; Jerrum, M.; Kannan, R., Learning linear transformations, 37th Annual Symposium on Foundations of Computer Science, 359-368 (1996), Los Alamitos: IEEE Comput. Soc. Press, Los Alamitos [6] C. Gentry, M. Szydlo, Cryptanalysis of the revised NTRU signature scheme, in Proc. of Eurocrypt ’02. LNCS, vol. 2332 (Springer, Berlin, 2002) · Zbl 1055.94015 [7] C. Gentry, C. Peikert, V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, in Proc. 40th ACM Symp. on Theory of Computing (STOC), pp. 197-206 (2008) · Zbl 1231.68124 [8] C. Gentry, J. Jonsson, J. Stern, M. Szydlo, Cryptanalysis of the NTRU signature scheme (NSS) from Eurocrypt 2001, in Proc. of Asiacrypt ’01. LNCS, vol. 2248 (Springer, Berlin, 2001) · Zbl 1062.94547 [9] Goldreich, O.; Goldwasser, S.; Halevi, S., Public-key cryptosystems from lattice reduction problems, Proc. of Crypto ’97, 112-131 (1997), Berlin: Springer, Berlin · Zbl 0889.94011 [10] O. Goldreich, S. Goldwasser, S. Halevi, Challenges for the GGH cryptosystem. Available at http://theory.lcs.mit.edu/ shaih/challenge.html · Zbl 0889.94010 [11] Golub, G.; Loan, C., Matrix Computations (1996), Baltimore: Johns Hopkins Univ. Press, Baltimore · Zbl 0865.65009 [12] Hoffstein, J.; Pipher, J.; Silverman, J., NTRU: a ring based public key cryptosystem, Proc. of ANTS III, 267-288 (1998), Berlin: Springer, Berlin · Zbl 1067.94538 [13] J. Hoffstein, J. Pipher, J.H. Silverman, NSS: An NTRU lattice-based signature scheme, in Proc. of Eurocrypt ’01. LNCS, vol. 2045 (Springer, Berlin, 2001) · Zbl 0981.94039 [14] J. Hoffstein, N.A.H. Graham, J. Pipher, J.H. Silverman, W. Whyte, NTRUsign: Digital signatures using the NTRU lattice. Full version of Proc. of CT-RSA. LNCS, vol. 2612. Draft of April 2, 2002, available on NTRU’s website · Zbl 1039.94525 [15] J. Hoffstein, N.A.H. Graham, J. Pipher, J.H. Silverman, W. Whyte, NTRUsign: Digital signatures using the NTRU lattice, in Proc. of CT-RSA. LNCS, vol. 2612 (Springer, Berlin, 2003) · Zbl 1039.94525 [16] J. Hoffstein, N.A.H. Graham, J. Pipher, J.H. Silverman, W. Whyte, Performances improvements and a baseline parameter generation algorithm for NTRUsign, in Proc. of Workshop on Mathematical Problems and Techniques in Cryptology (CRM, 2005), pp. 99-126 [17] Hyvärinen, A.; Oja, E., A fast fixed-point algorithm for independent component analysis, Neural Comput., 9, 7, 1483-1492 (1997) [18] Hyvärinen, A.; Karhunen, J.; Oja, E., Independent Component Analysis (2001), New York: Wiley, New York [19] IEEE P1363.1. Public-key cryptographic techniques based on hard problems over lattices. See http://grouper.ieee.org/groups/1363/lattPK/index.html, June 2003 [20] P. Klein, Finding the closest lattice vector when it’s unusually close, in Proc. of SODA ’00 (ACM-SIAM, 2000) · Zbl 0953.65043 [21] V. Lyubashevsky, D. Micciancio, Asymptotically efficient lattice-based digital signatures, in Fifth Theory of Cryptography Conference (TCC). Lecture Notes in Computer Science, vol. 4948 (Springer, Berlin, 2008) · Zbl 1162.94389 [22] R. McEliece, A public-key cryptosystem based on algebraic number theory. Technical report, Jet Propulsion Laboratory, 1978. DSN Progress Report 42-44 [23] D. Micciancio, Improving lattice-based cryptosystems using the Hermite normal form, in Proc. of CALC ’01. LNCS, vol. 2146 (Springer, Berlin, 2001) · Zbl 1006.94529 [24] D. Micciancio, Cryptographic functions from worst-case complexity assumptions. Survey paper prepared for the LLL+25 conference. To appear · Zbl 1191.94098 [25] Micciancio, D.; Goldwasser, S., Complexity of Lattice Problems: A Cryptographic Perspective (2002), Boston: Kluwer Academic, Boston · Zbl 1140.94010 [26] D. Micciancio, O. Regev, Lattice-based cryptography, in Post-Quantum Cryprography, ed. by D.J. Bernstein, J. Buchmann (Springer, Berlin, 2008) · Zbl 1161.81324 [27] Micciancio, D.; Vadhan, S., Statistical zero-knowledge proofs with efficient provers: lattice problems and more, Advances in Cryptology—Proc. CRYPTO ’03, 282-298 (2003), Berlin: Springer, Berlin · Zbl 1122.68448 [28] M. Naor, M. Yung, Universal one-way hash functions and their cryptographic applications, in Proc. 21st ACM Symp. on Theory of Computing (STOC), pp. 33-43 (1989) [29] Nguyen, P. Q., Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto ’97, Proc. of Crypto ’99, 288-304 (1999), Berlin: Springer, Berlin · Zbl 1038.94543 [30] Nguyen, P. Q.; Regev, O., Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures, Advances in Cryptology—Proceedings of EUROCRYPT ’06, 215-233 (2006), Berlin: Springer, Berlin · Zbl 1140.94365 [31] P.Q. Nguyen, J. Stern, The two faces of lattices in cryptology, in Proc. of CALC ’01. LNCS, vol. 2146 (Springer, Berlin, 2001) · Zbl 1006.94531 [32] Regev, O., Lattice-based cryptography, Advances in Cryptology—Proc. of CRYPTO ’06, 131-141 (2006), Berlin: Springer, Berlin · Zbl 1161.94425 [33] Schnorr, C. P.; Euchner, M., Lattice basis reduction: improved practical algorithms and solving subset sum problems, Math. Program., 66, 181-199 (1994) · Zbl 0829.90099 [34] V. Shoup, NTL: A library for doing number theory. Available at http://www.shoup.net/ntl/ [35] M. Szydlo, Hypercubic lattice reduction and analysis of GGH and NTRU signatures, in Proc. of Eurocrypt ’03. LNCS, vol. 2656 (Springer, Berlin, 2003) · Zbl 1038.94558 [36] W. Whyte, Improved NTRUSign transcript analysis. Presentation at the rump session of Eurocrypt ’06, on May 30 (2006)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.