RSA 模數和素階群之間的零知識證明
假設有一個 RSA 公鑰 $ (e,n) $ 這樣的分解 $ n $ 證明方和驗證方都不知道。我們還有一個主要訂單組 $ G $ 和一個發電機 $ g $ 為組。為了 $ m\in QR_n $ ，是否有零知識證明協議來證明 $ C_1=m^e $ 和 $ C_2=g^m $ , 對於公共價值觀 $ (C_1, C_2, e, n, g) $ ?
**TL,DR：**簡單的結合 $ \Sigma $ -protocols 可以用零知識證明這個複合語句。但是，證明有點大。
首先，讓我們將復合語句分解為更簡單的語句。觀察到本質上你想以零知識證明 $ C_1=m^e $ 和 $ C_2=g^m $ 即以下關係 $ \mathcal{R}(x,\omega) $ ( $ x $ 是公共參數並且 $ \omega $ 是證人）持有：$$ \mathcal{R}={((C_1,C_2),(m,l)):m\in QR_{N}\land C_1=m^e\bmod{N}\land C_2=g^m\bmod{p}}, $$ 在哪裡 $ l $ 是平方根 $ m\bmod{N} $ ，即見證人是 $ (m,l) $ 一對。為簡單起見，讓我們對基本語句使用以下符號：$$ \mathcal{R}1={((C_1,C_2),(m,l)):m\in QR{N}}, $$ $$ \mathcal{R}_2={((C_1,C_2),(m,l)): C_1=m^e\bmod{N}}, $$ $$ \mathcal{R}_3={((C_1,C_2),(m,l)):C_2=g^m\bmod{p}}. $$
請注意，這兩個基本語句 $ \mathcal{R}_2 $ 和 $ \mathcal{R}_3 $ 很容易證明 $ \Sigma $ -協議，因為這兩種關係都證明了在群同態下的原像知識（即， $ w $ 令人滿意的 $ x=\phi(w) $ ）。如果是 $ \mathcal{R}_2 $ 群同態 $ \phi(\omega)=\omega^e $ ， 而在 $ \mathcal{R}_3 $ , 同態是 $ \phi(\omega)=g^{\omega} $ . 這些是非常標準的陳述，您可以在Bangerter 等人中找到如何證明同態的原像。或在Boneh-Shoup 書中，等等。
證明 $ \mathcal{R}1 $ 乍一看有點棘手，因為 $ m $ 需要保密，我們想證明 $ m $ 是二次餘數，即， $ m\in QR_N $ . 在 RSA 密碼系統的幾乎所有部署中 $ e $ 很奇怪（我假設您的應用程序也是這種情況），所以 $ C_1=m^e\in QR{N} \iff m\in QR_{N} $ . 我還假設加密器知道 $ l $ , 的平方根之一 $ m $ ，因為分解是未知的。如果加密者不知道這樣的 $ l $ ，那麼它不能證明它是二次餘數，因為它不知道分解。鑑於這個討論，現在 $ \mathcal{R}_1 $ 本質上需要證明以下陳述：$$ \mathcal{R}_1={((C_1),(l)):C_1=l^{2e}\bmod{N}}, $$ 這再次證明了群同態的原像知識。我們知道如何證明這個陳述。
結合所有這些以獲得複合語句的零知識證明 $ \mathcal{R} $ ，驗證者只需要為所有基本語句發送相同的隨機挑戰（儘管隨機挑戰在協議的重複中是不同的！）。
證明的大小是多少？為了 $ \Sigma $ - 以未知順序分組的協議，可靠性誤差大，因此需要重複 $ \Sigma $ -protocol 多次獲得合理的健全性水平。在每次重複中，可靠性誤差減少 $ \approx 1/2 $ . 因此，必須按順序重複該協議以獲得足夠小的知識錯誤（例如， $ 80 $ 需要連續重複才能獲得知識錯誤 $ 1/2^{80} $ ）。這將導致一個證明包括 $ 2280=320 $ 組元素 $ 3 $ 基本語句（其中 2 個語句出現在 RSA 組中，因此我們需要重複多次）。
為了規避這個效率限制，你需要使用一個通用的參考字元串來減少證明的大小。見班格特等人。
希望這會有所幫助！如果我在答案中留下任何灰色區域，請告訴我！