Definition of soundness for interactive proof systems

Abced Decba

3/22/24, 8:21 PM

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.

1 + 0

interactive-proofs

Score:2

Crypto

ckamath

3/23/24, 7:53 AM

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)

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Definition of soundness for interactive proof systems

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.