# FHE-Friendly Symmetric Ciphers and Transciphering

## 前情提要
最原始的全同態加密 (fully homomorphic encryption) 技術，其效率可說是非常的差，但在近年來個學者專家的努力下，各種加快運算速度的方式不斷出現，讓這個技術在實務上越來越容易被應用。

然而，無論專家們如何加快計算的速度，FHE 終究有個無法避免的阿基里斯之踵，也就是經過加密之後，那些加密資料的空間大小實在是**太太太大了**，考慮到這個技術幾乎都會應用在外包計算 (outsourced computation) 上，這會給雙方在資料通訊上，增加非常大的負擔。

這個時候， Transciphering 技術開始被多次拿來討論，以求解決這個問題。

## Transciphering 是什麼？

**Transciphering** 指的是：
> 將傳統對稱密文轉換為 FHE 密文，使得同態處理仍可繼續進行。

這項技術通常包括：

- 使用 FHE 加密過的對稱金鑰。
- 於雲端伺服器（僅擁有密文金鑰）上**同態模擬對稱解密與後續處理**。
- 所使用的對稱式加密方法，會被稱為 FHE-friendly。

---

## 🔍 Transciphering 流程概覽

以下為一個典型的 transciphering 架構：

1. **Client 端：**
- 使用 FHE 公鑰加密對稱金鑰 `K`
- 傳送 `Enc_FHE(K)` 和 `C_sym = Enc_sym(M, K)` 至雲端

2. **Server 端：**
- 利用 `Enc_FHE(K)`，在密文下進行 `Dec_sym(C_sym, K)` 的模擬（同態方式）
- 對明文進行同態處理，回傳 `Enc_FHE(f(M))`

3. **Client 端：**
- 使用私鑰解開 FHE 密文，得到最終結果 `f(M)`

這樣可確保**原始資料與金鑰皆不洩漏給雲端**，且雲端仍能進行指定的運算。

---

## 優點
考慮到對稱式加密的成本(不管是空間或時間)，會比 FHE 加密小非常多，這樣的方法，會讓 client 得以大幅降低計算的負擔 (尤其考慮到需要 outsourcing 的使用者，算力通常沒那麼高)。

## 使用限制
雖然一切對 client 端來說似乎都很美好，但是，仔細去看這個方案，會發現它會帶給 server 端非常大的額外計算負擔。考慮到 FHE 的計算本身就效率不佳，在需要對各個資料計算前，居然還需要先把 symmetric key 給解密，才可以進行下一步動作。要注意，在 FHE 中，每個密文的內容基本不是一個數字，就是一個 bit，這代表在應用上，可能會有成千上萬個密文 (這樣說可能都太保守了) 在運算前要解密。

所以，在設計 transcipher 前，需要確保對 symmetric key 的解密計算不要太過複雜。怎麼樣才算複雜？在 FHE 中，效率最差的計算是就是 bootstrapping。 bootstrapping 的存在，通常是為了避免密文乘法時，會產生過大的 noise，造成解密失敗；因此在這個 symmetric key 的解密，就必須要盡量減少乘法的使用，從而讓計算的速度不致於太慢，導致得不償失，所以像目前常用的對稱式加密 AES，由於解密時會需要多次乘法，就不太會被拿來設計 transcipher。

另一個需要注意的是，雖然這幾年，FHE 的 transciphering 有很多相關研究，但其安全性一直受到挑戰，在近兩年，就有好幾篇 paper 證明了幾種不同的 transcipher 方法，在安全參數不夠大時，會產生安全問題，這代表這個技術目前並未完全成熟，還處於研究階段，不適合直接拿來應用在實務上。

## FHE-Friendly 對稱加密演算法有哪些？

由於 AES 等傳統對稱加密算法使用非線性 S-box，對 FHE 不友善，因此研究者提出了多種專為 FHE 設計的輕量級對稱加密演算法，例如：

| 演算法 | 適用方案 | 特點 |
|--------|----------|------|
| **LowMC** | TFHE, BFV, BGV | 簡化的 S-box 結構，降低乘法複雜度 |
| **Chakraborti et al. Cipher** | CKKS | 針對 SIMD 和浮點數設計 |
| **Marvellous** | 支援 block-wise | 混合性好，支援安全參數可擴展 |
| **Rasta** | 無線性代數 | 簡單邏輯門實現，可快速同態運算 |

---

## 🧠 感想
在看這個技術時，一直讓我想到 KEM(key encapsulation mechanism)，感覺它們的概念非常相似，都是用 public key 加密 symmetric key，以增進加密和通訊效率。無論如何，FHE transciphering ，讓 FHE outsoucing 在 client 端得以用更有效率的方式來產生密文，降低 client 端的計算成本。或許再過一段時間，這個技術真正成熟，隱私保護技術的使用門檻會因此大幅降低。

## 📚 參考資料

- SoK: FHE-Friendly Symmetric Ciphers and Transciphering [(ePrint 2025/669)](https://eprint.iacr.org/2025/669)