Top

Published in:

2025 | OriginalPaper | Chapter

Worst-Case to Average-Case Hardness of LWE: An Alternative Perspective

Authors : Aggarwal Divesh, Jin Ming Leong, Veliche Alexandra

Published in: Theory of Cryptography

Publisher: Springer Nature Switzerland

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this work, we study the worst-case to average-case hardness of the Learning with Errors problem (LWE) under an alternative measure of hardness − the maximum success probability achievable by a probabilistic polynomial-time (PPT) algorithm. Previous works by Regev (STOC 2005), Peikert (STOC 2009), and Brakerski, Peikert, Langlois, Regev, Stehle (STOC 2013) give worst-case to average-case reductions from lattice problems to LWE, specifically from the approximate decision variant of the Shortest Vector Problem (GapSVP) and the Bounded Distance Decoding (BDD) problem. These reductions, however, are lossy in the sense that even the strongest assumption on the worst-case hardness of GapSVP or BDD implies only mild hardness of LWE. Our alternative perspective gives a much tighter reduction and strongly relates the hardness of LWE to that of BDD. In particular, we show that under a reasonable assumption about the success probability of solving BDD via a PPT algorithm, we obtain a nearly tight lower bound on the highest possible success probability for solving LWE via a PPT algorithm. Furthermore, we show a tight relationship between the best achievable success probability by any PPT algorithm for decision-LWE to that of search-LWE. Our results not only refine our understanding of the computational complexity of LWE, but also provide a useful framework for analyzing the practical security implications.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Sparse Linear Regression and Lattice Problems

next chapter Batching Adaptively-Sound SNARGs for NP

[ABGSD21]

Aggarwal, D., Bennett, H., Golovnev, A., Stephens-Davidowitz, N.: Fine-grained hardness of CVP(P) – Everything that we can prove (and nothing else) (2021)

[ADRS14]

Aggarwal, D., Dadush, D., Regev, O., Stephens-Davidowitz, N.: Solving the shortest vector problem in \(2^n\) time via discrete gaussian sampling. CoRR, abs/1412.7994 (2014)

[ADRS15]

Aggarwal, D., Dadush, D., Regev, O., Stephens-Davidowitz, N.: Solving the shortest vector problem in \(2^n\) time via discrete gaussian sampling (2015)

[Ajt96]

Ajtai, M.: Generating hard instances of lattice problems. Electron. Colloquium Comput. Complex. TR96 (1996)

[ALNSD20]

Aggarwal, D., Li, J., Nguyen, P.Q., Stephens-Davidowitz, N.: Slide reduction, revisited—filling the gaps in SVP approximation. In: Annual International Cryptology Conference, pp. 274–295. Springer (2020)

[ALS20]

Aggarwal, D., Li, Z., Stephens-Davidowitz, N.: A \(2^{n/2}\)-Time Algorithm for \(\sqrt{n}\)-SVP and \(\sqrt{n}\)-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP. arXiv e-prints (2020)

[AM11]

Aggarwal, D., Maurer, U.: The leakage-resilience limit of a computational problem is equal to its unpredictability entropy. In: Advances in Cryptology–ASIACRYPT 2011: 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, 4-8 December 2011. Proceedings 17, pp. 686–701. Springer (2011)

[ASD18]

Aggarwal, D., Stephens-Davidowitz, N.: (Gap/S)ETH Hardness of SVP. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp. 228–238, New York, NY, USA (2018). Association for Computing Machinery

[Bab86]

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

[BGS17]

Bennett, H., Golovnev, A., Stephens-Davidowitz, N.: On the Quantitative Hardness of CVP. CoRR, abs/1704.03928 (2017)

[BKW00]

Blum, A., Kalai, A., Wasserman, H.; Noise-tolerant learning, the parity problem, and the statistical query model. CoRR, cs.LG/0010022 (2000)

[BLP+13]

Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC 2013, pp. 575–584, New York, NY, USA (2013). Association for Computing Machinery

[Bri83]

Brickell, E.F.: Solving low density knapsacks. In: Advances in Cryptology: Proceedings of CRYPTO 1983, pp. 25–37. Plenum (1983)

[BV14]

Brakerski, Z., Vaikuntanathan, V.: Lattice-based FHE as secure as PKE. In: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014, pp. 1–12, New York, NY, USA (2014). Association for Computing Machinery

[Cai98]

Cai, J.-Y.: A relation of primal-dual lattices and the complexity of shortest lattice vector problem. Theoret. Comput. Sci. 207(1), 105–116 (1998)MathSciNetCrossRef

[Din02]

Dinur, I.: Approximating SVP\( _{\text{ infinity }}\) to within almost-polynomial factors is NP-hard. Theor. Comput. Sci. 285(1), 55–71 (2002)CrossRef

[DKRS03]

Dinur, I., Kindler, G., Raz, R., Safra, S.: Approximating CVP to within almost-polynomial factors is NP-Hard. Combinatorica 23(2), 205–243 (2003)MathSciNetCrossRef

[FT87]

Frank, A., Tardos,É.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1), 49–65 (1987)

[Gen09]

Gentry, C.: Fully Homomorphic Encryption Using Ideal Lattices. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 169–178, New York, NY, USA (2009). Association for Computing Machinery

[GL89]

Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC 1989, pp. 25–32, New York, NY, USA (1989). Association for Computing Machinery

[GMSS99]

Goldreich, O., Micciancio, D., Safra, S., Seifert, J.-P.: Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Inf. Process. Lett. 71(2), 55–61 (1999)MathSciNetCrossRef

[GN08]

Gama, N., Nguyen, P.Q.: Finding short lattice vectors within Mordell’s inequality. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 207–216 (2008)

[GPV08]

Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 197–206, New York, NY, USA (2008). Association for Computing Machinery

[HR18]

Haviv, I., Regev, O.: Tensor-based hardness of the shortest vector problem to within almost polynomial factors. CoRR, abs/1806.04087 (2018)

[Kan87]

Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415–440 (1987)MathSciNetCrossRef

[Kho05]

Khot, S.: Hardness of approximating the shortest vector problem in lattices. J. ACM 52(5), 789–808 (2005)MathSciNetCrossRef

[Lev12]

Levin, L.A.: Randomness and non-determinism. CoRR, abs/1211.0071 (2012)

[LLL82]

Lenstra, A., Lenstra, H., László, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 12 (1982)MathSciNetCrossRef

[LM09]

Lyubashevsky, V., Micciancio, D.: On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In: Shai Halevi, (ed.) Advances in Cryptology - CRYPTO 2009, pp. 577–594. Springer, Heidelberg (2009)

[LO85]

Lagarias, J., Odlyzko, A.: Solving low-density subset sum problems. J. ACM 32, 229–246 (1985)MathSciNetCrossRef

[Mic12]

Micciancio, D.: Inapproximability of the shortest vector problem: toward a deterministic reduction. Theory Comput. 8(1), 487–512 (2012)MathSciNetCrossRef

[MM11]

Micciancio, D., Mol, P.: Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions. Cryptology ePrint Archive, Paper 2011/521 (2011)

[MR04]

Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. In: 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 372–381 (2004)

[MR09]

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

[MV13]

Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. SIAM J. Comput. 42(3), 1364–1391 (2013)MathSciNetCrossRef

[MW18]

Micciancio, D., Walter, M.: On the bit security of cryptographic primitives. In Jesper Buus Nielsen and Vincent Rijmen, (eds.) Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part I, vol. 10820 LNCS, pp. 3–28. Springer (2018)

[Pei09]

Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 333–342 (2009)

[PP10]

Paturi, R., Pudlák, P.: On the Complexity of Circuit Satisfiability. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC 2010, pp. 241–250, New York, NY, USA (2010). Association for Computing Machinery

[Reg06]

Regev, O.: Lattice-based cryptography. In Cynthia Dwork, (ed.) Advances in Cryptology - CRYPTO 2006, pp. 131–141. Springer, Heidelberg (2006)

[Reg09]

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

[Sha85]

Shamir, A.: Identity-based cryptosystems and signature schemes. In: George Robert Blakley and David Chaum, (eds.) Advances in Cryptology, pp. 47–53. Springer, Heidelberg, (1985)

[Vad12]

Vadhan, S.P.: Pseudorandomness. Found. Trends Theor. Comput. Sci. 7(1–3), 1–336 (2012)MathSciNetCrossRef

[vEB81]

van Emde Boas, P.: Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report, Department of Mathmatics, University of Amsterdam (1981)

Title: Worst-Case to Average-Case Hardness of LWE: An Alternative Perspective
Authors: Aggarwal Divesh
Jin Ming Leong
Veliche Alexandra
Publisher: Springer Nature Switzerland
Book: Theory of Cryptography
Print ISBN: 978-3-031-78016-5

Electronic ISBN: 978-3-031-78017-2

Copyright Year: 2025
DOI: https://doi.org/10.1007/978-3-031-78017-2_11

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"