Paper 2020/880 Original: eprint.iacr.org/2020/880 ↗
Classical Reduction of Gap SVP to LWE: A Concrete Security Analysis
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2021-02-10: last updated
- 2020-07-16: published
- Short URL
- https://ia.cr/2020/880
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2020/880,
author = {Palash Sarkar and Subhadip Singha},
title = {Classical Reduction of Gap SVP to LWE: A Concrete Security Analysis},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/880},
year = {2020},
url = {https://eprint.iacr.org/2020/880}
}