ZK Research Highlights (Crypto 2023)
https://crypto.iacr.org/2023/
Succinctness
SNARGs for Monotone Policy Batch NP
Zvika Brakerski Maya Farber Brodsky Yael Tauman Kalai Alex Lombardi Omer Paneth
construct a SNARG for the class of monotone policy batch NP languages, under the LWE assumption.
arguments of knowledge in the non-adaptive setting, and satisfy a new notion of somewhere extractability against adaptive adversaries.
combines existing quasi-arguments for NP (based on batch arguments for NP) with a new type of cryptographic encoding of the instance and a new analysis going from local to global soundness.
The main novel ingredient : predicate-extractable hash (PEH) family, which is a primitive that generalizes the notion of a somewhere extractable hash.
Lattice-based Succinct Arguments from Vanishing Polynomials
Valerio Cini Russell W. F. Lai Giulio Malavolta
present some new approaches to constructing efficient lattice-based succinct arguments.
a new commitment scheme based on vanishing polynomials
The first recursive folding (i.e. Bulletproofs-like) protocol for linear relations with polylogarithmic verifier runtime.
The first verifiable delay function (VDF) based on lattices
The first lattice-based linear-time prover succinct argument for NP, in the preprocessing model. The soundness of the scheme is based on (knowledge)-k-R-ISIS assumption.
Orbweaver: Succinct Linear Functional Commitments from Lattices
Ben Fisch Zeyu Liu Psi Vesely
present Orbweaver, the first plausibly post-quantum functional commitment to achieve quasilinear prover time together with O(log(n)) proof size and O(log(n)loglog(n)) verifier time.
Orbweaver enables evaluation of linear maps on committed vectors over cyclotomic rings or the integers.
It is extractable, preprocessing, non-interactive, structure-preserving, amenable to recursive composition, and supports logarithmic public proof aggregation.
The security of our scheme is based on the k-R-ISIS assumption (and its knowledge counterpart), whereby require a trusted setup to generate a universal structured reference string.
use Orbweaver to construct a succinct polynomial commitment for integer polynomials.
Non-interactive Universal Arguments
Nir Bitansky Omer Paneth Dana Shamir Tomer Solomon
Assuming polynomially hard fully homomorphic encryption and a widely believed worst-case complexity assumption, prove a general lifting theorem showing that all existing non-interactive succinct arguments can be made universal.
Non-Interactive Zero-Knowledge from Non-Interactive Batch Arguments
Jeffrey Champion David J. Wu
leveraging succinctness for zero-knowledge.
show how to combine a batch argument for NP with a local pseudorandom generator and a dual-mode commitment scheme to obtain a NIZK for NP.
Succinct Arguments for RAM Programs via Projection Codes
Yuval Ishai Rafail Ostrovsky Akash Shah
a construction of projection codes with a near-optimal increase in the length of x and size of s.
succinct arguments for the computation of a RAM program on a (big) committed database, where the communication and the run-time of both the prover and the verifier are close to optimal even when the RAM program run-time is much smaller than the database size.
Brakedown: Linear-time and field-agnostic SNARKs for R1CS
Alexander Golovnev Jonathan Lee Srinath Setty Justin Thaler Riad Wahby
introduces a SNARK called Brakedown.
Brakedown targets R1CS.
linear-time prover
It does not require a trusted setup
and may be post-quantum secure.
compatible with arbitrary finite fields of sufficient size
a linear-time encodable code.
Shockwave: a variant of Brakedown that uses Reed-Solomon codes
Lattice-Based Succinct Arguments for NP with Polylogarithmic-Time Verification
Jonathan Bootle Alessandro Chiesa Katerina Sotiraki
construct the first lattice-based succinct interactive argument system for NP statements with succinct verification exploits the homomorphic properties of lattice-based commitments.
based on the hardness of the RSIS problem.
a delegation protocol built from commitment schemes based on leveled bilinear modules.
Revisiting cycles of pairing-friendly elliptic curves
Marta Bellés Muñoz Jorge Jiménez Urroz Javier Silva
explore 2-cycles composed of curves from families parameterized by polynomials, and show that such cycles do not exist unless a strong condition holds.
prove that no 2-cycles can arise from the known families, except for those cycles already known.
Post-Quantum ZK
Efficient Hybrid Exact/Relaxed Lattice Proofs and Applications to Rounding and VRFs
Muhammed F. Esgin Ron Steinfeld Dongxi Liu Sushmita Ruj
study hybrid exact/relaxed zero-knowledge proofs from lattices, where the proved relation is exact in one part and relaxed in the other.
introduce a general framework, LANES+, for realizing such hybrid proofs efficiently by combining standard relaxed proofs of knowledge RPoK and the LANES framework
construct substantially shorter proofs of rounding
design an efficient long-term verifiable random function (VRF), named LaV. LaV leads to the shortest VRF outputs among the proposals of standard VRFs based on quantum-safe assumptions.
LaBRADOR: Compact Proofs for R1CS from Module-SIS
Ward Beullens Gregor Seiler
introducing a Lattice-Based Recursively Amortized Demonstration Of R1CS (LaBRADOR), with more compact proof sizes than known hash-based proof systems.
At the 128 bits security level, LaBRADOR proves knowledge of a solution for an R1CS mod 2^64+1 with 2^20 constraints, with a proof size of only 58 KB
Toward Practical Lattice-based Proof of Knowledge from Hint-MLWE
Duhyeong Kim Dongwon Lee Jinyeong Seo Yongsoo Song
improve the state-of-the-art proof of knowledge protocols for RLWE-based public-key encryption and BDLOP commitment schemes.
present new proof of knowledge protocols without using noise flooding or rejection sampling which are provably secure under a computational hardness assumption, called Hint-MLWE.
no computational overhead from repetition (abort) and achieves a polynomial overhead between the honest and proven languages.
Publicly Verifiable Zero-Knowledge and Post-Quantum Signatures From VOLE-in-the-Head
Carsten Baum Lennart Braun Cyprien Delpech de Saint Guilhem Michael Klooß Emmanuela Orsini Lawrence Roy Peter Scholl
present a new method for transforming zero-knowledge protocols in the designated verifier setting into public-coin protocols, which can be made non-interactive and publicly verifiable.
show that it can be applied to protocols based on vector oblivious linear evaluation (VOLE), with a technique call VOLE-in-the-head, upgrading these protocols to support public verifiability.
present 𝖥𝖠𝖤𝖲𝖳, a post-quantum signature scheme based on AES.
ZK Based on DL
Algebraic Reductions of Knowledge
Abhiram Kothapalli Bryan Parno
introduce reductions of knowledge, a generalization of arguments of knowledge, which reduce checking knowledge of a witness in one relation to checking knowledge of a witness in another (simpler) relation.
unify a growing class of modern techniques as well as provide a compositional framework to modularly reason about individual steps in complex arguments of knowledge. simplify and unify recursive arguments over linear algebraic statements by decomposing them as a sequence of reductions of knowledge.
develop the tensor reduction of knowledge, which generalizes the central reductive step common to many recursive arguments.
Correlation Intractability and SNARGs from Sub-exponential DDH
Arka Rai Choudhuri Sanjam Garg Abhishek Jain Zhengzhong Jin Jiaheng Zhang
first constructions of SNARGs for Batch-NP and P based solely on the sub-exponential Decisional Diffie Hellman (DDH) assumption.
achieve poly-logarithmic proof sizes.
following the correlation-intractability framework for secure instantiation of the Fiat-Shamir paradigm.
a new construction of correlation-intractable hash functions for small input product relations verifiable in TC0, based on sub-exponential DDH.
On the Impossibility of Algebraic NIZK In Pairing-Free Groups
Emanuele Giunta
prove that for a large class of NIZK either a pairing-free group is used non black-box by relying on element representation, or security reduces to external hardness assumptions.
applies to two incomparable cases.
The first one covers Arguments of Knowledge (AoK) which proves that a preimage under a given one way function is known.
The second one covers NIZK (not necessarily AoK) for hard subset problems, which captures relations such as DDH, Decision-Linear and Matrix-DDH.
A Note on Non-Interactive Zero-Knowledge from CDH
Geoffroy Couteau Abhishek Jain Zhengzhong Jin Willy Quach
build non-interactive zero-knowledge (NIZK) and ZAP arguments for all NP where soundness holds for infinitely-many security parameters, and against uniform adversaries, assuming the subexponential hardness of the Computational Diffie-Hellman (CDH) assumption.
prove the existence of NIZK arguments with these same properties assuming the polynomial hardness of both CDH and the Learning Parity with Noise (LPN) assumption.
