不知道隨機性的範圍證明
甲方有密文 $ c = (g^r, g^2 h^r) $ ，即在 A 的公鑰下對整數 2 進行加密， $ h $ . 使用的加密方案是 El Gamal 的加法同態變體。這個密文已經被其他方同態修改過，所以A不知道隨機性 $ r $ .
有沒有辦法讓A證明 $ c $ 是非負整數的加密嗎？我發現的所有範圍證明方案似乎都使用了承諾，這需要 A 知道密文中的隨機性。
首先（只是為了確定）： $ (g^r, g^2h^r) $ 不是加密的 $ 2 $ 但是 $ g^2 $ （因為一般解密只會給你 $ g^2 $ ，那麼你就剩下解決 DLOG 的問題了。我假設這在您的方案中不是問題（例如，只有多項式許多有效值可能會被加密）。
第二：不清楚“非負整數”是什麼意思。的所有指數 $ g $ 可以解釋為非負整數。那麼 ne 負整數是多少呢？我假設你裡面有一些數字範圍 $ \mathbb{Z}_{|\mathbb{G}|} $ 您將其解釋為“非負面”。我不會弄亂你想要的範圍證明，只是給你一個 ElGamal 部分的想法。
我會呼叫你想要範圍證明的整數 $ z $ 和你的密文 $ (x,y) := (g^r, g^zh^r) $ （在你的例子中， $ z = 2 $ ）。你承諾 $ z $ 無論您的範圍證明需要什麼承諾。將承諾和密文發送給驗證者。然後你應該證明（例如，使用類似 Schnorr 的協議，請參閱此處的構造 2.5 ）存在密鑰 $ a $ （ElGamal 密鑰）並且你知道 $ z $ 這樣：
- $ h = g^a $ （IE $ a $ 確實是 ElGamal 密鑰）
- $ (x^{-1})^a\cdot y = g^z $ （密文解密為 $ z $ )
- 你的承諾開放給 $ z $ .
然後，使用承諾 $ z $ ，你執行你的範圍證明。
另一種方法可能是省略額外的承諾，只是將範圍證明集成到相同的 Sigma 協議中，其中 $ z $ 已經是其中的一部分。我的猜測是，您找到的範圍證明只需要您送出該值，以便該語句不平凡（“我知道此範圍內的某個整數”本身並不是一個特別有趣的語句），但可能可以結合使用與同一協議中的其他聲明沒有額外的承諾（實際上，ElGamal 密文將是你的承諾 $ z $ ).