# 全同態加密（Fully Homomorphic Encryption, FHE）
全同態加密技術是一種允許直接對加密數據（Ciphertext）做計算，過程中無需解密的加密方法。特性是支持任意次數的加法和乘法操作，只有在最後解密時才顯示出正確的明文（plaintext）。

FHE想解決的問題：我們是否可以在不直接提供數據内容的情況下讓第三方進行數據處理

## FHE的核心
對比常見的加密方式，FHE多了同態操作的演算法，由以下4個polynomial time的演算法組成
1. 密鑰生成 $KeyGen(1^k)$: 輸入安全參數 $k$，輸出密鑰 $pk$，解密密鑰 $sk$ 和同態計算密鑰 $evk$
2. 加密 $Enc(pk, m)$: 輸入加密密鑰 $pk$ 和消息 $m$，輸出密文 $c$， $c \leftarrow Enc(pk, m)$
3. 解密 $Dec(sk, c)$: 輸入解密密鑰 $sk$ 和密文 $c$，輸出明文 $m$， $m \leftarrow Dec(sk, c)$
4. 同態操作 $Eval(pk, evk, f, c)$: 輸入加密和計算密鑰 $pk$，$evk$，函數 $f$ 和密文 $c$，輸出密文 $c_f$

以加法為例（假設計算 $m_1 + m_2$）：
1. 用戶將 $m_1, m_2$ 加密為 $c_1, c_2$ 並傳給第三方。
2. 第三方執行同態加法運算（Homomorphic Addition）：$c_{sum} \leftarrow c_1 \oplus c_2$。
3. 第三方回傳 $c_{sum}$。
4. 用戶解密 $Dec(c_{sum})$ 即可得到正確結果 $m_1 + m_2$。

過程中第三方持有 $c_1, c_2$ 與 $c_{sum}$，但完全不知道 $m_1, m_2$ 的數值。
> 補充：乘法或是其他操作也同理

## FHE的性質
**正確性（Correctness）**
如果對任意的$KeyGen(1^k) \to (pk, sk, evk)$，任意的電路$f \in F$，任意的明文向量$m = (m_1, m_2,...,m_k) \in M$，以及密文向量 $c = (c_1, c_2, ..., c_k)$，其中 $c_i = Enc(pk, m_i)$，有等式恒成立 $f(m) = Dec(sk, Eval(pk, evk, f, c))$。那我們就會稱FHE $\prod$ 對電路族 $F$ 是正確的。
> 圖片取自參考資料1

**緊致性（Compactness）**
$c^*$的解密複雜度和$f$無關

**安全性（Security）**
滿足IND-CPA，IND-CCA1，但不滿足IND-CCA2

簡單證明
* CPA： 標准的FHE是機率性加密（Probabilistic Encryption），每一次加密都會獲得不同結果的密文$c$，滿足IND-CPA security
* CCA1： 任意Adversary在取得挑戰密文 $C^*$ 後失去解密權限，所以無法通過同態特性修改 $C^*$ 後去驗證猜想
* CCA2： 任意Adversary在取得挑戰密文$C^*$後可以通過同態特性運算產生 $C^{*'}$，所以可以通過解密 $C^{*'}$ 得到 $C^*$ 的内容

## FHE的運作機制
LWE/ringLWE based FHE的安全性與正確性建立在**隨機噪聲**和**確定性解密**上：
**機率性加密：**
* 目的：爲了防止Adversary透過窮舉（Brute Force）來破解密文，滿足IND-CPA安全
* 機制：$c \leftarrow Enc(pk, m)$。加密時不直接對準明文數值，而是加上一個隨機生成的噪聲（Noise）$e$
* 結果：同一個明文 $m$ 每次加密都會產生不同的密文 $c$（落點不同），但都在某個安全區間內

**確定性解密（Deterministic Decryption）：**
* 目的：為了正確性，確保運算結果穩定
* 機制：$m := Dec(sk, c)$，解密是一個固定的數學過程（如移除padding後取mod/四捨五入）
* 原理：只要密文還在設計的容錯範圍內，解密函數會強制將其校正回歸到最近的正確明文刻度上，過程沒有隨機性

**噪聲預算（Noise Budget）**
* 概念：加密時預留的容錯空間扣掉當前噪聲後剩餘的額度
* 消耗：同態加法會使噪聲相加，同態乘法會使噪聲相乘
* 失敗：當運算過多導致噪聲累積超過容錯範圍（Budget < 0），解密時的校正就會出錯（對應到錯誤的明文），這時就需要Bootstrapping來重置噪聲

## FHE的生命周期
1. **Fresh Ciphertext**: 剛加密完的密文，噪聲最小
2. **Modulus Switching / Rescaling**: 在乘法後為了控制噪聲增長，通常會削減密文的模數（Modulus $q$），可以看作是爲了精準度而捨棄一部分空間
3. **Bootstrapping**: 當噪聲累積到臨界值快要無法解密時，在加密狀態下執行解密電路，將舊的密文換成一個新的、噪聲較小的密文

## FHE的限制
FHE雖然可以做任何可計算的函數，但也有一些限制：
**乘法限制（multiplicative depth）**
每做一次同態乘法都會大幅增長噪聲，故很多實作是leveled FHE。我們需要事先知道最大乘法深度$D$，超過深度就需要Bootstrapping不然會解密錯誤。
**必須可以電路化**
因爲server看不到明文的關係，所以FHE不擅長資料依賴的控制流程，沒辦法做條件判斷。常見的解決方法是：
* branch：兩邊都算，然後用密文條件做mux選擇
* looping：如果loop的次數依賴明文計算成本會變高，可以unroll成固定次數的loop
* compare：可以用bit-decomposition來做（>, max, argmax）等operation
* division：除法一般沒有自然實現的方式，常見的實作成本比較高

## 主流FHE實現方案分類
| 方案類型 | 代表算法 | 特點 | 適用場景 |
| -------- | -------- | -------- | -------- |
| 算術運算型 (Integer Arithmetic) | BFV, BGV | 處理整數的精確加減乘運算。運算在有限域 $\mathbb{Z}_t$ 上 | 簡單統計、投票、精確整數計算 |
| 近似運算型 (Approximate Arithmetic) | CKKS | 處理浮點數/複數，允許解密後有微小誤差（類似機器學習中的精度損失） | 機器學習 (ML)、隱私保護模型推論 |
| 布林電路型 (Boolean Circuit / Bit-wise) | TFHE, FHEW | 將數據看作 bits，擅長邏輯閘運算（AND, XOR, NAND）。Bootstrapping 速度快，但大量數據計算慢 | 比較大小（Compare）、條件判斷（MUX）、神經網路的激活函數 |

## 參考資料
1. [9.5 全同态加密技术介绍](https://www.bilibili.com/video/BV18p4y1Z7Ws/)
2. [全同態加密 (FHE) 是什麼？如何利用隱私計算改變區塊鏈應用生態](https://abmedia.io/what-is-fully-homomorphic-encryption)
3. [同态加密算法与工程计算（隐私计算）](https://zhuanlan.zhihu.com/p/550796916)
> 隨手筆記，有錯誤或需要補充的部分歡迎討論，~~還請鞭小力一點~~