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.
|Translated title of the contribution||Practical zero-knowledge proofs for circuit evaluation|
|Title of host publication||Coding and Cryptography - IMACC 2009|
|Publisher||Springer Berlin Heidelberg|
|Publication status||Published - 2009|
Bibliographical noteOther page information: 469-494
Conference Proceedings/Title of Journal: Coding and Cryptography: IMACC 2009
Other identifier: 2001122