Paper 2022/1633

Vortex : Building a Lattice-based SNARK scheme with Transparent Setup

Alexandre Belling, Consensys R&D
Azam Soleimanian, Consensys R&D
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
No rights reserved
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.