是否存在與活板門無碰撞功能等效的資訊理論？
警告：可能是不恰當的問題。
我正在使用此處最近可用的一篇論文中的以下定義。我相信他們的術語略有不同，但在這裡重現了我對它的理解。
2 對 1 陷門無碰撞函式的概念滿足以下屬性。對於每一個 $ y $ 這樣 $ f(x) = y $ ， 那裡存在 $ f(x’) = y $ 和 $ x\neq x’ $ . 如果可以進入活板門，很容易找到 $ (x,x’) $ 對於任何 $ y $ 否則計算起來很困難。
在最近線上發布的一次談話中，作者討論了對此的資訊論概括，但沒有提供更多細節。明顯的障礙是計算無界的攻擊者可以嘗試所有可能的輸入 $ f $ 並最終知道碰撞。我的猜測是，不知何故， $ f $ 以模糊的方式給出，因此攻擊者無法知道碰撞。這樣的事情有可能嗎？人們如何才能做到這一點？
任何固定功能 $ f\colon A \to B $ 有限域的 $ A $ 如果範圍保證會發生衝突 $ B $ 元素少於 $ A $ , 所以總是存在一個隨機算法 $ C() $ 返回一個衝突：只返回一個衝突的算法。我們只是不知道如何找到 $ C $ 對於像 SHA-256 這樣的函式（儘管我們對 MD5 和 SHA-1 這樣做！）。這就是為什麼應用於固定散列函式（如 SHA-256）的“抗碰撞”概念甚至沒有正式定義的原因，儘管有人試圖將這個難以捉摸的人類無知問題正式化$$ 1 $$$$ 2 $$.
我們可以考慮一個機率或“資訊論”模型：一個隨機函式 $ f\colon A \to B $ 從所有函式中均勻分佈地繪製 $ A $ 至 $ B $ . 任意隨機算法 $ C(f) $ 發現碰撞僅限於生日攻擊 $ O(\sqrt{|B|}) $ 呼籲 $ f $ 達到不可忽略的成功機率。*
當然，隨機均勻地選擇一個函式需要很多位：通常，您需要儲存一個表 $ |B|^{|A|} $ 如果您希望能夠指定所有條目。我們可能會選擇一個較小的函式族 $ f_k\colon A \to B $ 用快捷鍵 $ k $ ，並分別考慮對手對密鑰的了解：
- 如果對手永遠不知道密鑰（當然，也無法從諸如雜湊表操作時間之類的側通道中了解任何有關它的資訊），則有許多廉價計算的函式可供選擇，它們具有“資訊理論上”保證的有界衝突稱為通用雜湊族的機率——也就是說，對於任何 $ x $ 和 $ y $ , $ \Pr[f_k(x) = f_k(y)] \leq \varepsilon $ 對於一些小 $ \varepsilon $ . 這是一個很容易證明的定理，例如 GHASH 或 Poly1305。看$$ 3 $$更多相關概念和參考資料。
- 如果對手事先不知道密鑰，Rogaway 和 Shrimpton 給出了標準的正式定義$$ 4 $$家庭碰撞阻力的概念 $ f_k $ 就隨機算法的最佳成本而言 $ C(k) $ 尋找碰撞 $ f_k $ （或者，更具體地說，就成本而言，成本有限算法的最佳成功機率）。我們推測在這種形式上具有抗碰撞性的家族包括 HMAC-SHA256 和 keyed BLAKE2b。
顯然，對於每個 $ k $ , 只要有碰撞 $ |B| < |A| $ ，但是即使我們有一個預先計算的預言機來提前為我們找到它們，儲存一個映射每個值的表的成本也非常高 $ k $ 發生碰撞 $ f_k $ , 我們假設對手可能買不起 $ 2^{128} $ 字節的 RAM 甚至 ROM 來儲存它。像 HMAC-SHA256 和 BLAKE2b 這樣的函式似乎展示了這種抗碰撞概念，但證明任何關於它的定理似乎很困難。相比之下，像 Poly1305 這樣的函式很容易被證明具有低碰撞機率。
活板門功能怎麼樣 $ m \mapsto x^m \bmod n $ 在哪裡 $ n = pq $ 對於秘密因素 $ n $ ? 任何可以在此函式中發現衝突的人都可以考慮 $ n $ , 所以只要因式分解 $ n $ 很難——直到誰知道 $ p $ 和 $ q $ 發佈單個碰撞！-似乎很難找到碰撞。但如上所述，域和範圍是有限的，如果 $ n $ 限於特定大小，那麼這些函式的空間也是有限的。因此，您無法保證有限但成本無限的攻擊者發現衝突的機率有限。
我不知道作者對此的資訊論概括可能意味著什麼——你必須問他們。順便說一句，這篇論文似乎在討論無爪函式對 $ f_0 $ 和 $ f_1 $ 很難找到 $ x_0 $ 和 $ x_1 $ 和 $ f_0(x_0) = f_1(x_1) $ , 不是抗碰撞功能 $ f $ 很難找到 $ x_0 \ne x_1 $ 和 $ f(x_0) = f(x_1) $ .
到目前為止，您可以天真地製作一個結果表，並在每次呼叫時檢查它是否有衝突 $ f $ ，但這需要花費 $ O(\sqrt{|B|}) $ 時間和* $ O(\sqrt{|B|}) $ 總面積*時間成本（代表盧布或爾格）的空間 $ O(|B|) $ . 相比之下，它需要大約相同數量的呼叫 $ f $ ，並且只有常量記憶體，才能使用 van Oorschot 和 Wiener 的碰撞搜尋算法$$ 5 $$, 也可以並行化以加快速度，但功耗更高。擁有一台可以評估疊加態的量子電腦似乎也無濟於事 $ f $ $$ 6 $$.