Practical zero-knowledge proofs for circuit evaluationEssam Ghadafi, Nigel Smart, Bogdan Warinschi, Practical zero-knowledge proofs for circuit evaluation. Coding and Cryptography: IMACC 2009, pp. 469–494. December 2009. No electronic version available. External information
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.