# 後量子密碼學10 簡介編碼密碼學（Code-based Cryptography）
**編碼密碼學（Code-based Cryptography）** 是以**糾錯碼**（Error-Correcting Code）的理論為基礎所建立的一類密碼系統。它的安全性通常依賴於「在未知結構（secret structure）」的情況下，解碼某些碼字（codewords）極為困難。本類系統最早由 McEliece 於 1978 年提出，目前是**後量子密碼**領域的重要候選之一。
## 數學核心概念
### 糾錯碼 (Error-Correcting Code)
在通訊領域，糾錯碼可用於對抗傳輸雜訊，使訊息即使被雜訊干擾，也能透過「解碼」重建原文。其中一種常見的糾錯碼就是「線性碼 (Linear Code)」。
- **線性碼**定義：
訊息向量透過一個「生成矩陣 G」映射到碼字（codeword）空間。在沒有額外結構洩漏的情況下（例如隱藏了哪些 rows / columns 或混淆了某些矩陣），要從雜訊後的碼字還原原始訊息，是一個相當困難的問題（尤其當碼長與距離參數較大時）。
- **解碼困難問題**：
給定一個隨機線性碼（或被改裝過的線性碼）及一個受到雜訊干擾的碼字，想要在「不知道碼的原始結構」的前提下正確解碼，通常被認為是個 NP-困難問題。
### 安全基礎：Syndrome Decoding Problem
**Syndrome Decoding** 問題是在編碼密碼學中相當經典的「困難問題」。它可以簡述如下：
1. 給定一個亂數般的生成矩陣或校驗矩陣 H，以及一個像是「症狀 (syndrome)」的向量 s。
2. 問題在於：求出一個「重量（Hamming weight）相對較小」的錯誤向量 e，使得 $\mathbf{H} \cdot \mathbf{e}^T=\mathbf{s}$。
這個問題的**解碼**步驟若沒有私鑰（即不知道用於解碼的真正結構），在一般情況下被認為極其困難。多數編碼密碼學方案都是在「恰當挑選的線性碼」基礎上，利用私鑰中的某些結構，能有效且快速地完成解碼；但觀察者若只看到經「混淆（Scrambling）」或「隱藏（Masking）」後的公鑰碼，就難以破譯。
## 典型的編碼密碼學系統
### McEliece 加密系統
**McEliece** 是最早、也最具代表性的編碼加密系統。它的核心包含三個主要步驟（類似「雙極構造法」在多元二次密碼的概念）：
1. **選擇可高效解碼的碼**：
例如「Goppa Code」等具有快速解碼演算法的代數碼。這些碼本身能夠快速糾錯。
2. **隱藏結構**：
對生成矩陣 $G$ 做**亂序化**（Permutation）與**混淆**（Scrambling）後，形成公鑰矩陣 $\widetilde{G}$；攻擊者只看得到 $\widetilde{G}$，而不知道如何高效解碼。
3. **加密與解密**：
- 加密：發送者使用公鑰 $\widetilde{G}$ 將明文碼字「編碼」並人工添加固定重量的錯誤向量 $e$，生成密文。
- 解密：私鑰持有者知道如何「移除混淆」並用原始 Goppa Code 演算法完成快速解碼，還原出訊息。
**優點**：高傳統安全性與抗量子攻擊潛力。
**缺點**：公鑰矩陣尺寸較大，導致儲存量需求大。
### Niederreiter 加密系統
**Niederreiter** 系統與 McEliece 本質相似，但在定義上使用「校驗矩陣 (Parity-Check Matrix)」代替「生成矩陣」。兩者在安全性與實作效能上相當接近，也常被視為同一族的兩個代表。
## 安全性與抗量子攻擊
編碼密碼學被歸類為**後量子密碼**的主力之一，主要原因在於現行已知的量子演算法（例如 Shor 演算法）並不能有效地破解**一般性的線性碼解碼問題**。量子搜尋加速（如 Grover 演算法）雖然能提供平方級的搜尋優化，但面對大參數空間時，仍舊不可行。
## 優點與挑戰
**優點**
1. **後量子安全**：如同上所述，已知量子攻擊方式尚無法有效破解大參數下的解碼問題。
2. **加解密速度快**：若選用適合的碼（如 Goppa Code、QC-LDPC 等），解碼演算法非常高效，完成解密所需的運算量往往不算大。
3. **長期研究歷史**：McEliece 系統自 1978 年以來就被廣泛討論，累積許多安全性分析與改進建議。
**挑戰**
1. **公鑰體積龐大**：傳統 McEliece 系統的公鑰可能要數百 KB 甚至更大，對儲存與傳輸造成負擔。
2. **結構選擇 / 參數選定**：如何在「足夠安全」與「公鑰長度／解碼效率」中找到平衡，需要精細的安全分析和大量測試。
