nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

How (Not) to Instantiate Ring-LWE

verfasst von : Chris Peikert

Erschienen in: Security and Cryptography for Networks

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 learning with errors over rings (Ring-LWE) problem—or more accurately, family of problems—has emerged as a promising foundation for cryptography due to its practical efficiency, conjectured quantum resistance, and provable worst-case hardness: breaking certain instantiations of Ring-LWE is at least as hard as quantumly approximating the Shortest Vector Problem on any ideal lattice in the ring.

Despite this hardness guarantee, several recent works have shown that certain instantiations of Ring-LWE can be broken by relatively simple attacks. While the affected instantiations are not supported by worst-case hardness theorems (and were not ever proposed for cryptographic purposes), this state of affairs raises natural questions about what other instantiations might be vulnerable, and in particular whether certain classes of rings are inherently unsafe for Ring-LWE.

This work comprehensively reviews the known attacks on Ring-LWE and vulnerable instantiations. We give a new, unified exposition which reveals an elementary geometric reason why the attacks work, and provide rigorous analysis to explain certain phenomena that were previously only exhibited by experiments. In all cases, the insecurity of an instantiation is due to the fact that the error distribution is insufficiently “well spread” relative to the ring. In particular, the insecure instantiations use the so-called non-dual form of Ring-LWE, together with spherical error distributions that are much narrower and of a very different shape than the ones supported by hardness proofs.

On the positive side, we show that any Ring-LWE instantiation which satisfies (or only almost satisfies) the hypotheses of the “worst-case hardness of search” theorem is provably immune to broad generalizations of the above-described attacks: the running time divided by advantage is at least exponential in the degree of the ring. This holds for the ring of integers in any number field, so the rings themselves are not the source of insecurity in the vulnerable instantiations. Moreover, the hypotheses of the worst-case hardness theorem are nearly minimal ones which provide these immunity guarantees.

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 Practical Round-Optimal Blind Signatures in the Standard Model from Weaker Assumptions

Nächstes Kapitel Pen and Paper Arguments for SIMON and SIMON-like Designs

Indeed, it is easy to design trivially insecure (Ring-)LWE instantiations for any choice of dimension or ring: just define the error distribution to always output zero. However, the vulnerable instantiations in question do involve some nontrivial error.

Note that have we have \(\varepsilon =2^{-2n}\) instead of \(2^{-n}\) as in [20], but the proof is exactly the same.

The attack easily generalizes to arbitrary ideal divisors \(\mathfrak {q}| qR\) of not-too-large norm; we omit the details, because the present form will be enough for our purposes.

A preliminary version of this work incorrectly concluded that for each instantiation, more than 90 % of the coordinates are errorless; this was due to a misinterpretation of the parameter w from [14, Sect. 9]. We thank an anonymous reviewer for pointing this out.

We remark that the ring dimensions in these instantiations are all at most 144, which is small enough that search is reasonably easy to solve using standard basis-reduction techniques. Here we restrict our attention to the class of attacks from Sect. 3.

More precisely, this argument applies to any discretization \({\lfloor } \cdot {\rceil } :K_{\mathbb {R}} \rightarrow R^{\vee }\) for which \({\lfloor } z + e {\rceil } = z + {\lfloor } e {\rceil }\) for any \(z \in R^{\vee }\) and \(e \in K_{\mathbb {R}}\), which is the case for any standard method. See [17, Sect. 2.6] for further details.

Aggarwal, D., Dadush, D., Regev, O., Stephens-Davidowitz, N.: Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling. In: STOC, pp. 733–742 (2015)

Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: STOC, pp. 601–610 (2001)

Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. In: USENIX Security Symposium (2016, to appear)

Alperin-Sheriff, J., Peikert, C.: Practical bootstrapping in quasilinear time. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 1–20. Springer, Heidelberg (2013)CrossRef

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

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

Bos, J.W., Costello, C., Naehrig, M., Stebila, D.: Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. In: IEEE Symposium on Security and Privacy, pp. 553–570 (2015)

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

Castryck, W., Iliashenko, I., Vercauteren, F.: Provably weak instances of Ring-LWE revisited. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 147–167. Springer, Heidelberg (2016). doi:10.1007/978-3-662-49890-3_6 CrossRef

10.

Chen, H., Lauter, K., Stange, K.E.: Attacks on search RLWE. Cryptology ePrint Archive, Report 2015/971 (2015). http://eprint.iacr.org/

11.

Chen, H., Lauter, K., Stange, K.E.: Vulnerable galois RLWE families and improved attacks. Cryptology ePrint Archive, Report 2016/193 (2016). http://eprint.iacr.org/

12.

Crockett, E., Peikert, C.: \(\Lambda \circ \lambda \): a functional library for lattice cryptography. Cryptology ePrint Archive, Report 2015/1134 (2015). http://eprint.iacr.org/

13.

Eisenträger, K., Hallgren, S., Lauter, K.: Weak instances of PLWE. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 183–194. Springer, Heidelberg (2014)CrossRef

14.

Elias, Y., Lauter, K.E., Ozman, E., Stange, K.E.: Provably weak instances of Ring-LWE. In: Gennaro, R., Robshaw, M. (eds.) Advances in Cryptology – CRYPTO 2015. LNCS, vol. 9215, pp. 63–92. Springer, Heidelberg (2015)CrossRef

15.

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

16.

Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. J. ACM 60(6), 43:1–43:35 (2013). Preliminary version in Eurocrypt 2010MathSciNetCrossRefMATH

17.

Lyubashevsky, V., Peikert, C., Regev, O.: A toolkit for Ring-LWE cryptography. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 35–54. Springer, Heidelberg (2013)CrossRef

18.

Micciancio, D., Mol, P.: Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 465–484. Springer, Heidelberg (2011)CrossRef

19.

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

20.

Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007). Preliminary version in FOCS 2004MathSciNetCrossRefMATH

21.

Micciancio, D., Regev, O.: Lattice-based cryptography. Post Quantum Cryptography, pp. 147–191. Springer, Heidelberg (2009)CrossRef

22.

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)

23.

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

24.

Peikert, C.: Lattice cryptography for the internet. In: Mosca, M. (ed.) PQCrypto 2014. LNCS, vol. 8772, pp. 197–219. Springer, Heidelberg (2014)

25.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 1–40 (2009). Preliminary version in STOC 2005MathSciNetCrossRefMATH

Titel: How (Not) to Instantiate Ring-LWE
verfasst von: Chris Peikert
Verlag: Springer International Publishing
Buch: Security and Cryptography for Networks
Print ISBN: 978-3-319-44617-2

Electronic ISBN: 978-3-319-44618-9

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-44618-9_22

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