nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Learning with Errors and Extrapolated Dihedral Cosets

verfasst von : Zvika Brakerski, Elena Kirshanova, Damien Stehlé, Weiqiang Wen

Erschienen in: Public-Key Cryptography – PKC 2018

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 hardness of the learning with errors (LWE) problem is one of the most fruitful resources of modern cryptography. In particular, it is one of the most prominent candidates for secure post-quantum cryptography. Understanding its quantum complexity is therefore an important goal.

We show that under quantum polynomial time reductions, LWE is equivalent to a relaxed version of the dihedral coset problem (DCP), which we call extrapolated DCP (eDCP). The extent of extrapolation varies with the LWE noise rate. By considering different extents of extrapolation, our result generalizes Regev’s famous proof that if DCP is in BQP (quantum poly-time) then so is LWE (FOCS 02). We also discuss a connection between eDCP and Childs and Van Dam’s algorithm for generalized hidden shift problems (SODA 07).

Our result implies that a BQP solution for LWE might not require the full power of solving DCP, but rather only a solution for its relaxed version, eDCP, which could be easier.

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 Privately Constraining and Programming PRFs, the LWE Way

Nächstes Kapitel Rounded Gaussians

Note that the assumption on f implies, via Markov’s inequality, that one may restrict the sum to a finite index set and obtain a superposition which remains within negligible \(\ell _2\) distance from the countable superposition above.

https://groups.google.com/d/msg/cryptanalytic-algorithms/uhr6gGrVkIk/XxEv4uvEBwAJ.

Here we cut the tail of the Gaussian distribution on the first register. Otherwise, a measurement that follows leads to a state mixed with noisy vectors from different lattice points with large (unbounded) noise. However, it has \(\ell _2\) distance exponentially close to the state we consider in the current algorithm.

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

Bacon, D., Childs, A.M., van Dam, W.: From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups. In: Proceedings of FOCS, pp. 469–478. IEEE Computer Society Press (2005)

Bacon, D., Childs, A.M., van Dam, W.: Optimal measurements for the Dihedral hidden subgroup problem. Chicago J. Theor. Comput. Sci. (2006)

Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296(4), 625–635 (1993)MathSciNetCrossRefMATH

Bernstein, D.J., Buchmann, J., Dahmen, E.: Post Quantum Cryptography, 1st edn. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88702-7

Brakerski, Z., Kirshanova, E., Stehlé, D., Wen, W.: Learning with errors and extrapolated Dihedral cosets. CoRR, abs/1710.08223 (2017)

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

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

Childs, A.M., van Dam, W.: Quantum algorithm for a generalized hidden shift problem. In: Procedings of SODA, pp. 1225–1232. SIAM (2007)

10.

Ettinger, M., Høyer, P.: On quantum algorithms for noncommutative hidden subgroups. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 478–487. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-49116-3_45 CrossRef

11.

Friedl, K., Ivanyos, G., Magniez, F., Santha, M., Sen, P.: Hidden translation and translating coset in quantum computing. SIAM J. Comput. 43(1), 1–24 (2014)MathSciNetCrossRefMATH

12.

Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of STOC, pp. 197–206. ACM (2008). http://eprint.iacr.org/2007/432.pdf

13.

Goldwasser, S., Kalai, Y.T., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: Reusable garbled circuits and succinct functional encryption. In: Proceedings of STOC, pp. 555–564. ACM (2013)

14.

Gorbunov, S., Vaikuntanathan, V., Wee, H.: Attribute-based encryption for circuits. In: Proceedings of STOC, pp. 545–554. ACM (2013)

15.

Grover, L., Rudolph, T.: Creating superpositions that correspond to efficiently integrable probability distributions (2002). Draft https://arxiv.org/pdf/quant-ph/0208112v1

16.

Hausladen, P., Wootters, W.K.: A ‘pretty good’ measurement for distinguishing quantum states. J. Mod. Opt. 41(12), 2385–2390 (1994)MathSciNetCrossRefMATH

17.

Kuperberg, G.: A subexponential-time quantum algorithm for the Dihedral hidden subgroup problem. SIAM J. Comput. 35(1), 170–188 (2005)MathSciNetCrossRefMATH

18.

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

19.

Lenstra Jr., H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538–548 (1983)MathSciNetCrossRefMATH

20.

Lyubashevsky, V., Micciancio, D.: On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In: Proceedings of CRYPTO, pp. 577–594 (2009)

21.

Micciancio, D., Regev, O.: Lattice-based cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 147–191. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-540-88702-7_5 CrossRef

22.

Ozols, M., Roetteler, M., Roland, J.: Quantum rejection sampling. ACM Trans. Comput. Theory 5(3), 11:1–11:33 (2013)MathSciNetCrossRefMATH

23.

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

24.

Peikert, C.: A decade of lattice cryptography. Found. Trends Theor. Comput. Sci. 10(4), 283–424 (2016)MathSciNetCrossRefMATH

25.

Regev, O.: Quantum computation and lattice problems. In: Proceedings of the 43rd Symposium on Foundations of Computer Science, FOCS 2002, pp. 520–529. IEEE Computer Society (2002)

26.

Regev, O.: New lattice-based cryptographic constructions. J. ACM 51(6), 899–942 (2004)MathSciNetCrossRefMATH

27.

Regev, O.: Quantum computation and lattice problems. SIAM J. Comput. 33(3), 738–760 (2004)MathSciNetCrossRefMATH

28.

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

29.

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

30.

Shoup, V.: A Computational Introduction to Number Theory and Algebra. Cambridge University Press, Cambridge (2005)

31.

Stehlé, D., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient public key encryption based on ideal lattices. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 617–635. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_36 CrossRef

Titel: Learning with Errors and Extrapolated Dihedral Cosets
verfasst von: Zvika Brakerski
Elena Kirshanova
Damien Stehlé
Weiqiang Wen
Verlag: Springer International Publishing
Buch: Public-Key Cryptography – PKC 2018
Print ISBN: 978-3-319-76580-8

Electronic ISBN: 978-3-319-76581-5

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-76581-5_24

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