Welcome to the resource topic for
**2022/1072**

**Title:**

Recursion over Public-Coin Interactive Proof Systems; Faster Hash Verification

**Authors:**
Alexandre Belling, Azam Soleimanian, Olivier Bégassat

**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 - which are used in many applications. 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 for the Fiat-Shamir hashes have very short inputs. The technique we present is generic and can be applied to over most known SNARK scheme and any public-coin argument system in place of GKR. It outputs an augmented proof system combining the performances of the two.

**ePrint:**
https://eprint.iacr.org/2022/1072

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .