1
$\begingroup$

Everywhere I look in PCP literature I find the soundness error advertised as $1/2$. For example, here on page 17 it says (regarding soundness)

SCI uses 14 repetitions to reduce the probability of error to $error = 1/2$

and then

the security analysis guarantees that this verdict is correct with probability $1 − error$

This implies that even after additional tests, soundness is no less than $1/2$. I interpret this and similar statements in other papers to mean that on average an adversarial prover's false proof will be accepted half the time. This would be unacceptable for most applications (such as computational integrity). I must be misunderstanding the context for these statements.

It seems that in order to minimize the error below $1/2$, the verification process (and maybe even the proving process) must be repeated $k$ times for a soundness error of $2^{-k}$.

$\endgroup$
1
$\begingroup$

In the full version of Delegating Computation: Interactive Proofs for Muggles on the bottom of page 18 it says that it is well known that interactive protocols with input size $n$, completeness $2/3$, and soundness $1/3$, are equivalent to interactive protocols with completeness $1-2^{-n}$ and soundness $2^{-n}$. Though soundness $1/3$ differs from $1/2$ mentioned in the question, a similar equivalence likely exists. Apparently the equivalence is proven somewhere in Goldreich's lengthy paper Modern cryptography, probabilistic proofs and pseudorandomness, volume 17 of Algorithms and Combinatorics.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.