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

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
latticeslearning with errorsdiscrete gaussian samplingstatistical testconcrete analysis
Contact author(s)
palash @ isical ac in
subha_r @ isical ac in
History
2019-11-08: last of 4 revisions
2019-06-20: received
See all versions
Short URL
https://ia.cr/2019/728
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/728,
      author = {Palash Sarkar and Subhadip Singha},
      title = {Verifying Solutions to LWE with Implications for Concrete Security},
      howpublished = {Cryptology ePrint Archive, Paper 2019/728},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/728}},
      url = {https://eprint.iacr.org/2019/728}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.