0
$\begingroup$

I know that an interactive proof system $(P,V)$ is a pair of interactive machines for a language $L$ if $V$ is polynomial-time and the following two conditions hold:

1) Completeness: For every $x \in L$, $$\Pr [\langle P,V \rangle (x) = 1] \geq \frac{2}{3}$$

2) Soundness: For every $x \not\in L$ and every interactive machine $B$, $$\Pr [\langle B,V \rangle (x) = 1] \leq \frac{1}{3}$$

Actually, in an interactive proof system $(P,V)$ for language $L$, $P$ proves the fact whether $x \in L$ to $V$.

However, for a general pair of interactive machines, what is the meaning of the common input? Can we construct a system $\langle A,B \rangle$ such that $A$ wants to send $x$ to $B$ and prove that $x$ is not malicious before sending it. Or can we construct other communication systems instead of a proof system?

$\endgroup$
2
$\begingroup$

Interactive Turing Machines are used to model real-world parties that interact and perform local computations using some algorithms. So, why would they not have a common input? The common input simply capture the fact that both parties can start a protocol knowing some common value, which perfectly makes sense in any real-life application. In the definition of interactive proof system, we want to abstract out what it means to interactively prove a statement; so, the natural approach is to let both parties initially know the statement, and ask for one of the parties to prove it to its opponent. The question of how the statement became known to the parties is irrelevant to the question of building an interactive proof.

That being said, yes, you can trivially let one of the parties send the statement to the other party, and then prove its truth with an interactive proof system. Depending of the specific interactive proof system you consider, some might not require knowing the actual statement during the interaction (although it will be clearly needed by the verifier when executing his verification algorithm on the transcript). In this case, the proof could indeed be performed first, and the actual statement be sent later. But that's not the case of all existing proof systems.

$\endgroup$
  • $\begingroup$ I still feel a little confuse about the "interactive proof system" I mentioned. You mean that "the proof could indeed be performed first, and the actual statement be sent later". But there are not any specific schemes or examples that show how to achieve it? It requires that the common input can be used to prove that the statement is "not malicious" or "valid" before it is sent, right? $\endgroup$ – TeamBright Jul 30 '18 at 14:49
  • $\begingroup$ What I meant is that the common input is the statement in general. And with some proof system, you can perform the entire proof without knowing the specific statement (in other terms, executing the proof require knowing the target language L, but not the specific word x whose membership to L must be proven), and only send the statement x afterward. But the verifier will not be able to verify that the proof is true before even receiving x (that would make no sense); rather, he will be able to check the proof as soon as he receives the statement. $\endgroup$ – Geoffroy Couteau Jul 30 '18 at 17:29
  • $\begingroup$ You say "But the verifier will not be able to verify that the proof is true before even receiving $x$ (that would make no sense); rather, he will be able to check the proof as soon as he receives the statement." So, without loss of generality, we always assume that the common input contains $x$, right? The verifier always needs the statement when he checks the proof, no matter how the verifier gets the statement. $\endgroup$ – TeamBright Aug 1 '18 at 5:42

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.