Chosen-Plaintext-Attack
關於 RFO-rCTR 中的碰撞機率
我的幻燈片顯示，假設一個多項式數 $ q(n) $ 在 CPA 遊戲的上下文中，已由隨機函式 oracle 加密的塊，在 oracle 的輸入中發生衝突的機率為 $ \frac{q(n)^2}{2^{l(n)}} $ （參見 Katz 和 Lidell，第 2 版，第 93-94 頁）。
然後我提出以下建議：假設總共 $ e(n) $ 消息被加密，每個消息最多包含 $ s(n) $ 塊，則輸入中碰撞的機率為 $ \frac{e(n)^2s(n)}{2^{l(n)}} $ .
這是一個錯字嗎？為什麼我們要放棄廣場 $ s(n) $ ?
在這裡你可能會看到我提到的幻燈片（見幻燈片 18 和 19）
這裡的關鍵思想是同一消息中的塊不會發生衝突——消息 $ 1 $ 不會有可能的塊衝突，消息 $ 2 $ 可以與消息發生衝突 $ 1 $ 的 $ s(n) $ 塊，消息 $ i $ 可以與消息碰撞 $ i-1 $ 的 $ s(n) $ 塊或消息 $ i-2 $ 的 $ s(n) $ 塊等
換句話說，可能發生碰撞的塊組合的數量由下式給出 $$ \sum_{i=1}^{e(n)} (i - 1)s(n),, $$ 這簡化為 $ s(n) {e(n) \choose 2} $ . 我們把它變成一個機率$$ \frac{s(n){e(n) \choose 2}}{2^{l(n)}} \le \frac{s(n)e(n)^2}{2^{l(n)}},. $$