Onigoroshi: Polynomial Interactive Oracle Proofs for Circuit Satisfiability over Cyclotomic Rings with Automorphism Gates
Loading...
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2024-08-21
Department
Major/Subject
Security and Cloud Computing
Mcode
Degree programme
Master's Programme in Security and Cloud Computing
Language
en
Pages
62
Series
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.Description
Supervisor
Lai, Russell W. F.Thesis advisor
Lipmaa, HelgerKeywords
SNARK, PIOP, lattice-based cryptography, post quantum, galois group, automorphism