Back to Search
Start Over
Classical reduction of gap SVP to LWE: A concrete security analysis
- Source :
- Advances in Mathematics of Communications. 17:484-499
- Publication Year :
- 2023
- Publisher :
- American Institute of Mathematical Sciences (AIMS), 2023.
-
Abstract
- Regev (2005) introduced the learning with errors (LWE) problem and showed a quantum reduction from a worst case lattice problem to LWE. Building on the work of Peikert (2009), a classical reduction from the gap shortest vector problem to LWE was obtained by Brakerski et al. (2013). A concrete security analysis of Regev's reduction by Chatterjee et al. (2016) identified a huge tightness gap. The present work performs a concrete analysis of the tightness gap in the classical reduction of Brakerski et al. It turns out that the tightness gap in the Brakerski et al. classical reduction is even larger than the tightness gap in the quantum reduction of Regev. This casts doubts on the implication of the reduction to security assurance of practical cryptosystems.
- Subjects :
- Discrete mathematics
Algebra and Number Theory
Computer Networks and Communications
Applied Mathematics
Lattice problem
Chatterjee
020206 networking & telecommunications
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Microbiology
Reduction (complexity)
010201 computation theory & mathematics
0202 electrical engineering, electronic engineering, information engineering
Discrete Mathematics and Combinatorics
Cryptosystem
Concrete security
Learning with errors
Mathematics
Subjects
Details
- ISSN :
- 19305338 and 19305346
- Volume :
- 17
- Database :
- OpenAIRE
- Journal :
- Advances in Mathematics of Communications
- Accession number :
- edsair.doi...........e166463a03c09d59da466c4c17ad7813