A ZAP is a witness-indistinguishable two-message public-coin interactive proof with the following simple structure: the verifier sends a uniformly random string, the prover responds, and the verifier decides in polynomial time whether to accept or reject. We show that one-way functions imply the existence of ZAPs for NP where the prover runs in time \(2^{n^\epsilon }\) for arbitrarily small constant \(\epsilon >0\) (where n denotes the length on the NP instance). Moreover, it suffices to simply assume there exist functions that are hard to invert, but valid image/preimage pairs can be efficiently recognized. Such functions need not be efficiently computable and hence are not known to imply even one-way functions. Prior to this work such ZAPs were only known from one-way permutations [Ball et al., CRYPTO’20]. Ghosal et al. [STOC’23] recently showed a separation of \(\textsf{P}\) and \(\textsf{NP}\cap \textsf{coNP}\) assuming \(\textsf{UP}\not \subseteq \textsf{RP}\) in the random oracle model. As an application of our main result, we show that one-way functions (in addition to other complexity theoretic assumptions) imply a non-uniform variant of this separation in the plain model.