是否有一組可以符合 CT-Computational Diffie-Hellman 假設的素數順序？
根據本文中的定義，我試圖選擇一個在 Chosen-Target Computational Diffie-Hellman 假設下較難的組，以實現第 10 頁頂部框中定義的不經意傳輸方案（=406） .
（對我來說很嚇人）CT-CDH 假設定義如下（第 7 頁=403）：
讓 $ \mathbb{G}_q $ 是一組素數 $ q $ , $ g $ 成為 $ \mathbb{G}_q $ , $ x\in \mathbb{Z}^*_q $ . 讓 $ H_1 : {0, 1}^∗ \rightarrow \mathbb{G}_q $ 是一個密碼散列函式。對手 $ A $ 給定輸入 $ (q, g, g^x, H_1) $ 和兩個預言機：目標預言機 $ TG(\cdot) $ 返回一個隨機元素 $ w_i \in \mathbb{G}_q $ 在 $ i $ -th 查詢和輔助 oracle $ HG(\cdot) $ 返回 $ (\cdot)^x $ . 讓 $ q_T $ 和 $ q_H $ 是查詢的數量 $ A $ 分別對目標 oracle 和輔助 oracle 進行。
假設：機率 $ A $ 輸出 $ k $ 對 $ ((v_1, j_1), (v_2, j_2), \dots, (v_k, j_k)) $ ， 在哪裡 $ v_i = (w_{j_i})^x $ 為了 $ i \in {1, 2, \dots , k} $ , $ q_H \lt k \leq q_T $ , 可以忽略不計。
應該注意的是，這個假設等價於標準的計算 Diffie-Hellman 假設，當 $ q_T=1 $ ，根據這篇論文。
任何人都可以舉一個符合要求的組的例子嗎？我試過 $ \mathbb{Z}^*_q $ 為了一個素數 $ q $ 在乘法下，但這是有序的 $ q-1 $ ，這顯然不是素數。然而，論文第 12 頁上的複雜性分析是根據模冪計算的。
另外（如果被罵，我可以為此提出一個新問題），如何實施 $ (D_j)^{a_j^{-1}} $ 協議步驟 5 中的操作？我不知道它是否等同於離散日誌問題。
擁有一組素數大小的常用技術 $ q $ 是以素數為模工作 $ p $ 這樣 $ q $ 劃分 $ p-1 $ . 那麼目標群體就是 $ q $ -th 根 $ 1 $ 在 $ \mathbb{Z}_p $ . 要建立這樣一個組，首先選擇 $ q $ ，然後選擇隨機值 $ r $ 直到你找到一個這樣的 $ p = qr+1 $ 是素數。這是DSA 標準中定義的方式。
剩下的部分是：如何建構 $ H_1 $ ，在目標組中產生元素的散列函式？為此，您首先使用產生模數的雜湊函式 $ p $ （例如，您使用以散列數據為種子的PRNG，並生成大小為 $ p $ 直到你找到一個介於兩者之間的 $ 0 $ 和 $ p-1 $ ); 然後，你把這個價值提升到了權力 $ (p-1)/q $ . 結果必然是 $ q $ - 1 的根，整體是一個“散列函式”。
據我所知，這樣的組將滿足 CT-CDH 假設——即沒有已知的方法可以打破它。CT-CDH 是一個比標準 CDH 更“弱”的假設，但沒有證據表明它比標準 CDH 更弱。
對於您的其他問題： $ R $ 知道 $ a_j $ ，它們是隨機的非零整數模 $ q $ . $ R $ 因此可以計算每個 $ a_j^{-1} $ 模組 $ q $ （這是正常的模組化反轉）。在表達式“ $ (D_j)^{a_j^{-1}} $ , $ D_j $ 是一組大小的一部分 $ q $ , 所以任何指數都可以取模 $ q $ .