**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 frameworkconstruct 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.