如何僅使用加法和乘法在同態加密中構造任意布爾門？

我最近對同態加密感興趣，特別是如何構造布爾門來對加密數據進行任意電路算術而不解密它。

我聽說你所需要的只是任意加法和乘法運算來任意構造可以對密文進行操作的布爾門，特別是與非門，它在功能上是完整的，或者換句話說可以表示任何布爾門及其任何組合。

那麼這些布爾門是如何僅用加法和乘法運算建構的呢？

我們寫 $ \odot $ 用於乘法 $ \mathbb F_2 $ , 這與布爾 AND 操作相同。同樣我們寫 $ \oplus $ 用於添加 $ \mathbb F_2 $ 這與布爾 XOR 操作相同。

如果我們引入一個設置為 1 的輔助（加密）操作數，這兩者一起可以產生任何布爾運算。在這種情況下，與非門可以通過以下方式實現 $ \mathrm{NAND}(a,b)=a\odot b\oplus 1 $ . 香農定理比說所有其他布爾運算都可以產生。

引用自：https://crypto.stackexchange.com/questions/102707