You are looking at a specific version 20210525:192950 of this paper. See the latest version.

Paper 2021/353

Fully-succinct Publicly Verifiable Delegation from Constant Size Assumptions

Alonso González and Alexandros Zacharakis

Abstract

We construct a publicly verifiable, non-interactive delegation scheme for any polynomial size arithmetic circuit with proof-size and verification complexity comparable to those of pairing based zk-SNARKS. Concretely, the proof consists of $O(1)$ group elements and verification requires $O(1)$ pairings and $n$ group exponentiations, where $n$ is the size of the input. While known SNARK-based constructions rely on non-falsifiable assumptions, our construction can be proven sound under any constant size ($k\geq 2$) $k$-Matrix Diffie-Hellman ($k$-MDDH) assumption. However, the size of the reference string as well as the prover's complexity are quadratic in the size of the circuit. This result demonstrates that we can construct delegation from very simple and well-understood assumptions. We consider this work a first step towards achieving practical delegation from standard, falsifiable assumptions. Our main technical contributions are first, the introduction and construction of what we call "no-signaling, somewhere statistically binding commitment schemes". These commitments are extractable for any small part $x_S$ of an opening $x$, where $S\subseteq [n]$ is of size at most $K$. Here $n$ is the dimension of $x$ and $x_S=(x_i)_{i\in S}$. Importantly, for any $S'\subseteq S$, extracting $x_{S'}$ can be done independently of $S\setminus S'$. Second, we use of these commitments to construct more efficient "quasi-arguments"' with no-signaling extraction, introduced by Paneth and Rothblum (TCC 17). These arguments allow extracting parts of the witness of a statement and checking it against some local constraints without revealing which part is checked. We construct pairing-based quasi arguments for linear and quadratic constraints and combine them with the low-depth delegation result of Gonzáles et. al. (Asiacrypt 19) to construct the delegation scheme. Finally, we note that our delegation construction can be turned into a SNARK for NP with similar efficiency but using "shorter" non-falsifiable assumptions than the state of the art. Additionally, using the techniques of Katsumata et al. (Crypto 2019 and Eurocrypt 2020) we can build a compact NIZK argument for polynomial size arithmetic circuits with proof size linear in the size of the witness, while the state of the art has proof size linear in the size of the circuit.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
DelegationSuccinct ArgumentsNon-Interactive Zero-Knowledge
Contact author(s)
alonso gonzalez @ ens-lyon fr
alexandros zacharakis @ upf edu
History
2021-09-17: last of 3 revisions
2021-03-18: received
See all versions
Short URL
https://ia.cr/2021/353
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.