Cryptology ePrint Archive: Report 2019/1076

Fractal: Post-Quantum and Transparent Recursive Proofs from Holography

Alessandro Chiesa and Dev Ojha and Nicholas Spooner

Abstract: We present a new methodology to efficiently realize recursive composition of succinct non-interactive arguments of knowledge (SNARKs). Prior to this work, the only known methodology relied on pairing-based SNARKs instantiated on cycles of pairing-friendly elliptic curves, an expensive algebraic object. Our methodology does not rely on any special algebraic objects and, moreover, achieves new desirable properties: it is *post-quantum* and it is *transparent* (the setup is public coin).

We exploit the fact that recursive composition is simpler for SNARKs with *preprocessing*, and the core of our work is obtaining a preprocessing zkSNARK for rank-1 constraint satisfiability (R1CS) that is post-quantum and transparent. We obtain this latter by establishing a connection between holography and preprocessing in the random oracle model, and then constructing a holographic proof for R1CS.

We experimentally validate our methodology, demonstrating feasibility in practice.

Category / Keywords: foundations / succinct arguments; holographic proofs; recursive proof composition; post-quantum cryptography

Date: received 20 Sep 2019, last revised 25 Oct 2019

Contact author: alexch at berkeley edu

Available format(s): PDF | BibTeX Citation

Version: 20191025:205446 (All versions of this report)

Short URL: ia.cr/2019/1076


[ Cryptology ePrint archive ]