Score:2

What's the meaning of verifier is "ppt" ? and why we need verifier is ppt in Interactive Proof?

nl flag

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

Score:2
et flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.