Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-205 | 21st December 2023 22:54

(Inefficient Prover) ZAPs from Hard-to-Invert Functions


Authors: Marshall Ball, Dana Dachman-Soled
Publication: 22nd December 2023 11:02
Downloads: 85


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

ISSN 1433-8092 | Imprint