CryptoDB
(Inefficient Prover) ZAPs from Hard-to-Invert Functions
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2025 |
| Abstract: | 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 P and NP intersect coNP in the random oracle model (assuming UP is not contained in RP). 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. |
BibTeX
@inproceedings{eurocrypt-2025-35111,
title={(Inefficient Prover) ZAPs from Hard-to-Invert Functions},
publisher={Springer-Verlag},
author={Marshall Ball and Dana Dachman-Soled},
year=2025
}