# ZK Research Highlights (June 2023)

In this issue, I intentionally excludedhugeamount of important works that will appear in Crypto 2023. There will be aspecial issueto 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 membershipcryptographic 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*primitivesshow 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.