ZK Research Highlights (June 2023)
In this issue, I intentionally excluded huge amount of important works that will appear in Crypto 2023. There will be a special issue to present these works.
zkSaaS: Zero-Knowledge SNARKs as a Service
by Sanjam Garg, Aarushi Goel, Abhishek Jain, Guru-Vamsi Policharla, and Sruthi Sekar (USENIX Security 2023)
introduce a framework called zk-SNARKs-as-a-service (zkSaaS).
distributing proof computation across multiple servers such that each server is expected to run for a shorter duration than a single prover.
instantiate this framework with custom protocols to obtain faster runtimes than local provers for widely used zk-SNARKs, such as Groth16 , Marlin and Plonk. get ≈22× speed-up when run with 128 parties for 2^25 constraints with Groth16 and 2^21 gates with Plonk.
the privacy of the prover's witness is ensured against any minority of colluding servers.
Reed-Solomon Codes over the Circle Group
by Ulrich Habock and Daniel Lubarov and Jacqueline Nabaglo
discuss Reed-Solomon codes with domain of definition within the unit circle of the complex extension C(F) of a Mersenne prime field F.
expect these "almost native" Reed-Solomon codes to perform as native ones based on prime fields with high two-adicity, but less processor-friendly arithmetic.
Efficient Zero Knowledge for Regular Language
by Michael Raymond and Gillian Evers and Jan Ponti and Diya Krishnan and Xiang Fu
present zkreg, a distributed commit-and-prove system ,a succinct zero knowledge proof for regular language membership
cryptographic operations are encoded using arithmetic circuits, and input acceptance is modeled as a zero knowledge subset problem using Σ-protocols.
introduce a Feedback Commit-and-Prove (FB-CP) scheme, which connects Σ-protocols and the Groth16 system with O(1) proof size and verifier cost.
present a close-to-optimal univariate instantiation of zk-VPD, a zero knowledge variation of the KZG polynomial commitment scheme, based on which an efficient zk-subset protocol is developed.
SublonK: Sublinear Prover PlonK
by Arka Rai Choudhuri and Sanjam Garg and Aarushi Goel and Sruthi Sekar and Rohit Sinha
propose SublonK - a new zkSNARK, builds on PlonK
achieves improved prover running time over PlonK. prover runtime grows with the size of the "active part" of the circuit.
UniPlonk: Plonk with Universal Verifier
by Shumo Chu and Brandon H. Gomes and Francisco Hernandez Iglesias and Todd Norton and Duncan Tebbs
propose UniPlonK, a modification of the PlonK protocol that uniformizes the Verifier’s work for families of circuits.
extends the universality of PlonK beyond the SRS; it enables a single “Universal Verifier Circuit” capable of verifying proofs from different PlonK circuits.
SoK: Vector OLE-Based Zero-Knowledge Protocols
by Carsten Baum and Samuel Dittmer and Peter Scholl and Xiao Wang
a survey of recent developments in building practical systems for zero-knowledge proofs of knowledge using vector oblivious linear evaluation (VOLE), a tool from secure two-party computation.
Lattice-Based Polynomial Commitments: Towards Asymptotic and Concrete Efficiency
by Giacomo Fenzi and Ngoc Khanh Nguyen
propose a lattice-based polynomial commitment that achieves succinct proof size and verification time.
Extractability of our scheme holds in the random oracle model under a natural ring version of the BASIS assumption introduced by Wee and Wu (EUROCRYPT 2023).
do not require any expensive preprocessing steps
instantiate polynomial commitment, together with the Marlin PIOP (Eurocrypt 2020), to obtain a publicly-verifiable trusted-setup succinct argument for Rank-1 Constraint System (R1CS).
Zeromorph: Zero-Knowledge Multilinear-Evaluation Proofs from Homomorphic Univariate Commitments
by Tohru Kohrita and Patrick Towa
presents a scheme to commit to multilinear polynomials and to later prove evaluations of committed polynomials.
relies on additively homomorphic schemes to commit to univariate polynomials.
gives a method to batch executions of any degree-check protocol on homomorphic commitments.
Testudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup
by Matteo Campanelli and Nicolas Gailly and Rosario Gennaro and Philipp Jovanovic and Mara Mihali and Justin Thaler
present Testudo, a new FFT-less SNARK with a near linear-time prover, constant-time verifier, constant-size proofs and a square-rootsize universal setup.
based on a variant of Spartan
a new, fast multivariate polynomial commitment scheme (PCS) with a square-root-sized trusted setup that is derived from PST (TCC 2013) and IPPs (Asiacrypt 2021).
combine PCS openings proofs recursively with a Groth16 SNARK.
achieves a 110x speed-up compared to PST and 3x compared to Gemini (Eurocrypt 2022)
Revisiting the Nova Proof System on a Cycle of Curves
by Wilson Nguyen and Dan Boneh and Srinath Setty
point out a soundness vulnerability in the original implementation of the 2-cycle Nova system.
present a modification of the 2-cycle Nova system and formally prove its security.
the modification eliminates an R1CS instance-witness pair from the recursive proof.
show that Nova's IVC proofs are malleable and discuss several mitigations.
Lightweight Authentication of Web Data via Garble-Then-Prove
by Xiang Xie and Kang Yang and Xiao Wang and Yu Yu
proposes the garble-then-prove technique without using any heavy mechanism like generic malicious 2PC.
shows 14× improvement in communication and an order of magnitude improvement in computation over the state-of-the-art protocol;
show worldwide performance when using our protocol to authenticate payload data from Coinbase and Twitter APIs.
propose an efficient gadget to privately convert the above authenticated TLS payload to Pedersen commitments so that the properties of the payload can be proven efficiently using zkSNARKs.
VSS from Distributed ZK Proofs and Applications
by Shahla Atapoor and Karim Baghery and Daniele Cozzo and Robi Pedersen
present an efficient NI-VSS scheme using ZK proofs on secret shared data.
uses a quantum random oracle and a quantum computationally hiding commitment scheme in a black-box manner, which ensures its ease of use, especially in post-quantum threshold protocols.
present two DKG protocols for CSIDH-based primitives
show similar improvements in some threshold signatures built based on Schnorr and CSI-FiSh signature schemes.
MUXProofs: Succinct Arguments for Machine Computation from Tuple Lookups
by Zijing Di and Lucas Xia and Wilson Nguyen and Nirvan Tyagi
present a new protocol for proving machine execution allowing for prover efficiency on the order of executed instructions while achieving zero-knowledge and avoiding the use of proof recursion.
a new primitive tuple lookup argument which is used to allow a prover to build up a machine execution “on-the-fly”.
relies on univariate polynomial commitments in which tuples are encoded as evaluations on cosets of a multiplicative subgroup.
instantiate our protocol by combining our tuple lookup with the popular Marlin succinct non-interactive proof system.