Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Shortest Vector Problems in Ideal Lattices and the Hardness of Ring Learning with Errors

Zen Revista, 10 MFC

Published Jan 4, 2026• 0 citations
Publisher

Abstract

A rigorous derivation of quantum reductions for ideal lattice constraints within the module-theoretic framework of cyclotomic number fields and the asymptotic hardness of algebraic lattice problems.
DOI
10.5281/zenodo.18145971

Related papers

Hardness of the Shortest Vector Problem on Ideal Lattices under Quantum Reductions

Zen Revista, 10 MFC

The security of efficient post-quantum cryptographic primitives, particularly those based on the Ring Learning With Errors (Ring-LWE) problem, relies fundamentally on the presumed intractability of the Shortest Vector Problem (SVP) over ideal lattices. This monograph investigates the hardness of Ideal-SVP in the presence of quantum adversaries. We rigorously analyze the worst-case to average-case reductions that underpin the security of ideal lattice-based schemes, extending classical Gaussian smoothing arguments to the quantum setting. Specifically, we examine the impact of quantum sieving algorithms and the Quantum Fourier Transform (QFT) on the algebraic structure of number fields. While quantum algorithms provide a quadratic speedup for general lattice sieving, we argue that the additional algebraic structure of ideal lattices does not yield a catastrophic collapse in hardness under current quantum reduction models. We present a synthesis of recent results concerning the lower bounds of quantum query complexity for Ideal-SVP, establishing that for cyclotomic fields of degree n, the problem remains hard up to sub-exponential factors, thereby validating the asymptotic security of structured lattice cryptography.

•Feb 4, 2026•0 citations

On Ideal Lattices and Learning with Errors over Rings

Vadim Lyubashevsky, Chris Peikert, Oded Regev

Lecture notes in computer science•Jan 1, 2010•1,909 citations

Hardness of Structured Lattice Problems for Post-Quantum Cryptography

Joël Felderhoff

•Nov 26, 2024•0 citations

Hardness of Lattice Based Cryptography

Thor Tunge

In this thesis we will discuss hard computational problems in lattice theory and relate them to cryptographic constructions. Many of these problems enjoy average-case hardness which makes them attractive for cryptography. In addition, lattice based cryptography is a candidate for post-quantum cryptography, as there is no known quantum algorithm which breaks various hardness theorems.\n\nWe build a foundation in algebraic number theory to have the required background to discuss schemes based on discrete algebraic structures. These structures are free Z-modules which permits unique factorization in prime ideals. We relate this algebraic number theory to lattices in R^n so we can use the theory from algebra to our advantage.\n\nWe then define some standard hard computational lattice problems and show how many of these are related to each other. We prove that these problems are at least as hard as finding the shortest vector of a lattice, which we conjecture is computationally infeasible. We then prove a quantum reduction the learning with errors problem, a problem in machine learning . We also show that there is a similar reduction for a variant of this problem over more general rings.

•Jan 1, 2018•0 citations

The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations

Sanjeev Arora, László Babai, Jacques Stern +1 more

Journal of Computer and System Sciences•Apr 1, 1997•346 citations

Concrete analysis of approximate ideal-SIVP to decision ring-LWE reduction

Neal Koblitz, Subhabrata Samajder, Palash Sarkar +1 more

A seminal 2013 paper by Lyubashevsky, Peikert, and Regev proposed basing post-quantum cryptography on ideal lattices and supported this proposal by giving a polynomial-time security reduction from the approximate Shortest Independent Vectors Problem (SIVP) to the Decision Learning With Errors (DLWE) problem in ideal lattices. We give a concrete analysis of this multi-step reduction. We find that the tightness gap in the reduction is so great as to vitiate any meaningful security guarantee, and we find reasons to doubt the feasibility in the foreseeable future of the quantum part of the reduction. In addition, when we make the reduction concrete it appears that the approximation factor in the SIVP problem is far larger than expected, a circumstance that causes the corresponding approximate-SIVP problem most likely not to be hard for proposed cryptosystem parameters. We also discuss implications for systems such as Kyber and SABER that are based on module-DLWE.

Advances in Mathematics of Communications•Oct 19, 2022•5 citations
The security of efficient post-quantum cryptographic primitives, particularly those based on the Ring Learning With Errors (Ring-LWE) problem, relies fundamentally on the presumed intractability of the Shortest Vector Problem (SVP) over ideal lattices. This monograph investigates the hardness of Ideal-SVP in the presence of quantum adversaries. We rigorously analyze the worst-case to average-case reductions that underpin the security of ideal lattice-based schemes, extending classical Gaussian smoothing arguments to the quantum setting. Specifically, we examine the impact of quantum sieving algorithms and the Quantum Fourier Transform (QFT) on the algebraic structure of number fields. While quantum algorithms provide a quadratic speedup for general lattice sieving, we argue that the additional algebraic structure of ideal lattices does not yield a catastrophic collapse in hardness under current quantum reduction models. We present a synthesis of recent results concerning the lower bounds of quantum query complexity for Ideal-SVP, establishing that for cyclotomic fields of degree n, the problem remains hard up to sub-exponential factors, thereby validating the asymptotic security of structured lattice cryptography.
In this thesis we will discuss hard computational problems in lattice theory and relate them to cryptographic constructions. Many of these problems enjoy average-case hardness which makes them attractive for cryptography. In addition, lattice based cryptography is a candidate for post-quantum cryptography, as there is no known quantum algorithm which breaks various hardness theorems.\n\nWe build a foundation in algebraic number theory to have the required background to discuss schemes based on discrete algebraic structures. These structures are free Z-modules which permits unique factorization in prime ideals. We relate this algebraic number theory to lattices in R^n so we can use the theory from algebra to our advantage.\n\nWe then define some standard hard computational lattice problems and show how many of these are related to each other. We prove that these problems are at least as hard as finding the shortest vector of a lattice, which we conjecture is computationally infeasible. We then prove a quantum reduction the learning with errors problem, a problem in machine learning . We also show that there is a similar reduction for a variant of this problem over more general rings.
A seminal 2013 paper by Lyubashevsky, Peikert, and Regev proposed basing post-quantum cryptography on ideal lattices and supported this proposal by giving a polynomial-time security reduction from the approximate Shortest Independent Vectors Problem (SIVP) to the Decision Learning With Errors (DLWE) problem in ideal lattices. We give a concrete analysis of this multi-step reduction. We find that the tightness gap in the reduction is so great as to vitiate any meaningful security guarantee, and we find reasons to doubt the feasibility in the foreseeable future of the quantum part of the reduction. In addition, when we make the reduction concrete it appears that the approximation factor in the SIVP problem is far larger than expected, a circumstance that causes the corresponding approximate-SIVP problem most likely not to be hard for proposed cryptosystem parameters. We also discuss implications for systems such as Kyber and SABER that are based on module-DLWE.