為什麼AND門在完全同態加密，BFV方案上是*？
根據將函式表示為 FHE 電路
A*B，在明文只有0或1係數的情況下， FHE 加密數據的與門就是。請記住，在 BFV FHE 方案中，它對多項式進行加密，我們可以設置多項式係數的最大值。因此，如果我們將最大值設置為
1，那麼我們可以輕鬆地進行二進制門。例如：1 + 0x^1 + 1x^2 + 0x^3 + 0 + 1x^1 + 1x^2 + 0x^3 ______________________ 1 + 1x^1 + 0x^2 + 0x^3
+多項式的 OR 門本質上也是如此。但我很難理解*為 AND，特別是因為這些多項式的乘法是mod x^n +1，多項式的次數在哪裡n。所以這不是一個簡單的乘法。為什麼
AND = *？
與門表示係數域中的乘法，在這種情況下，係數域是兩個元素 0 和 1 的二進制域。類似地，該域加法的作用與異或門相同。
如果我們知道如何對係數進行加法和乘法運算，我們可以將其擴展到使用算術性質的多項式的加法和乘法。在加法的情況下，這只涉及匹配係數和加法。在乘法的情況下，我們需要使用分配律。在您的範例中，為 XOR 和 & 為 AND 編寫 # 我們必須配對其冪加起來為相同值的單項式的係數
(1 + 0x^1 + 1x^2 + 0x^3)*(0 + 1x^1 + 1x^2 +0 x^3)
= (1&0) + (1&1 # 0&0)x^1 + (1&1 # 0&1 # 1&0)x^2 + (1&0 # 0&1 # 1&1 # 0&0)x^3 +
+ (0&0 # 1&1 # 0&1)x^4 + (1&0 # 0&1)x^5 + (0&0)x^6
= 0 + 1x^1 + 1x^2 + 1x^3 + 1x^4 + 0x^5 + 0x^6
首先，請注意 BFV 傳統上是用算術電路來表達的，而不是布爾電路。例如，初始論文有一個消息空間的形式 $ R_t := \mathbb{Z}_t[x] / (\Phi_n(x)) $ ， 在哪裡 $ \Phi_n $ 是個 $ n $ th 分圓多項式（當 $ n $ 是二的冪 這很簡單 $ x^n+1 $ ）。這是相對重要的，因為算術電路的基本建構塊不是OR 和 AND，而是（mod $ p $ 版本）XOR 和 AND，略有不同。
至於您對 BFV 乘法的問題，我認為您稍微誤讀了 BFV 的規範。通常（比如在最初的論文中）消息空間被指定為 $ R_t $ ，如前所述，它是一個多項式環（當 $ n $ 是 2 的冪） $ \bmod x^n+1 $ . 因此，要使我們的加密方案完全同態，我們需要能夠對密文*進行消息空間的加法和乘法運算。*消息空間的乘積是 $ \bmod x^n+1 $ （和 $ \bmod t $ ，但無論如何），正如你所指出的。這就是說算術存在 $ \bmod x^n+1 $ 是該方案完全同態的數學要求，因此該形式的乘積是預期的，而不是問題。
當然，應用程序設計者可能不想使用這種“有趣的算法”。這是圖書館設計者以後要解決的問題。例如，“解決”這個問題的一種方法（這很天真——我猜有更好的解決方案）是只將消息編碼為多項式的常數項。當限制為常數多項式時，應該相對簡單地看到這種“有趣的乘法”成為標準乘法。
還有其他事情可以做，例如可以允許以下形式的多項式 $ m(x) = m_0+m_1x $ 如果您知道您正在評估的電路的乘法深度最多為 $ \log_2 n $ ，或更一般地 $ m(x) = \sum_{i =0}^p m_i x^i $ 如果乘法深度最多為 $ \log_{1+p} n $ . 這僅僅是因為在這個深度範圍內，不能產生一個多項式 $ \geq n $ ，所以乘法可能“環繞”這一事實並不重要。當然，我確信有更聰明的想法可以用“有趣”的算術來模擬“標準”算術，但這與理解 BFV 確實是正交的。
還值得一提的是，您的評論
但它需要是係數方面和多項式上的，而不是多項式本身
聽起來您可能正在尋找規範嵌入的想法。具體來說，大約十年前有人注意到，如果我們想要一個類似數組的數據類型 $ [a_0,\dots,a_n] $ 如果一個人可以執行（時隙）算術，那麼多項式的係數確實是一個非常糟糕的選擇。這是因為（除其他外）多項式上的自然乘法運算不會導致基礎係數的乘法，而是它們的捲積。特別是，有一個
$$ (a_0+a_1x+a_2x^2)(b_0+b_1x+b_2x^2) = a_0b_0+(a_0b_1+b_0a_1)x + (a_0b_2+a_1b_1+a_2b_0)x^2+(a_1b_2+a_2b_1) x^3+a_2b_2x^4 $$
特別是，一個人不回收產品 $ a_1b_1 $ . 可以通過（基本上）訴諸傅里葉變換的一個版本來解決這個問題，因為傅里葉變換通常可以寫成同構
$$ \mathcal{F} : (R, +,\times)\to (R, +,\ast) $$
例如，它用（coefficinent-wise）乘法“交換”卷積。這就是說，如果我們改為在“規範嵌入”中對消息進行編碼（或者等效地，我們對消息的“傅立葉變換”進行編碼），那麼卷積將變為元素乘法（在我們的消息空間中）。
我不相信最初的 BFV 論文會這樣做，這取決於您正在閱讀的 BFV 規範可能會導致混淆。但我相信它是一個相對常見的優化，並且應該能夠被視為“只是”一種不同的消息編碼（使用規範嵌入還有其他好處，因此您可能希望根據它重新分析協議）。