為蓄電池選擇合適的素數
我正在嘗試計算累加器並生成 $ S = { e_1,e_2 \ldots, e_n } $ 由此（第 3.4 節 - 選擇合適的素數）。
對於每個元素 $ e_i $ 計算其表示 $ x_i $ .（這是我要計算的）。
計算表示（ $ x_i $ ）使用以下 （根據論文 $ x_i $ 應該這樣計算，這部分我需要幫助。請幫助我理解這一點）
我們有興趣獲得表示 Universal-2 散列函式的線性系統的素數解。
引理： 設 H 是一個universal-2 族 $ {0,1}^{3k} $ 至 $ {0,1}^k $ . 然後，除了一個 $ 2^{-k} $ 功能的一部分 $ h \in H $ . 對於每一個 $ e \in {0,1}^k $ 至少的一小部分 $ 1/ck $ 中的元素 $ f^{-1}(e) $ 是素數，對於一些小的常數 c。
只有當它大於 $ \sqrt{2^{3k}} $ . 由於 H 的域是 $ {0,1}^{3k} $ . 所以，根據素數理論的結果，大素數的密度小於 $ 2^k $ 是關於 $ 1/2k $ 除了一個 $ 2^{\Omega(k)} $ H.* 家族中的部分功能
請幫助我，我該如何計算 $ x_i $ 作為代表 $ e_i $ ?
我將使用 Michael T. Goodrich、Roberto Tamassia、Jasminka Hasic 的An Efficient Dynamic and Distributed RSA Accumulator from arXiv (2009)作為參考，而不是最初在 ISC 2002 會議記錄中或在問題中連結的版本。
免責聲明：我在寫這個答案時發現了這篇論文，因此以下內容是高度試探性的。此外，有些重要的事情我無法理解，這意味著我的理解或論文是錯誤的。因此，請勿將以下內容用於比探索更嚴重的事情。
初步：RSA模數的選擇 $ N=P,Q $ , 和基 $ a $ .
當它希望儲存 $ e_i $ 高達 $ k $ 位，所描述的方案首先生成“強素數¹” $ P $ 和 $ Q $ 至少 $ 3k/2 $ 每個位。我相信它們還需要至少與 RSA 安全性所需的一樣大（未說明）。文章的實驗結果指出“參數 $ N $ RSA 累加器是一個 200 位整數”，但如果我理解其餘的建議 $ k=165 $ ，這將使 $ N $ 495 位。當文章發表時，即使這也太低了，看這個。這種無視安全選擇的 $ N $ 在文章的理論和實踐部分都迫切需要修復。我會嘗試一下。
文章對“強素數¹”的參考是應用密碼學定義 4.52 手冊：
一個素數 $ p $ 如果整數被稱為強素數 $ r $ , $ s $ ， 和 $ t $ 滿足以下三個條件：
(i) $ p−1 $ 有一個大²的素因數，表示為 $ r $ ;
(二) $ p+1 $ 有一個大²的素因數，表示為 $ s $ ; (
iii) $ r−1 $ 有一個大²的素因數，表示為 $ t $ .
在 RSA 累加器和依賴於強 RSA 假設（包括問題的方案）的問題的背景下，我至少需要 (i) 堅持 $ P $ 和 $ Q $ ; 並且為了更好地衡量，我會使用文章參考中要求的相同位大小的安全素數
$$ 6 $$, Josh Benaloh 和 Michael de Mare 的單向累加器：數字簽名的去中心化替代方案，在Eurocrypt 1993的會議記錄中（帶有擴展摘要）。 對於現代實施，我會考慮 $ k=680 $ ， 和 $ P $ 和 $ Q $ 區間中的隨機 1024 位安全素數 $ [2^{1023.5},2^{1024}), $ ，很容易生成。
此外，它需要“一個適當大的基礎 $ a $ 這是相對質數 $ N=P ,Q $ ”。由於缺乏其他指導，我會考慮 $ a=\lfloor\pi,2^{2045}\rfloor $ .
素數代表 $ e_i $ 要積累。
論文定義了一個函式 $$ \begin{align}h:{0,1}^{3k}&\mapsto{0,1}^k\ x\quad&\to h(x)\underset{\text{def}}=U\times x\end{align} $$ 在哪裡 $ U $ 是一個二進制矩陣 $ k $ 線條和 $ 3,k $ 列。它定義了主要代表 $ e_i $ 累積為素數 $ p_i $ 在 $ [2^{3k/2},2^{3k}) $ 這樣 $ h(p_i)=e_i $ （根據例如大端約定將整數同化為位串）。
為了找到 $ p_i $ 從 $ e_i $ ，我們可以簡化系統 $ k $ 二元方程與 $ 3k $ 二元未知數 $ U\times x=e_i $ , 至少列舉解 $ 2^{3k/2} $ ，並在第一個素數處停止 $ x $ 成立。我對列舉順序沒有任何要求，但我想它必須是確定性的，偽隨機不會有害。
其餘的似乎是 RSA 累加器的標準使用。
¹ 注意：在普通的 RSA 中，現在是否真的需要強素數是值得懷疑的。條件（一）
$$ resp. (ii) $$旨在阻止波拉德的 $ p-1 $ [分別。威廉的 $ p+1 $ ] 因式分解，但這變得毫無希望，因為 $ p $ 增加（根據需要抵抗GNFS），並且只能真正幫助低參數化的多目標攻擊。條件 (iii) 旨在阻止循環攻擊，但似乎毫無意義，請參閱 Ronald L. Rivest 和 Robert D. Silverman 的RSA 需要“強”素數嗎？. 對於用於簽名中使用的 RSA 模數的 1024 位或更大的素數，保守的FIPS 186-4 附錄 B3不需要這些條件。 ² 論文或 HAC 中都沒有暗示 RSA 累加器的上下文有多大。FIPS 186-4 中的指南不適用於這種情況；將它用於（i）將是冒險的。