Paper 2022/1633
Vortex : Building a Lattice-based SNARK scheme with Transparent Setup
Abstract
We present the first transparent and plausibly post-quantum SNARK relying on the Ring Short Integer Solution problem (Ring-SIS), a well-known assumption from lattice-based cryptography. At its core, our proof system relies on a new linear-commitment scheme named Vortex which is inspired from the work of Orion and Brakedown. Vortex uses a hash function based on Ring-SIS derived from “SWIFFT" (Lyubashevsky et al., FSE08). We take advantage of the linear structure of this particular hash function to craft an efficient self-recursion technique. Although Vortex proofs have $O(\sqrt{n})$ size in the witness size, we show how our self-recursion technique can be used to build a SNARK scheme based on Vortex. The resulting SNARK works over any field with reasonably large 2-adicity (also known as FFT-friendly fields). Moreover, we introduce Wizard-IOP, an extension of the concept of polynomial-IOP. Working with Wizard-IOP rather than separate polynomial-IOPs provides us with a strong tool for handling a wide class of queries, needed for proving the correct executions of the complex state machines (e.g., zk-EVM as our use-case) efficiently and conveniently.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- SNARKzkEVMPolynomial-IOPRecursionPolynomial commitmentSISring-SISPost-Quantum
- Contact author(s)
-
alexandre belling @ consensys net
azam soleimanian @ consensys net - History
- 2023-03-02: last of 2 revisions
- 2022-11-24: received
- See all versions
- Short URL
- https://ia.cr/2022/1633
- License
-
CC0
BibTeX
@misc{cryptoeprint:2022/1633, author = {Alexandre Belling and Azam Soleimanian}, title = {Vortex : Building a Lattice-based SNARK scheme with Transparent Setup}, howpublished = {Cryptology ePrint Archive, Paper 2022/1633}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1633}}, url = {https://eprint.iacr.org/2022/1633} }