CryptoDB
Fractal: Post-Quantum and Transparent Recursive Proofs from Holography
| Authors: |
|
|---|---|
| Download: |
|
| Conference: | EUROCRYPT 2020 |
| 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. |
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30227,
title={Fractal: Post-Quantum and Transparent Recursive Proofs from Holography},
booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
series={Lecture Notes in Computer Science},
publisher={Springer},
keywords={succinct arguments;holographic proofs;recursive proof composition;post-quantum cryptography},
volume={12105},
doi={10.1007/978-3-030-45721-1_27},
author={Alessandro Chiesa and Dev Ojha and Nicholas Spooner},
year=2020
}