ZK Research Highlights (September 2023)
zkDL: Efficient Zero-Knowledge Proofs of Deep Learning Training
by Haochen Sun and Hongyang Zhang
present zkDL, an efficient zero-knowledge proof of deep learning training.
At the core of zkDL is zkReLU, a specialized zero-knowledge proof protocol with optimized proving time and proof size for the ReLU activation function
devise a novel construction of an arithmetic circuit from neural networks, reduces proving time and proof sizes by a factor of the network depth.
SwiftRange: A Short and Efficient Zero-Knowledge Range Argument For Confidential Transactions and More
by Nan Wang and Sid Chi-Kin Chau and Dongxi Liu (The 45th IEEE Symposium on Security and Privacy)
propose SwiftRange, a new type of logarithmic-sized zero-knowledge range argument with a transparent setup in the discrete logarithm setting.
Compared with Bulletproofs, has higher computational efficiency and lower round complexity while incurring comparable communication overheads for CT-friendly ranges
Improving logarithmic derivative lookups using GKR
Shahar Papini and Ulrich Haböck
instantiate the Goldwasser-Kalai-Rothblum (GKR) protocol to prove fractional sumchecks as present in lookup arguments based on logarithmic derivatives, with the following impact on the prover cost of logUp (IACR eprint 2022/1530):
When looking up M columns in a single column table, the prover has to commit only to a single extra column
introduce a novel transformation for turning a univariate polynomial commitment scheme into a multilinear one. to prove arbitrary powers of the lexicographic shift over the Boolean hypercube.
Pianist: Scalable zkRollups via Fully Distributed Zero-Knowledge Proofs
Tianyi Liu and Tiancheng Xie and Jiaheng Zhang and Dawn Song and Yupeng Zhang (S&P 2024)
proposing new schemes of fully distributed ZKPs.
improve the efficiency and the scalability of ZKPs using multiple machines, while the communication among the machines is minimal. With our schemes, the ZKP generation can be distributed to multiple participants in a model similar to the mining pools.
Instant Zero Knowledge Proof of Reserve
Xiang Fu
present two zero knowledge protocols that allow one to assert solvency of a financial organization instantly with high throughput.
Succinct Proofs and Linear Algebra
Alex Evans and Guillermo Angeris
show that using some simple abstractions, a number of commonly-used tools used in the construction of succinct proof systems may be viewed as basic consequences of linear algebra over finite fields.
build a toolkit of useful techniques that can be combined to create different protocols.
give a short proof of the security of the FRI protocol.
Cicada: A framework for private non-interactive on-chain auctions and voting
Noemi Glaeser and István András Seres and Michael Zhu and Joseph Bonneau
introduce Cicada, a general framework for using linearly homomorphic time-lock puzzles (HTLPs) to enable provably secure, non-interactive private auction and voting protocols.
instantiate our framework with an efficient new HTLP construction and novel packing techniques that enable succinct ballot correctness proofs independent of the number of candidates.
Naysayer proofs
István András Seres and Noemi Glaeser and Joseph Bonneau
introduces the notion of naysayer proofs.
show that every NP language has constant-size and constant-time naysayer proofs.
show practical constructions for several example proof systems, including FRI polynomial commitments, post-quantum secure digital signatures, and verifiable shuffles.
Zero-Knowledge Systems from MPC-in-the-Head and Oblivious Transfer
Cyprien Delpech de Saint Guilhem and Ehsan Ebrahimi and Barry van Leeuwen (IMA Cryptography and Coding 2023)
presents a novel method to construct zero-knowledge protocols which takes advantage of the unique properties of MPC-in-the-Head and replaces commitments with an oblivious transfer protocol.
The security of the new construction is proven in the Universal Composability framework of security
suitable choices of oblivious transfer protocols are discussed
SLAP: Succinct Lattice-Based Polynomial Commitments from Standard Assumptions
Martin R. Albrecht and Giacomo Fenzi and Oleksandra Lapiha and Ngoc Khanh Nguyen
propose the first lattice-based non-interactive extractable polynomial commitment scheme which achieves polylogarithmic proof size and verifier runtime (in the length of the committed message) under standard assumptions.
a new tree-based commitment scheme, along with an efficient proof of polynomial evaluation inspired by FRI.
Commitments with Efficient Zero-Knowledge Arguments from Subset Sum Problems
Jules Maire and Damien Vergnaud (ESORICS 2023)
present a cryptographic string commitment scheme that is computationally hiding and binding based on (modular) subset sum problems.
Using techniques recently introduced by Feneuil, Maire, Rivain and Vergnaud, this simple commitment scheme enables an efficient zero-knowledge proof of knowledge for committed values as well as proofs showing Boolean relations amongst the committed bits.
Rogue-Instance Security for Batch Knowledge Proofs
Gil Segev and Amit Sharabi and Eylon Yogev (TCC 2023)
propose a new notion of knowledge soundness, denoted rogue-instance security, for interactive and non-interactive batch knowledge proofs.
present a highly-efficient generic construction of a batch proof-of-knowledge applicable to any algebraic Sigma protocols.
On Black-Box Knowledge-Sound Commit-And-Prove SNARKs
Helger Lipmaa (ASIACRYPT 2023)
define and construct a fully algebraic F-position-binding vector commitment scheme VCF.
construct a concretely efficient commit-and-prove zk-SNARK Punic, a version of FANA with an additional VCF commitment to the witness.
zk-SNARKs from Codes with Rank Metrics
Xuan-Thanh Do and Dang-Truong Mac and Quoc-Huy Vu (IMA International Conference on Cryptography and Coding 2023)
propose a code-based zk-SNARK scheme, whose security is based on the rank support learning (RSL) problem, a variant of the random linear code decoding problem in the rank metric.
Sigmabus: Binding Sigmas in Circuits for Fast Curve Operations
George Kadianakis and Mary Maller and Andrija Novakovic
introduces Sigmabus, a technique designed to enhance the efficiency of zero-knowledge circuits by relocating computationally expensive operations outside the circuit.
moving elliptic curve group operations to external computations.
By leveraging Sigma protocols, elliptic curve group operations are proven outside the circuit, while additional constraints are applied to the circuit to ensure correct execution of the Sigma protocol.
Incrementally Verifiable Computation via Rate-1 Batch Arguments
Omer Paneth and Rafael Pass (FOCS 2023)
present a provably secure mergeable delegation construction based on the standard LWE assumption.
obtain a construction of incrementally verifiable computation (IVC) (with polylogarithmic length proofs) for any (unbounded) polynomial number of steps based on LWE
The central building block is rate-1 batch argument (BARG)
On the Security of KZG Commitment for VSS
Atsuki Momose and Sourav Das and Ling Ren (ACM CCS 2023)
point out, however, that the KZG commitment is missing two important properties that are crucial for VSS protocols.
First, the KZG commitment has not been proven to be degree binding in the standard adversary model without idealized group assumptions.
Second, the KZG commitment does not support polynomials with different degrees at once with a single setup.
augment the KZG commitment to address both of these limitations.
scheme is degree-binding in the standard model under the strong Diffie-Hellman (SDH) assumption.
Experimenting with Zero-Knowledge Proofs of Training
Sanjam Garg and Aarushi Goel and Somesh Jha and Saeed Mahloujifar and Mohammad Mahmoody and Guru-Vamsi Policharla and Mingyuan Wang (ACM CCS 2023)
formulate the notion of zero-knowledge proof of training (zkPoT)
propose the idea of combining techniques from MPC-in-the-head and zkSNARKs literature to strike an appropriate trade-off between proof size and proof computation time.
instantiate this idea and propose a concretely efficient, novel zkPoT protocol for logistic regression.
Modular Sumcheck Proofs with Applications to Machine Learning and Image Processing
David Balbás and Dario Fiore and Maria Isabel González Vasco and Damien Robissout and Claudio Soriente (ACM CCS 2023)
introducing a modular framework for verifiable computation of sequential operations.
The main tool is a new information-theoretic primitive called Verifiable Evaluation Scheme on Fingerprinted Data (VE) that captures the properties of diverse sumcheck-based interactive proofs, including the well-established GKR protocol.
propose a novel VE for convolution operations that can handle multiple input-output channels and batching,
use it in our framework to build proofs for (convolutional) neural networks and image processing.
An optimization of the addition gate count in Plonkish circuits
Steve Thakur
generalize Plonk's ([GWC19]) permutation argument by replacing permutations with (possibly non-injective) self-maps of an interval.
use this succinct argument to obtain a protocol for weighted sums on committed vectors, which, in turn, allows us to eliminate the intermediate gates arising from high fan-in additions in Plonkish circuits.
Recursion over Public-Coin Interactive Proof Systems; Faster Hash Verification
Alexandre Belling and Azam Soleimanian and Olivier Bégassat
present a recursive technique that can improve the efficiency of the prover by an order of magnitude compared to proving MiMC hashes with a Groth16 proof.
use GKR to prove the integrity of hash computations and embed the GKR verifier inside a SNARK circuit.
ZKROWNN: Zero Knowledge Right of Ownership for Neural Networks
Nojan Sheybani Zahra Ghodsi Ritvik Kapila Farinaz Koushanfar
present ZKROWNN, the first automated end-to-end framework utilizing Zero-Knowledge Proofs (ZKP) that enable an entity to validate their ownership of a model, while preserving the privacy of the watermarks.