公鑰生成 - 素數重用
給定以下陷門承諾方案
- 密鑰接收者： $ x_B \in_u Z_q $
- 公鑰接收器： $ y_B = g^{x_B} \mod p $
這裡， $ p=qk+1 $ 對於兩個素數 $ p,q $ 和 $ k \in Z $ . 和 $ g $ 是子組的生成器 $ G_q $ 的 $ Z_p^{} $ , 有序的 $ q $ .
對發件人送出 $ w \in Z_q $ , 他選擇 $ r \in_u Z_q $ , 承諾是 $ c=g^wy_B^r \mod p $ . 為了開啟承諾，他發送 $ (w,r) $ .
我的問題是：如果我想為數百萬不同的發件人創建數百萬個這些公鑰，我可以重複使用嗎 $ p,q $ ?
修復組 $ G $ 大素數的 $ q $ . 修復生成器 $ g \in G $ . 對於公鑰 $ h \in G $ 除了身份，一條消息 $ m \in \mathbb Z/q\mathbb Z $ , 和隨機化 $ r \in \mathbb Z/q\mathbb Z $ , 定義承諾 $ c = g^m h^r $ .
使固定 $ h $ . 認為 $ r $ 均勻分佈在 $ \mathbb Z/q\mathbb Z $ . 然後 $ h^r $ 均勻分佈在 $ G $ ， 自從 $ G $ 有素數所以 $ h $ 是一個發電機，所以只要 $ x $ 獨立於 $ r $ , $ c = g^m h^r $ 也是均勻分佈的。因此，一個對手給出了承諾 $ c $ 對消息一無所知 $ m $ , 無論分佈在 $ m $ 是——承諾是理論上隱藏的資訊。
假設你有一個隨機算法 $ A\colon G \to (\mathbb Z/q\mathbb Z)^4 $ 那，給定 $ h $ , 計算 $ (m, r, m’, r’) = A(h) $ 和 $ m \ne m’ $ 這樣 $ g^m h^r = g^{m’} h^{r’} $ 機率很高。那麼必然 $ r \ne r’ $ ， 和 $ g^{(m - m’)(r’ - r)^{-1}} = h $ ，即 $ (m - m’)(r’ - r)^{-1} $ 是的離散對數 $ h $ 在基地 $ g $ , 這樣我們就可以解決離散對數問題 $ G $ 隨機算法具有高機率和可忽略的額外成本 $ A’(h) = (m - m’)(r’ - r)^{-1} \bmod q $ 在哪裡 $ (m, r, m’, r’) = A(h) $ . 因此，可以打破承諾的算法可以用作算法中的子程序，以高機率計算離散日誌，而附加成本可以忽略不計——承諾是計算綁定的。
當然，誰知道 $ x $ 這樣 $ h = g^x $ 可以通過計算打破承諾 $ r’ = (m - m’) x^{-1} + r $ 對於任何消息 $ m $ 和 $ m’ $ 他們的選擇。所以應該選擇這個組，讓任何人都幾乎不可能計算 $ x = \log_g h $ ，但就像在有限域 Diffie-Hellman 或 Schnorr 簽名或 DSA 中一樣，同一組可以被許多密鑰對使用 $ (x, g^x) $ .
我們應該使用什麼組 $ G $ ? 阻止像 Pollard’s 這樣的通用離散對數算法 $ \rho $ , $ q $ 必須至少 $ 2^{256} $ 或者。兩個明顯的選擇是 Schnorr 組，即order- $ q $ 的子群 $ (\mathbb Z/p\mathbb Z)^\times $ 在哪裡 $ p $ 必須至少 $ 2^{2048} $ 左右阻止指數演算，或一些橢圓曲線上的一組 $ E/k $ 在某個領域 $ k $ 至少 $ 2^{256} $ 元素左右。雖然對手的力量比他們學習的 Diffie-Hellman 環境中的能力要有限一些 $ \gamma^x $ 對於任何 $ \gamma $ 他們選擇的標準遠不止這些：對於有限域， $ p $ 必須選擇抵抗SNFS；對於橢圓曲線，有很多事情需要擔心。