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

Designs Codes and Cryptography

Worst-case to average-case reductions for module lattices

Adeline Roux-Langlois, Damien Stehlé

Published Feb 25, 2014• 718 citations
Publisher
DOI
10.1007/s10623-014-9938-4

Related papers

Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems

Nicolas Gama, Malika Izabachène, Phong Q. Nguyễn +1 more

Lecture notes in computer science•Jan 1, 2016•59 citations

Module Lattice Security (Part I): Unconditional Verification of Weber's Conjecture for $k \le 12$

Ming-Xing Luo

Weber's conjecture (1886) governs three aspects of lattice-based cryptography: the solvability of the Principal Ideal Problem, the freeness of modules over rings of integers, and the tightness of worst-case-to-average-case reductions in Ring-LWE (R-LWE) and Module-LWE (MLWE). Existing verifications for $k \ge 9$ rely on Generalized Riemann Hypothesis (GRH). In this paper, we present the first unconditional proof for $k \le 12$. Our method combines the Fukuda-Komatsu computational sieve, inductive structure of the cyclotomic $\mathbb{Z}_2$-tower, and Herbrand's theorem.

cs.CRCross-listedarXiv:2604.15858•Apr 20, 2026

Concrete Security from Worst-Case to Average-Case Lattice Reductions

Joel Gärtner

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

Generating Hard Instances of Lattice Problems

Miklós Ajtai

Electronic colloquium on computational complexity•Jan 1, 1996•598 citations

Worst-Case to Average-Case Reductions for the SIS Problem: Tightness and Security

Elena Bakos Lang

We present a framework for evaluating the concrete security assurances of cryptographic constructions given by the worst-case SIVP_γ to average-case SIS_{n,m,q,β} reductions. As part of this analysis, we present the tightness gaps for three worst-case SIVP_γ to average-case SIS_{n,m,q,β} reductions. We also analyze the hardness of worst-case SIVP_γ instances. \nWe apply our methodology to two SIS-based signature schemes, and compute the security guarantees that these systems get from reductions to worst-case SIVP_γ. We find that most of the presented reductions do not apply to the chosen parameter sets for the signature schemes. We propose modifications to the schemes to make the reductions applicable, and find that the worst-case security assurances of the (modified) signature schemes are, for both signature schemes, significantly lower than the amount of security previously claimed.

•Jul 30, 2019•0 citations

Towards Classical Hardness of Module-LWE: The Linear Rank Case

Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois +1 more

Lecture notes in computer science•Jan 1, 2020•30 citations
Module Lattice Security (Part I): Unconditional Verification of Weber's Conjecture for k≤12k \le 12k≤12
Weber's conjecture (1886) governs three aspects of lattice-based cryptography: the solvability of the Principal Ideal Problem, the freeness of modules over rings of integers, and the tightness of worst-case-to-average-case reductions in Ring-LWE (R-LWE) and Module-LWE (MLWE). Existing verifications for k≥9k \ge 9k≥9 rely on Generalized Riemann Hypothesis (GRH). In this paper, we present the first unconditional proof for k≤12k \le 12k≤12. Our method combines the Fukuda-Komatsu computational sieve, inductive structure of the cyclotomic Z2\mathbb{Z}_2Z2​-tower, and Herbrand's theorem.
We present a framework for evaluating the concrete security assurances of cryptographic constructions given by the worst-case SIVP_γ to average-case SIS_{n,m,q,β} reductions. As part of this analysis, we present the tightness gaps for three worst-case SIVP_γ to average-case SIS_{n,m,q,β} reductions. We also analyze the hardness of worst-case SIVP_γ instances. \nWe apply our methodology to two SIS-based signature schemes, and compute the security guarantees that these systems get from reductions to worst-case SIVP_γ. We find that most of the presented reductions do not apply to the chosen parameter sets for the signature schemes. We propose modifications to the schemes to make the reductions applicable, and find that the worst-case security assurances of the (modified) signature schemes are, for both signature schemes, significantly lower than the amount of security previously claimed.