Chameleon Signature 變色龍簽名入門

傳統電子簽名 (Conventional Digital Signature Algorithms)
傳統的電子簽名方法，例如 DSA / ECDSA 等，
主要可分為公鑰 (Public Key) 、私鑰 (Private Key) 以及簽署 (Signature / Digest) 三個部分。

例如，Alice 可以運用自己的私鑰，透過 DSA，得出一份加上了簽署的文件。
然後，Bob 就可以利用 Alice 的公鑰，透過驗證該簽署，去確認文件是由 Alice 所發出的。

過程中，當 Alice 簽署了這份文件，就代表她認同，電子簽署具有以下所有特性：

• 不可偽造性 (Unforgeability): 因為只有 Alice 擁有私鑰，任何人都不可能輕易偽造一份合法的電子簽名，冒認 Alice 已經認可另一份文件。
• 不可爭議性 (Non-Repudiation): 因為簽名難以偽造，一旦 Alice 簽署過這一份文件，她就不可能否認自己已經簽過。情況就有如銀行過數一樣，一旦成功操作，就不可逆轉。
• 可傳播性 (Transferability): 同一個簽名，不但只 Bob 會相信。只要任何一個人擁有 Alice 的公鑰，只要私鑰沒有外泄，他們都一樣會相信 Alice 已經認可這份文件。

然後，有人就提出了一個問題：有沒有一種電子簽名，可以只保留部分特點？
於是，變色龍簽署 (Chameleon Signature) 應運而生。

---

變色龍電子簽名 (Chameleon Signature Algorithms)
在 1997 年左右，Krawczyk 與 Rabin 發表了一種算法 [1]，
透過在 Hash Function 中加多一個後門 (trapdoor)，達至「簽名不變，內容可篡改」的特性。

聽起上來，「可以篡改內容」的電子簽名，就像「沒有用」的簽名，
但實際上，情況卻正好相反，因為：

• 假設 Alice 擁有 K 的公鑰、私鑰和後門，而 Bob 則只有 K 的公私鑰。當一份文件中包含了 K 簽名，這份文件就有可能是由 Alice 或 Bob 所簽署。所以，如果該文件是由 Bob 利用 K 簽發的話，除了 Alice 以外，沒有其他會相信 Bob：因為其他人會質疑 Bob 發出的文件，即使簽名不變、驗證也成功，但因為 Alice 有後門，所以她有可能偷偷改過內容。換句話說，文件中的簽名的可傳播性 (transferability)，就降低到只有 Alice 與 Bob 之間：只有他們兩個，才知道真相如何。
• 同一個例子，如果 Alice 真的偷偷改過文件內容，到「審判」的一天，Bob 就可以拿出原文件，證明自己清白：因為 Bob 沒有後門，要在短時間內，要找出可以產生同一個簽名的文件，幾乎不可能發生。所以，Bob 就可以用自己原文件，向「審判官」證明是 Alice 動了手腳，與己無尤。可見，這種簽名，仍然有一定程度的不可爭議性 (non-repudiatory)。
• 其實整個系統，論安全性而言，基本上與傳統的 DSA 無異：如果黑客沒有私鑰或者後門，簽名同樣難以偽造 (unforgeable)，所以仍然算得上安全。

---

變色龍簽名系統架構
由於涉及數論 (Number Theory) 及 Discrete Log Arithmetic，為避免鑽得太過深入，
以下只提及一些重要元件，數學推算內容則輕輕帶過。

變色龍散列 / 哈希函數 (Chameleon Hash)

• 假設訊息為 m，修改過的訊息為 m'，目標為：ChameleonHash(m) = ChameleonHash(m')
• 只要達到以上目標，產生的簽名 σ = (CH(m), SK) 就自然不變。

初始化

• 隨機產生後門 x ∈ Zp，並計算出變色龍函數公鑰 K = (g, y) = (g, g^x mod p)
• 排除後門的話，它有點像 HMAC 的概念。

ChameleonHash 計算過程（使用公鑰 K 產生）

• 隨機產生臨時變數 r
• 計算出 CH = (g^my^r mod p) = (g^mg^xr mod p) = (g^m+xr mod p)
• 最後得出 (m, r, CH)

ChameleonHash 驗證過程（使用公鑰 K）

• 由於 r 已經提供，計算方法同上，得出 CH2，對比 CH 即可得出結果。

ChameleonHash 的後門 x 使用過程

• 目標：假設已有 CH 及 m'，利用 x 幫助找出 r' 的值。
• 公式：移項後可得出 r' = [ ( m + xr - m' ) / x ] mod q
• 結果得出 (m', r', CH)，當中即使 m 已經改變，但 r 同時更新，故 CH 可以不變。
• 如果黑客沒有 x，找出新的 r 將會變成 DLP 問題 (Discrete Log Problem)。

將 ChameleonHash 與簽名系統結合

• 初始化：
• 產生 Alice 的 DSA 公私鑰 PK_A 及 SK_A（或稱為私鑰 S）
• 產生 ID，CH 的公鑰 K（或稱為公鑰 R）及後門 x
• 簽名：
• 簽署者擁有 K, PK_A, SK_A
• 使用 K 將訊息 m 進行 Chameleon Hash，得出結果 Digest = (m, r, CH)
• 將結果加上 ID，並以 Alice 的私鑰進行 DSA 簽署，得出 σ = Sign_SKA(CH || ID)
• 最後，整個訊息為 (m, r, σ)
• 驗證：
• 任何人均擁有 K, PK_A
• 收到 (m, r, σ) 後，使用 K 及 r 將訊息 m 進行 Chameleon Hash，得出結果 CH
• 將結果加上 ID，再以 DSA 驗證，得出 Result = Verify_PKA((CH || ID), σ)
• 修改內容：
• 修改者需擁有 K 及 x
• 擁有 x 的人可以選擇修改內容（由 m 變成 m'），並得出新的 r 值（r'）
• 由於 Chameleon Hash 值一致，所以不用重新進行 DSA 簽名
• 結果得出 (m', r', σ)

如是者，系統將有公鑰 (Public Key) 、私鑰 (Private Key) 、變色龍公鑰 (K)、變色龍後門 (Trapdoor x)，以及簽署 (Signature / Digest) 五個部分。

---

變色龍簽名（或散列）的應用

現實生活中，這種簽名的應用仍未普及，以下為一些可行例子：

• 公開記帳系統 (Open Ledger) [2]：
  假設 Alice 想給 Bob 10% 的家財，Alice 可以立下單據，並用 Bob 的給予的變色龍公鑰 K 及自己的電子簽名私鑰 SK 進行變色龍簽名，然後將簽名公開。這樣，每一個外人都可以見證這一個簽名，但卻不會完全相信 Alice 與 Bob 之間的約定（因為 Bob 有後門可以修改內容）。這種方法，可以以保障 Alice 和 Bob 之間的約定，有多人見證，但同時也不會因外人妒忌，而影響自己的人身安全。假若有一天，Bob 真的偷偷改掉內容，Alice 只需向大家公開原單據，就可以證明自己清白。
• 可修改式區塊鏈 (Redactable Blockchain)：
  在一些私人區塊鏈中，給予某方（例如管理層）最大權力，保留可改性，可以防止因為錯誤決定，或者資料問題，而導致整個系統不可用的情況。例如當 GPDR 私隱條例實施後，管理層就可以決定先暫停一下區塊鏈網絡，然後將所有敏感資料，從區塊鏈中擦去，最後重新啟動系統。系統根據 Longest Chain Rule，就會在日後自動抹去舊的區塊鏈，如是者，管理員就不必重新建立整個系統。
• RUSH 5G Handover 系統：
  這篇由 Y. Zhang 發布的論文 [3]，也提到 Chameleon Hash 的應用。
  內容主要是用作 mutual authentication。

---

參考：

[1]: Krawczyk, Hugo, and Tal Rabin. "Chameleon hashing and signatures." Internet-https://pdfs.semanticscholar.org/1c29/4428c76ba7d1d0bb5e1d1bc931138c092453.pdf (1997).

[2]: 哈希（Chameleon Hash）、零知识证明（Zero—Knowledge Proof）和广播加密相关知识, MUZIBing's BLOG, https://muzibing.github.io/2019/10/12/2019.10.12%EF%BC%8885%EF%BC%89/#%E4%B8%80%E3%80%81%E5%8F%98%E8%89%B2%E9%BE%99%E5%93%88%E5%B8%8C%EF%BC%88Chameleon-Hash%EF%BC%89

[3]: Y. Zhang, R. Deng, E. Bertino, and D. Zheng, “Robust and Universal Seamless Handover Authentication in 5G HetNets,” IEEE Trans. Dependable Secur. Comput., vol. 47907, no. c, pp. 1–1, 2019, doi: 10.1109/tdsc.2019.2927664.