參考文獻：

1. [LM21] Li B, Micciancio D. On the security of homomorphic encryption on approximate numbers[C]//Advances in Cryptology–EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part I 40. Springer International Publishing, 2021: 648-677.
2. [CHK20] Cheon J H, Hong S, Kim D. Remark on the security of ckks scheme in practice[J]. Cryptology ePrint Archive, 2020.
3. [Bel20] M. Bellare. personal communication, December 2020.
4. [DS16] Ducas L, Stehlé D. Sanitization of FHE ciphertexts[C]//Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I 35. Springer Berlin Heidelberg, 2016: 294-310.

CKKS 滿足 IND-CPA 安全性，但是并非是 IND-CPA+ 安全的，它在某些 MPC 場景中完全不安全！

Preliminaries

Passive Attacker

由于 FHE 密文的延展性，安全性 IND-CCA2 是不可達的，同時 IND-CCA1 實際中也難以實現，因此讓人們往往把 IND-CPA 作為設計目標。

然而，在云計算、MPC 等場景下，敵手可以獲得某些消息的解密（訪問了受限的解密神諭），這導致敵手的能力實際上沒能被 IND-CPA 安全性定義所完全捕獲。

我們考慮三方場景（解密者 Alice，服務器 Bob，加密者 Eva）：Alice 生成 $(sk,pk)$，Eva 加密數據 $m$ 發送給 Bob，Bob 收到密文 $ct$ 之后做一定的運算 $f$，將 $c{t}^{\prime }$ 發送給 Alice 解密，最后將 $m^{\prime }$ 發送給 Eva。整個流程中，$m,f$ 可以被 Eva 主動選擇（也可以不選擇、甚至不知道），$ct,c{t}^{\prime },m^{\prime }$ 可以被 Eva 被動接收（不可以篡改、不可以注入）。

實際上 Eva 是一個被動敵手（passive attacker），其行為如圖：

被動敵手可以通過訪問 FHE 提供的公開標準接口（legitimate operations）構造出某個 $m^{?}$ 對應的 $c{t}^{\prime }$，要求解密神諭（有能力檢查 $c{t}^{\prime }$ 確實是合法產生的）回應 $m^{\prime }$，從而可能幫助被動敵手區分密文、甚至私鑰恢復。

Approximate Encryption

Raw (R)LWE Encryption Scheme，

• KeyGen：私鑰 $s\leftarrow {\chi }_s$，公鑰 $(b:=a?s+e,a)$，其中 $a\leftarrow \mathcal{U}({\mathcal{R}}_q)$，$e\leftarrow {\chi }_e$
• Encrypt：簡單計算 $c:=u?(b,a)+(m,0)+(e_0,e_1)$，其中 $u\leftarrow {\chi }_r$，$e_0,e_1\leftarrow {\chi }_e$
• Decrypt：簡單輸出 $m^{\prime }:=?s,c?(\mathrm{mod}q)$，易知 $m^{\prime }=m+e^{\prime }$

注意上述的加解密不包含編碼（糾錯碼、SIMD 打包），解密就是一個線性運算

1. 如果采取了糾錯碼（比如 MSD 編碼），使滿足解密正確性，稱之為精確同態方案（Exact），比如 BGV、BFV
2. 如果密文的解密結果不是精確值，稱之為近似同態方案（Approximate），比如 CKKS

CKKS 因為沒有使用 $\Delta \approx q/t$ 縮放因子，這使得噪聲增長速度比 BGV、BFV 慢得多，因此可以執行特別深的電路（而不必自舉）

采取 BV 的 tensor 技術，采取 GHS 的 raising the modulus 技術，同態乘法為：

• 預計算：運算秘鑰 $evk=(b:=as+e+p{s}^2,a)\in {\mathcal{R}}_{pq}^2$，其中 $a\leftarrow \mathcal{U}({\mathcal{R}}_{pq})$，$e\leftarrow {\chi }_e$

• 在線計算：輸入 $c_0,c_1\in {\mathcal{R}}_q^2$，計算多項式乘積并且重線性化，
  $$c=(b_0{b}_1,a_0{b}_1+a_1{b}_0)+?\frac{[a_0{a}_1{]}_q?evk}{p}?(\mathrm{mod}q)$$

CKKS 選取模數為 $q_l=q_0?p^l$，其中 $p=2$ 是 base，$l$ 是 level，密文 $(c,\Delta ,l)$ 是帶標記的，其中的 $\Delta$ 是定點數的縮放因子，SIMD 編碼是 $m=Encode(z;\Delta):=\lfloor \phi^{-1}(\Delta \cdot z)\rceil $，映射 $?:\mathcal{R}\to {\mathbb{C}}^{N/2}$ 是典范嵌入，選用 ${\zeta }_{2N}^{4j+1},j\in [N/2]$ 作為根。

為了控制噪聲增長速度，使用 Rescaling 技術（就是 BGV 的模切換），
$$RS((c\in {\mathcal{R}}_{q_l}^2,\Delta ,l),l^{\prime })=\left(?\frac{c}{p^{l?l^{\prime }}}?\in {\mathcal{R}}_{q_{l^{\prime }}}^2,p^{l?l^{\prime }}\Delta ,l^{\prime }\right)$$
CKKS 的線性解密結果為 $m^{\prime }=m+e\in {\mathcal{R}}_q$，其中 $m=\lfloor \phi^{-1}(\Delta \cdot z)\rceil $，最終的輸出是近似值 $z^{\prime }=Decode(m^{\prime };\Delta ):=?(m^{\prime }/\Delta )=z+e^{\prime }$

Security Notions

Indistinguishability-Based

[LM21] 首先基于游戲，給出了 IND-CPA+ 的定義，

Simulation-Based

[LM21] 接著基于模擬，給出了 SIM-CPA+ 的定義，

Separations Between Them

易知，IND-CPA+ 立即導致 IND-CPA（它僅訪問一次 E，并且不訪問 H 和 D），可以證明 IND-CPA+ 是嚴格強的：

• 對于精確同態加密，[LM21] 證明了 IND-CPA+ 等價于 IND-CPA
• 對于近似同態加密，[LM21] 證明了 IND-CPA+ 嚴格強于 IND-CPA

可以證明，SIM-CPA+ 導致了 IND-CPA+，并且兩者相分離（SIM-CPA+ 嚴格更強）：

• 對于精確同態加密，[LM21] 證明了 SIM-CPA+ 等價于 IND-CPA+
• 對于近似同態加密，[Bel20] 證明了 SIM-CPA+ 嚴格強于 IND-CPA+

確切地說，我們定義有界查詢數量的變體 $(q,l)$-IND-CPA+ 和 $(q,l)$-SIM-CPA+，它對于任意的受限敵手滿足上述 IND-CPA+ 安全定義、SIM-CPA+ 安全定義，除了這里的敵手只能訪問至多 $l(\kappa )$ 次 E 和 H 神諭，訪問至多 $q(\kappa )$ 次 D 神諭。[LM21] 證明了：對于任意的 $q\ge 2$，都存在 $(q,l)$-SIM-CPA+ 安全，但是 $(q+1,l)$-IND-CPA+ 不安全的近似同態加密。因此，在 IND-CPA 和 IND-CPA+ 之間，存在無限長的安全性（嚴格）遞增的安全性序列。

此外，上述的定義都是適應性的（security with adaptively chosen queries）：敵手可以主動選取不同的查詢次數和順序。我們可以要求敵手在看到 $pk,evk$ 之前就已經確定了它的查詢順序，這就是非適應的（fully non-adaptive model）。[LM21] 證明了非適應安全比適應性安全弱的多：存在近似同態加密方案，它是 SIM-CPA+ 非適應安全的，但不是 $(2,2)$-IND-CPA+ 適應性安全的。

Circuit Privacy and Functional Decryption

Circuit Privacy：電路隱私是說，從 $Enc(m)$ 同態計算出 $Enc(f(x))$，不會泄露 $f$ 的信息。

Functional Decryption：函數解密是說，選取 $f\in \mathcal{L}$，要求 D 神諭回應 $f(Dec(c))$，而非 $m=Dec(c)$ 本身。

[LM21] 簡單描述了如何將 IND-CPA+ 以及 SIM-CPA+ 的安全性定義擴展到兩者。

Attacks to CKKS

[LM21] 給出了 CKKS 的被動敵手下的私鑰恢復攻擊（這遠比 IND-CPA+ 攻擊更強），因此 CKKS 雖然是 IND-CPA 安全，卻不是 IND-CPA+ 安全。

Linear Key-Recovery Attack

簡單起見，我們考慮對稱加密。

如果敵手可以獲得密文 $c=(b:=a?s+m+e,a)$ 的解密 $m^{\prime }=m+e$，那么
$$b?m^{\prime }=a?s(\mathrm{mod}q)$$
它是關于 $s$ 的線性方程，

• 對于 LWE-based，只需要收集 $n$ 個線性方程組，就可以求解出 $s$
• 對于 RLWE-based，只要 $a\in {\mathcal{R}}_q$ 可逆，甚至只需要一個方程，就可以計算出 $s=(b?m^{\prime })?a^{?1}$

CKKS 的模數為 $q_l=q_0?2^l$，導致 $a\in {\mathcal{R}}_q$ 基本都是不可逆的，但依舊可以恢復出 $s$ 的部分信息

Lattice Attack

CKKS 采取了 SIMD 編碼，最終的解密結果是 $z^{\prime }=Decode(m^{\prime })$ 而非 $m^{\prime }$ 本身

[LM21] 采取重編碼手段，嘗試恢復出 $m^{\prime }$

• 如果 $Encode(z^{\prime })=Dec(Enc(m;e))$，那么獲得 $m^{\prime }=m+e$ 之后，可以采取上述的線程代數的手段恢復出私鑰
• 如果 $Encode(z^{\prime })=Dec(Enc(m;e))+?$，只要 $\Vert ?{\Vert }_2\le 2^{?N/2}?(q\sqrt{N}?h),h=HW(s)$，那么使用格基約簡求解近似 CVP 問題，依舊可以高效恢復出私鑰

在多種 CKKS 的實現中（HEAAN、HElib、SEAL、PALISADE），編碼解碼過程都是利用 double-precision FFT 完成的。而密文的存儲/運算，有些使用 Multi-precision Integer，有些則使用 RNS 系統。總體上，CKKS 的計算精度越高，那么 $?$ 就越小，這導致更加有效的攻擊。

Experiments

僅使用線性代數攻擊 CKKS，

對于不同實現的攻擊結果，

Against IND-CPA+ Attack

最后 [LM21] 建議修改解密函數，不要輸出 $m^{\prime }=m+\tilde{e}$（其中的 $\tilde{e}$ 包含了 $sk$ 和 $u,e$ 的信息），而是輸出一個近似值（不依賴私鑰和隨機帶）

1. 添加高斯噪聲：簡單在解密結果上添加高斯噪聲，但是敵手可以通過多次解密同一個密文，統計出原本的解密結果
2. 添加確定性噪聲：利用 PRF 關于 ct 計算出確定的噪聲（強制每個密文至多解密一次），這個類似于噪聲洪泛（noise flooding techniques），但是需要超多項式的模數。或者使用 [DS16] 的密文消毒（Sanitization of FHE Ciphertexts，通過 soak-spin-repeat 策略，迭代 Rerandomize、Bootstrapping 滾洗），使用較小的參數達到某個先驗的界 $q$-IND-CPA+ 安全
3. 精確解密：選取合適的 $\Delta$ 使得高概率滿足 $?(m+\tilde{e})/\Delta ?=?m/\Delta ?$（后者是精確值），輸出近似值 $?(m+\tilde{e})/\Delta ?$ 而非 $m+\tilde{e}$ 本身，這似乎是對于 CKKS 更有前途的

[CHK20] 對 HEAAN 做了修改，提供了兩種場景下的解密函數，

• Dec：這是原始的解密函數，它提供了 IND-CPA 安全，不允許泄露解密結果給任何人
• DecForShare：對解密結果添加一定的高斯噪聲，但是 $B_{ctxt}$ 的規模 [CHK20] 并沒有具體給出

[CHK20] 調查了其他幾個實現的辦法：

• HElib 粗糙地估計各個密文的噪聲上界 $B$，然后根據它來添加噪聲
• PALISADE 限制明文空間僅使用實部，虛部強行置為 $0$，運算過程中虛部會累積一定的噪聲，用它們來估計密文的噪聲規模
• Lattigo 要求用戶提供期望的輸出精度 $b$，然后執行 DecodeAndRound，舍入解碼的結果
• SEAL 簡單要求用戶不要泄露解密結果（躺平了）

但是上述這些都只能緩解問題，重新設計一個更加安全可靠的近似同態加密，仍是個開放問題。