Cryptology ePrint Archive: Report 2022/170

gOTzilla: Efficient Disjunctive Zero-Knowledge Proofs from MPC in the Head, with Application to Proofs of Assets in Cryptocurrencies

Foteini Baldimtsi and Panagiotis Chatzigiannis and S. Dov Gordon and Phi Hung Le and Daniel McVicker

Abstract: We present gOTzilla, a protocol for interactive zero-knowledge proofs for large disjunctive statements of the following format: given publicly known circuit $C$, and set of values $Y = \{y_1, \ldots, y_n\}$, prove knowledge of a witness $x$ such that $C(x) = y_1 \lor C(x) = y_2 \lor \cdots \lor C(x) = y_n$. These type of statements are extremely important for the proof of assets (PoA) problem in cryptocurrencies where a prover wants to prove the knowledge of a secret key $sk$ that associates with the hash of a public key $H(pk)$ posted on the ledger.

gOTzilla is based on the MPC in the head (MPCitH) paradigm and is based on the observation that if we restructure the proof statement to an equivalent of proving knowledge of $(x,y)$ such that $(C(x) = y) \land (y = y_1 \lor \cdots \lor y = y_n))$, then we can reduce the disjunction of equalities to 1-out-of-N oblivious transfer (OT). We additionally provide a concrete, efficient extension of our protocol for the case where $C$ combines algebraic and non-algebraic statements (which is the case in the PoA application). We achieve an asymptotic communication cost of $O(\log n)$ plus the proof size of the underlying MPCitH protocol. While related work has similar asymptotic complexity, our approach results in concrete performance improvements. We implement our protocol and provide benchmarks. Concretely, for a set of size 1 million entries, the total run-time of our protocol is 14.89 seconds using 48 threads, with 6.18 MB total communication, which is about 4x faster compared to the state of the art when considering a disjunctive statement with algebraic and non-algebraic elements.

Category / Keywords: applications / secure multiparty computation, oblivious transfer, zero knowledge, disjunctive proofs, privacy, auditability, cryptocurrencies

Date: received 14 Feb 2022, last revised 17 Feb 2022

Contact author: foteini at gmu edu, pchatzig at gmu edu, gordon at gmu edu, ple13 at gmu edu, dmcvicke at gmu edu

Available format(s): PDF | BibTeX Citation

Version: 20220220:200905 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]