為什麼FHE只需要支持加法和乘法

例如，給定 $ E(m_1) $ 和 $ E(m_2) $ 到雲端。它是如何計算的 $ E(m{_1}^{m_2}) $ ?

它是否與任何可計算函式都可以表示為包含或xor（加法）和and（乘法）門的電路的說法有關？

如果是這樣，方法是什麼？

是的，它是相關的，它們不僅需要加法和乘法。如果您從電子產品中了解功能完整性；

在邏輯中，一組功能完整的邏輯連接詞或布爾運算符可用於通過將集合的成員組合成布爾表達式來表達所有可能的真值表

適合功能完整性的操作是可以的。但是，加法和乘法很常見，因為許多數學結構都有它。此外，還有其他的，例如；有一個部分 FHE 只支持 x-or。

這與 FHE 中的想法相似，您幾乎可以建構任何電路。基本問題是語義安全性，它阻止了密文的直接比較。您以不同的方式進行比較。

此外，如果您查看TFHE: Fast Fully Homomorphic Encryption over the Torus ，您可以看到支持的布爾運算；

該庫支持 10 個二進制門（And、Or、Xor、Nand、Nor 等）的同態評估，以及否定和 Mux 門。每個二進制門需要大約 13 毫秒的單核時間來評估，這提高了

$$ DM15 $$乘以 53 倍，mux 門大約需要 26 CPU-ms。

計算 $ E(m_1^{m_2}) $ ? 真的取決於方案。但基本上你不能使用 $ E(m_1^{m_2}) = E(m_1) E(m_1) \dots E(m_1) $ 因為它會揭示你的 $ m_2 $ . 您至少需要 repatations 平方方法來隱藏實際值。

---

使用平方和乘法，您至少可以隱藏功率的實際值，而不是大小。讓我們將以下程式碼轉換為基於位的 FHE；

Let b be the “base” of the power, let p be the exponent.
Let r = the multiplicative identity (e.g.: 1).
Let s = b.
While p > 0 do:
   if p is odd
       let r = r * s.  // The "multiply"
   Let s = s * s       // The "square"
   Let p = p / 2 //(throw out the remainder).
The result is r

FHE 版本（我保留 $ b=m_1 $ 和 $ p=m_2 $ );

While C(p,0) do:
   r =(r*s∗ S)+(r∗S′)
   Let s = s * s
   Let p = p >> 1 
The result is r

在此程式碼中，C(p,0) 是比較器，如將函式表示為 FHE 電路。乘法由 if 條件“S”執行，保持 p 的值為奇數。因為它在語義上是安全的，所以我們對 if 應用位乘法，而在 else 情況下它是相反的。

從這個電路可以看出，這只會釋放 $ m_2 $

簡而言之：我們幾乎可以建構任何電路，但是，某些電路可能會顯示一些敏感或不敏感的資訊，具體取決於問題

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