基于SM9聚合簽名局部可驗證算法

摘 要：針對目前SM9簽名方案生成的n條消息的簽名占用較大存儲空間的問題，提出了一種基于SM9算法的聚合簽名方案。該方案使得驗證多條簽名的時間開銷相較于原SM9方案有所降低，空間開銷約為原SM9方案的66.7%。在此基礎上，針對目前聚合簽名算法在驗證簽名時，驗證者僅需驗證特定消息的正確性，但仍需知道完整消息列表的問題，提出了基于SM9聚合簽名局部可驗證方案。對于單個用戶生成的n條消息的聚合簽名S，簽名者生成特定消息m的驗證提示信息aux，驗證者可以在不知道完整的消息列表的情況下，對消息m的簽名正確性進行驗證。理論與實驗分析表明，該方案在給定聚合簽名S的情況下，驗證特定消息的時間復雜度為O（1）。

關鍵詞：SM9； 聚合簽名； 局部可驗證

中圖分類號：TP309.2 文獻標志碼：A

文章編號：1001-3695（2024）10-040-3160-06

doi：10.19734/j.issn.1001-3695.2023.11.0640

Aggregate signature local verifiability algorithm based on SM9

Du Jian Ma Limina，b，c

（a.School of Computer Science， b.Beijing Advanced Innovation Center for Future Blockchain & Privacy Computing， c.Beijing Laboratory of National Economic Security Early-warning Engineering， Beijing Information Technology University， Beijing 100101， China）

Abstract：This paper proposed an aggregate signature scheme based on the SM9 algorithm to address the issue of excessive storage space occupied by the signatures of n messages generated by the conventional SM9 signature scheme. This scheme reduced the time cost of verifying multiple signatures compared to the original SM9 scheme， with a space cost of about 66.7% of the original SM9 scheme. Furthermore， the scheme introduced a locally verifiable approach based on the SM9 aggregate signature to tackle the problem where validators need only verify the correctness of specific messages when verifying signatures in current aggregate signature algorithms but still require knowledge of the complete message list. For the aggregated signatures S of n messages generated by a single user， the signer generated verification tags for a specific message m， enabling the verifier to verify the correctness of the message’s signature without knowledge of the complete message list. Theoretical and experimental analysis confirm that the proposed scheme achieves a time complexity of O（1） for verifying specific messages given an aggregated signature.

Key words：SM9; aggregate signature; locally verifiable

0 引言

SM9算法[1]屬于標識密碼算法（identity-based cryptography，IBC）[2]的一種，在兼有IBC算法優點的同時，解決了公鑰基礎設施（public key infrastructure，PKI）[3]體系中證書管理和密鑰托管的問題。SM9算法隨著待簽名消息數量的增加，驗證簽名的計算開銷也會線性增長，導致在有大量數據待驗證時，驗簽效率較為低下。理論上，使用SM9算法生成的單個簽名大小為96 Byte，計算開銷主要為橢圓曲線上的2次標量乘法運算和2次雙線性配對運算。若簽名個數為n，則n個簽名的總大小為n×96 Byte，驗簽時需要執行n×2次橢圓曲線標量乘法運算和n×2次雙線性配對運算，存儲占用與計算開銷均與簽名個數呈正線性關系。為了解決上述問題，本文在SM9算法的基礎上進行了改進，將單個用戶生成的多條簽名進行線性聚合，實現了一種基于SM9算法的聚合簽名（aggregate signature，AS）方案。

在某些情況下，驗證者僅需要對聚合簽名中的特定消息進行驗證，而無須驗證所有消息，也不必獲取完整的消息列表。但以往的聚合簽名算法中，驗簽者通常需要驗證所有簽名才能確認特定簽名的有效性，并且需要獲取完整的消息列表，導致驗簽的時間復雜度為O（n），其中n是簽名的數量。例如，在區塊鏈交易中，聚合簽名技術被用于減輕區塊鏈交易數據傳輸負擔，但交易中收款方的驗證者往往只關心與自身相關的交易，當前的聚合簽名算法在驗簽時要求驗證者下載區塊上的所有消息，并驗證所有簽名才能確認交易成功，這導致驗簽效率不高，降低了區塊鏈網絡交易的吞吐率。在進行區塊鏈數據校驗時，任何驗證方均能獲取所有交易信息，同樣會存在隱私泄露的潛在風險。另一方面，用戶訪問互聯網網站時，需要先與服務器建立連接，驗證服務器身份，證書透明日志（certificate transparency logs，CT）技術用于在互聯網上輔助驗證身份。CT創建公共日志以記錄證書頒發機構簽發的所有證書，用戶的瀏覽器在接收到來自網站的證書后，在繼續建立連接之前會檢查該證書是否存在于CT日志中。目前為了減輕CT日志的存儲壓力，使用聚合簽名的技術將一組證書的簽名合并成一個短小的聚合簽名，并搭配一個緊湊的數據結構來存儲消息列表。盡管用戶的瀏覽器可能存儲或下載了聚合簽名，但在驗證特定條目是否存在于日志中時仍需要下載所有條目，這導致在訪問互聯網時產生了不必要的網絡開銷。

針對上述問題，本文在實現SM9聚合簽名算法的基礎上，進一步提出了基于SM9聚合簽名局部可驗證算法。該算法使得驗證方在驗證簽名時的時間成本大大降低，提升了簽名的驗證效率。同時采用了局部可驗證技術，使得驗證方在對聚合簽名中特定明文消息進行驗證時，無須獲取所有消息明文，只需獲取特定明文消息和一個簡短提示即可驗簽，減輕了驗證方的計算負擔，并能降低數據傳輸的網絡開銷。

1 相關工作

聚合簽名是一種數字簽名的變體，它將多個簽名合并成一個簽名，從而減少簽名數據的存儲和傳輸成本，降低驗證簽名的計算開銷。針對聚合簽名技術，國內外學者做了大量研究。聚合簽名的技術起源于2001年Boneh等人[4]提出的基于雙線性映射的聚合簽名方案，該方案將n個簽名聚合成一個簽名，但是要求所有的簽名者使用相同的消息。2003年Boneh等人[5]提出了BGLS聚合簽名方案，它允許不同的簽名者使用不同的消息和公鑰驗證簽名。在BGLS聚合簽名之后，許多學者對聚合簽名進行了進一步的研究和改進，主要集中在以下幾個方面：

a）研究如何提高聚合簽名的安全性，防止簽名被偽造或竄改，如在標準模型下抵抗偽造攻擊、在不可信環境下保證聚合簽名的不可否認性等。周彥偉等人[6]針對基于證書的密碼體制的泄露攻擊問題，提出了基于證書的抗泄露簽名機制，并使用離散對數困難性進行形式化證明，以確保其不可偽造性，同時維持較高的計算效率；楊憶歐等人[7]提出了一種支持并行密鑰隔離的無證書聚合簽名方案，采用并行密鑰隔離機制和無證書橢圓曲線密碼技術，通過定時更新參與簽名用戶的密鑰，確保密鑰前向和后向安全，同時降低了密碼運算復雜度；游民國[8]通過設計三種基于量子隱形傳態和疊加態原理的量子聚合簽名方案，克服了傳統聚合簽名方案所依賴的經典密碼學問題在量子計算崛起下面臨的挑戰，確保了簽名的不可否認性、不可偽造性，并且能抵御糾纏測量攻擊；周利峰[9]針對智慧醫療環境中的通信安全和隱私保護問題，設計了一種高效安全的無證書聚合簽名方案，解決了智慧醫療中可能存在的公鑰替換攻擊、身份隱私泄露和數據完整性等問題。

b）研究如何提高聚合簽名的簽名驗簽效率，降低計算、存儲和通信開銷。郭瑞等人[10]提出了一種基于區塊鏈的無雙線性對的無證書聚合簽名方案，解決了無線醫療傳感網絡中存儲資源限制的問題，方案實現了醫療數據的高效聚合，擴展了區塊鏈的存儲性能，降低了計算和數據傳輸的開銷；翟嘉祺等人[11]改進了序列聚合簽名方案，通過消除先前方案中的一個隨機預言機，實現了更高效的序列聚合簽名，從而提高了聚合簽名方案的效率；王竹等人[12]構建了一種基于雙線性對的無證書有序聚合簽名方案，以解決之前方案中因逐一驗證簽名導致整體計算時間過長的效率問題，該方案中多個用戶按照一定的順序對文件進行簽名和認證生成聚合簽名，驗證者只需驗證最終一個簽名，即可確認簽名順序的正確性以及多個用戶簽名的合法性；唐飛等人[13]通過將聚合簽名方法用于區塊鏈共識機制中的消息驗證，降低了共識過程中的驗證復雜性，同時結合分布式密鑰生成技術實現多中心的密鑰授權機制，解決了密鑰中心權限過大的問題；陳佳偉等人[14]提出了一種聚合簽名的拜占庭容錯算法，用于解決在聯盟鏈中應用實用拜占庭容錯共識算法時遇到的通信復雜度限制問題，通過改進實用拜占庭容錯的信息交互方式和引入BLS簽名，成功地將通信復雜度降低為O（n）；張博鑫等人[15]提出了一種可撤銷的SM9標識簽名算法，解決標識簽名算法中存在的密鑰撤銷難題和SM9特殊結構導致技術無法完全適用的問題。該算法引入完全子樹，使密鑰中心能夠快速實現對用戶簽名權限的撤銷和更新操作。

c）研究如何擴展聚合簽名的功能，將聚合簽名技術與實際場景結合，如醫療、物聯網、云計算、社交網絡、電子投票等領域。安濤等人[16]針對車輛自組織網絡中的車輛隱私泄露和繁瑣的信息認證問題，提出了一種基于國產密碼SM9算法的聚合簽名方案，方案基于IBC密碼體制，使用假名代替真實身份，有效地保護了車輛隱私信息，同時利用聚合簽名技術提高了認證效率；劉琪等人[17]提出了一種基于BLS聚合簽名技術的平行鏈共識算法優化方案，通過在平行鏈上對共識交易進行簽名和聚合，有效解決了重復發送共識交易到主鏈的問題，減少了主鏈的存儲空間占用，節省了交易手續費；周利峰等人[18]提出了一種基于區塊鏈的無證書聚合簽名方案，采用分布式哈希表存儲機制，保障醫療數據的安全，實現了數據的去中心化存儲，并通過智能合約技術實現身份認證，滿足不可偽造性、可追蹤性和匿名性等安全需求；張曉均等人[19]針對可穿戴設備上傳的醫療數據的安全傳輸問題，提出了基于移動邊緣服務計算的容錯機制的醫療密態數據聚合方案，結合同態加密和聚合簽名技術，確保醫療數據在傳輸過程中的機密性、完整性。

在2022年，Goyal等人[20]針對驗證者在驗證指定明文消息和聚合簽名時仍需獲取完整消息集合的問題，引入了局部可驗證聚合簽名的概念，以實現對聚合簽名的高效驗證。方案中新增了Local-Open、Local-Agg-Verify操作步驟，簽名聚合方使用Local-Open生成短提示，而驗證方則利用Local-Agg-Verify對聚合簽名、短提示以及指定消息進行局部驗證。通過這一方法，驗證方在對聚合簽名進行驗證時不再需要獲取整個消息集合，只需獲取指定消息及其對應的短提示即可完成聚合簽名的驗證。此外，研究團隊還提出了基于RSA和雙線性對的兩種局部可驗證聚合簽名的構造方案。

2 相關技術和算法

2.1 雙線性映射

三個階為素數N的加法循環群G1、G2和一個乘法循環群GT，群G1、G2的生成元分別為g1（另記為P1）、g2（另記為P2）。設有一個雙線性映射e：G1×G2→GT滿足如下關系：

a）雙線性：a，b∈Z+，aP1∈G1，bP2∈G2，e（aP1，bP2）=ab*e（P1，P2）。

b）非退化性：Q1∈G1，Q2∈G2，e（Q1，Q2）≠1。

c）可計算性：P∈G1，Q∈G2，存在多項式時間內有效計算出e（P，Q）的算法。

2.2 Diffie-Hellman問題

Diffie-Hellman問題[21]是一個離散對數問題。任取一個λ-bits的大素數p，設G∈Zp是一個階為素數q的加法循環群，其生成元為g。

2.2.1 CDH（computational Diffie-Hellman）問題

x，y∈Zp，輸入g、gx、gy，在多項式時間內計算gxy是困難的。

2.2.2 SCDH（square computational Diffie-Hellman）問題

x∈Zp，輸入g、gx，在多項式時間內計算gx2是困難的。

2.2.3 ICDH（inverse computational Diffie-Hellman）問題

x∈Zp，輸入g、gx，在多項式時間內計算gx-1是困難的。

2.2.4 BIDH（bilinear inverse computational Diffie-Hellman）問題

三個階為素數p的循環群G1、G2（生成元分別為g1、g2）、GT，存在一個非退化的雙線性映射：e：G1×G2→GT，x∈Zp，給定g1、g2、gx1、gx2、e（g1，g2），在多項式時間內計算e（g1，g2）x-1是困難的。

2.3 簽名方案概述

2.3.1 系統參數生成

定義大素數p，Fp為有限域，設g是橢圓曲線群的生成元，N是橢圓曲線的階，H（）為哈希算法，e（.）為雙線性對配對算法。

2.3.2 密鑰生成

簽名者生成隨機數α∈Fp，α即為簽名者私鑰。

2.3.3 消息簽名

給定消息m，簽名者構造S=g1α+H（m）作為消息m的簽名，且（α+H（m）） mod N≠0，則消息簽名結果為（S，gα）。

2.3.4 消息簽名驗證

驗證者獲取簽名（S，gα），計算H（m），并構造

e（S，gagH（m））=（g1α+H（m））（a+H（m））=g（1）

進行驗簽。

2.3.5 消息聚合簽名

假設有n條消息m1，…，mn，則單個消息的簽名為Si=g1α+H（mi）。將α視為變量，則存在一組γ1，γ2，…，γn，使得

∏ni1α+H（mi）=∑niγiα+H（mi）（2）

成立。因此可得聚合簽名：S^=∏niSγii。消息聚合簽名結果為（S^，{gai}），i∈（1，n）。

2.3.6 消息聚合簽名驗證

驗證者收到聚合簽名（S^，{gai}），i∈（1，n），已知：

∏ni=1（α+H（mi））=∑ni=0（βi×αi）（3）

則驗證者構造：e（S^，g∑ni（βi×αi））=（g∏ni1α+H（mi））∏ni（α+H（mi））=g進行驗簽。當常數集合{hi}已知時，可計算出系數集合{βi}。進行簽名驗證時，需要將{gαi}包含在驗證公鑰中進行驗簽。

2.3.7 消息簽名局部驗證提示消息生成

簽名者生成聚合簽名（S^，{gai}），i∈（1，n），假設驗證者只需要驗證消息mj，則簽名者需要生成mj的局部驗證提示信息。由式（3）可得

∏ni=1（α+H（mi））=（α+H（mj））∏ni≠j（α+H（mi））=

α∏ni≠j（α+H（mi））+H（mj）∏ni≠j（α+H（mi））=∑n-1i=0（β0i×αi+1）+H（mj）∑n-1i=0（β1i×αi）（4）

則簽名者生成auxj，1=∑n-1i=0（β0i×αi），auxj，2=∑n-1i=0（β0i×αi+1）兩份提示信息。最終的聚合簽名局部可驗證簽名結果為（S^，{gai}，auxj，1，auxj，2），i∈（1，n）。

2.3.8 消息聚合簽名局部驗證

驗證者收到簽名（S^，{gai}，auxj，1，auxj，2），i∈（1，n），驗證：

e（S^，（gauxj，1）H（mj）gauxj，2）=e（g，g）是否成立，成立則驗證通過。

2.4 SM9系統參數

SM9系統使用的參數配置如表1所示。

3 基于SM9聚合簽名局部可驗證算法

本章將詳細介紹基于SM9聚合簽名局部可驗證算法。算法包括密鑰生成（Key-Gen）、消息簽名（Sign）、消息簽名驗證（Verify）、消息聚合簽名（Aggregate-Signature）、消息聚合簽名驗證（Aggregate-Verify）、消息聚合簽名局部驗證提示信息生成（Local-Open）、消息聚合簽名局部驗證（Local-Aggregate-Verify）七個部分。

3.1 密鑰生成

設置SM9系統參數，KGC產生隨機數ks∈［1，N-1］作為簽名主私鑰，計算G2中的元素Ppub-s=ks×P2作為簽名主公鑰，簽名密鑰對為（ks，Ppub-s）。KGC秘密保存ks，公開Ppub-s。

KGC選擇并公開1 Byte表示的簽名私鑰生成函數識別符hid。用戶A的標識為IDA，KGC計算t1=（H1（IDA‖hid，N）+ks） mod N。若t1=0，則需要重新產生主私鑰ks，并計算和公開新的簽名主公鑰，更新已有用戶的簽名私鑰；否則計算t2=（ks-1×t1） mod N，最后計算dsA=t2×P1。

以上所有計算由KGC完成，計算結果dsA發送給用戶A。

3.2 消息簽名

假設待簽名消息為M，用戶A計算以下數據：

a）產生隨機數r∈［1，N-1］；

b）計算G2中的元素w=r×Ppub-s；

c）計算整數h=H2（M，N）；

d）計算整數l=（r+h） mod N，若l為0，則返回步驟a）；

e）計算群G1中的元素S=l-1×dsA；

f）消息M的簽名為（w，S）。

3.3 消息簽名驗證

為檢驗收到的消息M及其數字簽名（w，S）的正確性，驗證者B計算以下數據：

a）計算整數h=H2（M，N）；

b）計算G2中的元素T=h×Ppub-s+w；

c）計算整數h1=H1（IDA‖hid，N）；

d）計算G2中的元素P3=h1×P2+Ppub-s；

e）根據式（1）驗證e（S，T）=e（P1，P3）是否成立。若成立則驗證通過；否則驗證不通過。

3.4 消息聚合簽名

假設有n條待簽名的消息（M1，M2，…，Mn），用戶A計算以下數據：

a）產生隨機數r∈［1，N-1］；

b）計算G2中的元素：w=r×Ppub-s，w2=r2×Ppub-s，…，wn=rn×Ppub-s；

c）計算整數hmi=H2（Mi，N），i∈［1，n］；

d）計算整數li=（r+hmi）mod N，若li為0，則返回步驟a）；

e）計算群G1中的元素：S^=∏n（l-1i）×dsA；

f）消息（M1，M2，…，Mn）的聚合簽名為（{wi}，S^）。

3.5 消息聚合簽名驗證

為檢驗收到的消息（M1，M2，…，Mn）及其聚合簽名（{wi}，S^）的正確性，驗證者B計算以下數據：

a）計算整數hmi=H2（Mi，N），i∈［1，n］；

b）已知{hmi}，根據式（3）計算出系數{βi}；

c）計算整數h1=H1（IDA‖hid，N）；

d）計算G2中的元素P3=h1×P2+Ppub-s；

e）驗證e（S^，∑ni=0（βi×wi））=e（P1，P3）是否成立，若成立則驗證通過；否則驗證不通過。

3.6 消息聚合簽名局部驗證提示信息生成

假設用戶A為消息（M1，…，Mj-1，Mj，Mj+1，…，Mn）生成了聚合簽名（{wi}，S^），驗證者B僅需要驗證消息Mj的正確性，則用戶A計算：

a）產生隨機數r∈［1，N－1］；

b）計算G1中的元素K=r×P1；

c）計算G2中的元素：w=r×Ppub-s，w2=r2×Ppub-s，…，wn=rn×Ppub-s；

d）計算整數hmi=H2（Mi，N），i∈［1，n］，i≠j；

e）已知{hmi|i≠j}，根據式（3）計算出系數{βi}；

f）計算群G2中的元素：auxj，1=∑n-1i=0（βi×wi），auxj，2=∑n-1i=0（βi×wi+1）；

g）簽名消息為（K，S^，auxj，1，auxj，2）。

3.7 消息聚合簽名局部驗證

假設用戶A為消息（M1，…，Mj－1，Mj，Mj+1，…，Mn）生成了聚合簽名（K，S^，auxj，1，auxj，2），驗證者B僅需要驗證消息Mj，驗證者B計算如下數據：

a）計算整數hmj=H2（Mj，N）；

b）計算整數h1=H1（IDA‖hid，N）；

c）計算G2中的元素P3=h1×P2+Ppub-s；

d）驗證e（K，auxj，1）=e（P1，auxj，2）是否成立，若不成立則驗證不通過；

e）驗證e（S^，auxhmjj，1×auxj，2）=e（P1，P3）是否成立。若成立則驗證通過；否則驗證不通過。

4 正確性與安全性分析

4.1 正確性分析

4.1.1 消息簽名驗證方案正確性分析

e（S，T）=e（l-1×dsA，h×Ppub-s+w）=

e（1r+h×ks－1×（h1+ks）×P1，（r+h）×ks×P2）=

1r+h×ks－1×（h1+ks）×（r+h）×ks×e（P1，P2）=

（h1+ks）×e（P1，P2）=e（P1，P3）（5）

根據簽名的驗證結果可知，消息簽名與消息簽名驗證方案滿足正確性要求。

4.1.2 消息聚合簽名驗證方案正確性分析

e（S^，∑ni=0（βi×wi））=

e（S^，∑ni=0（βi×ri×Ppub-s））=

e（S^，ks×（β0×r0+β1×r1+…+βn×rn）×P2）=

e（S^，ks×∏ni（r+hmi）×P2）=

e（ks-1×（h1+ks）×∏ni（1r+hmi）×P1，ks×∏ni（r+hmi）×P2）=

ks-1×（h1+ks）×∏ni（1r+hmi）×ks×∏ni（r+hmi）×e（P1，P2）=

（h1+ks）×e（P1，P2）=e（P1，P3）（6）

根據簽名的驗證結果可知，消息聚合簽名與消息聚合簽名驗證方案滿足正確性要求。

4.1.3 聚合消息局部驗證方案正確性分析

e（S^，auxhmjj，1×auxj，2）=

e（S^，hmj×auxj，1+r×auxj，1）=

e（S^，（r+hmj）×auxj，1）=

e（S^，（r+hmj）×∑n-1i=0（βi×wi））=

e（S^，∑ni=0（βi×wi））=e（P1，P3）（7）

根據簽名的驗證結果可知，消息聚合簽名局部驗證提示信息生成與消息聚合簽名局部驗證方案滿足正確性要求。

4.2 安全性分析

定理1 如果求解ICDH問題是困難的，則本方案是隨機預言模型安全的。

證明 由ICDH問題可知，x∈Zp，輸入g、gx，在多項式時間內計算gx-1的難度與解決DLP問題難度相當，故而在給定Ppub-s=ks×P2的前提下，在多項式時間內計算出ks-1×P2是困難的，進而無法求出ks-1。

1）系統建立階段

挑戰者B根據Key-Gen密鑰生成算法生成系統參數。

2）詢問階段

H2詢問：挑戰者B生成消息m，發送給攻擊算法A，A返回給挑戰者B消息m的哈希值H2（m）。

簽名詢問：挑戰者B生成m，發送給攻擊算法A，A返回m的有效簽名（w，S）給挑戰者B。

3）偽造階段

假設敵手能成功找出哈希函數的碰撞，挑戰者B可獲取誠實的算法A在不改變隨機數r的情況下所產生的簽名S1、S2，其中：

S1=l-11×dsA=1（r+h1）×ks-1×（ks+hid）×P1（8）

S2=l-12×dsA=1（r+h2）×ks-1×（ks+hid）×P1（9）

敵手γ計算：

S1-S2=（1（r+h1）-1（r+h2））×ks-1×（ks+hid）×P1（10）

敵手γ想找出一組r、h1、h2，使得：

1（r+h1）-1（r+h2）=1 mod N（11）

假設δ=r+h1，h2=h1+θ，r+h2=δ+θ，那么：

1（r+h1）-1（r+h2）=1δ-1δ+θ=1

θδ×（δ+θ）=1

δ=－θ±θ2+4×θ2∈［1，N－1］

r+h1=δ=－θ±θ2+4×θ2

r=－θ±θ2+4×θ2-h1（12）

等式右邊僅和h1、h2的值相關，挑戰者B可找到hash函數碰撞，因此可以在選擇密文攻擊的情況下，構造上述等式，使得式（12）成立，進而獲取簽名私鑰r。

綜上所述，若攻擊算法A可以在多項式時間內求出ks-1，則挑戰者B可以在多項式時間內攻破ICDH問題，所以若ICDH問題無法在多項式時間內被攻破，則攻擊算法A無法在多項式時間內求出ks-1。

5 算法效率分析

假設n條簽名進行了聚合。國密SM9算法簽名驗證時間的復雜度如表2所示。

假設n條簽名進行了聚合。基于SM9的局部可驗證簽名驗簽算法的時間復雜度如表3所示。

從表2和3可以看出，原SM9算法在驗證多條簽名消息時，ECC點乘操作、ECC點加法操作和雙線性配對操作時間復雜度為O（n）。改進后的算法在驗證聚合簽名消息時，時間復雜度為O（n）；驗證某一條特定消息的簽名時，驗證簽名的時間復雜度為O（1），驗證效率非常高。

下面將對基于SM9的簽名方案與幾種性能較好的方案進行對比。表4列舉了幾種現存的聚合簽名方案，主要對消息簽名驗證和消息聚合簽名驗證的效率進行對比，其中B表示雙線性對運算，M表示橢圓曲線標量乘法運算，“—”表示沒有此功能，n表示簽名數量。

假設n條簽名進行了聚合，SM9算法和基于SM9聚合簽名局部可驗證算法生成的簽名，其空間復雜度結果如表5所示。

從表5可以看出，本方案相較于原SM9算法，簽名數據占用空間有一定的減少，在簽名消息條數為n，ECC點不進行壓縮的情況下，本方案生成的簽名所占空間與原SM9算法生成的簽名所占空間，比值約為512×n512×n+256×n≈66.7%。在僅需驗證某一條特定消息時，簽名數據僅占用常數大小的空間。

6 實驗分析

本方案使用國家密碼標準SM9推薦的橢圓曲線構建，基于GmSSL密碼庫編寫代碼。CPU為AMD Ryzen 5 PRO 4650G；操作系統為Unraid 6.11.5，在虛擬機中安裝Ubuntu20.04；編程語言版本為Python3.11.2，GCC版本為12.2.0。

實驗方法：使用SM9算法生成一條簽名，對其進行n次簽名驗證操作；使用本方案的消息簽名算法生成一條簽名，并對其進行n次簽名驗證操作；使用本方案的消息聚合簽名算法生成n條消息的簽名，對已經生成的聚合簽名進行驗證操作；使用本方案的消息聚合簽名算法生成n條消息的簽名，選擇其中一條特定消息，使用消息聚合簽名局部驗證提示信息生成算法生成特定消息的驗簽提示信息，并對其進行驗證操作。方案未進行多線程優化，實驗消息條數分別為250，300，350，400，450，500，600，700，800。實驗記錄各個算法計算耗時，單位為毫秒（ms）。實驗結果如表6和圖1所示。

由表6與圖1可以看出，SM9算法驗證多條消息計算開銷時間復雜度為O（n）；消息簽名驗證算法驗證多條消息計算開銷時間復雜度為O（n）；聚合簽名驗證算法驗證多條消息的聚合簽名時，其計算開銷小于SM9算法計算開銷；聚合簽名局部驗證算法驗證聚合簽名中某一條消息的計算開銷，其時間復雜度恒定為O（1），約為800 ms。實驗結果符合預期。

7 結束語

本文介紹了聚合簽名技術研究方向，指出其在節省簽名存儲成本、提高驗證效率和保護隱私方面的潛力，并分析了目前聚合簽名算法存在的問題，即驗證簽名時需要知道所有消息。針對這一問題，本文提出了基于SM9算法的聚合簽名方案，并引入了局部可驗證簽名的機制，允許驗證者可以僅對聚合簽名中特定消息的簽名進行驗證，而無須驗證所有消息的簽名。但當前的算法僅能夠滿足單一用戶對一組消息進行簽名的需求，無法適應多用戶協作或多方計算場景。因此，未來的研究方向需要對算法進行進一步改進，以支持多用戶之間的協同簽名操作，提升算法的適用性和實用性。

參考文獻：

[1]GM/T 0044—2016， SM9標識密碼算法[S]. 2016. （GM/T 0044， 2016， SM9 identity-based cryptographic algorithm[S]. 2016.）

[2]TellenbachB.Identity-based cryptography[M]. [S.l.]： IOS Press， 2009.

[3]林璟鏘， 荊繼武， 張瓊露， 等. PKI技術的近年研究綜述[J]. 密碼學報， 2015， 2（6）： 487-496. （Lin Jingqiang， Jing Jiwu， Zhang Qionglu， et al. Recent advances in PKI technologies[J]. Journal of Cryptologic Research， 2015， 2（6）： 487-496.）

[4]Boneh D， Lynn B， Shacham H. Short signatures from the Weil pairing[C]//Proc of International Conference on the Theory and Application of Cryptology and Information Security. Berlin： Springer， 2001： 514-532.

[5]Boneh D， Gentry C， Lynn B，et al. Aggregate and verifiably encrypted signatures from bilinear maps[C]//Proc of International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2003： 416-432.

[6]周彥偉， 馬巋， 喬子芮，等. 基于證書的抗連續泄露簽名機制[J]. 計算機學報， 2022， 45（11）： 2363-2376. （Zhou Yanwei， Ma Kui， Qiao Zirui， et al. Certificate-based signature scheme with continuous leakage resilience[J]. Chinese Journal of Computers， 2022， 45（11）： 2363-2376.）

[7]楊憶歐， 彭長根， 丁紅發，等. 一種支持并行密鑰隔離的無證書聚合簽名方案[J]. 計算機技術與發展， 2022， 32（11）： 106-114. （Yang Yiou， Peng Changgen， Ding Hongfa， et al. A certificateless aggregation signature scheme supporting parallel key-isolated[J]. Computer Technology and Development， 2022， 32（11）： 106-114.）

[8]游民國. 基于量子隱形傳態的量子聚合簽名方案研究[D]. 西寧：青海師范大學， 2023. （You Minguo. Research on quantum aggregated signature scheme based on quantum teleportation[D]. Xining：Qinghai Normal University， 2023.）

[9]周利峰. 面向智慧醫療的無證書聚合簽名方案研究[D]. 揚州：揚州大學， 2023. （Zhou Lifeng. Research on certificateless aggregate signature schemes for smart healthcare[D]. Yangzhou：Yangzhou University， 2023.）

[10]郭瑞， 陳宇霜， 鄭東. 無線醫療傳感網絡中基于區塊鏈的高效無證書聚合簽名方案[J]. 信息網絡安全， 2020， 20（10）： 6-18. （Guo Rui， Chen Yushuang， Zheng Dong. A blockchain-based efficient certificateless aggregate signature scheme for wireless medical sensor networks[J]. Netinfo Security， 2020， 20（10）： 6-18.）

[11]翟嘉祺， 劉建， 陳魯生. 高效的基于陷門置換的可延遲驗證聚合簽名（英文）[J]. 南開大學學報： 自然科學版， 2021， 54（1）： 54-63. （Zhai Jiaqi， Liu Jian， Chen Lusheng. Efficient SAS scheme with lazy verification from TDPs[J]. Acta Scientiarum Naturalium Universitatis Nankaiensis： Natural Science Edition， 2021， 54（1）： 54-63.）

[12]王竹， 楊思琦， 李鳳華，等. 高效可證明安全的無證書有序聚合簽名方案[J]. 通信學報， 2022， 43（5）： 58-67. （Wang Zhu， Yang Siqi， Li Fenghua， et al. Efficient and provably-secure certificateless sequential aggregate signature scheme[J]. Journal on Communications， 2022， 43（5）： 58-67.）

[13]唐飛， 劉文婧， 馮卓，等. 支持多中心聚合簽名的實用性拜占庭容錯改進方案[J]. 重慶郵電大學學報： 自然科學版， 2022， 34（4）： 705-711. （Tang Fei， Liu Wenjing， Feng Zhuo， et al. Improved scheme of practical Byzantine fault tolerance based on multi-authority aggregated signature[J]. Journal of Chongqing University of Posts and Telecommunications： Natural Science Edition， 2022， 34（4）： 705-711.）

[14]陳佳偉， 冼祥斌， 楊振國， 等. 結合BLS聚合簽名改進實用拜占庭容錯共識算法[J]. 計算機應用研究， 2021， 38（7）： 1952-1955，1962. （Chen Jiawei， Xian Xiangbin， Yang Zhenguo， et al. Improved practical Byzantine fault tolerant consensus algorithm combined with BLS aggregating signature[J]. Application Research of Computers， 2021， 38（7）： 1952-1955，1962.）

[15]張博鑫， 耿生玲， 秦寶東. 高效的可撤銷SM9標識簽名算法[J]. 計算機應用研究， 2022， 39（9）： 2837-2842，2849. （Zhang Boxin， Geng Shengling， Qin Baodong. Efficient revocable SM9 identity-based signature algorithm[J]. Application Research of Compu-ters， 2022， 39（9）： 2837-2842，2849.）

[16]安濤， 馬文平， 劉小雪. VANET中基于SM9密碼算法的聚合簽名方案[J]. 計算機應用與軟件， 2020， 37（12）： 280-284，321. （An Tao， Ma Wenping， Liu Xiaoxue. Aggregated signature scheme based on SM9 cryptographic algorithm in VANET[J]. Computer Applications and Software， 2020， 37（12）： 280-284，321.）

[17]劉琪， 郭榮新， 蔣文賢， 等. 基于BLS聚合簽名技術的平行鏈共識算法優化方案[J]. 計算機應用， 2022， 42（12）： 3785-3791. （Liu Qi， Guo Rongxin， Jiang Wenxian， et al. Parallel chain consensus algorithm optimization scheme based on Boneh-Lynn-Shacham aggregate signature technology[J]. Journal of Computer Applications， 2022， 42（12）： 3785-3791.）

[18]周利峰， 殷新春， 寧建廷. 一種適用于無線醫療傳感器網絡的基于區塊鏈的無證書聚合簽名方案[J]. 小型微型計算機系統， 2022， 43（6）： 1128-1135. （Zhou Lifeng， Yin Xinchun， Ning Jian-ting. Blockchain-based certificateless aggregated signature scheme for wireless medical sensor networks[J]. Journal of Chinese Compu-ter Systems， 2022， 43（6）： 1128-1135.）

[19]張曉均， 張經偉， 黃超，等. 可驗證醫療密態數據聚合與統計分析方案[J]. 軟件學報， 2022， 33（11）： 4285-4304. （Zhang Xiaojun， Zhang Jingwei， Huang Chao， et al. Verifiable encrypted medical data aggregation and statistical analysis scheme[J]. Journal of Software， 2022， 33（11）： 4285-4304.）

[20]Goyal R， Vaikuntanathan V. Locally verifiable signature and key aggregation[C]//Proc of Annual International Cryptology Conference. Cham： Springer， 2022： 761-791.

[21]Bao Feng， Deng R H， Zhu Huafei. Variations of Diffie-Hellman problem[C]//Proc of International Conference on Information and Communications Security. Berlin： Springer， 2003： 301-312.

[22]趙楠， 章國安， 谷曉會. VANET中隱私保護的無證書聚合簽名方案[J]. 計算機工程， 2020， 46（1）： 114-120，128. （Zhao Nan， Zhang Guoan， Gu Xiaohui. Certificateless aggregate signature scheme for privacy protection in VANET[J]. Computer Engineering， 2020， 46（1）： 114-120，128.）

[23]王大星， 滕濟凱. 車載傳感網中基于聚合簽名的認證方案[J]. 吉林大學學報： 理學版， 2018， 56（3）： 657-662. （Wang Daxing， Teng Jikai. Authentication scheme based on aggregate signature in VSNs[J]. Journal of Jilin University： Science Edition， 2018， 56（3）： 657-662.）

[24]劉二根， 王露， 易傳佳，等. 基于聚合簽名的變電終端數據安全傳輸[J]. 計算機工程與設計， 2019， 40（7）： 1809-1815. （Liu Ergen， Wang Lu， Yi Chuanjia，et al. Data security transmission of substation based on aggregate signature[J]. Computer Engineering and Design， 2019， 40（7）： 1809-1815.）