在這種情況下可以延長生日攻擊嗎？
讓 $ H:{0,1}^*\to{0,1}^n $ 是一個作為黑盒的密碼散列函式，並假設我們有無限的空間。
據我了解，發現 $ x $ 這樣 $ H(x)=0 $ （如果存在）將需要原像攻擊，並且平均。時間 $ O(2^n) $ （與輸出大小成線性關係）。另一方面，發現 $ x\neq y $ 這樣 $ H(x)\oplus H(y)=0 $ 可以使用生日攻擊，因此平均。時間 $ O(2^{n/2}) $ .
我的問題是，如果找到 3 個（或更多）不同的值可以說更好 $ x,y,z $ 這樣 $ H(x)\oplus H(y)\oplus H(z)=0 $ . 很明顯，這可以使用更少的樣本來完成 $ H $ ，但我不清楚是否可以提高時間複雜度。
所以，正如@poncho 的評論，廣義生日問題 $ m=2^k $ 輸入，固定 $ k\geq 2 $ , $$ H(x_1)\oplus \cdots \oplus H(x_m)=a,\qquad a \in {0,1}^n $$ 對於任何常數 $ a $ 可以通過使用基本上解決（最多 $ o(n) $ 指數項） $$ T=O(m⋅2^{n/(k+1)}), $$ 和 $$ M=O(2^{n/(k+1)}) $$ 通過瓦格納論文中的算法。
如果 $ m $ 不是 2 的冪，可以使用下一個 2 的冪的算法。
據我所知，沒有比一般算法更複雜的算法 $ T=O(2^{n/2}) $ 因案而出名 $ m=3. $ 修復一個輸入並對另外兩個的總和進行生日攻擊，這需要一個大小列表 $ O(2^n). $ 如果您被限制使用可能的最小記憶體，那麼大小列表 $ O(2^{n/3}) $ 就足夠了（這也是資訊論的下限，以獲得具有不可忽略的機率的解決方案），但您似乎需要從具有時間複雜度的列表中生成所有 2-wise 和 $ O(2^{2n/3}) $ 並在每次檢查的恆定時間內檢查雜湊排序列表中的衝突。
如果不是上述情況，或許這裡的專家能給我們啟發。
呼叫 $ m=3 $ 案例，3XORSUM 問題，整數（而不是二進制向量）的類似 3SUM 問題在具有許多應用程序的算法中很有趣，例如，參見 TCS 堆棧交換中的問題。