Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / lattices, shortest vector problem, learning with errors, classical reduction, concrete analysis

Date: received 13 Jul 2020

Contact author: palash at isical ac in, subha_r@isical ac in

Available format(s): PDF | BibTeX Citation

Version: 20200716:132832 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]