Paper 2024/800 Original: eprint.iacr.org/2024/800 ↗
A Note on Zero-Knowledge for NP and One-Way Functions
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.
- History
- 2025-06-12: last updated
- 2024-05-23: published
- Short URL
- https://ia.cr/2024/800
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}