Paper 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.
Note: Updates (21.11.22) 1. Revise comparison tables - table 1, table 2 2. Unify reference style
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- Zero-knowledge argumentRange proofCircuit satisfiabilityTrustless setup
- Contact author(s)
- leehb3706 @ hanyang ac kr,jaehongseo @ hanyang ac kr
- History
- 2022-10-01: last of 6 revisions
- 2021-10-29: received
- See all versions
- Short URL
- https://ia.cr/2021/1450
- License
-
CC BY