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. We also remark that the same result hold for (imperfect) iO for 3CNF, or Witness Encryption for NP.

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-09-06: revised; 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},
      url = {https://eprint.iacr.org/2024/800}
}