Cryptology ePrint Archive: Report 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. In this work, we work out a concrete lower
bound on the success probability and its effect in determining an upper bound on the tightness gap of the reduction. The success probability
is determined by the value of the rejection threshold $t$ of the statistical test. Using a particular value of $t$, Regev showed that
asymptotically, the success probability of the test is exponentially close to one for all values of the LWE error $\alpha\in(0,1)$.
From the concrete
analysis point of view, the value of the rejection threshold used by Regev is sub-optimal. It leads to considering the lattice dimension
to be as high as 400000 to obtain somewhat meaningful tightness gap. We show that by using a different value of the rejection
threshold and considering $\alpha$ to be at most $1/\sqrt{n}$ results in the success probability going to 1 for small values of the
lattice dimension. Consequently, our work shows that it may be required to modify values of parameters used in an asymptotic analysis
to obtain much improved and meaningful concrete security.
Category / Keywords: public-key cryptography / lattices, learning with errors, discrete gaussian sampling, statistical test, concrete analysis
Date: received 19 Jun 2019, last revised 7 Nov 2019
Contact author: palash at isical ac in, subha_r at isical ac in
Available format(s): PDF | BibTeX Citation
Note: An alternative concrete analysis has been included which shows that the success probability of the statistical test is close to one for small values of lattice dimension.
Version: 20191108:043155 (All versions of this report)
Short URL: ia.cr/2019/728
[ Cryptology ePrint archive ]