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: ia.cr/2022/170