Cryptology ePrint Archive: Report 2021/1450

Efficient Zero-Knowledge Argument in Discrete Logarithm Setting: Sublogarithmic Proof or Sublinear Verifier

Hyeonbum Lee and Jae Hong Seo

Abstract: We propose two zero-knowledge arguments for arithmetic circuits with fan-in 2 gates in the uniform random string model. Our first protocol features $O(\sqrt{\log_2 N})$ communication and round complexities and $O(N)$ computational complexity for the verifier, where $N$ is the size of the circuit. Our second protocol features $O(\log_2N)$ communication and $O(\sqrt{N})$ computational complexity for the verifier. We prove the soundness of our arguments under the discrete logarithm assumption or the double pairing assumption, which is at least as reliable as the decisional Diffie-Hellman assumption. The main ingredient of our arguments is two different generalizations of B\"unz et al.'s Bulletproofs inner-product argument (IEEE S\&P 2018) that convinces a verifier of knowledge of two vectors satisfying an inner-product relation. For a protocol with sublogarithmic communication, we devise a novel method to aggregate multiple arguments for bilinear operations such as multi-exponentiations, which is essential for reducing communication overheads. For a protocol with a sublinear verifier, we develop a generalization of the discrete logarithm relation assumption, which is essential for reducing verification overhead while keeping the soundness proof solely relying on the discrete logarithm assumption. These techniques are of independent interest.

Category / Keywords: cryptographic protocols / Zero-knowledge argument, Range proof, Circuit satisfiability, Trustless setup

Date: received 28 Oct 2021, last revised 21 Nov 2021

Contact author: leehb3706 at hanyang ac kr, jaehongseo at hanyang ac kr

Available format(s): PDF | BibTeX Citation

Note: Updates (21.11.22) 1. Revise comparison tables - table 1, table 2 2. Unify reference style

Version: 20211121:152716 (All versions of this report)

Short URL: ia.cr/2021/1450


[ Cryptology ePrint archive ]