一組整數模安全素數的離散對數的位強度
預賽
讓 $ p $ 是一個安全的素數。讓 $ \mathbb{Z}_p^* $ 是整數模的乘法群 $ p $ . 我們有 $ \mathbb{Z}_p = {,a \in \mathbb{Z} \mid 1 \le a \lt p,} $ .
讓 $ g \in \mathbb{Z}_p $ 是一個原始元素 $ \mathbb{Z}_p $ . 讓 $ h $ 成為其中的一個元素 $ \mathbb{Z}_p $ .
我們將一組整數模安全素數(DLPS) 的離散對數問題定義為：
DLPS：查找整數 $ k $ 這樣 $ ;;1 \le k \lt p;; $ 和 $ ;;g^k \equiv h \pmod p $ .
我們假設求解 DLPS 的最佳算法是離散對數的數域篩，其預期執行時間為 $$ L_p\left[1/3, \sqrt[3]{64/9}\right] ,=; e^{\textstyle \left(\sqrt[3]{64/9}+o(1)\right)\big(\ln p\big)^{1/3}\big(\ln \ln p\big)^{2/3}} $$
問題
如果我們選擇 $ p $ 是一個 2048 位的安全素數，至少等於 $ 2^{2047} $ ，那麼求解 DLPS 所需的預期算術運算數大約等於：
$$ e^{\textstyle \left(\sqrt[3]{64/9}+o(1)\right)\big(\ln 2^{2047}\big)^{1/3}\big(\ln \ln 2^{2047}\big)^{2/3}} \ \approx , e^{\textstyle \big(1.923\big)\big(1419\big)^{1/3}\big(7.258\big)^{2/3}} \ \approx , e^{\textstyle \big(1.923\big)\big(11.24\big)\big(3.749\big)} \ \approx , e^{\textstyle \big(81.00\big)} \ \approx , 2^{116.9} $$
這是對的嗎？
我應該確保 $ (p+1) $ 有很大的素因數嗎？（使 $ p $ 強素數）
如果我沒記錯的話，這是顯示 DLPS 的安全級別與 $ p $ :
2019 年 6 月 7 日編輯：這是我將使用此離散對數問題的上下文：
語境
我正在創建一個線上大型多人影片遊戲。在這個遊戲中，玩家圍繞一個角色移動並在一個持久的虛擬世界中執行動作。我使用離散對數問題作為遊戲貨幣。角色執行的每個動作（四處走動、購買物品、投擲彈丸等）都必須由玩家支付 CPU 時間。這樣一來，我就不必花時間監視玩家來檢測作弊者（多個帳戶、農業機器人等），因為作弊者通常會在我的遊戲中明確允許這樣做。
它是這樣工作的：為了獲得在虛擬世界中執行動作的權利，玩家向遊戲伺服器請求離散對數挑戰。然後，伺服器為生成器生成隨機值 $ g $ 和指數 $ k $ , 計算結果 $ h \equiv g^k \pmod p $ ，並發送的值 $ g $ 和 $ h $ 給玩家。然後玩家的客戶端計算指數的值 $ k $ 並將其發送回伺服器以接收積分。
的價值 $ p $ 永遠不會改變，價值觀 $ g $ 和 $ k $ 每個挑戰都會有所不同。玩家可以通過設置指數值的位長上限來選擇挑戰的難度 $ k $ （獲得的積分數量與所花費的 CPU 時間量成正比）。
對於工作量證明方案，您可能最好制定 $ p $ 足夠大，您不必擔心 NFS（例如 2048 位或更多），或者使用橢圓曲線組（例如 P256 或 Curve25519）。
相反，你會調整一些東西，使一般攻擊（例如 Big-Step-Little-Step）是最佳攻擊，並使用它來選擇困難（範圍 $ k $ ); 如果求解器知道 $ 0 < k \le M $ ，那麼這些通用搜尋將花費大約 $ \sqrt{M} $ 組運算（模乘法、橢圓曲線加法），這是搜尋者能做的最好的事情（假設他對組結構沒有任何進一步的了解——這就是我們試圖通過使 NFS 不可行來確保的）。
現在，雖然這可以作為“總工作量證明”，但我不確定它是否真的滿足您的要求，因為具有大量並行性的人（例如殭屍網路農場）可能能夠加速這種計算顯著地。
更好的方法可能是讓服務發布整數 $ g $ , $ k $ 和一個複合 $ n $ ，並要求客戶端計算 $ g^{2^k} \bmod n $ ; 這種類型的操作不能很好地並行化（因為每個平方操作必須按順序進行），並且伺服器（誰知道 $ n = pq $ ) 可以通過檢查聲稱的答案來驗證這一點 $ A $ 由關係 $ A \equiv g^{2^k \bmod p-1} \pmod p $