Onigoroshi: Polynomial Interactive Oracle Proofs for Circuit Satisfiability over Cyclotomic Rings with Automorphism Gates

Abstract

Lattice-based cryptography is a leading candidate for quantum-secure cryptography, and it provides a wide range of advanced cryptographic primitives. Constructing advanced cryptographic primitives requires proving relations involving cryptographic building blocks. Succinct non-interactive arguments of knowledge (SNARKs) enable the efficient non-interactive verification of such relations with short proofs. The construction of SNARKs can be accomplished by compiling an informatic theoretical object known as a polynomial interactive oracle proof (PIOP) with a compatible polynomial commitment scheme.

For efficient constructions of cryptographic primitives, it is important that the cryptographic building blocks and SNARKs operate over the same mathematical structure. However, most existing SNARKs cannot be directly applied to lattice-based cryptographic building blocks because most SNARKs operate over fields, whereas many lattice-based cryptographic primitives work over cyclotomic rings. Some lattice-based cryptographic primitives involve specific non-arithmetic operations such as ring-automorphism operations (e.g., bootstrapping in Fully Homomorphic Encryption).

We present Onigoroshi: the first polynomial interactive oracle proof over cyclotomic rings that can prove relations involving the ring-addition, ring-multiplication, and ring-automorphism operations. To construct the PIOP, we adapted HyperPlonk into the cyclotomic ring setting. We introduced Automorphism-Check, a new PIOP capable of verifying the consistency between the input and output of an automorphism over a cyclotomic ring.