Hash
具有質數域的抗碰撞雜湊函式
為了使用 RSA 累加器，元素必須是素數。是否有具有質數域的抗衝突雜湊函式的範例？
您可以使用 Hash(element:nonce) 然後增加 nonce 直到結果為素數。查看論文“Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains”的第 7 節“Hashing To Primes ”
例如 Hash() 可以是 SHA256。
假設你有一個 PPT 算法 $ M(1^n;r) $ 給定目標素數的長度和隨機性 $ r\in{0,1}^{\rho(n)} $ 找到長度的素數 $ n $ . 進一步假設 $ M $ 從某種意義上說是安全的，如果你給它一個適當的隨機輸入 $ r $ 它將輸出一個不可預測的隨機素數，適用於說 RSA。大多數密碼庫都有這樣的實現。
進一步假設你有一個 PRG $ G:{0,1}^l\to{0,1}^{p(l)} $ 給定一個正確的隨機字元串作為輸入輸出一個（多）更長的隨機字元串作為輸出。例如，這是通過使用諸如 AES-CTR 之類的東西來實現的，其中輸入是密鑰並使用固定的隨機數。
然後取任何可以合理建模為隨機預言機的雜湊函式 $ O:{0,1}^*\to{0,1}^l $ ，例如 SHA3。隨機預言機的定義特徵是，您可以獲得新的隨機抽取的值作為每個新輸入值的輸出。
現在按如下方式建構您的雜湊： $ P_n(x)=M(1^n;G(O(x))) $ . 假設您可以安全地生成 RSA 密鑰，這也是安全的（只要 $ x $ 是不可預測的）。