nach oben

Designs, Codes and Cryptography

Erschienen in:

01.02.2015

On the complexity of the BKW algorithm on LWE

verfasst von: Martin R. Albrecht, Carlos Cid, Jean-Charles Faugère, Robert Fitzpatrick, Ludovic Perret

Erschienen in: Designs, Codes and Cryptography | Ausgabe 2/2015

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This work presents a study of the complexity of the Blum–Kalai–Wasserman (BKW) algorithm when applied to the Learning with Errors (LWE) problem, by providing refined estimates for the data and computational effort requirements for solving concrete instances of the LWE problem. We apply this refined analysis to suggested parameters for various LWE-based cryptographic schemes from the literature and compare with alternative approaches based on lattice reduction. As a result, we provide new upper bounds for the concrete hardness of these LWE-based schemes. Rather surprisingly, it appears that BKW algorithm outperforms known estimates for lattice reduction algorithms starting in dimension \(n \approx 250\) when LWE is reduced to SIS. However, this assumes access to an unbounded number of LWE samples.

Vorheriger Artikel Semi-cyclic holey group divisible designs with block size three

Nächster Artikel On self-dual constacyclic codes over finite fields

It is common in the literature on LWE to parameterise discrete Gaussian distributions by \(s = \sigma \sqrt{2\pi }\) instead of \(\sigma \). Since we are mainly interested in the “size” of the noise, we deviate from this standard in this work.

However, a detailed study of the algorithm to the LPN case was provided [14], which in fact heavily inspired this work. The authors of [14] conducted a detailed analysis of the BKW algorithm as applied to LPN, while also giving revised security estimates for some HB-type authentication protocols relying on the hardness of LPN.

Agrawal S., Gentry C., Halevi S., Sahai A.: Discrete Gaussian Leftover Hash Lemma over infinite domains. Cryptology ePrint Archive, Report 2012/714, http://eprint.iacr.org/ (2012). Accessed 27 Dec 2012.

Ajtai M., Kumar R., Sivakumar, D.: Sampling short lattice vectors and the closest lattice vector problem. In: IEEE Conference on Computational Complexity, pp. 53–57 (2002).

Albrecht M.R.: https://bitbucket.org/malb/research-snippets/ (2012). Accessed 30 June 2013.

Albrecht M.R., Farshim P., Faugère J-.C., Perret L.: Polly Cracker, revisited. In: Advances in Cryptology—ASIACRYPT 2011. Lecture Notes in Computer Science, vol. 7073, pp. 179–196. Springer, Berlin. Cryptology ePrint Archive, Report 2011/289, http://eprint.iacr.org/ (2011). Accessed 19 Nov 2012.

Albrecht M., Cid C., Faugère J-.C., Fitzpatrick R., Perret L.: On the complexity of the Arora–Ge algorithm against LWE. In: Faugère J-.C., Gomez D., Gutierrez J., Perret L. (eds.) SCC ’12: Proceedings of the 3nd International Conference on Symbolic Computation and Cryptography, pp. 93–99. Castro-Urdiales, July (2012).

Albrecht M.R., Fitzpatrick R., Cabracas D., Göpfert F., Schneider M.: A generator for LWE and Ring-LWE instances. http://www.iacr.org/news/files/2013-04-29lwe-generator.pdf (2013). Accessed 29 Apr 2013.

Arora S.. Ge R.: New algorithms for learning in presence of errors. In: Aceto L., Henzinger M., Sgall J. (eds.) ICALP. Lecture Notes in Computer Science, vol. 6755, pp. 403–415. Springer, Berlin (2011).

Baigneres T., Junod P., Vaudenay S.: How far can we go beyond linear cryptanalysis? In: Lee P.J. (ed.) Advances in Cryptology—ASIACRYPT 2004. Lecture Notes in Computer Science, vol. 3329, pp. 432–450, Springer, Berlin (2004).

Blum A., Kalai A., Wasserman H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM. 50(4), 506–519 (2003).

10.

Brakerski Z., Vaikuntanathan V.: Efficient fully homomorphic encryption from (standard) LWE. In: Ostrovsky R. (ed.) IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 97–106. IEEE (2011).

11.

Brakerski Z., Langlois A., Peikert C., Regev O., Stehlé D.: Classical hardness of learning with errors. STOC. (2013) (to appear).

12.

Chen Y., Nguyen P.Q.: BKZ 2.0: better lattice security estimates. In: Lee D.H., Wang X. (eds.) Advances in Cryptology—ASIACRYPT 2011. Lecture Notes in Computer Science, vol. 7073, pp. 1–20, Springer, Berlin (2011).

13.

Duembgen L.: Bounding standard gaussian tail probabilities. arXiv:1012.2063 (2010).

14.

Fouque P-.A., Levieil É.: An improved LPN algorithm. In: De Prisco R., Yung M. (eds.) Security and Cryptography for Networks, 5th International Conference, SCN 2006. Lecture Notes in Computer Science, vol. 4116, pp. 348–359. Springer, Berlin (2006).

15.

Gama N., Nguyen P.Q., Regev O.: Lattice enumeration using extreme pruning. In: Gilbert H. (ed.) Advances in Cryptology—EUROCRYPT 2010. Lecture Notes in Computer Science, vol. 6110, pp. 257–278. Springer, Berlin (2010).

16.

Gentry C.: A fully homomorphic encryption scheme. Ph.D. thesis, Stanford University. http://crypto.stanford.edu/craig (2009).

17.

Gentry C., Peikert C., Vaikuntanathan V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC 08: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 197–206. ACM (2008).

18.

Hanrot G., Pujol X., Stehlé, D.: Algorithms for the shortest and closest lattice vector problems. In: Chee Y.M., Guo Z., Ling S., Shao F., Tang Y., Wang H., Xing C. (eds.) IWCC. Lecture Notes in Computer Science, vol. 6639, pp. 159–190. Springer, Berlin (2011).

19.

Hanrot G., Pujol X., Stehlé D.: Analyzing blockwise lattice algorithms using dynamical systems. In: Rogaway P. (ed.) Advances in Cryptology—CRYPTO 2011. Lecture Notes in Computer Science, vol. 6841, pp. 447–464. Springer, Berlin (2011).

20.

Johansson F. et al.: mpmath: a Python library for arbitrary-precision floating-point arithmetic (version 0.17), February 2011. http://code.google.com/p/mpmath/. Accessed 30 June 2013.

21.

Lindner R., Peikert C.: Better key sizes (and attacks) for LWE-based encryption. In: Topics in Cryptology—CT-RSA 2011. Lecture Notes in Computer Science, vol. 6558, pp. 319–339, Springer, Berlin (2011).

22.

Liu M., Nguyen P.Q.: Solving BDD by enumeration: An update. In: Dawson E. (ed.) CT-RSA. Lecture Notes in Computer Science, vol. 7779, pp. 293–309. Springer, Berlin (2013).

23.

Lyubashevsky V., Micciancio D., Peikert C., Rosen A.: SWIFFT: A modest proposal for FFT hashing. In: Nyberg K. (ed.) Fast Software Encryption. Lecture Notes in Computer Science, vol. 5086, pp. 54–72. Springer, Berlin (2008).

24.

Micciancio D., Regev O.: Lattice-based cryptography. In: Bernstein D.J., Buchmann J., Dahmen E. (eds.) Post-Quantum Cryptography, pp. 147–191. Springer, Berlin (2009).

25.

Morel I., Stehlé D., Villard G.: H-LLL: using householder inside LLL. In: Johnson J.R., Park H., Kaltofen E. (eds) Symbolic and Algebraic Computation, International Symposium, ISSAC, 2009 pp. 271–278. ACM (2009).

26.

Nguyen P.Q.: Lattice reduction algorithms: theory and practice. In: Paterson K.G. (eds.) Advances in Cryptology—EUROCRYPT 2011. Lecture Notes in Computer Science, vol. 6632, pp. 2–6. Springer, Berlin (2011).

27.

Nguyen P.Q., Stehlé D.: Low-dimensional lattice basis reduction revisited. ACM Trans. Algorithms 5(4) (2009).

28.

Pujol X., Stehlé D.: Solving the shortest lattice vector problem in time \(2^{2.465n}\). IACR Cryptology ePrint Archive 2009:605 (2009).

29.

Regev O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM. 56(6), 84–93 (2009).

30.

Regev O.: The learning with errors problem (invited survey). In: IEEE Conference on Computational Complexity, pp. 191–204. IEEE Computer Society (2010).

31.

Rückert M., Schneider M.: Estimating the security of lattice-based cryptosystems. IACR Cryptology ePrint Archive 2010, 137 (2010).

32.

Stein W.A. et al.: Sage Mathematics Software (Version 5.2). The Sage Development Team, http://www.sagemath.org (2012). Accessed 30 June 2013.

Titel: On the complexity of the BKW algorithm on LWE
verfasst von: Martin R. Albrecht
Carlos Cid
Jean-Charles Faugère
Robert Fitzpatrick
Ludovic Perret
Publikationsdatum: 01.02.2015
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 2/2015
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-013-9864-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 2/2015

On embeddings of minimum dimension of

A class of minimal cyclic codes over finite fields

Extending Brickell–Davenport theorem to non-perfect secret sharing schemes

Compression of periodic complementary sequences and applications

Constructing self-dual codes over

Optimum commutative group codes