FHE、MPC和ZK中AND運算的作用
通過LowMC，它的主要優勢之一似乎在全同態加密 (FHE)、多方計算 (MPC)和零知識 (ZK)證明中很有用。我對這些一無所知，但降低與門的數量似乎很重要。Kreyvium密碼也有類似的說法。
誰能向我解釋一下，在這 3 種情況下，AND 門的數量少有什麼幫助？主要是，私鑰加密算法如何幫助那些完全不相關的領域？此外，這是否意味著 FHE/MPC/ZK 中線性運算（異或門）的成本為零？
一般來說，與門沒什麼大不了的。然而，在實踐中，許多零知識系統基於 rank-1-constraint 系統（R1CS，在民間傳說中通常是“算術電路”），LowMC 試圖解決的問題與這種實用性有關。請注意，我是從 ZK 的角度討論的，儘管這些原則可能會延續到 FHE 和 MPC。
在 R1CS 中，您聲明輸入和輸出之間的約束，這些約束是算術形式的。例如，你會寫“（輸入
$$ 0 $$+ 1)秘密$$ 0 $$= 輸出$$ 0 $$”。在大多數 R1CS 系統中（閱讀：我所知道的所有內容），乘法門在證明/驗證函式中的權重很大，而加法大部分都是免費的。 現在，大多數加密/解密函式是根據位*運算定義的，而不是根據
+and來定義的*。為了證明您知道某個值及其關聯密鑰的解密，因此您需要將所有這些位運算符轉換為算術運算。你可以想像這些方程變得非常大。AND正如您正確辨識的那樣，此上下文中的主要操作是OR和XOR。根據您使用的約定，您將編碼True為 1 和False0，反之亦然。然後相對容易看出x AND y變成 $ x * y $ 並x XOR y成為 $ x + y - 2 * x * y $ , 並x OR y變成 $ x + y - x * y $ .現在，您可以在這裡進行很多優化。例如，如果您要使用流密碼來顯示解密，那麼您必須對密碼流進行 XOR $ s[..] $ 與密文 $ c[..] $ . 前者是你的電路的結果，但後者通常是公共價值。如果是這種情況，您可以通過執行類似的操作來提高特定 XOR 的效率
let xor = if c[i] == 0 { s[i] } else { 1 - s[i] };對於這個特定的 XOR，它不需要乘法。
OR 存在一個相關的優化：如果你把約定
False當作 0，True就像其他任何東西一樣，那麼x OR y就變成 $ x + y $ ，只要你的領域足夠大。TL;DR：
AND變成乘法，乘法會花費處理時間。XOR有時可以優化一下。順便說一句，如果你對低乘數對稱加密感興趣，也可以看看Poseidon！
在大多數 FHE 方案中，密文包含在執行操作後會增長的雜訊。與乘法相比，它的**加法增長通常可以忽略不計。此外，運營成本也不同。因此，人們希望盡量減少乘法深度，但也要盡量減少乘法次數，因為它們的成本更高。
例如，在整數的全同態加密中，密文為 $$ c = pq + 2r + m, $$ 在哪裡 $ p $ 是密鑰， $ q $ 和 $ r $ 是噪音， $ m $ 是消息位。
如果你添加兩個這樣的密文，你會得到 $$ c’ = c_1 + c_2 = p(q_1 + q_2) + 2(r_1 + r_2 + \epsilon) + (m_1 \oplus m_2). $$ 的大小 $ q $ 和 $ r $ 最多增加 1 位。
如果你將兩個這樣的密文相乘，你會得到 $$ c’ = c_1 * c_2 = p(q_1q_2 + \ldots) + 2r_1r_2 + \ldots + m_1 m_2. $$ 的大小 $ q $ 和 $ r $ 大約翻了一番。這限制了在變得太大和太慢之前可以完成的後續乘法的數量，需要進一步昂貴的引導（用新鮮的小雜訊重新加密密文）。