International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Alexandros Zacharakis

Publications

Year
Venue
Title
2021
TCC
Fully-succinct Publicly Verifiable Delegation from Constant-Size Assumptions 📺
Alonso González Alexandros Zacharakis
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 final delegation scheme.
2020
PKC
Updateable Inner Product Argument with Logarithmic Verifier and Applications 📺
Vanesa Daza Carla Ràfols Alexandros Zacharakis
We propose an improvement for the inner product argument of Bootle et al. (EUROCRYPT’16). The new argument replaces the unstructured common reference string (the commitment key) by a structured one. We give two instantiations of this argument, for two different distributions of the CRS. In the designated verifier setting, this structure can be used to reduce verification from linear to logarithmic in the circuit size. The argument can be compiled to the publicly verifiable setting in asymmetric bilinear groups. The new common reference string can easily be updateable. The argument can be directly used to improve verification of Bulletproofs range proofs (IEEE SP’18). On the other hand, to use the improved argument to prove circuit satisfiability with logarithmic verification, we adapt recent techniques from Sonic (ACM CCS’19) to work with the new common reference string. The resulting argument is secure under standard assumptions (in the Random Oracle Model), in contrast with Sonic and recent works that improve its efficiency (Plonk, Marlin, AuroraLight), which, apart from the Random Oracle Model, need either the Algebraic Group Model or Knowledge Type assumptions.