Paper 2023/164

Input Transformation Based Zero-Knowledge Argument System for Arbitrary Circuits

Abstract

We introduce a new efficient, transparent, interactive zero-knowledge argument system that is based on the new input transformation concept that we will introduce in this paper. The core of this concept is a mechanism that converts input parameters into a format that can be processed directly by the circuit so that the circuit output can be verified through direct computation of the circuit.  In the default setting, our protocol only requires the prover to use vector commitment to commit to the square root of the polynomial degree ($\sqrt{p_d}$) the circuit generates. Our benchmark result shows our approach can significantly improve both prover runtime and verifier runtime performance over state-of-the-art by over one order of magnitude while keeping the communication cost comparable with that of the state-of-the-art.  Our approach also allows our protocol to be memory-efficient without forcing it to require a designated verifier. The theoretical memory cost of our protocol is  $O(b)$, where $b$ is a parameter set by the user. Lowering the $b$ value will result in better prover runtime performance at the expense of higher communication cost. Our benchmark result shows the prover speed of our protocol is at least comparable to that of state-of-the-art VOLE-based protocols, but with much smaller proof size and the significant advantage of being non-interactive at the same time.

Note: major revision