Practical zero-knowledge proofs for circuit evaluation

Ghadafi, Essam; Smart, Nigel P.; Warinschi, Bogdan

Abstract

Showing that a circuit is satisfiable without revealing information is a key problem in modern cryptography. The related (and more general) problem of showing that a circuit evaluates to a particular value if executed on the input contained in a public commitment has potentially multiple practical applications. Although numerous solutions for the problem had been proposed, their practical applicability is poorly understood. In this paper, we take an important step towards moving existent solutions to practice. We implement and evaluate four solutions for the problem. We investigate solutions both in the common reference string model and the random oracle model. In particular, in the CRS model we use the recent techniques of Groth-Sahai for proofs that use bilinear groups in the asymmetric pairings environment. We provide various optimizations to the different solutions we investigate. We present timing results for two circuits the larger of which is an implementation of AES that uses about 30000 gates. © 2009 Springer-Verlag.

• Presentation Conference Type: Conference Paper (published)
• Conference Name: IMA International Conference on Cryptography and Coding
• Start Date: Dec 15, 2009
• End Date: Dec 17, 2009
• Acceptance Date: Dec 1, 2009
• Publication Date: Dec 28, 2009
• Journal: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
• Print ISSN: 0302-9743
• Publisher: Springer Verlag
• Peer Reviewed: Peer Reviewed
• Volume: 5921 LNCS
• Pages: 469-494
• DOI: https://doi.org/10.1007/978-3-642-10868-6_28
• Keywords: practical, zero-knowledge, proofs, circuit evaluation
• Public URL: https://uwe-repository.worktribe.com/output/989777
• Publisher URL: http://dx.doi.org/10.1007/978-3-642-10868-6_28
• Additional Information: Title of Conference or Conference Proceedings : IMA International Conference on Cryptography and Coding