Welcome to the resource topic for 2013/121
Title:
Succinct Non-Interactive Zero Knowledge Arguments from Span Programs and Linear Error-Correcting Codes
Authors: Helger Lipmaa
Abstract:Recently, Gennaro, Gentry, Parno and Raykova~\cite{eprint2012:GennaroGPR} proposed an efficient non-interactive zero knowledge argument for Circuit-SAT, based on non-standard notions like conscientious and quadratic span programs. We propose a new non-interactive zero knowledge argument, based on a simple combination of \emph{standard} span programs (that verify the correctness of every individual gate) and high-distance linear error-correcting codes (that check the consistency of wire assignments). We simplify all steps of the argument. As one of the corollaries, we design an (optimal) wire checker, based on systematic Reed-Solomon codes, of size 8 n and degree 4 n, while the wire checker from~\cite{eprint2012:GennaroGPR} has size 24 n and degree 76 n, where n is the circuit size. Importantly, the new argument has constant verifier’s computation.
ePrint: https://eprint.iacr.org/2013/121
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 .