Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR24-095 | 12th June 2025 08:46

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

RSS-Feed




Revision #2
Authors: Yanyi Liu, Noam Mazor, Rafael Pass
Accepted on: 12th June 2025 08:46
Downloads: 8
Keywords: 


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.

Indeed, using our modular approach, we can directly extend the result to hold also in the uniform setting. Additionally, we show that the same result holds for (imperfect) iO for 3CNF, or Witness Encryption for NP, solving an open problem from Komargodski et al (FOCS '14).


Revision #1 to TR24-095 | 6th September 2024 15:02

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





Revision #1
Authors: Yanyi Liu, Noam Mazor, Rafael Pass
Accepted on: 6th September 2024 15:02
Downloads: 163
Keywords: 


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.


Paper:

TR24-095 | 23rd May 2024 15:43

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





TR24-095
Authors: Yanyi Liu, Noam Mazor, Rafael Pass
Publication: 27th May 2024 00:31
Downloads: 569
Keywords: 


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.



ISSN 1433-8092 | Imprint