Helger Lipmaa's publications

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

Helger Lipmaa. Succinct Non-interactive Zero Knowledge Arguments from Span Programs and Linear Error-Correcting Codes. In Kazue Sako and Palash Sarkar, editors, ASIACRYPT 2013, volume 8269 of Lecture Notes in Computer Science, pages 41--60, Bangalore, India, December 1--5, 2013. Springer, Heidelberg.

File: [.pdf (505 KB)] pdf recommended.

Abstract:

Gennaro, Gentry, Parno and Raykova proposed an efficient NIZK argument for \textsc{Circuit-SAT}, based on non-standard tools like conscientious and quadratic span programs. We propose a new linear PCP for the \textsc{Circuit-SAT}, based on a 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). This allows us to simplify all steps of the argument, which results in significantly improved efficiency. We then construct an NIZK \textsc{Circuit-SAT} argument based on existing techniques. .

Keywords: Circuit-SAT, linear error-correcting codes, non-interactive zero knowledge, polynomial algebra, span program, verifiable computation.


Comment: Conference version misses several proofs, etc. Full version available from http://eprint.iacr.org/2013/121.


Authors:

Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa><at>gmail.com.