International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Sungwook Kim , Seoul Women's University
Hyeonbum Lee , Hanyang University
Jae Hong Seo , Hanyang University
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2022
Abstract: We propose three interactive zero-knowledge arguments for arithmetic circuit of size N in the common random string model, which can be converted to be non-interactive by Fiat-Shamir heuristics in the random oracle model. First argument features O( log N ) communication and round complexities and O(N) computational complexity for the verifier. Second argument features O(log N ) communication and O( N ) computational complexity for the verifier. Third argument features O(log N ) communication and O( N log N ) computational complexity for the verifier. Contrary to first and second arguments, the 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.
Video from ASIACRYPT 2022
BibTeX
@inproceedings{asiacrypt-2022-32541,
  title={Efficient Zero-Knowledge Arguments in Discrete Logarithm Setting: Sublogarithmic Proof or Sublinear Verifier},
  publisher={Springer-Verlag},
  author={Sungwook Kim and Hyeonbum Lee and Jae Hong Seo},
  year=2022
}