One-Way Functions and Zero Knowledge

The fundamental theorem of Goldreich, Micali, and Wigderson (J. ACM 1991) shows that the existence of a one-way function is sufficient for constructing computational zero knowledge ( CZK ) proofs for all languages in NP . We prove its converse, thereby establishing characterizations of one-way functions based on the worst-case complexities of zero knowledge. Specifically, we prove that the following are equivalent: - A one-way function exists. - NP ⊆ CZK and NP is hard in the worst case. - CZK is hard in the worst case and the problem GapMCSP of approximating circuit complexity is in CZK . The characterization above also holds for statistical and computational zero-knowledge argument systems. We further extend this characterization to a proof system with knowledge complexity O (log n ). In particular, we show that the existence of a one-way function is characterized by the worst-case hardness of CZK if GapMCSP has a proof system with knowledge complexity O (log n ). We complement this result by showing that NP admits an interactive proof system with knowledge complexity ω(log n ) under the existence of an exponentially hard auxiliary-input one-way function (which is a weaker primitive than an exponentially hard one-way function). We also characterize the existence of a robustly-often nonuniformly computable one-way function by the nondeterministic hardness of CZK under the weak assumption that PSPACE ⊈ AM . We present two applications of our results. First, we simplify the proof of the recent characterization of a one-way function by NP -hardness of a meta-computational problem and the worst-case hardness of NP given by Hirahara (STOC’23). Second, we show that if NP has a laconic zero-knowledge argument system, then there exists a public-key encryption scheme whose security can be based on the worst-case hardness of NP . This improves previous results which assume the existence of an indistinguishable obfuscation.

Authors

• Shuichi Hirahara
• Mikito Nanashima

Keywords

• interactive proof
• knowledge complexity
• one-way functions