Paper 2017/759

Simple Amortized Proofs of Shortness for Linear Relations over Polynomial Rings

Carsten Baum and Vadim Lyubashevsky


For a public value $y$ and a linear function $f$, giving a zero-knowledge proof of knowledge of a secret value $x$ that satisfies $f(x)=y$ is a key ingredient in many cryptographic protocols. Lattice-based 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 lattice-based zero-knowledge 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 zero-knowledge 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 zero-knowledge 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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
lattice cryptographyzero-knowledge proofs
Contact author(s)
vadim lyubash @ gmail com
2017-08-07: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.