新的格上變色龍簽名方案

丁 亮*，陳 巖，胡鴻宣，魯國陽，高 淼

（1.河南中煙工業有限責任公司，河南 鄭州；2.鄭州輕工業大學 計算機科學與技術學院，河南 鄭州）

數字簽名可用來鑒別文件的真偽，又能夠防止通信雙方中由任意一方所造成的抵賴。然而，傳統的數字簽名往往是公開可驗證的，無法阻止不誠實的驗證者對簽名者所簽署的敏感文件進行二次傳播。為避免該行為，1989 年，Chaum 和Antwerpen[1]提出了不可否認簽名（Undeniable Signature, US），其通過控制簽名的驗證解決該問題，但在驗證環節要求簽名者必須在線參與，且不可避免地涉及到繁重的零知識證明。1996 年，Jakobsson 等人[2]提出了指定驗證者簽名（Designated Verifier Signature, DVS），簽名者和指定驗證者擁有相同的簽名權限，任意第三方無法確認簽名是由簽名者真實生成還是由指定驗證者模擬，但在簽名的真實性出現爭議時無法提供有效的仲裁機制。1998 年，Krawczyk 和Rabin[3]創造性地提出了變色龍簽名（Chameleon Signature, CS），更簡便地解決了簽名的二次傳遞問題。

變色龍簽名在簽名算法中嵌入一個有效的變色龍哈希函數（Chameleon Hash Function, CHF）來對消息進行散列。對指定驗證者而言，其利用秘密持有的陷門來計算CHF 的碰撞是可行的，即能夠在變色龍哈希值不變的條件下隨意更換原始消息，從而使得二次傳遞的消息在任意第三方前失去“可信度”；相反地，對不擁有陷門的任意用戶，CHF 仍保持抗碰撞性。相較于US，CS 不依賴復雜的交互式協議和零知識證明，而是采用“哈希- 簽名”范式來實現離線驗證。相較于DVS，對于指定驗證者的偽造，CS 中的簽名者能夠對其“證偽”，即滿足簽名者可拒絕性。顯然地，CS在云醫療、電子選舉和數字版權保護等應用場景中尤為適用[4-5]。

在后量子密碼時代，基于傳統數論難題的CS 方案將面臨在多項式時間內被量子計算機攻破的現實威脅[6]。2008 年，Gentry 等人[7]創造性地設計出格上原像采樣算法，并基于經典的小整數解（Small Integer Solution, SIS）難題假設，構造了格上強不可偽造的簽名方案。2010 年，Cash 等人[8]給出了格上安全的CHF。2013 年，基于文獻[7-8]的工作，謝等人[9]宣稱構造了格上第一個CS 方案。2016 年，采用文獻[8]的CHF，Noh 等人[10]給出了格上標準模型下安全的強指定驗證者簽名方案，缺陷是簽名必須攜帶大尺寸密文，且無法解決簽名的爭議問題。2017 年，Xie 等人[11]提出了同態CHF的概念，并宣稱構造了一個格上有限級數的全同態簽名方案，缺陷是同態CHF 的設計存在天然的計算錯誤。2021 年，Thanalakshmi 等人[12]構造了基于哈希的CS 方案，缺陷是簽名者和指定驗證者必需各自存儲一個復雜的有向無環圖，且簽名的生成過程比較繁瑣。

本文對文獻[9]中的格上第一個CS 方案進行密碼學分析，指出其不滿足抗選擇消息攻擊下的第三方不可偽造性和簽名者可拒絕性；進一步地，提出了一個新的格上CS 方案，并在隨機預言機模型下嚴格證明了新方案滿足抗適應性選擇消息攻擊下強不可偽造性、簽名不可傳遞性、簽名者可拒絕性以及不可抵賴性。

1 預備知識

1.1 格

1.2 變色龍簽名

令消息空間為 M，隨機數空間為 R以及簽名值空間為 S。一個標準的CS 方案[3]主要包括三個參與方：簽名者 S，指定驗證者V 以及仲裁者：

(1) Setup：輸入安全參數λ，輸出公共參數pp。

(2) KeyGen：輸入pp，輸出 S和V 的公私鑰對和。

(3) Sign：由 S運行的概率性算法。輸入pp，公鑰pkV，公私鑰對和消息 μ ?M， 輸出隨機數r?R和簽名值 σ ?S。

一個安全的CS 方案需滿足以下性質：

定義6 若 (μ, r,σ) ? M× R × S 為指定驗證者V 偽造，且簽名者S 有能力說服仲裁者J 拒絕該簽名，則稱CS 方案滿足簽名者可拒絕性；相反地，若 (μ, r,σ)為S 真實生成，且其無法否認，則稱CS 方案滿足簽名者不可抵賴性。

2 謝等人方案的安全性分析

定理1 謝等人的格上CS 方案不滿足抗選擇消息攻擊下的第三方不可偽造性。

證明 對于謝等人的方案，通過分析其簽名過程，本文發現任意第三方可以偽造出一個有效的簽名，且S 無法使J 拒絕該簽名：

綜上可知，謝等人的格上CS 方案不滿足抗選擇消息攻擊下的第三方不可偽造性。

定理2 謝等人的格上CS 方案不滿足簽名者可拒絕性。

綜上可知，謝等人的CS 方案不滿足簽名者可拒絕性。

3 新的格上CS 方案

3.1 方案描述

3.2 安全分析

定理4 新方案滿足簽名不可傳遞性。

定理5 新方案滿足簽名者可拒絕性和不可抵賴性。

證明 因篇幅所限，定理3、4 和5 的證明過程不再贅述，任何需要的讀者可聯系通訊作者。

4 性能分析

將給出的新的格上CS 方案與其他抗量子計算攻擊的可傳遞性簽名方案[9-12]在功能性、存儲與傳輸成本方面相比較，結果如表1 所示，其中，k0表示同態計算的數據集尺寸，k1表示有向無環圖的內部頂點集；×表示不滿足，√表示滿足，- 表示不考慮。顯然地，本文方案在功能方面更加全面，可適用于更加廣泛的應用場景；在存儲和傳輸成本方面，減少了公共參數的存儲以及簽名生成和傳輸的開銷，滿足輕量級設備進行簽名的實用性需求。

表1 不同方案的性能對比

結束語

結合抗量子計算攻擊的格密碼體制和CS 原語的安全特性，本文對格上第一個CS 方案進行了密碼學分析，指出其不滿足抗選擇消息攻擊下的第三方不可偽造性和簽名者可拒絕性；進一步地，給出了一個新的格上CS 方案，并在隨機預言機模型下嚴格證明了其滿足抗適應性選擇消息攻擊下強不可偽造性、簽名不可傳遞性、簽名者可拒絕性以及不可抵賴性。此外，給出的新方案也減少了簽名生成和傳輸的開銷，符合輕量級簽名的實用性需求。