“全同態加密模費馬數”方案中“整數模 4”的含義

我的問題是指Antoine Joux 的論文“Fully homomorphic encryption modulo Fermat numbers”。在第 3 頁，作者描述了系統的一個基本概念：

與許多 FHE 系統一樣，我們處理嘈雜的消息。在我們的例子中，每個塊的高位用於保存有效位，而低位包含雜訊。使系統工作的基本恆等式是給定兩個位 x 和 y，我們有：x + y = 2(x ∧ y) + (x ⊕ y)。因此，如果我們可以將兩位的值作為整數相加，或者甚至作為模 4 的整數，我們同時計算 AND 和 XOR 門。

我不明白“整數”和“整數模 4”之間的區別。如果我們只有兩個變數持有一個位，那麼兩者之和最多可以是 2。那麼使用模 4 環的必要性是什麼？為什麼不取模 3、取模 8 或任何其他數字？

我認為 Antoine Joux 說模 4 只是因為他明確使用兩位（xor 的最低有效位和 and 的最高有效位），儘管這個等式確實成立 $ \mathbb{Z} $ 即使您減少了 mod 3，正如您所注意到的。

事實上，在論文的某些地方，他甚至定義了一個函式來同態地提取一點。

減少模一個更大的整數（如 mod 8）也可以，但它會是一個矯枉過正。

這裡的重點是，如果你能拿兩個位，在外面操作它們 $ \mathbb{Z}_2 $ ，然後獨立提取得到的位，然後就可以執行一套完整的邏輯二進制門。

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