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

Lecture notes in computer science

A Hybrid Lattice Basis Reduction and Quantum Search Attack on LWE

Florian Göpfert, Christine van Vredendaal, Thomas Wunderer

Published Jan 1, 2017• 47 citations
Publisher
DOI
10.1007/978-3-319-59879-6_11

Related papers

Quantum Search-to-Decision Reduction for the LWE Problem

Kyohei Sudo, Masayuki Tezuka, Keisuke Hara +1 more

Lecture notes in computer science•Jan 1, 2023•3 citations

Tight Lattice-Based Signatures Without Trapdoors from Search LWE

Rutchathon Chairattana-Apirom, Nico Döttling, Julian Loss +2 more

Lecture notes in computer science•Jan 1, 2026•0 citations

Learning with Correlated Errors: A New Lattice Hard Problem with Worst-Case Reductions and Public-Key Encryption

Kishore K

We introduce Learning with Correlated Errors (LCE), a new lattice-based computationalhardness assumption in which observed samples carry noise generated by a low-rank linearcorrelation structure. Formally, given samples (A, b = As + Ce0 + e1 mod q), whereC ∈ Zm×rq is a publicly known correlation matrix and e0, e1 are short Gaussian vectors, thetask is to recover the secret s.Unlike LWE, the noise in LCE is globally correlated: up to r independent root noise sourcesdrive m observations simultaneously. Unlike the recent hybrid sparse-small assumptions ofGhosal et al. [GJL+25], LCE preserves a lattice structure that enables a reduction from theLearning with Errors (LWE) problem, thereby inheriting its worst-case hardness guarantees.We prove: (1) Worst-case hardness via reduction: We give a polynomial-timereduction from Decision-LWE to Decision-LCE, establishing that LCE is at least as hardas LWE and thereby inheriting its worst-case lattice hardness guarantees. (2) Search-to-Decision reduction: Search-LCE and Decision-LCE are polynomial-time equivalent (viaan explicit n-hybrid argument). (3) Cryptographic construction: an IND-CPA-securepublic-key encryption scheme from Decision-LCE. (4) Quantum resistance: by composingour reduction with Regev’s quantum reduction, we show that LCE resists known quantumattacks, with quantum lattice sieving requiring an estimated 20.265n quantum gates (matchingthe estimated cost for standard LWE).LCE provides a new, independently motivated hardness foundation for post-quantumcryptography and adds meaningful assumption diversity beyond LWE and LPN.

•Mar 11, 2026•0 citations

A Faster Lattice Reduction Method Using Quantum Search

Christoph Ludwig

Lecture notes in computer science•Jan 1, 2003•28 citations

Lattice-Based Cryptography: A Comprehensive Analysis Of Post-Quantum Security Margins Against Hybrid Attack Vectors

Assistant Professor Dr. S. Sreelatha, Assistant Professor Dr. P. Pushpa

The imminent arrival of large-scale quantum computers necessitates a transition from classical number-theoretic cryptography to post-quantum alternatives. Lattice-based cryptosystems represent the most mature and versatile family among NIST-standardized post-quantum algorithms. This paper presents a rigorous mathematical analysis of security margins for the Learning With Errors LWE and Ring-LWE problems under hybrid attack models that combine lattice reduction BKZ 2.0 with meet-in-the-middle techniques. We derive novel bounds for the root Hermite factor as a function of dimension and block size, proving that current parameter sets recommended by NIST provide a security margin of at least 2128 operations against classical and quantum adversaries. Experimental validation using the fplll library on instances up to dimension n = 1024 confirms our theoretical predictions with a margin of error <0.3%. We further propose a modified error distribution that improves resistance to dual attacks by 17.4% without significant performance degradation.

International Journal of Science Engineering and Technology•Jun 7, 2026•0 citations

Ternary LWE Key Search: A New Frontier for Quantum Combinatorial Attacks

Yang Li

The Learning with Errors (LWE) problem, particularly its efficient ternary variant where secrets and errors are small, is a fundamental building block for numerous post-quantum cryptographic schemes. Combinatorial attacks provide a potent approach to cryptanalyzing ternary LWE. While classical attacks have achieved complexities close to their asymptotic S0.25 bound for a search space of size S, their quantum counterparts have faced a significant gap: the attack by van Hoof et al. (vHKM) only reached a concrete complexity of S0.251, far from its asymptotic promise of S0.193. This work introduces an efficient quantum combinatorial attack that substantially narrows this gap. We present a quantum walk adaptation of the locality-sensitive hashing algorithm by Kirshanova and May, which fundamentally removes the need for guessing error coordinates—the primary source of inefficiency in the vHKM approach. This crucial improvement allows our attack to achieve a concrete complexity of approximately S0.225, markedly improving over prior quantum combinatorial methods. For concrete parameters of major schemes including NTRU, BLISS, and GLP, our method demonstrates substantial runtime improvements over the vHKM attack, achieving speedup factors ranging from 216 to 260 across different parameter sets and establishing the new state-of-the-art for quantum combinatorial attacks. As a second contribution, we address the challenge of polynomial quantum memory constraints. We develop a hybrid approach combining the Kirshanova–May framework with a quantum claw-finding technique, requiring only O(n) qubits while utilizing exponential classical memory. This work provides the first comprehensive concrete security analysis of real-world LWE-based schemes under such practical quantum resource constraints, offering crucial insights for post-quantum security assessments. Our results reveal a nuanced landscape where our combinatorial attacks are superior for small-weight parameters, while lattice-based attacks maintain an advantage for others.

Information•Dec 7, 2025•0 citations
We introduce Learning with Correlated Errors (LCE), a new lattice-based computationalhardness assumption in which observed samples carry noise generated by a low-rank linearcorrelation structure. Formally, given samples (A, b = As + Ce0 + e1 mod q), whereC ∈ Zm×rq is a publicly known correlation matrix and e0, e1 are short Gaussian vectors, thetask is to recover the secret s.Unlike LWE, the noise in LCE is globally correlated: up to r independent root noise sourcesdrive m observations simultaneously. Unlike the recent hybrid sparse-small assumptions ofGhosal et al. [GJL+25], LCE preserves a lattice structure that enables a reduction from theLearning with Errors (LWE) problem, thereby inheriting its worst-case hardness guarantees.We prove: (1) Worst-case hardness via reduction: We give a polynomial-timereduction from Decision-LWE to Decision-LCE, establishing that LCE is at least as hardas LWE and thereby inheriting its worst-case lattice hardness guarantees. (2) Search-to-Decision reduction: Search-LCE and Decision-LCE are polynomial-time equivalent (viaan explicit n-hybrid argument). (3) Cryptographic construction: an IND-CPA-securepublic-key encryption scheme from Decision-LCE. (4) Quantum resistance: by composingour reduction with Regev’s quantum reduction, we show that LCE resists known quantumattacks, with quantum lattice sieving requiring an estimated 20.265n quantum gates (matchingthe estimated cost for standard LWE).LCE provides a new, independently motivated hardness foundation for post-quantumcryptography and adds meaningful assumption diversity beyond LWE and LPN.
The imminent arrival of large-scale quantum computers necessitates a transition from classical number-theoretic cryptography to post-quantum alternatives. Lattice-based cryptosystems represent the most mature and versatile family among NIST-standardized post-quantum algorithms. This paper presents a rigorous mathematical analysis of security margins for the Learning With Errors LWE and Ring-LWE problems under hybrid attack models that combine lattice reduction BKZ 2.0 with meet-in-the-middle techniques. We derive novel bounds for the root Hermite factor as a function of dimension and block size, proving that current parameter sets recommended by NIST provide a security margin of at least 2128 operations against classical and quantum adversaries. Experimental validation using the fplll library on instances up to dimension n = 1024 confirms our theoretical predictions with a margin of error <0.3%. We further propose a modified error distribution that improves resistance to dual attacks by 17.4% without significant performance degradation.
The Learning with Errors (LWE) problem, particularly its efficient ternary variant where secrets and errors are small, is a fundamental building block for numerous post-quantum cryptographic schemes. Combinatorial attacks provide a potent approach to cryptanalyzing ternary LWE. While classical attacks have achieved complexities close to their asymptotic S0.25 bound for a search space of size S, their quantum counterparts have faced a significant gap: the attack by van Hoof et al. (vHKM) only reached a concrete complexity of S0.251, far from its asymptotic promise of S0.193. This work introduces an efficient quantum combinatorial attack that substantially narrows this gap. We present a quantum walk adaptation of the locality-sensitive hashing algorithm by Kirshanova and May, which fundamentally removes the need for guessing error coordinates—the primary source of inefficiency in the vHKM approach. This crucial improvement allows our attack to achieve a concrete complexity of approximately S0.225, markedly improving over prior quantum combinatorial methods. For concrete parameters of major schemes including NTRU, BLISS, and GLP, our method demonstrates substantial runtime improvements over the vHKM attack, achieving speedup factors ranging from 216 to 260 across different parameter sets and establishing the new state-of-the-art for quantum combinatorial attacks. As a second contribution, we address the challenge of polynomial quantum memory constraints. We develop a hybrid approach combining the Kirshanova–May framework with a quantum claw-finding technique, requiring only O(n) qubits while utilizing exponential classical memory. This work provides the first comprehensive concrete security analysis of real-world LWE-based schemes under such practical quantum resource constraints, offering crucial insights for post-quantum security assessments. Our results reveal a nuanced landscape where our combinatorial attacks are superior for small-weight parameters, while lattice-based attacks maintain an advantage for others.