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

by Yanyi Liu, Noam Mazor, and Rafael Pass.

#### Oded's comments

The introduction provides an excellent overview of the actual contents of these recent developments.

As stated in its 2nd and 3rd paragraphs, results from the 1990s have established that
*if ZK contains problems that are infinitely often hard (wrt non-uniform circuits),
then aux-input one-way functions (ai-OWF) exist*,
whereas average-case hardness of ZK implies standard OWF.
This leaves a gap between worst-case and average-case (resp., ai-OWF and OWF),
which can be closed *if the hard set in ZK is a specific one in NP*.

Note that the restriction to NP can be justified by the fact that
OWF imply that NP is in ZK.

In particular, the latter result implies that OWF implies the
existence of sets in NP that are both average-case hard and in ZK.
The aforementioned recent result asserts the converse;
that is, there exists a set in NP such that
if it is both average-case hard and in ZK, then OWF exists.
Hence, combining both directions we get that
there is a set $S$ in NP such that OWF exists
if and only if $S$ is both average-case hard and in ZK.

#### The original abstract

We present a simple alternative exposition of the the recent result of Hirahara and Nanashima (STOC24)
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.

See ECCC TR24-095.

Back to
list of Oded's choices.