×

zbMATH — the first resource for mathematics

Better key sizes (and attacks) for LWE-based encryption. (English) Zbl 1284.94088
Kiayias, Aggelos (ed.), Topics in cryptology – CT-RSA 2011. The cryptographers’ track at the RSA conference 2011, San Francisco, CA, USA, February 14–18, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-19073-5/pbk). Lecture Notes in Computer Science 6558, 319-339 (2011).
Summary: We analyze the concrete security and key sizes of theoretically sound lattice-based encryption schemes based on the “learning with errors” (LWE) problem. Our main contributions are: (1) a new lattice attack on LWE that combines basis reduction with an enumeration algorithm admitting a time/success tradeoff, which performs better than the simple distinguishing attack considered in prior analyses; (2) concrete parameters and security estimates for an LWE-based cryptosystem that is more compact and efficient than the well-known schemes from the literature. Our new key sizes are up to 10 times smaller than prior examples, while providing even stronger concrete security levels.
For the entire collection see [Zbl 1206.94004].

MSC:
94A60 Cryptography
Software:
NTRU; NTL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 553–572. Springer, Heidelberg (2010) · Zbl 1227.94022
[2] Ajtai, M.: Generating hard instances of lattice problems. Quaderni di Matematica 13, 1–32 (2004); Preliminary version in STOC 1996
[3] Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: STOC, pp. 284–293 (1997) · Zbl 0962.68055
[4] Ajtai, M., Dwork, C.: The first and fourth public-key cryptosystems with worst-case/average-case equivalence. Electronic Colloquium on Computational Complexity (ECCC) 14(97) (2007)
[5] Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: STOC, pp. 601–610 (2001) · Zbl 1323.68561
[6] Alekhnovich, M.: More on average case vs approximation complexity. In: FOCS, pp. 298–307 (2003)
[7] Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 595–618. Springer, Heidelberg (2009) · Zbl 1252.94044
[8] Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986); Preliminary version in STACS 1985 · Zbl 0593.68030
[9] Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen 296(4), 625–635 (1993) · Zbl 0786.11035
[10] Banaszczyk, W.: Inequalites for convex bodies and polar reciprocal lattices in R n . Discrete & Computational Geometry 13, 217–231 (1995) · Zbl 0824.52011
[11] Bellare, M., Hofheinz, D., Yilek, S.: Possibility and impossibility results for encryption and commitment secure under selective opening. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 1–35. Springer, Heidelberg (2009) · Zbl 1239.94033
[12] Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50(4), 506–519 (2003) · Zbl 1325.68114
[13] Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai trees, or how to delegate a lattice basis. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 523–552. Springer, Heidelberg (2010) · Zbl 1280.94043
[14] Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Heidelberg (2008) · Zbl 1149.94314
[15] Gama, N., Nguyen, P.Q., Regev, O.: Lattice enumeration using extreme pruning. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 257–278. Springer, Heidelberg (2010) · Zbl 1280.94056
[16] Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC, pp. 169–178 (2009) · Zbl 1304.94059
[17] Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197–206 (2008) · Zbl 1231.68124
[18] Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998) · Zbl 1067.94538
[19] Klein, P.N.: Finding the closest lattice vector when it’s unusually close. In: SODA, pp. 937–941 (2000) · Zbl 0953.65043
[20] Lenstra, A.K., Verheul, E.R.: Selecting cryptographic key sizes. J. Cryptology 14(4), 255–293 (2001) · Zbl 1006.94020
[21] Lyubashevsky, V., Palacio, A., Segev, G.: Public-key cryptographic primitives provably as secure as subset sum. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 382–400. Springer, Heidelberg (2010) · Zbl 1274.94096
[22] Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 1–23. Springer, Heidelberg (2010) · Zbl 1279.94099
[23] Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Computational Complexity 16(4), 365–411 (2007); Preliminary version in FOCS 2002 · Zbl 1133.68024
[24] Micciancio, D.: Duality in lattice cryptography. In: Public Key Cryptography (2010) (invited talk)
[25] Micciancio, D., Regev, O.: Lattice-based cryptography. In: Post Quantum Cryptography, pp. 147–191. Springer, Heidelberg (February 2009) · Zbl 1161.81324
[26] Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. In: STOC, pp. 351–358 (2010) · Zbl 1293.68172
[27] Micciancio, D., Voulgaris, P.: Faster exponential time algorithms for the shortest vector problem. In: SODA, pp. 1468–1480 (2010) · Zbl 1288.94076
[28] Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem. In: STOC, pp. 333–342 (2009) · Zbl 1304.94079
[29] Peikert, C.: An efficient and parallel gaussian sampler for lattices. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 80–97. Springer, Heidelberg (2010) · Zbl 1280.94091
[30] Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554–571. Springer, Heidelberg (2008) · Zbl 1183.94046
[31] Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: STOC, pp. 187–196 (2008) · Zbl 1228.94027
[32] Regev, O.: New lattice-based cryptographic constructions. J. ACM 51(6), 899–942 (2004); Preliminary version in STOC 2003 · Zbl 1125.94026
[33] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 1–40 (2009); Preliminary version in STOC 2005 · Zbl 1325.68101
[34] Rückert, M., Schneider, M.: Selecting secure parameters for lattice-based cryptography. Cryptology ePrint Archive, Report 2010/137 (2010), http://eprint.iacr.org/
[35] Schnorr, C.-P.: Lattice reduction by random sampling and birthday methods. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 145–156. Springer, Heidelberg (2003) · Zbl 1035.68113
[36] Schnorr, C.-P., Euchner, M.: Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathmatical Programming 66, 181–199 (1994) · Zbl 0829.90099
[37] Shoup, V.: Number theory library 5.5.2 (NTL) for C++, http://www.shoup.net/ntl/
[38] Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–303. Springer, Heidelberg (2002) · Zbl 1026.94541
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.