具有更多信息的对抗性不区分性

Question

假设我们从对抗性的不可区分性出发玩游戏，但对抗性可以选择三条消息，m_0, m_1, m_2。当然，Pr[M=m_i]=1/3 for i=0,1,2。我认为，要具有对抗性的不可区分性，就不可能有比1/3更大的优势。问题是，这是否比有两条消息的版本更强。从直觉上看是这样，但这样我们就可以得到越来越多的信息，从而使对抗性的优势越来越小。有必要吗？出于某种原因，在定义中，有两条信息--这足够了吗？

Answer 1

备注:这里我使用的是索引0,1,2和0,1，而不是1, 2, 3和1,2。

我们必须证明3-indistinguishability问题等价于2-indistinguishability 1。

2-indistinguishability比3-indistinguishability.

容易

首先，考虑到它存在着一个对手\mathcal{A}_3，它是针对具有优势的3-indistinguishability问题的\epsilon。

定义\mathcal{B}^{\mathcal{A}_3}_2：

• 从(m_0, m_1, m_2)接收来自\mathcal{A}_3的三条消息
• x \xleftarrow{\\\$} \mathbb{Z}_3
• (m^\prime_0, m^\prime_1) := (m_{(1+ x \mod 3)}, m_{(2+ x \mod 3)})
• 将(m^\prime_0, m^\prime_1)发送给挑战者，并接收c。
• 将c发送到\mathcal{A}_3并接收b。
• 如果b=x返回随机位，则b^\prime其他返回(b- x \mod 3)。

我们首先证明了\mathcal{B}_2有赢得\frac{1-\epsilon}{4} +\epsilon的概率。

让我们称b''为挑战者选择的位。

\mathbb{P}(\mathcal{B}_2 wins)= \mathbb{P}(b- x \mod 3 = b'')\mathbb{P}(\mathcal{B}_2 wins| b- x \mod 3 = b'') + \mathbb{P}(b- x \mod 3 \neq b'')\mathbb{P}(\mathcal{B}_2 wins| b- x \mod 3 \neq b'')

= \epsilon \cdot 1 + (1 - \epsilon)\mathbb{P}((b=x) \wedge b^\prime =b'' | b- x \mod 3 \neq b^{\prime\prime})

= \epsilon + (1 - \epsilon)\frac{1}{2}\cdot\frac{1}{2}.qed

现在我们可以看看它的优势：|\frac{1}{2} - (\frac{1-\epsilon}{4} +\epsilon)|=|\frac{1- 3 \epsilon}{4}| = \frac{1}{12}|\frac{1}{3}- \epsilon|。

如果|\frac{1}{3}- \epsilon|不可忽略，它意味着|\frac{1}{2} - (\frac{1-\epsilon}{4} +\epsilon)|也是不可忽略的。

3-indistinguishability比2-indistinguishability.

容易

现在让我们来考虑一下，它存在着一个对抗\mathcal{A}_2的对手2-indistinguishability问题和优势\epsilon。

定义\mathcal{B}^{\mathcal{A}_2}_3：

• 从(m_0, m_1)接收来自\mathcal{A}_2的两条消息
• b \xleftarrow{\\\$} \mathbb{Z}_2
• m_2 := m_{b}
• 将(m_0, m_1, m_2)发送给挑战者，并接收c。
• 将c发送到\mathcal{A}_2并接收b^\prime。
• x \xleftarrow{\\\$} \big\{b, 2\big\}
• 如果b^\prime=b然后返回x，否则返回b^\prime

我们首先计算\mathcal{B}_3获胜的概率。

\mathbb{P}(\mathcal{B}_3 wins) = \frac{1}{3}\mathbb{P}(\mathcal{B}_3 wins|b''=2) + \frac{1}{3}\mathbb{P}(\mathcal{B}_3 wins| b''=b)+ \frac{1}{3}\mathbb{P}(\mathcal{B}_3 wins| b''=1 - b)

\mathbb{P}(\mathcal{B}_3 wins) = \frac{1}{3}\mathbb{P}(b'=b \wedge x=2|b''=2) + \frac{1}{3}\mathbb{P}(b'=b \wedge x=b| b''=b)+ \frac{\epsilon}{3}.

因为x是独立于b'选择的：

\mathbb{P}(\mathcal{B}_3 wins) = \frac{1}{3}\mathbb{P}(b'=b|b''=2) \cdot \mathbb{P}(x=2|b''=2) + \frac{1}{3}\mathbb{P}(b'=b|b''=b') \cdot \mathbb{P}(x=b''|b''=b')+ \frac{\epsilon}{3}

\mathbb{P}(\mathcal{B}_3 wins) = \frac{1}{3}\epsilon \cdot \frac1 2 + \frac{1}{3}\epsilon \cdot \frac1 2+ \frac{\epsilon}{3} = \frac{2\epsilon}{3}.

现在我们计算\mathcal{B}_3：|\frac1 3 - \frac{2\epsilon}{3} |= \frac1 6 |\frac 1 2 - \epsilon|.的优点。

如果|\frac{1}{2}- \epsilon|不可忽略，它意味着|\frac{1}{3} - \frac{2\epsilon}{3}|也是不可忽略的。

我们推导出这些问题是等价的。