<p>Consider this definition:</p>
<p>Interaction of Deterministic Functions: Let <span class="math-container">$f,g:\{0,1\}^* \to \{0,1\}^*$</span>  be functions. A <span class="math-container">$k-$</span>round interaction of <span class="math-container">$f$</span> and <span class="math-container">$g$</span> on input <span class="math-container">$x \in \{0,1\}^*$</span>, denoted by <span class="math-container">$\langle f,g\rangle (x)$</span> is the sequence of the following strings <span class="math-container">$a_1, \ldots , a_k \in \{0,1\}^*$</span> defined as follows:</p>
<p><span class="math-container">$$\begin{align*}
a_1&amp;=f(x)\\
a_2&amp;=g(x,a_1)\\
&amp;\vdots\\
a_{2i+1} &amp;= f(x, a_1, \ldots, a_{2i})\\
a_{2i+2} &amp;= g(x, a_1, \ldots, a_{2i+1})
\end{align*}$$</span></p>
<p>I have trouble wrapping my head around how the  Prover and the Verifier actually communicate in deterministic  interactive proof system. In particular I am interested in these topics:</p>
<ol>
<li>Does it matter who starts the interaction? I cannot think of a scenario where the interaction starts with the verifier. If there exists such a scenario (which I am sure this is the case) then what's the message <span class="math-container">$V$</span> sends to <span class="math-container">$P$</span>?</li>
<li>I can understand that the messages of <span class="math-container">$P$</span> contain a certificate that a statement <span class="math-container">$x$</span> belongs to a language <span class="math-container">$L$</span>. What's the content of <span class="math-container">$V$</span>'s messages?</li>
</ol>
<p>For example consider the language <span class="math-container">$L=\{x| x \text{ is composite}\}$</span>. How would a 2-round deterministic interactive proof system work for a statement <span class="math-container">$x$</span> e.g. <span class="math-container">$x=15$</span> between the prover <span class="math-container">$P$</span> and the verifier <span class="math-container">$V$</span>? I can understand that the prover can provide one factor at the first round e.g. <span class="math-container">$3$</span> and another factor at the second round e.g. <span class="math-container">$5$</span>. In that case what would the message <span class="math-container">$V(x)=a_1$</span> (specified in the definition above) contain?</p>

CC BY-SA 4.0
2024-12-05T10:48:21.660Z
It’s unclear what you want. If you ask about the general definition, the Verifier is free to send *anything* they like. If you ask about practical examples where that would be useful, there are not any: since you seem to have copied the definition from Arora and Barak, read Lemma 8.4 just below the definition (any deterministic IP is equivalent to a one-round protocol where the only message is sent by P). If you want to see examples how interaction can be actually useful, keep reading the section on randomized protocols.
Emil Jeřábek
CC BY-SA 4.0
2024-12-05T11:46:07.630Z
This was actually taken from some lecture notes. Thanks for referencing the original textbook, I'll have a look at it.
gk282828
CC BY-SA 4.0
2024-12-05T12:12:21.400Z
Oh, I see. The definition follows almost literally the one given in the book, hence I assumed that’s where you took it from. But anyway, it should help you to read the discussion there. In any case, deterministic IP are just a toy model whose only value is as a didactic step towards randomized IP.
Emil Jeřábek
<interactive-proofs>
In an deterministic interactive proof system what kind of messages does the verifier send to the prover?
gk282828
# In an deterministic interactive proof system what kind of messages does the verifier send to the prover?

(Asked by: username_0 on 2024-12-05)

Consider this definition:

Interaction of Deterministic Functions: Let $f,g:\{0,1\}^\* \to \{0,1\}^\*$ be functions. A $k-$round interaction of $f$ and $g$ on input $x \in \{0,1\}^\*$, denoted by $\langle f,g\rangle (x)$ is the sequence of the following strings $a\_1, \ldots , a\_k \in \{0,1\}^\*$ defined as follows:

$$\begin{align\*}
a\_1&=f(x)\\
a\_2&=g(x,a\_1)\\
&\vdots\\
a\_{2i+1} &= f(x, a\_1, \ldots, a\_{2i})\\
a\_{2i+2} &= g(x, a\_1, \ldots, a\_{2i+1})
\end{align\*}$$

I have trouble wrapping my head around how the Prover and the Verifier actually communicate in deterministic interactive proof system. In particular I am interested in these topics:

1. Does it matter who starts the interaction? I cannot think of a scenario where the interaction starts with the verifier. If there exists such a scenario (which I am sure this is the case) then what's the message $V$ sends to $P$?
2. I can understand that the messages of $P$ contain a certificate that a statement $x$ belongs to a language $L$. What's the content of $V$'s messages?

For example consider the language $L=\{x| x \text{ is composite}\}$. How would a 2-round deterministic interactive proof system work for a statement $x$ e.g. $x=15$ between the prover $P$ and the verifier $V$? I can understand that the prover can provide one factor at the first round e.g. $3$ and another factor at the second round e.g. $5$. In that case what would the message $V(x)=a\_1$ (specified in the definition above) contain?

**Tags:** interactive-proofs

> **Comments:**
> **username_1**: It’s unclear what you want. If you ask about the general definition, the Verifier is free to send *anything* they like. If you ask about practical examples where that would be useful, there are not any: since you seem to have copied the definition from Arora and Barak, read Lemma 8.4 just below the definition (any deterministic IP is equivalent to a one-round protocol where the only message is sent by P). If you want to see examples how interaction can be actually useful, keep reading the section on randomized protocols.  
> **username_0**: This was actually taken from some lecture notes. Thanks for referencing the original textbook, I'll have a look at it.  
> **username_1**: Oh, I see. The definition follows almost literally the one given in the book, hence I assumed that’s where you took it from. But anyway, it should help you to read the discussion there. In any case, deterministic IP are just a toy model whose only value is as a didactic step towards randomized IP.  

---

## 0 answers

