零知識RSA公鑰
假設鮑勃有 $ k>1 $ RSA 公鑰 $ (e_i, n_i) $ 在不知道他們相應的私鑰的情況下。Alice 也擁有所有的公鑰，但也只有其中一個的私鑰，比如說， $ (d_j, n_j) $ . 她是否有可能向 Bob 證明她至少擁有一個私鑰，而無需透露 $ j $
編輯：根據 fgrieu 建議更改符號
是的，甚至不需要互動也是可能的（Bob 不需要發送任何東西給 Alice）。該方法稱為“環簽名”。
假設她想簽署一條消息，例如“我是 Alice，特此向 Bob 證明我知道其中一個密鑰”。她雜湊它得到 $ m $ .
Alice 現在生成一個隨機值 $ r_i $ 對於每個公鑰 $ k_i $ 並加密它們以獲得 $ y_i $ .
請注意，他們都 $ y_i $ 是不可預測的偽隨機值。唯一的 $ y_i $ 她可以選擇的是屬於她的鑰匙 $ k_j $ ，她只是選擇 $ y_j $ 並簽名以獲得 $ r_j $ ( $ r_j $ 看起來像所有其他隨機數據）
現在她可以選擇 $ y_j $ 所以所有的異或 $ y_i $ 等於 $ m $ .
她發送消息和所有 $ r_i $ 給 Bob （如果訂單不明確，請添加備註 $ r_i $ 屬於哪個鍵）
為了驗證，Bob 只加密了每個 $ r_i $ 用公鑰 $ k_i $ 得到 $ y_i $ , 對它們進行異或併檢查它是否等於 $ m $ .
由於所有 $ y_i $ 就像隨機數一樣，當您不知道密鑰時，不知道私鑰就無法偽造簽名。此外，無法判斷哪個 $ y_i $ 和 $ r_i $ 不是隨機生成的，因為它們看起來都是隨機的。
重要編輯：我忘記了環簽名中的對稱加密步驟。在異或步驟之間應該應用對稱加密。這仍然允許 allice 恢復 $ y_i $ 她需要，但會使攻擊更加困難。有關更多詳細資訊，請查看維基百科