Paper 2021/322

Rinocchio: SNARKs for Ring Arithmetic

Chaya Ganesh, Indian Institute of Science Bangalore
Anca Nitulescu, Protocol Labs
Eduardo Soria-Vazquez, Technology Innovation Institute
Abstract

Succinct non-interactive arguments of knowledge (SNARKs) enable non-interactive efficient verification of NP computations and admit short proofs. However, all current SNARK constructions assume that the statements to be proven can be efficiently represented as either Boolean or arithmetic circuits over finite fields. For most constructions, the choice of the prime field $\mathbb{F}_p$ is limited by the existence of groups of matching order for which secure bilinear maps exist. In this work we overcome such restrictions and enable verifying computations over rings. We construct the first designated-verifier SNARK for statements which are represented as circuits over a broader kind of commutative rings, namely those containing big enough exceptional sets. Exceptional sets consist of elements such that their pairwise differences are invertible. Our contribution is threefold: We first introduce Quadratic Ring Programs (QRPs) as a characterization of NP where the arithmetic is over a ring. Second, inspired by the framework in Gennaro, Gentry, Parno and Raykova (EUROCRYPT 2013), we design SNARKs over rings in a modular way. We generalize pre-existent assumptions employed in field-restricted SNARKs to encoding schemes over rings. As our encoding notion is generic in the choice of the ring, it is amenable to different settings. Finally, we propose two applications for our SNARKs. Our first application is verifiable computation over encrypted data, specifically for evaluations of Ring- LWE-based homomorphic encryption schemes. In the second one, we use Rinocchio to naturally prove statements about circuits over e.g. $\mathbb{Z}_{2^{64}}$, which closely matches real-life computer architectures such as standard CPUs.

Note: typo

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Proofs and Arguments SNARKs Ring Arithmetic Galois Rings Zero Knowledge
Contact author(s)
anca @ protocol ai
History
2022-06-24: last of 6 revisions
2021-03-11: received
See all versions
Short URL
https://ia.cr/2021/322
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/322,
      author = {Chaya Ganesh and Anca Nitulescu and Eduardo Soria-Vazquez},
      title = {Rinocchio: SNARKs for Ring Arithmetic},
      howpublished = {Cryptology ePrint Archive, Paper 2021/322},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/322}},
      url = {https://eprint.iacr.org/2021/322}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.