Classical Reduction of Gap SVP to LWE: A Concrete Security Analysis

Palash Sarkar; Subhadip Singha

Paper 2020/880

Classical Reduction of Gap 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 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.

Note: Corrected some errors.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: lattices shortest vector problem learning with errors classical reduction concrete 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: CC BY

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}
}