Skip to main content
added 7 characters in body
Source Link

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

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$ (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$.

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

Source Link

Example of a zero-knowledge protocol for a strictly Pi_n sentence?

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$ (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$.