雜湊“原像副產品”阻力
讓 H() 是一個雜湊函式，它實現了抗碰撞性
以及第一和第二原像抗性。
讓我們裝備一個乘法群結構的 H 的輸出集，更準確地說是一個循環群。
問題
我的問題是：這很難嗎？ $ a $ 去尋找 $ (b,c) $ 這樣 $ H(b) \times H(c) = H(a) $ ?
啟發式/直覺
在嘗試減少其中一個雜湊屬性之前，我嘗試自己實現此功能：
給定 $ a $ ，我隨機取一個 $ b $ , 那我在找 $ c $ 滿足： $ H(c) = H(a) \times H(b)^{-1} $ .
然後H的原像電阻阻止我找到 $ c $ .
然後我的直覺是我的目標函式和原像抗性一樣難，但我不能
以減少結束：給定 $ H(a) $ 和一個解決我的問題的 Oracle，我找不到獲得的方法 $ a $ .
同樣，鑑於這樣的 Oracle，我找不到創建衝突的方法。
碰撞和原像阻力並不意味著這一點；假設我們選擇了一個抗碰撞和抗原像功能 $ H $ 具有已知值 $ I $ 和 $ H(I) = 1 $ （組標識）；這個額外的斷言與碰撞或抗原像性的假設並不矛盾。然後，給定 $ a $ ，我們可以很容易地輸出元組 $ (I, a) $ ; 正如我們所擁有的 $ H(I) \times H(a) = H(a) $ .
此外，我們可以看到這個問題比原像或第二原像問題更容易。假設 $ H $ 是一個隨機的 Oracle，並且組大小是 $ n $ ; 然後，我們可以通過選擇來解決問題 $ \sqrt{n} $ 的值 $ b $ , $ c $ ，併計算由值組成的兩個列表 $ H(b) $ 和 $ H(a)^{-1} \times H(c) $ 並尋找出現在兩個列表中的值，即 entry $ i $ 名單的 $ H(b_i) $ 和入口一樣 $ j $ 名單的 $ H(a)^{-1} \times H(c_j) $ . 如果隨機預言機是隨機行動的，那麼我們很有可能找到一個共同的值；這給了我們一對 $ (b_i,c_j) $ 在 $ \sqrt{n} $ 時間; 這比我們解決隨機 Oracle 的原像或第二個原像問題（這需要 $ O(n) $ 時間）。如果我們有一個減少時間少於 $ O(\sqrt{n}) $ 呼叫這個問題，這意味著我們可以更快地解決原像問題 $ O(n) $ ，我們知道我們做不到。
$$ Note: I updated this paragraph since the answer was accepted $$ 至於這個問題是否比抗碰撞問題更容易（假設我們不懂魔法 $ I $ 和 $ H(I)=1 $ )，這兩個問題都不能歸結為另一個問題，因為可以設計散列函式，其中一個問題很困難，另一個問題很容易。
對於碰撞很困難且“原像乘積”很容易的雜湊函式，採用 RSA 模數 $ N $ （秘密分解）和一個值 $ g $ 有秩序的 $ lcm(p-1, q-1) $ ，並定義散列函式 $ H(x) = g^x \bmod N $ 對於正值 $ x $ （並要求 $ H(0) $ 不允許; 0 不是正數）。找到兩個不同的值 $ x, y $ 和 $ H(x) = H(y) $ 等價於因式分解 $ N $ ，所以這很困難；然而，鑑於任何 $ a>1 $ ，我們可以找到對 $ a-1, 1 $ 和 $ H(a-1) \times H(1) = H(a) $ .
對於一個容易碰撞而“原像乘積”很難的散列函式，取一個隨機的 Oracle，並定義 $ H(x) = Oracle(trunc(x)) $ ， 在哪裡 $ trunc $ 剝去 lsbit $ x $ . 然後，找到衝突很容易（只需輸出兩個僅在 lsbit 中不同的值），但是解決 H 的“原像乘積”等同於解決隨機 Oracle 的問題。
我的直覺是，對於現實的雜湊函式，這些問題可能大致同樣困難；當然，針對抗碰撞性的通用攻擊（形成一個列表，基於 rho 的方法）可以適應您的問題。