來自集合的散列及其子集的集合的散列函式不會顯示集合中剩餘元素的散列
我正在尋找一個計算集合雜湊的函式。
它需要滿足兩個性質：
- 如果有人發布了雜湊 $ h(S) $ 一組的 $ S $ 和一個雜湊 $ h(S’) $ 某個子集的 $ S’ \subset S $ 其中，我應該無法計算 $ S \setminus S’ $ 從 $ h(S) $ 和 $ h(S’) $ .
- 從雜湊 $ h(S_1) $ 和 $ h(S_2) $ 兩個不相交的集合 $ S_1 $ 和 $ S_2 $ ，我應該能夠計算雜湊 $ h(S) $ 他們的工會 $ S = S_1 \cup S_2 $ .
這樣的雜湊函式存在嗎？
這是一個主要解決您想要的想法的想法；我對此不滿意，但我想我會分享它以防萬一。
我們的“雜湊”是 $ n $ 元素，每個元素都是介於 0 和 $ p-1 $ , 或特殊符號 $ \bot $ .
單例元素的雜湊 $ s $ （即由單個元素組成的集合）通過選擇 $ n $ 元素確定地為數字（例如，使用 SHAKE(s) 中的位），然後選擇 $ b $ 的 $ n $ 指標（再次，確定性地），並設置每一個 $ b $ 指標 $ \bot $ .
並且，結合兩個散列（使用 Ilmari 的符號，計算 $ c = a \otimes b $ ），您對兩個散列執行以下操作元素）：
$ c_i = \bot $ 如果 $ a_i = \bot $ 或者 $ b_i = \bot $
否則， $ c_i = a_i + b_i \bmod p $
很明顯，上述運算元既是結合的又是可交換的。
並且，假設 $ p, n, b $ 被正確設置，然後給出 $ a \otimes b $ 和 $ a $ , 應該很有可能 $ b $ 無法恢復（因為可能存在某些元素 $ i $ 在 $ a $ 你有 $ a_i = \bot $ 和 $ b_i \ne \bot $ ; 在這種情況下，您沒有關於 $ b_i $ ，因此任何 $ n $ 可能的值是等機率的。
當然，散列非常大，而且這種不可逆性只是可能的（即使只有當集合 $ a, b $ 不是太大）。
這不是一個真正的答案，而是一系列觀察結果。
條件 1) 似乎有點問題和令人困惑。似乎只有在大小為 $ S $ 是足夠大的獨立於 $ H(\cdot) $ 用過的。原因是如果 $ n $ ， 的大小 $ S $ 不夠大，那麼攻擊者可以嘗試以下條件（假設我們也知道 $ S $ ):
- 讓 $ P = 2^S $ 成為 $ S $ ，即所有子集的集合 $ S $
- 輸入： $ S, H(S), H(S’) $
- 讓 $ A $ 成為條件 1 的對手。
- 在每個元素上 $ s \in P $ , $ A $ 計算雜湊 $ H(s) $ 並檢查是否 $ H(s) = H(S’) $
- 如果檢查通過輸出 $ H(S\setminus s) $ .
現在，如果衝突的數量非常少並且假設雜湊計算是免費的（足夠有效），那麼複雜度最多為 $ O(2^N) $ 和 $ N $ 的大小 $ S $ . 注意：如果我們不知道 S，我們還需要最大集合（不是其他集合的子集的集合）的數量足夠大。
此外，假設我們實際上可以對複雜性進行更嚴格的限制 $ S $ 是已知的。如果 $ S’ $ 有大小 $ k $ 然後 $ S’ $ 有大小 $ k’= N-k $ . 所以總步數是 $ \sum^{k’}_{i = 1} \binom{n}{k} $ . 一個封閉的公式真的很受歡迎！;)
最後讓我感到困惑的是 $ S $ 也應該在任何這樣的領域 $ H(\cdot) $ ，因此根據上述推理，該屬性不適用於足夠小的子集。
有沒有可能這樣 $ H(\cdot) $ 一般來說，永遠不能退出並滿足條件1，還是我錯過了什麼？