Paper 2022/1072
Recursion over Public-Coin Interactive Proof Systems; Faster Hash Verification
Abstract
SNARK is a well-known family of cryptographic tools that is increasingly used in the field of computation integrity at scale. In this area, multiple works have introduced SNARK-friendly cryptographic primitives: hashing, but also encryption, and signature verification. Despite all the efforts to create cryptographic primitives that can be proved faster, it remains a major performance hole in practice. In this paper, we present a recursive technique that can improve the efficiency of the prover by an order of magnitude compared to proving MiMC hashes (a SNARK-friendly hash function, Albrecht et al. 2016) with a Groth16 (Eurocrypt 2016) proof. We use GKR (a well-known public-coin argument system by Goldwasser et al., STOC 2008) to prove the integrity of hash computations and embed the GKR verifier inside a SNARK circuit. The challenge comes from the fact that GKR is a public-coin interactive protocol, and applying Fiat-Shamir naively may result in worse performances than applying existing techniques directly. This is because Fiat-Shamir itself is involved with hash computation over a large string. We take advantage of a property that SNARK schemes commonly have, to build a protocol in which the Fiat-Shamir hashes have very short inputs. The technique we present is generic and can be applied over any SNARK-friendly hash, most known SNARK schemes, and any public-coin argument system in place of GKR.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- SNARK Hash Verification Proof Recursion Proof Composition GKR Public-Coin Fiat Shamir So-Far Digest Model
- Contact author(s)
-
alexandre belling @ consensys net
azam soleimanian @ consensys net
olivier begassat @ consensys net - History
- 2022-11-30: revised
- 2022-08-18: received
- See all versions
- Short URL
- https://ia.cr/2022/1072
- License
-
CC0
BibTeX
@misc{cryptoeprint:2022/1072, author = {Alexandre Belling and Azam Soleimanian and Olivier Bégassat}, title = {Recursion over Public-Coin Interactive Proof Systems; Faster Hash Verification}, howpublished = {Cryptology ePrint Archive, Paper 2022/1072}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1072}}, url = {https://eprint.iacr.org/2022/1072} }