You are looking at a specific version 20200716:132832 of this paper. See the latest version.

Paper 2020/880

Classical Reduction of SVP to LWE: A Concrete Security Analysis

Palash Sarkar and Subhadip Singha

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 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. MINOR revision.
Keywords
latticesshortest vector problemlearning with errorsclassical reductionconcrete analysis
Contact author(s)
palash @ isical ac in
subha_r @ isical ac in
History
2021-02-10: last of 2 revisions
2020-07-16: received
See all versions
Short URL
https://ia.cr/2020/880
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.