Birthday-Attack
為什麼k-lists廣義生日問題k=2ķ=2k=2是經典的生日問題嗎？
David Wagner 在他的文章A Generalized Birthday Problem in CRYPTO 2002 中說，在生日問題 (GBP)的k維（也是k列表）中，當 $ k=2 $ “這只是眾所周知的生日問題。” 為什麼呢？據我了解，在經典生日問題中，我們在一個列表中搜尋碰撞 $ L $ ， 在哪裡 $ x_1 $ 和 $ x_2 $ 應該是 $ \in L $ )，但是，在k -lists GBP 中，我們有k個列表，當 $ k=2 $ 它是 $ L_1, L_2 $ ， 我們發現 $ x_1 \in L_1 $ 和 $ x_2 \in L_2 $ 這樣 $ x_1 \oplus x_2 = 0 $ .
那麼，當k -lists GBP 收斂到經典生日問題時 $ k=2 $ ? 或者我錯過了什麼？
它們本質上是相同的，當然就複雜性而言。任何碰撞 $ x=y $ 和 $ x\in L_x $ 和 $ y\in L_y $ 是單個列表中的衝突 $ L_x \cup L_y $ 的大小最多為較大列表大小的兩倍。
單個列表中的任何衝突都與該列表中大約一半的分區兼容，分成大小相等的兩半。因此，在聯合中隨機發現碰撞的算法已經在兩個列表問題中發現了一個有機率的碰撞 $ 1/2. $
此外，在加密上下文中，列表包含散列或其他加密原語的（偽）隨機輸出。
它不收斂，看起來它只是一個完全不同的問題，被命名為相同的（可能是由於它們之間的相似性）。