nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Practical Analysis of Key Recovery Attack Against Search-LWE Problem

verfasst von : Momonari Kudo, Junpei Yamaguchi, Yang Guo, Masaya Yasuda

Erschienen in: Advances in Information and Computer Security

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The security of a number of modern cryptographic schemes relies on the computational hardness of the learning with errors (LWE) problem. In 2015, Laine and Lauter analyzed a key recovery (or decoding) attack against the search variant of LWE. Their analysis is based on a generalization of the Boneh-Venkatesan method for the hidden number problem to LWE. They adopted the LLL algorithm and Babai’s nearest plane method in the attack against LWE, and they also demonstrated a successful range of the attack by experiments for hundreds of LWE instances. In this paper, we give an alternative analysis of the key recovery attack. While Laine and Lauter’s analysis gives explicit information about the effective approximation factor in the LLL algorithm and Babai’s nearest plane method, our analysis is useful to estimate which LWE instances can be solved by the key recovery attack. Furthermore, our analysis enables one to determine a successful range of the attack with practical lattice reduction such as the BKZ algorithm.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel On the Division Property of Simon48 and Simon64

Nächstes Kapitel A Note on Fault Attacks Against Deterministic Signature Schemes (Short Paper)

Albrecht, M.A., Cid, C., Faugère, J.-C., Fitzpartrick, R., Perret, L.: On the complexity of the BKW algorithm on LWE. Des. Codes Crypt. 74, 325–354 (2015)MathSciNetCrossRefMATH

Albrecht, M.A., Cid, C., Faugère, J.-C., Perret, L.: Algebraic algorithms for LWE. IACR ePrint 2014/1018

Arora, S., Ge, R.: New algorithms for learning in presence of errors. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 403–415. Springer, Heidelberg (2011)CrossRef

Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptology 9(3), 169–203 (2015)MathSciNetCrossRefMATH

Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986)MathSciNetCrossRefMATH

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

Boneh, D., Venkatesan, R.: Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 129–142. Springer, Heidelberg (1996)

Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Innovations in Theoretical Computer Science-ITCS 2012, pp. 309–325, ACM (2012)

Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Theory of Computing-STOC 2013, pp. 575–584, ACM (2013)

10.

Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from ring-LWE and security for key dependent messages. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 505–524. Springer, Heidelberg (2011)CrossRef

11.

Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Foundations of Computer Science-FOCS 2011, pp. 97–106, IEEE (2011)

12.

Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1–20. Springer, Heidelberg (2011)CrossRef

13.

Galbraith, S.D.: Mathematics of Public Key Cryptography. Cambridge University Press, Cambridge (2012)CrossRefMATH

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)CrossRef

15.

Gentry, C., Gorbunov, S., Halevi, S.: Graph-induced multilinear maps from lattices. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 498–527. Springer, Heidelberg (2015)CrossRef

16.

Kearns, M.J., Mansour, Y., Ron, D., Rubinfeld, R., Schapire, R.E., Sellie, L.: On the learnability of discrete distributions. In: Theory of Computing-STOC 1994, pp. 273–282, ACM (1994)

17.

Laine, K., Lauter, K.: Key recovery for LWE in polynomial time. IACR ePrint 2015/176 (2015)

18.

Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982)MathSciNetCrossRefMATH

19.

Liu, M., Nguyen, P.Q.: Solving BDD by enumeration: an update. In: Dawson, E. (ed.) CT-RSA 2013. LNCS, vol. 7779, pp. 293–309. Springer, Heidelberg (2013)CrossRef

20.

Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 319–339. Springer, Heidelberg (2011)CrossRef

21.

Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 700–718. Springer, Heidelberg (2012)CrossRef

22.

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

23.

National Institute of Standards and Technology (NIST), Report on post-quantum cryptography. http://csrc.nist.gov/publications/drafts/nistir-8105/nistir_8105_draft.pdf

24.

The PARI Group, PARI/GP. http://pari.math.u-bordeaux.fr/

25.

Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Theory of Computing–STOC 2009, pp. 333–342, ACM (2009)

26.

Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. SIAM J. Comput. 40(6), 1803–1844 (2011)MathSciNetCrossRefMATH

27.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Theory of Computing–STOC 2005, pp. 84–93, ACM Press (2005)

28.

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

29.

The Sage Group, SageMath: Open-Source Mathematical SoftwareSystem. http://www.sagemath.org/

30.

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)CrossRef

31.

Schnorr, C.P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181–199 (1994)MathSciNetCrossRefMATH

Titel: Practical Analysis of Key Recovery Attack Against Search-LWE Problem
verfasst von: Momonari Kudo
Junpei Yamaguchi
Yang Guo
Masaya Yasuda
Verlag: Springer International Publishing
Buch: Advances in Information and Computer Security
Print ISBN: 978-3-319-44523-6

Electronic ISBN: 978-3-319-44524-3

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-44524-3_10

Springer Professional

Abstract

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

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner