0
$\begingroup$

I'm looking for an example of a zero-knowledge protocol such that (1) the prover Peggy can demonstrate to the verifier Victor that she has a proof of $P$ (to the usual standards of a zero-knowledge protocol) and (2) $P$ (when formalized in arithmetic) is a strictly $\varPi_n$ statement for some $n \geq 1$ (i.e., $\varPi_n$ but not $\varDelta_n$).

Do such cases exist? In all the examples of zero-knowledge protocols I've been able to find, $P$ is an existential claim (usually $\varSigma_1$): normally Peggy possesses a proof that $\exists x \ \varphi(x)$ in virtue of possessing a proof that $\varphi(a)$ for some $a$.

Improve this question
$\endgroup$
2
  • $\begingroup$ The statement “P is a proof of S in theory T” is $\Delta_0$ $\endgroup$
    – Monroe Eskew
    Commented Jul 12, 2018 at 5:53
  • $\begingroup$ Are you basically asking for the PCP theorem? $\endgroup$
    – none
    Commented Jul 17, 2018 at 7:33

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .