更多消息的對抗性不可區分性
假設我們從 Adversarial Indistinguishability 玩遊戲，但 Adversarial 可以選擇三個消息 $ m_0, m_1, m_2 $ . 當然， $ Pr[M=m_i]=1/3 $ 為了 $ i=0,1,2 $ . 我認為要具有對抗性不可區分性，一個人的優勢不能大於 $ 1/3 $ . 問題是這是否比帶有兩條消息的版本更強。直覺上是這樣，但隨後我們可以接收越來越多的消息，並使對抗性的優勢越來越小。有必要嗎？出於某種原因，在定義中，有兩條消息——這就夠了嗎？
備註：這裡我使用的是索引 $ 0,1,2 $ 和 $ 0,1 $ 代替 $ 1, 2, 3 $ 和 $ 1,2 $ .
我們必須展示 $ 3 $ - 不可區分性問題等價於 $ 2 $ -不可區分的一。
$ 2 $ - 不可區分性比 $ 3 $ - 不可區分性。
首先讓我們認為它存在一個對手 $ \mathcal{A}_3 $ 反對這 $ 3 $ - 優勢不可區分問題 $ \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 $ - 不可區分性比 $ 2 $ - 不可區分性。
現在讓我們考慮它存在一個對手 $ \mathcal{A}_2 $ 反對這 $ 2 $ - 優勢不可區分問題 $ \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}| $ 也是不可忽視的。
我們推斷這些問題是等價的。