2
$\begingroup$

I have been studying Zero Knowledge Proof. I found the Definition of Interactive Proof says that Verifier is ppt. And I only found in PP (Complexity) Wikipedia says that ppt:

Turing machines that are polynomially-bound and probabilistic are characterized as PPT, which stands for probabilistic polynomial-time machines.[2] This characterization of Turing machines does not require a bounded error probability. Hence, PP is the complexity class containing all problems solvable by a PPT machine with an error probability of less than 1/2.

Still very confusing about the PPT, what's the full name of PPT? we do we need the verifier to be PPT for interactive Proof?

Resource from: Zero Knowledge Proofs CS276: Cryptography, UC Berkeley

$\endgroup$

1 Answer 1

2
$\begingroup$

PPT is Probabilistic Polynomial Time Algorithm.

A deterministic verifier will always produce the same output/reply for any input.

Let's take an interactive sequence.

Prover sends $p_1$.

Verifier replies with $f(p_1) = v_1$

Prover replies back with $g(v_1) = p_2$

The function $f$ which the verifier uses is deterministic. i.e. for a particular input, it always replies with the same reply.

In a probabilistic verifier, $f$ also has randomisation as input. i.e. $g$ takes 2 inputs $f(v_i, r)$ where $r$ is a random value. Hence $f$ is not deterministic, and the verifier is a probabilistic verifier. And if $f$ runs in polynomial time, the verifier is a Probabilistic Polynomial Time (PPT) verifier.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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