獨立群的離散對數等式
給定兩個不同的安全素數 $ p_1 $ , $ p_2 $ 我們建構子群 $ G_1 $ 素數的 $ q_1 = \frac{p_1-1}{2} $ 和 $ G_2 $ 素數的 $ q_2 = \frac{p_2-1}{2} $ . 讓 $ g_1 $ 成為 $ G_1 $ 和 $ g_2 $ 成為 $ G_2 $ . 我們假設離散對數在兩組中都很難。
愛麗絲隨機選擇一些秘密值 $ s \in \mathbb{Z}_{min{q_1, q_2}} $ . 愛麗絲計算 $ x_1 := g_1^s \in G_1 $ 和 $ x_2 := g_2^s \in G_2 $ 和一個加密雜湊 $ H(s) $ .
愛麗絲發送 $ x_1 $ , $ x_2 $ 和 $ H(s) $ 通過安全通道發送給 Bob。
是否有一些實用的方法可以讓 Bob 確定 Alice 確實已經發送了值 $ x_1 = g_1^a $ 和 $ x_2 = g_2^b $ 這樣 $ a = b $ ? 如果沒有，Alice 能否提供額外的數據而不洩露？ $ s $ 說服鮑勃？
這個問題有點與“我們如何證明兩個離散對數相等？ ”有關。然而，在我們的例子中，使用了來自兩個不同組的兩個生成器，而不是來自一組的兩個生成器。
編輯：關於 poncho 和 Yehuda Lindell 的評論，我進一步澄清了我所說的“獨立群體的離散對數相等”的意思：
我想使用以下定義 $ dlog_{g} $ :
$ {dlog}_g(g^e) := $ 最小的 $ x \mid x \geqslant 0, g^x \equiv g^e \pmod p $
給定 $ s_1 = dlog_{g_1}(g_1^s) $ 和 $ s_2 = dlog_{g_2}(g_2^s) $
然後 $ dlog_{g_1}(g_1^s) \ $ 等於 $ \ dlog_{g_2}(g_2^s) \ $ 當且當 $ \ s_1 = s_2 $
讓我為簡單起見假設 $ q_1 \leq q_2 $ . 你想證明離散對數 $ x_1 $ 在 $ G_1 $ 與離散對數相同 $ x_2 $ 在 $ G_2 $ ，並且這個被視為整數的離散對數小於 $ q_1 $ . 這表明您應該依靠零知識證明來證明整數上的關係。進行這種證明的最自然的方法是對一組未知順序進行工作，因為直覺地說，如果證明者不知道該組的順序，他就不能以該順序為模來減少指數 - 並且關係應該保持不變整數。
所以讓 $ G $ 是一組未知階數，其中離散對數很難計算（例如，RSA 組的平方子組）。讓 com $ (\cdot) $ 是一個完全隱藏的整數承諾方案 $ G $ （例如Fujisaki Okamoto 承諾方案）。讓 $ s \le q_1 $ 成為你的秘密指數。此外 $ x_1 = g_1^{s} \in G_1 $ 和 $ x_2 = g_2^s \in G_2 $ , 證明者發送一個承諾 com $ (s) = c $ 超過 $ G $ .
讓我們以 Lindell 教授建議的協議為基礎。考慮對該協議進行以下修改：
- 答案不是模計算的 $ q_1\cdot q_2 $ ，但它們是在整數上計算的。為了不破壞零知識屬性，遮罩 $ r $ 應該採取，比方說，長 160 位 $ s $ ，以便在統計上掩蓋 $ e\cdot s $ 在整數上。
- 證明者證明知識 $ s $ 這是的離散對數 $ x_1 $ 和 $ x_2 $ 和承諾的價值 $ c $
- 證明者還證明了在 $ c $ 低於 $ q_1 $ . 這樣做的經典方法如下：雙方玩家都計算 $ c’ $ 從 $ c $ 和 $ q_1 $ , 一個承諾的價值 $ s’ = q_1 - s $ （Fujisaki-Okamoto 方案是同態的，它本質上是 com $ (m;r) = g^mh^r $ ）。請注意 $ s \leq q_1 $ 相當於 $ s’ \geq 0 $ . 此外，根據拉格朗日的經典結果，一個整數是正的當且僅當它可以寫成四個平方的和。因此，證明者計算這個分解 $ s’ $ 成四個平方的總和（通過 Rabin-Shallit 算法），送出給它們，並證明 $ s’ $ 是這些承諾值的平方和。這種協議被稱為範圍證明，並在幾篇論文中進行了描述，例如這篇論文。
一旦這個協議完成，驗證者就會確信證明者知道一個整數 $ s \leq q_1 $ 這樣 $ g_1^s = x_1 $ 和 $ g_2^s = x_2 $ . 人們可以改進協議以使其更有效，但我試圖使答案盡可能直覺。
我很確定正常的 DDH sigma 協議也應該在這里工作。為了使事情正常進行，需要進行一些更改。具體來說：
- 證明者隨機選擇一個 $ r\in\mathbb Z_{q_1\cdot q_2} $ 併計算 $ h_1 = g_1^r \mod p_1 $ 和 $ h_2 = g_2^r \mod p_2 $ , 並發送 $ h_1,h_2 $ 給驗證者。
- 驗證者發送隨機挑戰 $ e\in{0,1}^t $ .
- 證明者回复 $ z=r+es \mod q_1\cdot q_2 $
- 驗證者檢查 $ g_1^z = h_1 \cdot x_1^e \mod p_1 $ 和 $ g_2^z = h_2 \cdot x_2^e \mod p_2 $ .
這一切都應該很容易為健全性工作（但需要檢查）。唯一的問題是零知識，因為 $ r $ 不是隨機選擇的 $ \mathbb Z_q $ 但在 $ \mathbb Z_{q_1\cdot q_2} $ . 為了給您留下一些有趣的工作要做，應該檢查這一點。所以，試著證明它，然後讓我們知道:-)。