如何嚴格證明和nC圓周率′(k)(米)=我nCΠ(k)(米)||大號小號乙(ķ)和nC圓周率′(ķ)(米)=和nC圓周率(ķ)(米)||大號小號乙(ķ)Enc_{Pi’(k)}(M) = Enc_{Pi(k)}(M) || LSB(k)CP…
認為 $ \Pi $ 是 CPA 安全方案。讓 $ \Pi’ $ 是一個派生方案，使得消息的加密 $ M $ 如下：
$ Enc_{\Pi’(k)}(M) = Enc_{\Pi(k)}(M) || LSB(k) $ ， 在哪裡
$ LSB(k) $ 是隨機選擇的密鑰的最低有效位。
有人可以幫我完成我的證明 $ \Pi’ $ 方案也是 CPA 安全的嗎？
我的證明：
假設相反， $ \Pi’ $ 不是 CPA 安全的。然後對手可以找到兩條消息 $ M_0 $ 和 $ M_1 $ , 這樣每當挑戰者返回他 $ C’b = Enc{\Pi’(k)}(M_b) $ ，他可以正確猜測隨機選擇的位 $ b $ 機率高於 $ \frac{1}{2} + 2\epsilon_{fixed} $ .
現在對手想要贏得一場比賽 $ \Pi $ 反對我。他給我發了這兩條消息 $ M_0 $ 和 $ M_1 $ . 他讓我隨機挑選一點b然後返回 $ C_b = Enc_{\Pi(k)}(M_b) $ . 然後對手猜測 LSB(k)：
- 有機率 $ \frac{1}{2} $ 他會正確猜到 LSB(k)。因此，他知道 $ C’b $ 並且可以猜到 $ b $ 機率高於 $ \frac{1}{2} + 2\epsilon{fixed} $
- 有機率 $ \frac{1}{2} $ 他會錯誤地猜到 LSB(k)。
In this case, he will guess the bit b with probability 1/2. // Why?因此，攻擊者可以正確猜測比特 b $ p > \frac{1}{2}(\frac{1}{2} + 2\epsilon_{fixed}) + \frac{1}{2}(\frac{1}{2}) = \frac{1}{2} + \epsilon_{fixed} $ . 這與以下假設相矛盾 $ \Pi $ 是 CPA 安全的。
$ \square $
我很難證明的部分是為什麼當對手猜錯了 $ LSB(k) $ 有點，他還是能猜對的 $ b $ 有可能 $ \frac{1}{2} $ . 例如，假設對手執行一個算法 $ \alpha $ 猜測一下 $ b $ 當被挑戰贏得比賽時 $ \Pi’ $ :
- 如果我們還給他 $ C $ 等於_ $ Enc_{\Pi’(k)}(M_b) $ ， 然後 $ \alpha $ 猜對了 $ b $ 機率為 0.6
- 如果我們還給他 $ C $ 這不同於_ $ Enc_{\Pi’(k)}(M_b) $ 在最後一點，然後 $ \alpha $ 猜對了 $ b $ 機率為 0。
所以現在的對手 $ \alpha $ 算法將贏得 CPA 遊戲 $ \Pi’ $ ，因為遊戲規則迫使我們發送正確的密文 $ C $ . 然而， $ \alpha $ 以證明中描述的方式使用不會贏得 CPA 遊戲 $ \Pi $ 因為 $ \frac{1}{2} 0.6 + \frac{1}{2} 0 < \frac{1}{2} $
所以我想問的是為什麼我們總能找到比 $ \alpha $ ?
對於您的問題：
In this case, he will guess the bit b with probability 1/2. // Why?，我想這就是您的證明讓您懷疑的重點？這只是正確猜測值的機率 $ b $ 當您完全隨機進行時：位 $ b $ 只能取兩個值， $ 0 $ 和 $ 1 $ ，所以如果你嘗試一個“瘋狂的猜測”，你就有機率 $ \frac{1}{2} $ 要得到正確的答案，就是這樣。
所以你是對的，你有機率 $ \frac{1}{2} $ 擁有優勢和機率 $ \frac{1}{2} $ 沒有任何優勢，正如您所描述的，由於總機率定律，這最終轉化為優勢。
現在為您編輯的問題：您這麼說，
then α guesses correct b with probability 0但如果是這種情況，那麼算法輸出 $ \neg\alpha $ 會有機率 $ 1-\frac{1}{2}0.6+\frac{1}{2}0 = \frac{1}{2}0.4+\frac{1}{2}1 >\frac{1}{2} $ 找到正確的值。因此，在實踐中，贏得 CPA 遊戲的“最佳”算法將沒有機率 $ 0 $ 輸出正確的 $ b $ ，因為否則我們可以構造一個更好的算法（除非它有機率 1 在“等於”情況下找到正確的值）。
現在，我個人更喜歡像 tylo 一樣，在處理假定不是 IND-CPA 的事情時查看對手的優勢。
在這裡，我將展示任何有效的 IND-CPA 對手 $ \mathcal{A}_{LSB} $ 在 LSB 的情況下，具有以下優勢 $ \epsilon $ 可以轉化為 IND-CPA 對手 $ \mathcal{A} $ 具有多項式相似的效率和優勢 $ \frac{\epsilon}{2} $ 在非 LSB 的情況下。
這與 Tylo 的答案完全相同，只是我的表述方式有所不同：
- $ \mathcal{A} $ 冒充 LSB 挑戰者，所以 $ \mathcal{A}_{LSB} $ 可以給他發兩條消息 $ (m_0,m_1) $ ，就好像它是 LSB 挑戰者一樣；
- $ \mathcal{A} $ 然後將它們發送給正常的挑戰者；
- 挑戰者發回價值 $ \mathcal{C}=Enc_{\Pi(k)}(m_b) $ 至 $ \mathcal{A} $ ;
- $ \mathcal{A} $ 現在拋硬幣並獲得價值 $ b’ $ ;
- $ \mathcal{A} $ 現在可以傳遞值 $ \mathcal{C}|b’ $ 好像這是 LSB 挑戰者的答案 $ \mathcal{A}_{LSB} $ ;
- $ \mathcal{A} $ 返回相同的答案 $ \mathcal{A}_{LSB} $ .
所以， $ \mathcal{A}_{LSB} $ 會有優勢 $ \epsilon $ 贏得比賽，如果 $ b’=LSB(k) $ 並且如果 $ b’\neq LSB(k) $ ， 我們有：
$$ \begin{aligned} Adv(\mathcal{A}) =& |P(\mathcal{A}{LSB} \text{ wins})- P(\mathcal{A}{LSB} \text{ looses})| \\geq& P(\mathcal{A}{LSB} \text{ wins})- P(\mathcal{A}{LSB} \text{ looses}) \ =& P(\mathcal{A}{LSB} \text{ wins} | b’=LSB(k))P[b’=LSB(k)] \ -& P(\mathcal{A}{LSB} \text{ looses} | b’=LSB(k))P[b’=LSB(k)] \ +& P(\mathcal{A}{LSB} \text{ wins} | b’\neq LSB(k))P[b’\neq LSB(k)] \ -& P(\mathcal{A}{LSB} \text{ looses} | b’\neq LSB(k))P[b’\neq LSB(k)] \end{aligned} $$ 也直接來自總機率定律。
但兩者 $ b’ $ 和鑰匙 $ k $ 均勻地隨機選擇 $ {0, 1} $ ， 所以 $ P(b’\neq LSB(k)) = P(b’= LSB(k)) = \frac{1}{2} $ . 現在，當對手處於這種情況下 $ b’\neq LSB(k) $ 它甚至可以嘗試隨機猜測，並且有機率 $ \frac{1}{2} $ 贏和松。這是一個有效的假設，因為如果它具有精確的贏/輸逆機率而不是這種情況 $ b’= LSB(k) $ ，那麼我們可以構造一個多項式對手嘗試針對不同的多個查詢 $ b’ $ 與固定 $ b $ （即我們的 $ \mathcal{A} $ 會轉發 $ (m_b,m_b) $ 為了 $ b $ 一點它的選擇）並確定哪個 $ b’ $ 有最常見的正確答案，因此我們的對手將擁有比 $ \frac{1}{2} $ .
最後我們知道
$$ |P(\mathcal{A}_{LSB} \text{ wins} | b’=LSB(k))P[b’=LSB(k)] \
- P(\mathcal{A}_{LSB} \text{ looses} | b’=LSB(k))P[b’=LSB(k)]| = \epsilon $$通過假設，我們最終得到： $ Adv(\mathcal{A}) \geq \epsilon\frac{1}{2} + 0\frac{1}{2} = \frac{\epsilon}{2} $
所以如果第二種方案存在這樣的對手，第一種方案也會被破壞。