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

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

Joel Gärtner

Published Jan 1, 2023• 2 citations
Publisher
DOI
10.1007/978-3-031-37679-5_15

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

Worst-case to average-case reductions for module lattices

Adeline Roux-Langlois, Damien Stehlé

Designs Codes and Cryptography•Feb 25, 2014•718 citations

Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems

Akinori Kawachi, Keisuke Tanaka, Keita Xagawa

Lecture notes in computer science•Jan 1, 2008•220 citations

Making NTRU as Secure as Worst-Case Problems over Ideal Lattices

Damien Stehlé, Ron Steinfeld

Lecture notes in computer science•Jan 1, 2011•458 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

Lattice-Based Functional Commitments: Fast Verification and Cryptanalysis

Hoeteck Wee, David J. Wu

Lecture notes in computer science•Jan 1, 2023•30 citations
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.