用於 Paillier 公鑰正確性的 ZKIP
我在類似於心理撲克的協議中使用 Paillier 密碼系統。在協議開始時，每個玩家生成一個 Paillier 公鑰 $ (n,g) $ .
在協議的後期，玩家可以透露任何用他的公鑰加密的消息（通過透露消息和使用的隨機器）。其他玩家可以輕鬆驗證此消息+隨機器確實加密為原始密文。但是，他們可能無法保證這是該密文的唯一解密。
為此，有必要在生成他的公鑰後，每個玩家證明這是一個正確的 Paillier 公鑰（即 $ \gcd(\text{L}(g^\lambda !!!\mod n^2), n) = 1 $ ，或任何等效語句）。
我能想到的唯一方法是：
- 證明者生成 $ k $ 公鑰 $ K_1, \dots, K_k $
- 驗證者隨機選擇 $ i \in {1, \dots, k} $
- 證明者揭示所有公鑰的私鑰，除了 $ K_i $
- 驗證者檢查所有顯示的密鑰是否滿足條件，如果滿足，則假設 $ K_i $ 也是有效的密鑰
然而，作弊的機率只是線性下降（ $ 1/k $ ) 使用這種方案（而不是指數地 ( $ 1/2^k $ ) 使用大多數 ZKIP)，因此實現非常高的安全級別是不可行的。
也可以直接證明解密的唯一性（無需證明密鑰的正確性），例如通過驗證者加密 $ k $ 隨機消息，證明者解密它們並證明結果是相同的（這可以使用同態屬性在零知識中完成）。不幸的是，我無法確定使用無效密鑰唯一解密的機率是多少，因此這種方案的安全級別是未知的。
有任何想法嗎？
首先，在 Paillier 中 ZKP 和分佈式密鑰生成的尷尬是許多協議使用指數 Elgamal 來處理諸如心理撲克之類的協議的原因。它是加法同態的，但缺點是只能解密小的消息空間。在您的情況下，由於使用者正在打開他們的加密，這似乎很合適。整個協議可以在使用者之間共享的公共密鑰下執行（以分佈式或門檻值方式）。
我不知道 Paillier 中格式良好的密鑰的 ZKP。這只是一個初步的想法。在以下 Paillier 變體中（來自 Encyclopedia of Cryptography and Security）：
應該足以證明 $ n $ 是一個格式良好的 RSA 數（例如CM99）並且證明了 $ \lambda $ 給定 $ y=(g^n)^\lambda $ 為了 $ y=1 $ （例如，離散對數的知識）？
