Paper 2017/759
Simple Amortized Proofs of Shortness for Linear Relations over Polynomial Rings
Carsten Baum and Vadim Lyubashevsky
Abstract
For a public value $y$ and a linear function $f$, giving a zeroknowledge proof of knowledge of a secret value $x$ that satisfies $f(x)=y$ is a key ingredient in many cryptographic protocols. Latticebased constructions, in addition, require proofs of ``shortness'' of $x$. Of particular interest are constructions where $f$ is a function over polynomial rings, since these are the ones that result in efficient schemes with short keys and outputs. All known approaches for such latticebased zeroknowledge proofs are not very practical because they involve a basic protocol that needs to be repeated many times in order to achieve negligible soundness error. In the amortized setting, where one needs to give zeroknowledge proofs for many equations for the same function $f$, the situation is more promising, though still not yet fully satisfactory. Current techniques either result in proofs of knowledge of $x$'s that are exponentially larger than the $x$'s actually used for the proof (i.e. the \emph{slack} is exponential), or they have polynomial slack but require the number of proofs to be in the several thousands before the amortization advantages ``kick in''. In this work, we give a new approach for constructing amortized zeroknowledge proofs of knowledge of short solutions over polynomial rings. Our proof has small polynomial slack and is practical even when the number of relations is as small as the security parameter.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 lattice cryptographyzeroknowledge proofs
 Contact author(s)
 vadim lyubash @ gmail com
 History
 20170807: received
 Short URL
 https://ia.cr/2017/759
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/759, author = {Carsten Baum and Vadim Lyubashevsky}, title = {Simple Amortized Proofs of Shortness for Linear Relations over Polynomial Rings}, howpublished = {Cryptology ePrint Archive, Paper 2017/759}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/759}}, url = {https://eprint.iacr.org/2017/759} }