基於離散對數的承諾方案中的作弊
問題：
考慮以下承諾方案：
公共參數：大素數 $ q $ 和 $ p $ 這樣 $ p = 2\cdot q + 1 $ , 和兩個生成器 $ g, g’ $ 一個 $ q $ -階子群 $ \mathbb Z_p^* $ .
- 愛麗絲承諾 $ t $ 在 $ \mathbb Z_q $ 通過統一採摘 $ r $ 從 $ \mathbb Z_q $ , 並發送 $ g^t \cdot g’^r $ .
- 她通過發送打開承諾 $ s $ 和 $ r $ .
- 假設雙方都是多時間有界的。
- 如果 Bob 選擇了公共參數，他能以某種方式作弊嗎？（Alice 以 poly time 驗證參數）
嘗試的解決方案：
如果他能作弊，我認為鮑勃需要選擇 $ q $ 和 $ p $ 以一種聰明的方式，因為即使他選擇 $ g $ 和 $ g’ $ 為了平等，他被困在計算離散對數上，這在多時是不可能的。
我想也許鮑勃可以選擇 $ q $ 是一個 Carmichael 數，那麼 Alice 會認為它實際上是素數（通過 Miller-Rabin 算法檢查）。
我遇到了兩個問題：
- 我不確定這對他解決問題有多大幫助——他可以解決它的主要因素 $ q $ 並使用 CRT，但如果因素不夠小，它仍然是指數級的。
- 也許沒有素數 $ p $ 這樣 $ p=2q+1 $ 對於卡邁克爾數 $ q $ .
我認為我的解決方案由於上述問題而失敗……希望能指出正確的方向。
假設 Alice 驗證：
- $ p = 2q + 1 $ 和 $ p, q $ 主要
- $ g, g’ $ 是秩序的產生者 $ q $
那麼鮑勃就不能作弊。
首先請注意 $ g $ 和 $ g’ $ 生成相同的子組，使得 $ g’ = g^\alpha $ 對於某個整數 $ \alpha $ . 給定一個簽名值 $ s = g^t g’^r = g^{t + \alpha r} $ ， 有 $ q $ 可能的消息 $ t’ \bmod q $ ，並且對於每個 $ t’ $ 存在一個獨特的價值 $ r’ \bmod q $ 這樣
$$ r’ \equiv \frac{t - t’ + \alpha r}{\alpha} \pmod q $$ 和：
$$ g^tg’^r \equiv g^{t’}g’^{r’} \pmod p $$ 無需進一步了解 $ t $ 或者 $ r $ , 每對 $ (t’, r’) $ 滿足簽名的可能性相同。所以如果鮑勃只知道 $ (p, q, g, g’, s) $ ，他不能從簽名中推斷出任何資訊。
請注意，如果 Alice 知道 $ \alpha $ ，她可以通過計算作弊 $ r’ $ 對於任何消息 $ t’ $ 並揭示 $ (t’, r’) $ 代替 $ (t, r) $ .