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.