Algorithm-Design
驗證加密值斷言的算法設計
我正在嘗試設計某種協議，但我被卡住了，需要一些幫助..
給定 $ (a,b,c)\in \mathbb{N}^+ $ 和 $ a + b = c $
我需要通過必須驗證的第三方發送 a、b 和 c 的非對稱加密版本 $ a + b = c $ 但是這個第三方無法訪問這些數字，只能訪問它們的加密值。
我會很感激一些建議。
您的問題有兩種自然的解決方案。
第一個是依賴加法同態加密方案。在這樣的方案中，給定兩個數字的加密 $ a $ 和 $ b $ ，只要給定公鑰，任何人都可以同態計算他們總和的加密， $ a+b $ （通常取模某個值 $ M $ ，可以將其設置得足夠大，以便在給定值的範圍內不會發生溢出 $ a,b $ ).
如果值 $ (a,b) $ 足夠小，這可以使用ElGamal 加密方案來實例化，並在指數中使用消息（解密然後需要計算離散日誌）。如果輸入可能很大，一個很好的選擇是使用Paillier 加密方案，它沒有這麼小的輸入要求。
使用這樣的密碼系統，您想要的協議很簡單：只需發送加密 $ a $ 和 $ b $ 給第三方，讓他計算加密 $ a+b=c $ 獨自一人——這樣，他自動確信第三個密文確實加密了 $ a+b $ .
如果您無法真正選擇要使用的加密方案，或者出於其他原因想要依賴不同的加密方案，則上述方法的替代方法是使用零知識證明。將三個密文發送給第三方後，您可以與該方進行零知識證明，證明第三個密文加密了前兩個密文的總和 - 這不會洩露有關密文內容的任何資訊，除了事實證明該陳述是真實的。這種線性語句的零知識證明對於大多數標準公鑰加密方案都是已知的（理論上它們可以設計用於任意加密方案，甚至例如 AES，但對於沒有代數結構的加密方案來說效率非常低），使案例如