2009 - 全同態加密#

案件摘要#

2009 年，IBM 的 Craig Gentry 發表《Fully Homomorphic Encryption Using Ideal Lattices》：在密文上直接計算，結果仍是密文——不需要解密金鑰就能對加密資料做運算：

\[ Enc(a) \oplus Enc(b) = Enc(a + b), \quad Enc(a) \times Enc(b) = Enc(a \times b) \]

密碼學家稱之為「聖杯」（holy grail）——1976 年公鑰密碼學（見 1974-Diffie公鑰構想.md）誕生時就有人猜想它不可能（因為解密是設計成不可同態的），Gentry 證明它可能，但代價是巨大：密文膨脹上千倍、計算慢數千倍。十年後（2019 格orus–FHE），它變成可用的技術。

前因 -- 為什麼會有這個案子#

雲端的隱私悖論：要讓雲端（AWS、醫院伺服器）計算你的資料，必須解密交出去——資料在雲端期間是裸的（伺服器管理員、駭客、政府都能看）。

傳統方案的困境：

同態加密（homomorphic encryption，1980s）：只支援一種運算（加法或乘法）——雲端能做的運算太受限
MPC（多方安全計算，見 1979-Shamir秘密分享.md）：互動式、多輪通訊——不適合雲端單方計算
可信執行環境（TEE）：信任硬體——硬體後門（如 XSV 2018）讓信任崩塌

Gentry 的問題：能否一次加密，永不解密，直接計算？

根本障礙（推理的核心）：任何加密都有解密函數 \(D(Enc(m))\) ——若 \(D\) 是同態的，就能解密（在密文空間算 \(Enc(m)\) 與 \(m\) 的差），加密就毫無意義。所以 \(D\) 不能是同態的——但 \(D\) 又必須是 \(Enc\) 的逆！

Gentry 的突破：加密成多項式形式（不是整數），同態運算在多項式環中進行，解密只在末端做一次（依賴「近似 GCD 問題」的困難性）。

線索與推理 -- 數學式、程式、理論#

Gentry 的三元組#

全同態加密（FHE）方案 \((\text{KeyGen}, \text{Enc}, \text{Dec}, \text{Eval})\) ：

\[ Enc_{pk}(m) = c \quad \text{（加密）} \]

\[ Dec_{sk}(c) = m \quad \text{（解密——不是同態的，沒人能對任意密文解密）} \]

\[ Eval_{pk}(f, c_1, \dots, c_t) = Enc_{pk}(f(m_1, \dots, m_t)) \quad \text{（同態計算——公開！）} \]

關鍵性質：

正確性： \(Dec_{sk}(Eval(f, Enc(m))) = f(m)\)
同態性： \(Eval(+, c_1, c_2) = Enc(m_1 + m_2)\) （不需要 \(sk\) ）
安全性： \(Enc\) 是 IND-CPA 安全（密文不洩漏 \(m\) ）
解密非平凡：沒有 \(sk\) 不能解密——靠問題的計算難度（非平凡的解密才是安全的根源）

關鍵設計：Boost 與 Gentry 的消滅法#

問題：1990 年代（如 Bresson–Catalano–Pointcheval 2003）已有「部分同態」——但加法與乘法的組合（ \(\text{密文} \times \text{密文}\) ）會讓密文多項式的次數爆炸：

\[ \deg(\text{乘}n \text{次}) = n^{\log_2 n} \]

Gentry 的核心技術（Theorem 3.1, 2009）：

消滅（Erase）：設計 \(Dec\) 在密文噪音很大時輸出 ⊥（失敗）——正常解密不受影響
Boost：用特殊的「乘後立即洗牌」（乘 + 加特殊多項式 \(g\) ）讓密文重新「變短」（回到小的噪音狀態）

於是：任何部分同態方案都能被 boost 成全同態。用安全性換效率——這是 Gentry 定理的精髓。

從 Gentry 到實用：2019 格orus–FHE#

2009–2019 的十年，Gentry 方案慢到無用（2010 CKKS 方案的運算慢約 \(10^6\) 倍）。2019 年 Plotly 的 Craig Gentry + Zillow 的 Zhao 發表 CKKS：近似同態加密——浮點運算，允許小的精度損失：

CKKS 支援浮點：機器學習的矩陣運算直接對應（實務上雲端 ML 的終極應用）
性能提升 \(10^4\) 倍：分佈式編譯、多項式切換（NTT）、特徵映射的優化
Microsoft SEAL / OpenFHE：開源實作

現況（2020s）：CKKS 可在幾分鐘內加密運算中等規模的 ML 模型，延遲從數週降到分鐘——雲端隱私 ML 從理論變成工程。

程式碼：全同態加密的概念（同態聚合）#

# 全同態的「 killer app」：在密文上統計，完全不解密
# 場景：100 個病人加密年齡，雲端直接算平均年齡——醫院看不到個別資料

class Enc:
    def __init__(self, v): self.v = v          # 概念示範（非真 FHE）
    def __add__(self, o): return Enc(self.v + o.v)
    def __mul__(self, k): return Enc(self.v * k)
    def __truediv__(self, o): return Enc(self.v / o.v)

# 病人各自加密
ages = [Enc(a) for a in [35, 42, 28, 51, 33]]   # 密文
# 雲端在密文上計算（沒有解密金鑰！）
sum_enc = sum(ages[1:], ages[0])
count_enc = Enc(len(ages))
avg_enc = sum_enc / count_enc                    # 同態平均
print(f"平均年齡 = {avg_enc.v}")                  # 37.8（真實 FHE 中 avg_enc 是密文）
print("雲端從未解密任何個別年齡——隱私保護 ✓")

# 真實 FHE（CKKS）中，這些運算全部在密文上進行：
# Enc(35) + Enc(42) = Enc(77),  × 0.2 = Enc(15.4) —— 皆為密文
# 只有持有 sk 的病人端（其實無需）能解密

限制與現實#

開銷大：密文膨脹 \(100\text{x} - 10000\text{x}\) 、運算慢——仍未「好用」
正確性 vs 效能：CKKS 是近似的（小誤差），但「同態醫療記錄」需完全正確——用 BFV/BGV（整數同態）
惡意用家：同態運算不需要 sk——攻擊者可上傳構造的密文（如加密巨大數字做 DoS）——需要驗證/限流
真實需求：2020s 雲端 ML 隱私是真實需求——Microsoft、Google 的隱私 ML 產品

偵探筆記：FHE 的推理是一個「極大的運算方向性」：加密的解密函數必須非同態，但同態運算又必須能用——Gentry 用多項式 + 噪音 + 消滅/Boost 解決「解密函數」的悖論。這與 Merkle–Hellman 背包密碼的失敗（見 1979-MerkleHellman背包密碼.md）同源——都用 NP 難問題（近似 GCD、LLL）做安全性與效率的取捨。

結案 -- 後果與影響#

聖杯實現：1976 年公鑰密碼學被認為不可能的 FHE，Gentry 證明可能——密碼學理論的重大里程碑。
CKKS 與雲端 ML：2019 年之後，隱私機器學習（encrypted inference）從理論到工程——Apple 的 Private Cloud Compute、Google 的 FHE 服務。
MPC 競賽：2012 年以來，微軟、IBM、Meta、Duality 等投入 FHE 競賽（如 OpenFHE 同態加密競賽 2021）——工業化推進。
2025 年後的 LLM：FHE + LLM 推理（如 FHE-LLM 研究 2024）——加密資料上跑 AI 推理，仍是難題。
廣告：Google/Meta 的隱私增強計算——「資料不出裝置」。

關鍵人物與文獻#

Craig Gentry（1973–）：IBM/Plotly；Fully Homomorphic Encryption Using Ideal Lattices (2009, STOC)；圖靈獎的熱門候選（未得）
Gentry & Peikert：2011 的「可視/委託多乘法」——RLWE 方案的基礎（後量子 Kyber 的基礎）
Cheon, Kim, Kim, Song；CKKS 論文 (2017)
Gentry, Peikert, Vaikuntanathan：CKVS 方案 (2013)
OpenFHE：開源實作庫；Microsoft SEAL
交叉參照：1979-MerkleHellman背包密碼.md、1979-Shamir秘密分享.md、1974-Diffie公鑰構想.md