什麼是質數階 q 的循環群，使得 DLP 是困難的？
在關於 Linked Ring Signatures 的原始論文中，為了建構其方案，作者依賴於：
讓 $ G = \langle g\rangle $ 是一個素數循環群 $ q $ 這樣潛在的離散對數問題（DLP）就很難了。讓 $ H_1 : {0, 1}^∗ \to \mathbb Z_q $ 和 $ H_2 : {0, 1}^∗ \to G $ 是被視為隨機預言的不同雜湊函式。
具體來說，他提到的那個群體是什麼？有很多方法可以建構這樣的東西嗎？如果是這樣，是否有容易實施但難以攻擊的方法？還是我在尋找某種圖書館？此外，如何製作這樣的 $ H_2 $ 可以被視為隨機預言機？
質數q的循環群，使得 DLP 是困難的
形成循環群的簡單技術 $ G $ 素數的 $ q $ 使得潛在的離散對數問題 (DLP) 是（推測）困難的，適用於大型 $ q $ （以千位為單位），是挑選 $ q $ 作為適當大小的隨機素數，使得 $ p=2q+1 $ 是素數，隨機任意整數 $ g $ 和 $ 1<g<p-1 $ 這樣 $ g^q\bmod p=1 $ .
這 $ q $ 循環群的元素 $ G $ 是 $ g^i\bmod p $ 和 $ 0\le i<q $ , 在模乘模下 $ p $ .
的搜尋 $ q $ 可以通過使用篩分技術大大加快去除 $ q $ 這樣要麼 $ q $ 或者 $ 2q+1 $ 能被一個小素數整除。的搜尋 $ g $ 速度很快（平均兩次嘗試就足夠了；通常使用 $ g=2 $ ，然後朝著那個目標選擇另一個 $ q $ 和 $ p $ 如果 $ g^q\bmod p\neq1 $ ).
推測DLP是hard，即：給定 $ y=g^x\bmod p $ 對於未知的隨機 $ x $ 在 $ \mathbb Z_q $ , 計算上不可能找到 $ x $ . 目前解決此類問題的公共記錄是768 位的一個實例 $ p $ . 目前對十年安全性的建議是 2048 或 3072 位，但 1024 位仍被廣泛使用。標準組 $ p $ RFC 2409和RFC 3526給出了一種稍微特殊的形式，使模組化簡化更容易。
在不犧牲安全性（推測性）的情況下獲得加速的一種方法是減小 $ q $ ，在一定限度內，與 $ q $ 一個除數 $ p-1 $ . 那是一個施諾爾集團。請參閱Alfred J. Menezes、Paul C. van Oorschot 和 Scott A. Vanstone 的應用密碼學手冊的第 3.6.6 節，以及他們的算法 11.54。使用 256 位 $ q $ 對於 2048 位 $ p $ 被認為與使用 2047 位的一樣安全 $ q $ ，值得推薦。160 位 $ q $ 經常在什麼時候使用 $ p $ 是 1024 位的。執行時間大約與位大小成正比 $ q $ ，並且大致與位大小的平方成正比 $ p $ .
緩慢是一個經常擔心的問題！計算的常用算法 $ y=g^x\bmod p $ 表現得像 $ 3(\log_2(p)/w)^2\log_2(x) $ 的乘法 $ w $ -位字和添加的 $ 2w $ 位結果。對於使用 32 位字的軟體實現，2048 位 $ p $ 和 2047 位 $ x $ ，我們正在談論超過 2500 萬個 muladds。使用彙編語言的仔細實現大放異彩，包括GNU 多精度算術庫（它具有解釋語言的包裝器，包括gmpy2）。另外：請注意，包括時間在內的邊通道洩漏是一個安全問題，主要取決於模冪運算的實現。
還有其他結構在有限域上使用橢圓曲線，在不犧牲安全性的情況下提供另一個很大的加速（推測）；還有其他不太常見的技術。下面我會堅持一個 $ G $ 一個子群 $ \mathbb Z_p^* $ 素數的 $ q $ ， 和 $ p=r\cdot q+1 $ ; 並 $ r=2 $ （最初討論的簡單技術）除非另有說明。
H 1的建設
想要的是一個帶有輸出的散列 $ \mathbb Z_q $ ,（推測）在隨機預言模型中是安全的（即：在計算上與具有相同輸入和輸出域的隨機函式無法區分，知道 $ H_1 $ 除了該公共定義的一些任意常數部分）。
一個問題是，通常的加密散列具有有限的寬度；最常用的是SHA-512和 2047 位 $ q $ 寬度幾乎是原來的 4 倍。如果我們處理了消息 $ \alpha\in{0, 1}^* $ 使用 SHA-512，無論我們如何對結果進行後處理， $ \mathbb Z_q $ 將是可達的（小於 $ 2^{-1534} $ ); 並且為了 $ H_1 $ 為了在隨機預言模型中是安全的，它必須在計算上不可能辨識出 $ \mathbb Z_q $ 屬於那個部分。另一個問題是，對於隨機輸入，通常的加密雜湊的每個輸出位大約是均勻分佈的，但是 $ \mathbb Z_q $ 表示為與 $ q $ 它的高階位非常偏向 0，除非 $ q $ 剛好低於二的冪。
我們可以通過連接幾個獨立的雜湊來解決大小問題，我們可以使用HMAC -SHA-512 和不同的公鑰來獲得；以及一種近似正確分佈的方法 $ \mathbb Z_q $ （超出計算可檢測性）生成的位至少（比方說）比 $ q $ ，然後是模減少模 $ q $ （根據 big-endian 約定將位串同化為整數）。
用這種方法和 $ q $ 2047 位，我們需要 $ \lceil(2047+128)/512\rceil=5 $ 連接 HMAC-SHA-512。留言 $ \alpha\in{0, 1}^* $ 雜湊可能是 $$ H_1(\alpha)=\big(HMAC(\text{0x01},\alpha)|HMAC(\text{0x02},\alpha)|\dots |HMAC(\text{0x05},\alpha)\big)\bmod q $$
注意：使用時 $ q $ 最多 384 位，如果 $ p $ 仍然足夠大，我們不需要連接多個雜湊的複雜性。
H 2的建構
需要的是組中輸出的散列 $ G $ 在第一部分中建構，（推測）在隨機預言模型中是安全的。但是有一個問題！
問題中的引用與 Joseph K. Liu 和 Duncan S. Wong 的Linkable ring signature: security models and new scheme的第 3.1 節完全匹配，在ICCSA 2005 的訴訟中，我通過向Google Books詢問被視為隨機預言的不同雜湊函式找到了. 在問題的引用之後是：
假設對於任何 $ \alpha\in{0, 1}^* $ , 的離散對數 $ H_2(\alpha) $ 到基地 $ g $ 是棘手的。
解釋這個附加要求的合理方法是知道 $ H_2 $ , 並給定 $ \alpha $ ，一個人應該在計算上無法找到 $ x $ 和 $ g^x=H_2(\alpha) $ .
適應雨披的偉大建議，使其不管 $ r $ , 對於 2048 位 $ p $ 我們可以用 $$ H_2(\alpha)=\Big(\big((HMAC(\text{0x11},\alpha)|\dots|HMAC(\text{0x15},\alpha))\bmod(p-1)\big)+1\Big)^r\bmod p $$
這通過生成隨機元素來工作 $ u $ 的 $ \mathbb Z_p^* $ , 和計算 $ v=u^r\bmod p $ . 結果在 $ \mathbb Z_q $ ， 因為 $ v^q\equiv{(u^r)}^q\equiv u^{rq}\equiv u^{p-1}\bmod p\equiv 1\pmod p $ ，最後一步使用費馬小定理。和 $ u $ 基本一致 $ \mathbb Z_p^* $ , $ v $ 基本上是一致的 $ G $ .
我希望我能證明我的直覺，一般來說 $ r $ , 求解 $ g^x\bmod p=v $ 為了 $ x $ 很難，包括知識 $ u $ ; 並且我們可以擺脫生成 $ u $ 在 $ \mathbb Z_q^* $ 而不是在 $ \mathbb Z_p^* $ . 雨披證明了兩者 $ r=2 $ .
警告：我試圖關注的許多關於環簽名和電子投票的論文都讓我失望了；我經常想知道關於安全性的確切假設和證明，以及這在實踐中意味著什麼。有些使用雙線性配對；雖然有圖書館，但我建議只有在上述所有數學都作為證據的情況下才深入研究這些東西。
我敢肯定，只有一小部分投票人口可以就這些主題形成明智的意見。我的結論是，使用這樣的投票方法直接違背了一個主要目標：選民相信結果。