Welcome to the resource topic for 2017/759
Title:
Simple Amortized Proofs of Shortness for Linear Relations over Polynomial Rings
Authors: Carsten Baum, 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.
ePrint: https://eprint.iacr.org/2017/759
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .