兩個密碼原語之間的共享隨機性是否會使計算不可區分性的混合論證複雜化？
讓 $ (Enc, Dec) $ 是一個 IND-CPA 安全加密方案，其中 $ Enc: \mathcal{K} \times \mathcal{M}_1 \rightarrow \mathcal{C}_1 $ ， 和 $ F: \mathcal{K} \times \mathcal{M}_2 \rightarrow \mathcal{C}_2 $ 是一個偽隨機函式。
考慮一個簡單的例子，我們可能想證明分佈 $ (Enc_k(m_1), F_k(m_2)) $ （其隨機性來自共享密鑰 $ k \leftarrow \mathcal{K} $ ) 在計算上與上的均勻分佈無法區分 $ \mathcal{C}_1 \times \mathcal{C}_2 $ . 很明顯，我們可以證明分佈 $ Enc_k(m_1) $ 在計算上與上的均勻分佈無法區分 $ \mathcal{C}_1 $ 通過降低 IND-CPA 安全性。通過更換 $ Enc_k(m_1) $ 帶有隨機元素 $ r_1 \leftarrow \mathcal{C}_1 $ ，我們可以得到一個中間混合體 $ (r_1, F_k(m_2)) $ . 我的問題是：
然後我們可以應用偽隨機性 $ F $ 取代 $ F_k(m_2) $ 與另一個隨機元素 $ r_2 \leftarrow \mathcal{C}_2 $ ，為了證明上面的計算不可區分性？
從我的角度來看，這兩個隨機變數 $ Enc_k(m_1) $ 和 $ F_k(m_2) $ 不是獨立的**，**因為它們共享相同的隨機性 $ k $ . 這讓人想起為什麼我們應該考慮某人的視圖輸出元組的聯合分佈而不是其在安全計算中的視圖。所以，我認為這裡的共享隨機性確實阻止了一個簡單的混合參數通過。這個結論對嗎？非常感謝。
是的你是對的。
我的問題中確實缺少 IND-CPA 的正式定義。在這裡，我非正式地使用術語“IND-CPA”來指代加密方案可能導致偽隨機密文的屬性 $ \mathcal{C}_1 $
這當然是比 IND-CPA 更強的假設，但指出這一點很無聊。實際上，這個假設可以寫成
$ \mathsf{Enc}_k $ 是一個PRF家族。
從 PRF 的角度考慮這一點可能更直接，所以我將很快證明，如果 $ F_k, G_k $ 是（單獨的）PRF，那麼 $ (F_k, G_k) $ 不需要，例如共享 PRF 密鑰會破壞安全性。正如您所猜測的，這是因為左右組件之間存在依賴關係。
讓 $ F_k $ 是一個 PRF，並讓 $ G_k = F_k^{\circ 2} $ ， IE $ G_k(x) = F_k(F_k(x)) $ . 很容易看出 $ G_k $ 是（單獨地）一個 PRF — 它的任何區分器都意味著它的區分器 $ F_k $ ，因為您可以有效地模擬對 $ G_k $ 給定查詢訪問權限 $ F_k $ .
現在， $ (F_k, F_k^{\circ 2}) $ 不是 PRF。這是因為，給定一個預言機 $ \mathcal{O}(\cdot) $ 這是真實的或隨機的，你可以。
- $ (y_1, y_2)\gets \mathcal{O}(x) $ ,
- $ (z_1, z_2) \gets \mathcal{O}(y_1) $ ,
- 猜真如果 $ y_2 = z_1 $ ，否則為 RANDOM。
如果 $ \mathcal{O}(x) = (F_k(x), F_k^{\circ 2}(x)) $ 是你的 PRF，那麼 $ y_2 = F_k^{\circ 2}(x) $ ， 和 $ z_1 = F_k(y_1)= F_k(F_k(x)) = F_k^{\circ 2}(x) $ 碰撞。在隨機博弈中，任何兩個值碰撞的機率都非常小，因此這立即暗示了一個相當好的區分器。
不過還有更直接的問題。一種建構方式 $ \mathsf{Enc}_k(m) $ 是通過 XORing $ m $ 例如，使用 PRF $ \mathsf{Enc}_k(m) = (r, F_k(r)\oplus m) $ . 這只是隨機計數器模式（其中消息是單個塊）。在這種情況下，聯合建設是 $ (m_1,m_2)\mapsto (r, F_k(r)\oplus m_1, F_k(m_2)) $ . 再次，通過查詢 $ (m_1, m_2) $ ，然後查詢 $ (m_3, r) $ ，可以得到一個有效的區分器。這就是說一個自然構造（其中 $ \mathsf{Enc} $ 是隨機計數器模式）在您的設置中也不安全。