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• 48 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•27 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

Reducing the Number of Qubits in Solving LWE

Barbara Jiabao Benedikt

Lecture notes in computer science•Jan 1, 2025•1 citation
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.