Paper 2013/121

Succinct Non-Interactive Zero Knowledge Arguments from Span Programs and Linear Error-Correcting Codes

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
Circuit-SATlinear error-correcting codesnon-interactive zero knowledgepolynomial algebraspan programverifiable computation
Contact author(s)
helger lipmaa @ gmail com
History
2013-03-05: received
Short URL
https://ia.cr/2013/121
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/121,
      author = {Helger Lipmaa},
      title = {Succinct Non-Interactive Zero Knowledge Arguments from Span Programs and Linear Error-Correcting Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2013/121},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/121}},
      url = {https://eprint.iacr.org/2013/121}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.