CBC 作為無前綴 PRF 的安全證明
我目前正試圖完全理解 Dan Boneh/Victor Shoup 在他們出色的加密書草稿中的證明，即原始 CBC 構造是針對無前綴對手的安全偽隨機函式係列（參見第 6.4.1 節）。
證明的方法是替換PRF $ E_K: \mathcal{X} \rightarrow \mathcal{X} $ 有一個功能 $ f:\mathcal{X} \rightarrow \mathcal{X} $ ，即從所有函式的集合中隨機選擇 $ f \stackrel{$}{\leftarrow} \text{Funs}_{x,x} $ :
關鍵是計算對手區分這一點的能力 $ \text{CBC-}f $ 從隨機選擇中建構 $ \text{Funs}{mx,x} $ （所有函式的集合 $ \mathcal{X}^{\leq m\text{max}}\rightarrow \mathcal{X} $ 和 $ 1\leq m \leq m_\text{max} $ ）。為此，使用了有根樹，其中每個查詢代表該樹中的一條路徑。目標是找到兩個輸入的機率 $ f $ 碰撞（CBC鏈值 $ \oplus $ 一些 $ X_i $ 與其他一些 CBC 鏈值發生衝突 $ \oplus $ 一些 $ X_j $ ）。這就是前綴自由發揮作用的地方，因為它確保消息塊在統計上獨立於 CBC 鏈值，因此有兩個輸入 $ f $ 與機率相撞 $ 1/|\mathcal{X}| $ .
最後但並非最不重要的問題：為什麼我們也必須考慮內部衝突？為什麼只考慮最後一次的碰撞是不夠的 $ f $ 每個查詢的呼叫？一個無前綴的對手怎麼知道，如果有內部衝突，當他只看到 $ Y $ ?
答案在證明的最後一句話中：“一旦我們確定這些類型不存在衝突，那麼與非根節點關聯的所有值都是隨機且獨立的，這尤其適用於值與葉子相關聯，葉子代表對手看到的 FCBC 的輸出。”
解釋一下：我們只對最後一次呼叫的葉子感興趣。但是，證明它的方法是為所有呼叫證明它。這看起來很自然，因為一旦發生內部衝突，這是否導致最終衝突的問題取決於查詢內容，這是未知的。