Paper 2019/728

Verifying Solutions to LWE with Implications for Concrete Security

Palash Sarkar and Subhadip Singha

Abstract

A key step in Regev's (2009) reduction of the Discrete Gaussian Sampling (DGS) problem to that of solving the Learning With Errors (LWE) problem is a statistical test required for verifying possible solutions to the LWE problem. Regev showed that asymptotically, the success probability of this test is exponentially close to 1. In this work, we work out the concrete details of the success probability and its effect on the tightness gap of the reduction. For lattice dimensions from 2 to 187149, the tightness gap is determined entirely by the inverse of the success probability. The actual value of the tightness gap for such lattice dimensions is huge showing that the reduction cannot be used for choosing parameters for practical cryptosystems.