雜湊之和是否適合集合的雜湊？
讓 $ H: X \rightarrow {0, 1}^b $ 表示加密安全， $ b $ -bits 集合上的雜湊函式 $ X $ . 讓 $ H^: \mathbb{P}(X) \rightarrow {0, 1}^b $ 是冪集上的一個函式 $ X $ 被定義為 $$ \begin{equation} H^({x_1, \ldots, x_n}) = \sum_i H(x_i) \end{equation} $$ 其中總和旨在作為包裝加法 $ b $ 位整數。
我想知道是否 $ H^* $ 在密碼學上是安全的 $ \mathbb{P}(X) $ .
我很容易看到其他聚合機制（例如將所有雜湊值異或在一起）很容易發生衝突。我也看到了，如果相同的元素 $ X $ 可能會在被散列的集合中多次出現，可以通過簡單的整數除法來建構碰撞。但是，如果所有的元素 $ X $ 被雜湊是不同的，我不能輕易地看到對這種結構的攻擊。
與其他人所說的相反，這實際上（稍微修改後）很好。您似乎對同態散列問題感興趣。請注意，雖然完全同態加密指的是（環）同態，即相對於類似 $ (\mathbb{F}_2, +, \times) $ ，同態散列是指關於么半群同態 $ (\mathbb{P}(X), \cup) $ ，即正是你的同態概念。
不管怎樣，同態雜湊的構造早已為人所知。有關事物的半近期討論，請參閱此內容。與您的提議幾乎完全一樣的東西實際上是安全的（它被稱為“LtHash”，可以追溯到 90 年代）。這裡的“技巧”是一個散列到 $ \mathbb{Z}_q^n $ 為了 $ n $ 大的。然後可以將散列的抗碰撞性降低到標準格問題（短整數解決方案問題），這（當適當參數化時）被認為是困難的。請注意，設置 $ n = 1 $ （您的實際情況）可能不安全，至少沒有設置 $ q $ 相當大。
編輯： 我誤解了代數域，但答案可以修改，見下文。
所展示的複雜性呈指數級下降，但在雜湊函式、LWE、LPN 等使用類似結構的應用程序中，這些降低的複雜性很受關注。
$ H^\star $ 肯定是不安全的。與大多數針對雜湊函式的攻擊一樣，您將生成隨機輸入以尋找衝突。這裡讓我們考慮加法模 $ 2^b-1, $ 正如你所建議的。
如果 $ n $ 比較小 $ 2^b, $ 仍然有一些捷徑可以大大降低複雜性。這是一個發現此類功能碰撞的攻擊。給定一些所需的雜湊輸出 $ H_0, $ 假設我們有一組隨機的 $ v=2^{b/n} $ 散列，形式 $$ H^\star({x_{1,i},\ldots,x_{n,i}}),\quad i=1,\ldots,v\quad(1). $$ 因為這裡有 $ v^n=2^b $ 可能的 $ n- $ 形式 (1) 的總和 我們收集的這些總和將達到您的要求 $ H_0 $ 具有恆定機率，因為雜湊目標空間具有大小 $ 2^{b}. $
*解釋：*我們有一個有限域，並且 balls in bins 過程 $ 2^b $ 可能的輸入。
如果 $ n=2 $ 這本質上是複雜的生日問題 $ O(2^{b/2}). $ 通過減少到以下情況 $ n=2^s $ 是 2 的冪，Wagner給出了$$ O(2^{b/(1+s)}=O(2^{b/(1+\lceil \log n\rceil)}) $$XOR 情況的遞歸解決方案，但這可以適用於任何有限群，包括加法模 $ 2^b-1. $ 另請參閱Antoine Joux撰寫的算法密碼分析一書的第 8 章。