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].