HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates
Binyi Chen Benedikt Bünz Dan Boneh Zhenfei Zhang
present HyperPlonk, an adaptation of Plonk to the boolean hypercube, using multilinear polynomial commitments.
avoids the need for an FFT during proof generation.
supports custom gates of much higher degree than Plonk.
revisit two elegant multilinear polynomial commitments constructions: one from Orion and one from Virgo.
show how to reduce the Orion opening proof size to less than 10 KB
show how to make the Virgo FRI-based opening proof simpler and shorter
Succinct Vector, Polynomial, and Functional Commitments from Lattices
Hoeteck Wee David J. Wu
introduce a new framework for constructing non-interactive lattice-based vector commitments
A simple instantiation yields a new vector commitment scheme from the SIS assumption that supports private openings and large messages.
show how to use our framework to obtain the first succinct functional commitment scheme that supports openings with respect to arbitrary bounded-depth Boolean circuits.
security is based on a new falsifiable family of "basis-augmented" SIS assumptions (BASIS)
Speed-Stacking: Fast Sublinear Zero-Knowledge Proofs for Disjunctions
Aarushi Goel Mathias Hall-Andersen Gabriel Kaptchuk Nicholas Spooner
propose a new compiler that, when applied to sublinear-sized proofs, can result in sublinear-size disjunctive zero-knowledge with sublinear proving times.
key observation is that simulation in sublinear-size zero-knowledge proof systems can be much faster than the honest prover.
applying to two classes of protocols: interactive oracle proofs, specifically Aurora and Fractal, and folding arguments, specifically Compressed Σ-protocols and Bulletproofs.
Spartan and Bulletproofs are Simulation-Extractable (for free!)
Quang Dao Paul Grubbs
prove that two transparent, discrete-log-based zkSNARKs, Spartan and Bulletproofs, are simulation-extractable (𝖲𝖨𝖬-𝖤𝖷𝖳) in the random oracle model if the discrete logarithm assumption holds. show that 𝖲𝖨𝖬-𝖤𝖷𝖳 is, surprisingly, “for free” with these schemes.
develop a generalization of the tree-builder extraction theorem of Attema et al. (TCC’22).
Supersingular Curves You can Trust
Andrea Basso Giulio Codogni Deirdre Connolly Luca De Feo Tako Boris Fouotsa Guido Maria Lido Travis Morrison Lorenz Panny Sikhar Patranabis Benjamin Wesolowski
first statistically zero-knowledge proof of isogeny knowledge that is compatible with any base field.
introduce isogeny graphs with Borel level structure and prove they have the Ramanujan property.
analyze the security of a distributed trusted-setup protocol based on our ZK proof in the simplified universal composability framework.
On Valiant’s Conjecture: Impossibility of Incrementally Verifiable Computation from Random Oracles
Jesper Buus Nielsen Mathias Hall-Andersen
prove that under some mild extra assumptions on the proof system the Valiant’s conjecture is true: the standard random-oracle model does not allow incrementally verifiable computation without making computational assumptions.
Two extra assumptions under which we can prove the conjecture are
1) the proof system is also zero-knowledge or
2) when the proof system makes a query to its random oracle it can know with non-negligible probability whether the query is fresh or was made by the proof system earlier in the construction of the proof.
Witness-Succinct Universally-Composable SNARKs
Chaya Ganesh Yashvanth Kondi Claudio Orlandi Mahak Pancholi Akira Takahashi Daniel Tschudi
provide a compiler lifting any simulation-extractable NIZKAoK into a UC-secure one in the global random oracle model, importantly, while preserving the same level of witness succinctness.
Combining this with existing zkSNARKs achieve first zkSNARKs simultaneously achieving UC-security and constant sized proofs.
SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption
Yael Tauman Kalai Alex Lombardi Vinod Vaikuntanathan
construct SNARGs for bounded-depth computations assuming that the decisional Diffie-Hellman (DDH) problem is sub-exponentially hard.
showing how to instantiate the Fiat-Shamir heuristic, under DDH, for a variant of the Goldwasser-Kalai-Rothblum (GKR) interactive proof system.
giving a circuit family for finding roots of cubic polynomials over a special family of characteristic 2 fields
constructing a variant of the GKR protocol whose invocations of the sumcheck protocol only involve degree 3 polynomials over said fields.
show the existence of (sub-exponentially) computationally hard problems in the complexity class PPAD, assuming the sub-exponential hardness of DDH.
Proof-Carrying Data From Arithmetized Random Oracles
Megan Chen Alessandro Chiesa Tom Gur Jack O'Connor Nicholas Spooner
introduce a new model: the arithmetized random oracle model (AROM).
provide a plausible standard-model (software-only) instantiation of the AROM, and construct PCD in the AROM, given only a standard-model collision-resistant hash function.
construct an accumulation scheme for the AROM.
give an efficient “lazy sampling” algorithm (an emulator) for the ARO up to some error.
to prove the security of cryptographic constructs in the AROM and that zkSNARKs in the ROM also satisfy zero-knowledge in the AROM.