如果使用素數代表散列函式，是否可以找到具有相同 RSA 累加器值的兩組？
考慮Barić 和 Pfitzmann 提出的具有隨機預言的 RSA 累加器方案，其中隨機預言被安全散列函式取代 $ H $ 如下。
對於一套 $ S $ ，累加器值計算為 $ acc(S) = x^{\prod_{s \in S} h(s)} \mod N $ ， 在哪裡 $ h(s) $ 通過附加計算主要代表 $ l $ 合適的位 $ H(s) $ : $ h(s) = 2^l H(s) + d $ （使用足夠大的固定 $ l $ ， 和 $ d $ 選擇這樣 $ h(s) $ 成為素數）。
了解 RSA 模數分解的人能否有效地計算兩組不同的元素 $ S, S’ $ 評估為相同的累加器值？
雖然 RSA 累加器方案的這種變體並不是普遍無衝突的，因為它允許在知道因式分解的情況下為任意元素偽造成員資格證明，但我想不出一種方法來計算評估為的完整元素集特定的累加器值，或者在不計算原像的情況下找到兩個評估為相同值的集合 $ H $ . 但是我也找不到證明它不可行的證據。
如果你是選擇的人 $ x $ 和 $ N $ ，找到碰撞和第二個原像是可行的（並且在不危及系統安全的情況下似乎是可能的）。
這是一種可能的方法：
搜尋一組 $ n $ 原像 $ s_0, s_1, …, s_{n-1} $ 這樣：
- $ \prod h(s_i) -1 = k r $ , 對於素數 $ r $ 例如，在 256 和 512 位之間。這可以通過選擇一個使產品大小合適的集合來完成，並檢查該值是否是一個大素數乘以一個平滑數。
- 然後，選擇 $ p = k’r + 1 $ 和 $ q = k’‘r + 1 $ , 適當大小的兩個素數（每個至少 1024 位），並設置 $ N = pq $
- 然後，選擇 $ x $ 這樣的順序 $ x $ 反對 $ p $ 是 $ r $ 和訂單模式 $ q $ 是 $ r $
發布 $ N $ 和 $ x $ 作為系統參數。
然後，當有人積累了集合 $ t_0, t_1, …, t_m $ ，可以顯示第二次累積 $ t_0, t_1, …, t_m, s_0, s_1, …, s_{n-1} $ ，它散列到相同的值。
那是因為 $ h(s_0)h(s_1)…h(s_{n-1}) \equiv 1 \pmod r $ ， 和 $ r $ 是順序 $ x $ ， 因此 $ x^{h(s_0)h(s_1)…h(s_{n-1})} \equiv 1 \pmod N $
此外，我認為：
- 特殊形式的知識 $ N $ （不計算的確切值 $ r $ ) 和知識 $ x $ 不做 $ N $ 更容易考慮
- 鑑於它似乎是不可行的 $ N $ 和 $ x $ ，以確定是否正在執行此操作。