3
$\begingroup$

I am reading the Wikipedia page for Interactive proof systems and am having trouble understand the notation in the definition of soundness, many of which is left unspecified.

Given a formal language of strings $L$, a verifier $\mathcal{V}$ for this language satisfies the soundness property if for every prover $(\tilde{\mathcal{P}})$ and every $y \notin \mathcal{L}$,

$$ \operatorname{Pr}[(\bot,(\text{accept})) \leftarrow (\tilde{\mathcal{P}})(y) \leftrightarrow (\mathcal{V})(y)] < \epsilon $$

for some small $\epsilon \ll 1$. What is meant by the use of $\leftarrow$ and $\leftrightarrow$, as well as $(\bot,(\text{accept}))$? I would appreciate if someone could answer this or point me to a reference that uses (and defines) the same notation.

$\endgroup$

2 Answers 2

2
$\begingroup$

This notation is pretty common for interactive protocols (but it can vary from paper to paper). I believe:

  • $\tilde{\mathcal{P}}(y)\leftrightarrow\mathcal{V}(y)$ denotes that $\tilde{\mathcal{P}}$ and $\mathcal{V}$ are interactive machines involved in an interactive protocol with common input the statement $y$ (an alternative is to use $\langle\tilde{\mathcal{P}},\mathcal{V}\rangle(y)$)
  • $\leftarrow$ usually denotes the randomised output that results from this interaction (the verifier and the prover could use random coins)
  • $\bot$ denotes that the (malicious) prover $\tilde{\mathcal{P}}$ has no (private) output at the end of the protocol (think of zero-knowledge protocols, e.g.)
  • $\text{accept}$ denotes that the verifier accepts at the end of the protocol (again, think of zero-knowledge protocols)
$\endgroup$
0
$\begingroup$

In the context of interactive proof systems, the notation you're asking about is used to represent the interaction between the prover and the verifier.

  1. \textbf{$\leftarrow$}: This symbol represents the direction of communication. Specifically, $(\tilde{\mathcal{P}})(y) \leftarrow (\mathcal{V})(y)$ means that the prover $\tilde{\mathcal{P}}$ sends a message to the verifier $\mathcal{V}$ based on the input $y$.

  2. \textbf{$\leftrightarrow$}: This symbol represents the bidirectional nature of the interaction. When you see $(\tilde{\mathcal{P}})(y) \leftrightarrow (\mathcal{V})(y)$, it means that there is communication happening both ways between the prover and the verifier. The prover sends messages to the verifier, and vice versa.

  3. \textbf{$(\bot,(\text{accept}))$}: This notation denotes a possible outcome of the interaction. Here, $\bot$ represents a special symbol typically used to indicate rejection or failure, and $(\text{accept})$ denotes acceptance. So $(\bot,(\text{accept}))$ signifies either the verifier rejecting the proof or accepting it.

Putting it all together, the expression $\operatorname{Pr}[(\bot,(\text{accept})) \leftarrow (\tilde{\mathcal{P}})(y) \leftrightarrow (\mathcal{V})(y)]$ represents the probability of certain outcomes (specifically, rejection or acceptance) occurring during the interaction between the prover and the verifier.

The soundness property you're referring to states that this probability should be less than some small value $\epsilon$, ensuring that incorrect or false proofs are rejected with high probability.

$\endgroup$

Your Answer

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

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