# 後量子密碼學09 簡介哈希函數（Hash Function）簽章
## 什麼是哈希函數簽章？
**哈希函數簽章（Hash-based Signature）** 是一類以「安全雜湊函數」為核心建構的數位簽章機制。它的特點包括：
1. **安全性依賴於雜湊函數本身的安全性**：只要雜湊函數具備抗碰撞、抗第二原像攻擊等特性，即可提供簽章安全。
2. **抗量子攻擊**：在目前已知的量子攻擊模型中，安全雜湊函數依然能維持高度安全性，因此哈希簽章也被歸類為「後量子」的候選簽章方案。
3. **易於實作**：哈希函數的計算速度通常非常快，而且硬體、軟體都有豐富的優化技術，這讓哈希簽章在實作上相對便利。
## 哈希函數簽章的常見基本構造
### 3.1 One-Time Signature (OTS)
哈希簽章中最基本的思路，來自於「一次性簽章」（One-Time Signature, OTS）。
- **核心想法**：只要我們能用雜湊函數快速產生「一次性」鑰匙對，並且這個鑰匙對只能使用在一次簽名操作上，就能保障安全性。
- **具體作法**：
1. 生成一個「一次性」的公鑰與私鑰，其中私鑰常常是很多個隨機位元串的集合，公鑰則是將私鑰以哈希函數處理後得到。
2. 簽署文件時，針對文件內容做雜湊，再依據私鑰中特定的段落，選擇要「公開」哪些位元串與哈希證明，使驗證方能夠確定這些段落與公鑰對應無誤。
3. 簽完一次後，這些私鑰段落就不能再用了，故稱為「一次性」。如果重複使用，可能被攻擊者利用已公開的資訊還原或衍生其他私鑰。
延伸閱讀： https://ithelp.ithome.com.tw/articles/10360653
### 3.2 Merkle Tree
由於 OTS 每次簽名都需要全新的私鑰與公鑰，整體系統若要簽署多筆檔案，就需要管理多個鑰匙對。這時，**Merkle Tree**（Merkle 樹）能將一群 OTS 公鑰透過哈希樹結構「壓縮」成一個「主公鑰」。
- **結構概念**：
1. 頂端的樹根（Root）作為最終「主公鑰」。
2. 底層葉節點為各個一次性公鑰（OTS 公鑰）的雜湊值。
3. 使用 Merkle Tree 的樹根來代表整棵樹上的所有一次性公鑰。
- **簽章流程**：
1. 簽署時，選擇一片葉節點（對應某一次性公鑰），以 OTS 簽署文件。
2. 驗證時，除了檢查一次性簽名外，還須提供從這片葉到樹根的哈希路徑（「認證路徑」），讓驗證者能最終驗證樹根（主公鑰）相符。
3. 只要樹根（主公鑰）是可信的，且哈希路徑正確，就能驗證簽章合法。
延伸閱讀： https://ithelp.ithome.com.tw/articles/10361783
### 3.3 更進一步：Winternitz OTS、LMS、XMSS 等
- **Winternitz OTS**：為了一次簽名效率與密鑰長度之間做更好的平衡，提出了利用「Winternitz 參數」的變形，一次性私鑰或簽名長度可壓縮得更短，同時簽名速度也相對提升。
- **LMS (Leighton–Micali Signature) / XMSS (eXtended Merkle Signature Scheme)**：這些都是更先進的哈希簽章標準，透過改良的 Merkle Tree 結構、參數設定，達到更優的效能與安全性。
- 這些改進方案都以 OTS + Merkle Tree 為核心，並結合各種數學小技巧，使得整體系統在「簽章速度」「密鑰長度」「安全性」之間取得更好的平衡。
延伸閱讀： https://ithelp.ithome.com.tw/articles/10361355
## 優點與挑戰
優點：
1. **後量子安全**：哈希簽章的安全性高度依賴於安全雜湊函數的強度。現行常用的雜湊函數（如 SHA-2、SHA-3）在量子模型下的安全性依然堅固。Grover 演算法雖然能在搜尋工作上做平方加速，但是我們可以透過加大兩倍長度的雜湊值來達成同樣的安全等級。
2. **可實作性高**：雜湊函數在硬體和軟體中都能很快地執行，方便廣泛部署。
缺點
1. **簽名大小與鑰匙管理**：哈希簽章常需較長的簽名長度或需要管理大量一次性公鑰。這對儲存空間較小的裝置（如 IoT）是一大挑戰。
2. **一次性／有限次性**：若要簽署大量訊息，必須採用 Merkle Tree 等機制整合 OTS，增加了實作的複雜度。
