Paper 2021/1450

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

Sungwook Kim, Hyeonbum Lee, and Jae Hong Seo

Abstract

We propose three zero-knowledge arguments for arithmetic circuit of size $N$. First argument features $O(\sqrt{\log N})$ communication and round complexities and $O(N)$ computational complexity for the verifier. Second argument features $O(\log N)$ communication and $O(\sqrt{N})$ computational complexity for the verifier. Third argument features $O(\log N)$ communication and $O(\sqrt{N}\log N)$ computational complexity for the verifier. Contrary to first and second arguments, third argument is free of reliance on pairing-friendly elliptic curves. The soundness of three arguments is proven under the standard discrete logarithm and/or the double pairing assumption, which is at least as reliable as the decisional Diffie-Hellman assumption.

Note: Updates (21.11.22) Revise comparison tables - table 1, table 22, Unify reference style Updates (22.02.24) Add new protocols and reorganize contents

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
Zero-knowledge argumentCircuit satisfiabilityTrustless setup
Contact author(s)
kim sungwook @ swu ac kr
leehb3706 @ hanyang ac kr
jaehongseo @ hanyang ac kr
History
2022-02-24: last of 4 revisions
2021-10-29: received
See all versions
Short URL
https://ia.cr/2021/1450
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1450,
      author = {Sungwook Kim and Hyeonbum Lee and Jae Hong Seo},
      title = {Efficient Zero-Knowledge Argument in Discrete Logarithm Setting: Sublogarithmic Proof or Sublinear Verifier},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1450},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1450}},
      url = {https://eprint.iacr.org/2021/1450}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.