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