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$

1 Answer 1

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$

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.