基于SM9聚合簽名局部可驗(yàn)證算法

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

關(guān)鍵詞：SM9； 聚合簽名； 局部可驗(yàn)證

中圖分類號：TP309.2 文獻(xiàn)標(biāo)志碼：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]屬于標(biāo)識密碼算法（identity-based cryptography，IBC）[2]的一種，在兼有IBC算法優(yōu)點(diǎn)的同時(shí)，解決了公鑰基礎(chǔ)設(shè)施（public key infrastructure，PKI）[3]體系中證書管理和密鑰托管的問題。SM9算法隨著待簽名消息數(shù)量的增加，驗(yàn)證簽名的計(jì)算開銷也會線性增長，導(dǎo)致在有大量數(shù)據(jù)待驗(yàn)證時(shí)，驗(yàn)簽效率較為低下。理論上，使用SM9算法生成的單個(gè)簽名大小為96 Byte，計(jì)算開銷主要為橢圓曲線上的2次標(biāo)量乘法運(yùn)算和2次雙線性配對運(yùn)算。若簽名個(gè)數(shù)為n，則n個(gè)簽名的總大小為n×96 Byte，驗(yàn)簽時(shí)需要執(zhí)行n×2次橢圓曲線標(biāo)量乘法運(yùn)算和n×2次雙線性配對運(yùn)算，存儲占用與計(jì)算開銷均與簽名個(gè)數(shù)呈正線性關(guān)系。為了解決上述問題，本文在SM9算法的基礎(chǔ)上進(jìn)行了改進(jìn)，將單個(gè)用戶生成的多條簽名進(jìn)行線性聚合，實(shí)現(xiàn)了一種基于SM9算法的聚合簽名（aggregate signature，AS）方案。

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

針對上述問題，本文在實(shí)現(xiàn)SM9聚合簽名算法的基礎(chǔ)上，進(jìn)一步提出了基于SM9聚合簽名局部可驗(yàn)證算法。該算法使得驗(yàn)證方在驗(yàn)證簽名時(shí)的時(shí)間成本大大降低，提升了簽名的驗(yàn)證效率。同時(shí)采用了局部可驗(yàn)證技術(shù)，使得驗(yàn)證方在對聚合簽名中特定明文消息進(jìn)行驗(yàn)證時(shí)，無須獲取所有消息明文，只需獲取特定明文消息和一個(gè)簡短提示即可驗(yàn)簽，減輕了驗(yàn)證方的計(jì)算負(fù)擔(dān)，并能降低數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)開銷。

1 相關(guān)工作

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

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

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

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

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

2 相關(guān)技術(shù)和算法

2.1 雙線性映射

三個(gè)階為素?cái)?shù)N的加法循環(huán)群G1、G2和一個(gè)乘法循環(huán)群GT，群G1、G2的生成元分別為g1（另記為P1）、g2（另記為P2）。設(shè)有一個(gè)雙線性映射e：G1×G2→GT滿足如下關(guān)系：

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）可計(jì)算性：P∈G1，Q∈G2，存在多項(xiàng)式時(shí)間內(nèi)有效計(jì)算出e（P，Q）的算法。

2.2 Diffie-Hellman問題

Diffie-Hellman問題[21]是一個(gè)離散對數(shù)問題。任取一個(gè)λ-bits的大素?cái)?shù)p，設(shè)G∈Zp是一個(gè)階為素?cái)?shù)q的加法循環(huán)群，其生成元為g。

2.2.1 CDH（computational Diffie-Hellman）問題

x，y∈Zp，輸入g、gx、gy，在多項(xiàng)式時(shí)間內(nèi)計(jì)算gxy是困難的。

2.2.2 SCDH（square computational Diffie-Hellman）問題

x∈Zp，輸入g、gx，在多項(xiàng)式時(shí)間內(nèi)計(jì)算gx2是困難的。

2.2.3 ICDH（inverse computational Diffie-Hellman）問題

x∈Zp，輸入g、gx，在多項(xiàng)式時(shí)間內(nèi)計(jì)算gx-1是困難的。

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

三個(gè)階為素?cái)?shù)p的循環(huán)群G1、G2（生成元分別為g1、g2）、GT，存在一個(gè)非退化的雙線性映射：e：G1×G2→GT，x∈Zp，給定g1、g2、gx1、gx2、e（g1，g2），在多項(xiàng)式時(shí)間內(nèi)計(jì)算e（g1，g2）x-1是困難的。

2.3 簽名方案概述

2.3.1 系統(tǒng)參數(shù)生成

定義大素?cái)?shù)p，F(xiàn)p為有限域，設(shè)g是橢圓曲線群的生成元，N是橢圓曲線的階，H（）為哈希算法，e（.）為雙線性對配對算法。

2.3.2 密鑰生成

簽名者生成隨機(jī)數(shù)α∈Fp，α即為簽名者私鑰。

2.3.3 消息簽名

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

2.3.4 消息簽名驗(yàn)證

驗(yàn)證者獲取簽名（S，gα），計(jì)算H（m），并構(gòu)造

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

進(jìn)行驗(yàn)簽。

2.3.5 消息聚合簽名

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

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

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

2.3.6 消息聚合簽名驗(yàn)證

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

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

則驗(yàn)證者構(gòu)造：e（S^，g∑ni（βi×αi））=（g∏ni1α+H（mi））∏ni（α+H（mi））=g進(jìn)行驗(yàn)簽。當(dāng)常數(shù)集合{hi}已知時(shí)，可計(jì)算出系數(shù)集合{βi}。進(jìn)行簽名驗(yàn)證時(shí)，需要將{gαi}包含在驗(yàn)證公鑰中進(jìn)行驗(yàn)簽。

2.3.7 消息簽名局部驗(yàn)證提示消息生成

簽名者生成聚合簽名（S^，{gai}），i∈（1，n），假設(shè)驗(yàn)證者只需要驗(yàn)證消息mj，則簽名者需要生成mj的局部驗(yàn)證提示信息。由式（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）兩份提示信息。最終的聚合簽名局部可驗(yàn)證簽名結(jié)果為（S^，{gai}，auxj，1，auxj，2），i∈（1，n）。

2.3.8 消息聚合簽名局部驗(yàn)證

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

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

2.4 SM9系統(tǒng)參數(shù)

SM9系統(tǒng)使用的參數(shù)配置如表1所示。

3 基于SM9聚合簽名局部可驗(yàn)證算法

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

3.1 密鑰生成

設(shè)置SM9系統(tǒng)參數(shù)，KGC產(chǎn)生隨機(jī)數(shù)ks∈［1，N-1］作為簽名主私鑰，計(jì)算G2中的元素Ppub-s=ks×P2作為簽名主公鑰，簽名密鑰對為（ks，Ppub-s）。KGC秘密保存ks，公開Ppub-s。

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

以上所有計(jì)算由KGC完成，計(jì)算結(jié)果dsA發(fā)送給用戶A。

3.2 消息簽名

假設(shè)待簽名消息為M，用戶A計(jì)算以下數(shù)據(jù)：

a）產(chǎn)生隨機(jī)數(shù)r∈［1，N-1］；

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

c）計(jì)算整數(shù)h=H2（M，N）；

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

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

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

3.3 消息簽名驗(yàn)證

為檢驗(yàn)收到的消息M及其數(shù)字簽名（w，S）的正確性，驗(yàn)證者B計(jì)算以下數(shù)據(jù)：

a）計(jì)算整數(shù)h=H2（M，N）；

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

c）計(jì)算整數(shù)h1=H1（IDA‖hid，N）；

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

e）根據(jù)式（1）驗(yàn)證e（S，T）=e（P1，P3）是否成立。若成立則驗(yàn)證通過；否則驗(yàn)證不通過。

3.4 消息聚合簽名

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

a）產(chǎn)生隨機(jī)數(shù)r∈［1，N-1］；

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

c）計(jì)算整數(shù)hmi=H2（Mi，N），i∈［1，n］；

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

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

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

3.5 消息聚合簽名驗(yàn)證

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

a）計(jì)算整數(shù)hmi=H2（Mi，N），i∈［1，n］；

b）已知{hmi}，根據(jù)式（3）計(jì)算出系數(shù){βi}；

c）計(jì)算整數(shù)h1=H1（IDA‖hid，N）；

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

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

3.6 消息聚合簽名局部驗(yàn)證提示信息生成

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

a）產(chǎn)生隨機(jī)數(shù)r∈［1，N－1］；

b）計(jì)算G1中的元素K=r×P1；

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

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

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

f）計(jì)算群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 消息聚合簽名局部驗(yàn)證

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

a）計(jì)算整數(shù)hmj=H2（Mj，N）；

b）計(jì)算整數(shù)h1=H1（IDA‖hid，N）；

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

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

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

4 正確性與安全性分析

4.1 正確性分析

4.1.1 消息簽名驗(yàn)證方案正確性分析

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）

根據(jù)簽名的驗(yàn)證結(jié)果可知，消息簽名與消息簽名驗(yàn)證方案滿足正確性要求。

4.1.2 消息聚合簽名驗(yàn)證方案正確性分析

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）

根據(jù)簽名的驗(yàn)證結(jié)果可知，消息聚合簽名與消息聚合簽名驗(yàn)證方案滿足正確性要求。

4.1.3 聚合消息局部驗(yàn)證方案正確性分析

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）

根據(jù)簽名的驗(yàn)證結(jié)果可知，消息聚合簽名局部驗(yàn)證提示信息生成與消息聚合簽名局部驗(yàn)證方案滿足正確性要求。

4.2 安全性分析

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

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

1）系統(tǒng)建立階段

挑戰(zhàn)者B根據(jù)Key-Gen密鑰生成算法生成系統(tǒng)參數(shù)。

2）詢問階段

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

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

3）偽造階段

假設(shè)敵手能成功找出哈希函數(shù)的碰撞，挑戰(zhàn)者B可獲取誠實(shí)的算法A在不改變隨機(jī)數(shù)r的情況下所產(chǎn)生的簽名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）

敵手γ計(jì)算：

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）

假設(shè)δ=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的值相關(guān)，挑戰(zhàn)者B可找到hash函數(shù)碰撞，因此可以在選擇密文攻擊的情況下，構(gòu)造上述等式，使得式（12）成立，進(jìn)而獲取簽名私鑰r。

綜上所述，若攻擊算法A可以在多項(xiàng)式時(shí)間內(nèi)求出ks-1，則挑戰(zhàn)者B可以在多項(xiàng)式時(shí)間內(nèi)攻破ICDH問題，所以若ICDH問題無法在多項(xiàng)式時(shí)間內(nèi)被攻破，則攻擊算法A無法在多項(xiàng)式時(shí)間內(nèi)求出ks-1。

5 算法效率分析

假設(shè)n條簽名進(jìn)行了聚合。國密SM9算法簽名驗(yàn)證時(shí)間的復(fù)雜度如表2所示。

假設(shè)n條簽名進(jìn)行了聚合。基于SM9的局部可驗(yàn)證簽名驗(yàn)簽算法的時(shí)間復(fù)雜度如表3所示。

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

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

假設(shè)n條簽名進(jìn)行了聚合，SM9算法和基于SM9聚合簽名局部可驗(yàn)證算法生成的簽名，其空間復(fù)雜度結(jié)果如表5所示。

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

6 實(shí)驗(yàn)分析

本方案使用國家密碼標(biāo)準(zhǔn)SM9推薦的橢圓曲線構(gòu)建，基于GmSSL密碼庫編寫代碼。CPU為AMD Ryzen 5 PRO 4650G；操作系統(tǒng)為Unraid 6.11.5，在虛擬機(jī)中安裝Ubuntu20.04；編程語言版本為Python3.11.2，GCC版本為12.2.0。

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

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

7 結(jié)束語

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

參考文獻(xiàn)：

[1]GM/T 0044—2016， SM9標(biāo)識密碼算法[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技術(shù)的近年研究綜述[J]. 密碼學(xué)報(bào)， 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]周彥偉， 馬巋， 喬子芮，等. 基于證書的抗連續(xù)泄露簽名機(jī)制[J]. 計(jì)算機(jī)學(xué)報(bào)， 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]楊憶歐， 彭長根， 丁紅發(fā)，等. 一種支持并行密鑰隔離的無證書聚合簽名方案[J]. 計(jì)算機(jī)技術(shù)與發(fā)展， 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]游民國. 基于量子隱形傳態(tài)的量子聚合簽名方案研究[D]. 西寧：青海師范大學(xué)， 2023. （You Minguo. Research on quantum aggregated signature scheme based on quantum teleportation[D]. Xining：Qinghai Normal University， 2023.）

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

[10]郭瑞， 陳宇霜， 鄭東. 無線醫(yī)療傳感網(wǎng)絡(luò)中基于區(qū)塊鏈的高效無證書聚合簽名方案[J]. 信息網(wǎng)絡(luò)安全， 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]翟嘉祺， 劉建， 陳魯生. 高效的基于陷門置換的可延遲驗(yàn)證聚合簽名（英文）[J]. 南開大學(xué)學(xué)報(bào)： 自然科學(xué)版， 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]. 通信學(xué)報(bào)， 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]唐飛， 劉文婧， 馮卓，等. 支持多中心聚合簽名的實(shí)用性拜占庭容錯(cuò)改進(jìn)方案[J]. 重慶郵電大學(xué)學(xué)報(bào)： 自然科學(xué)版， 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]陳佳偉， 冼祥斌， 楊振國， 等. 結(jié)合BLS聚合簽名改進(jìn)實(shí)用拜占庭容錯(cuò)共識算法[J]. 計(jì)算機(jī)應(yīng)用研究， 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標(biāo)識簽名算法[J]. 計(jì)算機(jī)應(yīng)用研究， 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]. 計(jì)算機(jī)應(yīng)用與軟件， 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聚合簽名技術(shù)的平行鏈共識算法優(yōu)化方案[J]. 計(jì)算機(jī)應(yīng)用， 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]周利峰， 殷新春， 寧建廷. 一種適用于無線醫(yī)療傳感器網(wǎng)絡(luò)的基于區(qū)塊鏈的無證書聚合簽名方案[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 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īng)偉， 黃超，等. 可驗(yàn)證醫(yī)療密態(tài)數(shù)據(jù)聚合與統(tǒng)計(jì)分析方案[J]. 軟件學(xué)報(bào)， 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中隱私保護(hù)的無證書聚合簽名方案[J]. 計(jì)算機(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ì)凱. 車載傳感網(wǎng)中基于聚合簽名的認(rèn)證方案[J]. 吉林大學(xué)學(xué)報(bào)： 理學(xué)版， 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]劉二根， 王露， 易傳佳，等. 基于聚合簽名的變電終端數(shù)據(jù)安全傳輸[J]. 計(jì)算機(jī)工程與設(shè)計(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.）