Paper 2021/353
Fullysuccinct Publicly Verifiable Delegation from ConstantSize Assumptions
Alonso González and Alexandros Zacharakis
Abstract
We construct a publicly verifiable, noninteractive delegation scheme for any polynomial size arithmetic circuit with proofsize and verification complexity comparable to those of pairing based zkSNARKS. 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 SNARKbased constructions rely on nonfalsifiable assumptions, our construction can be proven sound under any constant size ($k\geq 2$) $k$Matrix DiffieHellman ($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 wellunderstood 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 "nosignaling, 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 "quasiarguments"' with nosignaling 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 pairingbased quasi arguments for linear and quadratic constraints and combine them with the lowdepth delegation result of Gonzáles et. al. (Asiacrypt 19) to construct the final delegation scheme.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in TCC 2021
 Keywords
 DelegationSuccinct ArgumentsNonInteractive ZeroKnowledge
 Contact author(s)

alonso gonzalez @ toposware com
alexandros zacharakis @ upf edu  History
 20210917: last of 3 revisions
 20210318: received
 See all versions
 Short URL
 https://ia.cr/2021/353
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/353, author = {Alonso González and Alexandros Zacharakis}, title = {Fullysuccinct Publicly Verifiable Delegation from ConstantSize Assumptions}, howpublished = {Cryptology ePrint Archive, Paper 2021/353}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/353}}, url = {https://eprint.iacr.org/2021/353} }