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

Zero-knowledge circuits are frequently required to prove gadgets that are not optimised for the constraint system in question. A particularly daunting task is to embed foreign arithmetic such as boolean operations, field arithmetic, or public-key cryptography.

We construct techniques for offloading foreign arithmetic from a zero-knowledge circuit including
(i) equality of discrete logarithms across different groups;
(ii) scalar multiplication without requiring elliptic curve addition;
(iii) proving knowledge of an AES encryption.
To achieve our goal, we employ techniques inherited from rejection sampling and lookup protocols. We implement and provide concrete benchmarks for our protocols. In particular, proving an AES preimage is comparable with state-of-the-art MPCitH techniques.