A Note on Zero-Knowledge for NP and One-Way Functions

Yanyi Liu; Noam Mazor; Rafael Pass

Paper 2024/800

A Note on Zero-Knowledge for NP and One-Way Functions

Yanyi Liu, Cornell Tech

Noam Mazor, Tel Aviv University

Rafael Pass, Tel Aviv University & Cornell Tech

Abstract

We present a simple alternative exposition of the the recent result of Hirahara and Nanashima (STOC’24) showing that one-way functions exist if (1) every language in NP has a zero-knowledge proof/argument and (2) ZKA contains non-trivial languages. Our presentation does not rely on meta-complexity and we hope it may be useful for didactic purposes.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: one-way function zero knowledge
Contact author(s): yl2866 @ cornell edu
noammaz @ gmail com
rafaelp @ tau ac il
History: 2024-05-24: approved; 2024-05-23: received; See all versions
Short URL: https://ia.cr/2024/800
License: CC BY

BibTeX

@misc{cryptoeprint:2024/800,
      author = {Yanyi Liu and Noam Mazor and Rafael Pass},
      title = {A Note on Zero-Knowledge for {NP} and One-Way Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2024/800},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/800}},
      url = {https://eprint.iacr.org/2024/800}
}