Paper 2019/642
Algebraic Techniques for Short(er) Exact LatticeBased ZeroKnowledge Proofs
Jonathan Bootle, Vadim Lyubashevsky, and Gregor Seiler
Abstract
A key component of many latticebased protocols is a zeroknowledge proof of knowledge of a vector $\vec{s}$ with small coefficients satisfying $A\vec{s}=\vec{u}\bmod\,q$. While there exist fairly efficient proofs for a relaxed version of this equation which prove the knowledge of $\vec{s}'$ and $c$ satisfying $A\vec{s}'=\vec{u}c$ where $\\vec{s}'\\gg\\vec{s}\$ and $c$ is some small element in the ring over which the proof is performed, the proofs for the exact version of the equation are considerably less practical. The best such proof technique is an adaptation of Stern's protocol (Crypto '93), for proving knowledge of nearby codewords, to larger moduli. The scheme is a $\Sigma$protocol, each of whose iterations has soundness error $2/3$, and thus requires over $200$ repetitions to obtain soundness error of $2^{128}$, which is the main culprit behind the large size of the proofs produced. In this paper, we propose the first latticebased proof system that significantly outperforms Sterntype proofs for proving knowledge of a short $\vec{s}$ satisfying $A\vec{s}=\vec{u}\bmod\,q$. Unlike Stern's proof, which is combinatorial in nature, our proof is more algebraic and uses various relaxed zeroknowledge proofs as subroutines. The main savings in our proof system comes from the fact that each round has soundness error of $1/n$, where $n$ is the number of columns of $A$. For typical applications, $n$ is a few thousand, and therefore our proof needs to be repeated around $10$ times to achieve a soundness error of $2^{128}$. For concrete parameters, it produces proofs that are around an order of magnitude smaller than those produced using Stern's approach.
Note: Added acknowledgements.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published by the IACR in CRYPTO 2019
 Keywords
 LatticesZeroKnowledge ProofsCommitments
 Contact author(s)

jbt @ zurich ibm com
vad @ zurich ibm com
gregor seiler @ inf ethz ch  History
 20190628: revised
 20190603: received
 See all versions
 Short URL
 https://ia.cr/2019/642
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/642, author = {Jonathan Bootle and Vadim Lyubashevsky and Gregor Seiler}, title = {Algebraic Techniques for Short(er) Exact LatticeBased ZeroKnowledge Proofs}, howpublished = {Cryptology ePrint Archive, Paper 2019/642}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/642}}, url = {https://eprint.iacr.org/2019/642} }