Beyond the circuit: How to Minimize Foreign Arithmetic in ZKP Circuits

A fundamental challenge in zero-knowledge proof systems is implementing operations that are “foreign” to the underlying constraint system, in that they are arithmetic operations with a different modulus than the one used by the proof system. The modulus of the constraint system is a large prime, and common examples of foreign operations are Boolean operations, field arithmetic, or public-key cryptography operations. We present novel techniques for efficiently embedding such foreign arithmetic in zero-knowledge, including (i) equality of discrete logarithms across different groups; (ii) scalar multiplication without requiring elliptic curve operations; (iii) proving knowledge of an AES encryption. Our approach combines rejection sampling, sigma protocols, and lookup protocols. We implement and provide concrete benchmarks for our protocols.