基于國產密碼算法SM9的可追蹤屬性簽名方案

唐 飛 凌國瑋 單進勇

①(重慶郵電大學計算機科學與技術學院 重慶 400065)

②(重慶郵電大學網絡空間安全與信息法學院 重慶 400065)

③(北京數牘科技有限公司 北京 100083)

1 引言

面向網絡空間安全自主可控的戰略需求，我國自主研發了一系列商用密碼方案，最為常用的商密方案包括SM2算法[1]、SM3算法[2]、SM4算法[3]、SM9算法[4]。其中，SM9算法是標識密碼方案，即為基于身份的密碼(Identity-Based Cryptography,IBC)方案，由國家密碼管理局于2016年正式發布。它是一種基于雙線性映射的標識密碼方案，同時也是我國商用密碼中的第1個標識密碼方案。在標識密碼方案中，用戶的私鑰由密鑰生成中心(Key Generation Center, KGC)根據主密鑰和用戶標識計算得出，用戶的公鑰由用戶標識充當，從而不需要證書中心對用戶公鑰進行真實性認證。與基于公鑰基礎設施(Public Key Infrastructure, PKI)的密碼方案(例如SM2算法[1]、ElGamal等[5])相比，標識密碼方案中的密鑰管理環節可以適當得到簡化。

近年來，SM9密碼方案逐步受到各界關注，涌現了一系列基于SM9密碼方案的相關工作。2017年，楊亞濤等人[6]基于SM9設計了可證明安全的區塊鏈隱私保護方案。2018年，馬曉婷等人[7]基于SM9設計了區塊鏈技術的跨域認證方案。2019年，林超等人[8]基于SM9設計了范圍證明協議。2020年，Mu等人[9]設計了兩方協作的SM9簽名方案；涂彬彬等人[10]對SM9的密鑰生成進行分布式門限化設計；魏榮等人[11]實現了支持SM9的JavaScript通用密碼庫。2021年，賴建昌等人[12,13]基于SM9分別設計了廣播加密方案與簽密方案；Ji等人[14]基于SM9加密算法設計了用于云上訪問控制的屬性加密方案。

屬性簽名(Attribute-Based Signature, ABS)方案是屬性加密方案(Attribute-Based Encryption,ABE)的擴展[15]，正式定義由Maji等人[16]提出。在ABS方案中，簽名者對消息進行簽名時，使用某一簽名策略對消息簽名。驗證者則可以驗證該簽名是否滿足簽名者聲明的簽名策略。此外，為保護簽名者隱私，驗證者只能確定簽名者的屬性滿足相應的簽名策略，而不能確定是簽名者的哪些屬性滿足該簽名策略。ABS方案能夠實現細粒度的訪問控制，現已被看作一種重要的匿名認證手段，主要應用于工業物聯網中邊緣節點的數據隱私保護[17]；用戶對于自身數據在隱私計算中的個人數據授權[18]；區塊鏈中的數據訪問控制[19]等。

ABS方案根據訪問策略可分為門限訪問策略與樹形訪問策略等，其中樹形訪問策略相較于門限訪問策略能提供更加細粒度的訪問控制機制，使用戶的訪問權限更為靈活，樹形訪問策略的ABS方案如文獻[20,21]等。為了防止簽名濫用，將身份追蹤功能加入到ABS方案中是有必要的，即給定一個簽名，KGC能夠通過該簽名恢復出簽名者的真實身份信息。否則，簽名者可能會利用屬性簽名的匿名性進行非法簽名，因為如果沒有人能夠知曉簽名者的真實身份，那么溯源追責也無法實現。由此可見，可追蹤的ABS方案非常具有吸引力。除此之外，現有的ABS方案的驗簽效率普遍偏低，原因是現有的屬性簽名的驗簽算法的計算復雜度通常與策略規模(策略的屬性個數)呈線性關系，且至少需要多次的雙線性對映射以及指數運算[20–23]，而這兩種基本運算均是較為耗時的。因此，設計驗簽開銷與屬性策略復雜程度無關且高效的屬性簽名方案同樣是很有必要的。

如上所述，目前缺乏基于國密標準的ABS方案，且存在現有的ABS方案驗簽效率普遍偏低。針對這一問題，本文凝練SM9簽名方案的核心技術，提出一種基于國密SM9的可追蹤身份屬性簽名方案。本文的主要貢獻如下：

(1) 基于國密SM9構造了屬性簽名方案，該方案同時具有樹形訪問策略、身份追蹤的功能。

(2) 安全性方面，形式化安全性證明表明所提方案在隨機諭言機模型下具有不可偽造性，同時也可抗合謀攻擊。

(3) 效率方面，通過方案對比分析表明本文所提方案的簽名開銷與驗簽開銷相較于現有的可追蹤ABS方案具有較大優勢。其中，完成1次本文所提方案的驗簽操作僅需要各做1次指數運算以及雙線性對映射。同時編程實現了所提方案，通過實驗驗證了所提方案的高效性。實驗結果表明，驗簽算法的計算復雜度與策略規模無關，完成1次驗簽操作僅需2 ms。

2 預備知識與定義

2.1 雙線性映射與復雜性假設

2.2 樹形訪問策略的可追蹤屬性簽名方案

Escala等人[26]提出了可追蹤ABS方案的定義，即KGC可通過簽名追蹤到簽名者的具體身份，避免了傳統ABS方案中無條件匿名性下的簽名濫用問題，可追蹤的ABS方案如文獻[21,22]。

一個樹形訪問策略的可追蹤屬性簽名方案包含以下5個算法。

2.3 拉格朗日插值

2.4 屬性樹

3 基于國密SM9的可追蹤屬性簽名方案

本節基于國密SM9構造可追蹤身份的屬性簽名方案，該方案支持樹形訪問策略，并對該方案進行了安全性分析以及功能與效率方面的分析。

3.1 方案構造

3.2 安全性分析

從上述計算過程可以看出，本方案的合法簽名能夠通過驗證算法。

定理2 不可偽造性。若密碼雜湊函數H1是隨機諭言機，如果τ-SDH問題是難解的，那么基于國密SM9的可追蹤屬性簽名方案的簽名是不可偽造的。

證明 如果存在一個概率多項式敵手A能以不可忽略的優勢ε偽造基于國密SM9的可追蹤屬性簽名方案的簽名，則可以構造一個挑戰者C以不可忽略的優勢解決τ-SDH問題。

3.3 功能與效率分析

本節給出所提方案與現有的屬性簽名方案在功能與效率兩方面的對比。為保證本文所提屬性簽名方案的高效性，將對所提方案的系統建立、用戶密鑰生成、簽名、驗簽等操作進行逐一實驗。由于屬性簽名方案的效率通常與策略復雜度相關，因此本節還會分析屬性策略的復雜程度與以上4種操作的關系。測試的硬件平臺采用Intel i7-1165G7處理器、內存為16 GB、主頻為2.8 GHz。操作系統為Ubuntu18.04，編程語言是Go1.19。

首先，本文比較現有的ABS方案與所提方案在功能方面的對比，如表1所示。從中可以看出，所提方案是同時支持可追蹤身份功能與樹形訪問策略的。

表1 與現有的ABS方案的功能對比

為了保證所提方案的高效性，表2給出了所提方案與現有的ABS方案的效率分析對比。計算開銷僅統計最為耗時的指數運算、標量乘運算、雙線性映射運算。AID代表簽名者擁有的屬性集，SΥ代表簽名策略Υ的屬性集，exp代表群GT上的指數運算，sca1代表群G1上的標量乘運算，E表示一次雙線性映射運算，ξ代表屬性樹T的非葉子節點個數，d代表門限訪問策略的門限值。

表2 與現有的ABS方案的效率對比

為了更好地展現本文方案在簽名開銷與驗簽開銷上的優勢，本文給出群G1,G2上的標量乘運算sca1, sca2、群GT上的指數運算exp、雙線性運算E這4種基本運算的運行效率，如表2所示。

結合表2與表3，可以明顯看出所提方案在簽名開銷、驗證開銷上具有較大的優勢。其中，在簽名開銷方面，由于sca1相較于e xp的計算開銷要小許多，因此可以明顯看出所提方案的簽名開銷相較于現有的ABS方案更具優勢；在驗簽開銷上，所提方案僅需要1次雙線性映射和1次指數運算，效率優勢更加明顯。

除了理論分析以外，本文編程實現了本文所提方案并對方案的效率進行了測試。由于屬性簽名方案的效率往往與屬性策略Υ的規模有關，因此屬性簽名方案的運行效率一般是基于具體的策略下的。為了不失一般性，本文以策略的屬性個數，即|SΥ|作為自變量，分析屬性策略Υ的規模與所提方案的效率關系。實驗結果如表4所示。

從表4可以看出，所提方案的系統建立算法與驗簽算法與|SΥ|無關，即與策略復雜度無關；密鑰生成算法與簽名算法與|SΥ|線性相關。在簽名算法開銷方面，|SΥ|的大小每增加5，完成一次簽名所需時間增加大約0.5 ms，相當于5次sca1的時間，這與表2與表3中本文對于所提方案的簽名算法開銷的分析是吻合的，也間接說明了表4簽名開銷的實驗結果是正確的。在驗簽開銷方面，不難發現，隨著簽名策略Υ的復雜性增長，即|SΥ|的數量逐漸變大，簽名開銷仍為1.96 ms左右，而1次雙線性對運算E與1次群GT上的指數運算的總時間已大約為1.6 ms(見表3)。結合以上實驗數據，可知本文所提方案的驗簽操作確實只需要1次指數運算與1次雙線性映射。這相比于其他的ABS方案具有較大的效率優勢。盡管這帶來的代價是用戶密鑰生成算法的開銷會隨著|SΥ|的增長而增長，但密鑰生成算法畢竟只會在用戶生成密鑰時執行一次，且效率仍是可觀的。當|SΥ| = 25(25個屬性)時，執行1次密鑰生成算法也僅需3.1 ms左右。除此之外，簽名算法與驗簽算法是需要多次執行的，因此本文認為這是可以接受的。

表3 基本運算效率對比(ms)

表4 本文所提方案實驗結果(ms)

除了計算開銷以外，本文還給出了所提方案與現有的ABS方案的通信與存儲對比，如表5所示。

結合以上對比分析與實驗結果，所提方案在功能方面，支持可追蹤身份以及樹形訪問策略；在效率方面，簽名開銷與驗簽開銷相較于現有的ABS方案更低；通信與存儲方面，所提方案也是與現有的ABS方案基本持平。

4 結束語

本文基于國密SM9設計了可追蹤屬性簽名方案，本方案支持樹形訪問策略，同時KGC可對簽名者身份進行追蹤。安全性方面證明了所提方案在隨機諭言機模型下具有不可偽造性，同時也可抗合謀攻擊。相較于現有的可追蹤屬性簽名方案，所提方案的追蹤算法避免了復雜的運算，并且在簽名開銷與驗簽開銷方面具有較大優勢。驗簽開銷方面，完成1次所提方案的驗簽操作僅需要1次雙線性對運算與1次指數運算。實驗結果表明，所提方案相較于現有的屬性簽名方案在簽名開銷與驗簽開銷上均有較大優勢，尤其是即便是復雜的屬性策略，完成1次驗簽操作也僅需要2 ms。