基于正交拉丁方理論的數(shù)字簽名分組批量驗(yàn)證

王宏，賴成喆，劉向陽，曾晗

（1.國防科技大學(xué)信息通信學(xué)院，陜西 西安 710106；2.西安郵電大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，陜西 西安 710121）

0 引言

隨著無線通信、傳感器及人工智能等技術(shù)的不斷進(jìn)步，各種態(tài)勢感知網(wǎng)絡(luò)在氣象水文監(jiān)測、城市智慧交通、能源在線監(jiān)測等方面發(fā)揮著越來越重要的作用。技術(shù)進(jìn)步帶來便捷的同時，也導(dǎo)致人們受制于技術(shù)，尤其是個人信息的被盜、冒充或偽造等現(xiàn)象時有發(fā)生，極易造成態(tài)勢感知網(wǎng)絡(luò)的不暢，甚至癱瘓。因此，如圖1 所示，對網(wǎng)絡(luò)傳遞的消息進(jìn)行簽名，確保消息的可靠性、完整性和不可抵賴性成為一種重要的網(wǎng)絡(luò)安全措施。傳統(tǒng)的數(shù)字簽名采用逐一驗(yàn)證方法，當(dāng)中心型節(jié)點(diǎn)驗(yàn)證的簽名數(shù)量較少時，逐一驗(yàn)證方法尚且可以適應(yīng)要求；當(dāng)需要驗(yàn)證的簽名數(shù)量巨大時，逐一驗(yàn)證需要消耗大量時間，導(dǎo)致大量消息由于不能及時得到驗(yàn)證而被迫丟棄，比如龐大的車聯(lián)網(wǎng)系統(tǒng)每隔100～300 ms 就要實(shí)時地進(jìn)行消息傳輸，大量的消息連同附帶的簽名涌向中心節(jié)點(diǎn)等待馬上驗(yàn)證[1-2]，以保證它們來源的可靠性。因此，有關(guān)數(shù)字簽名的快速驗(yàn)證算法的研究成為近年密碼學(xué)的研究熱點(diǎn)。

圖1 中心型網(wǎng)絡(luò)消息匯聚

圍繞數(shù)字簽名快速驗(yàn)證算法，研究者所做的工作歸納為2 個方面：一是數(shù)字簽名的批量驗(yàn)證算法研究；二是分組檢測方案設(shè)計。數(shù)字簽名的批量驗(yàn)證通常采取聚合簽名算法，聚合簽名是將具有同態(tài)結(jié)構(gòu)的簽名算法進(jìn)行聚合驗(yàn)證，達(dá)到一次性驗(yàn)證多個數(shù)字簽名的目的，基于模指數(shù)運(yùn)算的數(shù)字簽名算法（DSA,digital signature algorithm）就具有這種同態(tài)結(jié)構(gòu)[3-7]。近年來，許多聚合簽名研究成果實(shí)現(xiàn)并證明了簽名密鑰的生成、分發(fā)和數(shù)字簽名的聚合驗(yàn)證[8-11]，但聚合簽名只能批量檢測多個數(shù)字簽名的集合中是否存在非法數(shù)字簽名，不能鑒別非法數(shù)字簽名在集合中的具體位置。為此，研究者紛紛引入已在生物醫(yī)學(xué)檢測中廣泛應(yīng)用的分組檢測理論進(jìn)行數(shù)字簽名的分組檢測。當(dāng)數(shù)字簽名集合中存在非法數(shù)字簽名時，通過將數(shù)字簽名分成不同的組，分組實(shí)施批量驗(yàn)證，從而逐步確定非法數(shù)字簽名。

分組檢測方案是針對數(shù)字簽名聚合驗(yàn)證存在至少一個非法數(shù)字簽名而進(jìn)行非法對象識別的分組聚合驗(yàn)證方法，按照分組之間的關(guān)系，可以分為序貫類分組檢測和非適應(yīng)性分組檢測[12]。序貫類分組檢測是按照一定規(guī)則對檢測對象進(jìn)行“多次”有序分組檢測，直到所有非法對象被全部識別。但在序貫類分組檢測中，前一次檢測的結(jié)果決定后一次分組的情況，檢測過程具有嚴(yán)格的順序性，只能一步一步按照分組順序完成，如基于二元分叉樹的分組檢測。非適應(yīng)性分組檢測是根據(jù)一定規(guī)則巧妙地將檢測對象“一次性”分成若干組，同一檢測對象可以包含在多個組中，使檢測具有一定數(shù)量的對象析取性，便于采用平行檢測的方法對各組進(jìn)行同時檢測，并通過檢測結(jié)果的呈現(xiàn)情況析取非法數(shù)字簽名[3]。序貫類分組檢測簡單、實(shí)現(xiàn)容易，但運(yùn)算效率很難提高[13-14]。非適應(yīng)性分組檢測可以并行檢測，在多處理器的情況下，運(yùn)算效率較高，但分組方案構(gòu)造復(fù)雜?，F(xiàn)有的非適應(yīng)性分組檢測算法具有以下3個特點(diǎn)：一是分組檢測的次數(shù)、時間等參數(shù)界限研究探索較多[15-16]，而具體方案構(gòu)造研究成果較少；二是分組檢測方案構(gòu)造不準(zhǔn)確，存在非法數(shù)字簽名不能完全析出的情況，如隨機(jī)矩陣法[12]；三是分組檢測方案的存在性理論缺乏嚴(yán)格證明，如基于糾錯碼（ECC,error correction code）的分組方案構(gòu)建，缺少檢測對象數(shù)量變化時的分組方案存在性證明[3,17-18]。

綜上所述，本文針對數(shù)字簽名的快速驗(yàn)證問題，研究分組批量驗(yàn)證算法，基于拉丁方理論構(gòu)造分組方案，以較少次數(shù)的群組認(rèn)證完成非法數(shù)字簽名的識別，實(shí)現(xiàn)多個消息數(shù)字簽名的快速驗(yàn)證。本文主要貢獻(xiàn)如下。

1) 采用拉丁方理論構(gòu)建橫截設(shè)計。以有限域理論為基礎(chǔ)設(shè)計素數(shù)冪階拉丁方，證明素數(shù)冪階拉丁方存在性是橫截設(shè)計存在的充分必要條件，為數(shù)字簽名分組批量驗(yàn)證方案確立提供理論基礎(chǔ)。

2) 基于橫截設(shè)計理論構(gòu)建析取矩陣。證明當(dāng)橫截設(shè)計TD[k,;λm]的λ=1 時，其關(guān)聯(lián)矩陣M的轉(zhuǎn)置矩陣MT是一個析取矩陣，將區(qū)組設(shè)計與析取矩陣聯(lián)系起來，為析取矩陣的構(gòu)建提供具體方法。

3) 通過析取矩陣?yán)碚摯_定分組方案。以析取矩陣的列向量選擇性為基礎(chǔ)，根據(jù)檢測對象的總數(shù)量以及其中包含非法者的數(shù)量確定析取矩陣的階數(shù)，并由此構(gòu)建分組檢測方案，完成檢測，根據(jù)分組檢測結(jié)果推斷非法數(shù)字簽名在集合中的位置。

4) 對所提數(shù)字簽名分組批量驗(yàn)證方案進(jìn)行理論分析與仿真驗(yàn)證。理論分析證明了所提方案的正確性、安全性、高效性，并以Linux Ubantu20 為平臺、Python3.9 為編程語言，引入雙線性對函數(shù)庫pypbc，基于成熟的BGLS 聚合簽名算法[19]進(jìn)行數(shù)字簽名批量驗(yàn)證，仿真實(shí)現(xiàn)分組檢測算法并識別非法對象。結(jié)果表明，所提方案能準(zhǔn)確可靠地識別非法對象，同時在多個處理器并行計算時相較其他算法檢測效率有所提高。

1 相關(guān)知識

本節(jié)介紹析取矩陣、區(qū)組設(shè)計、關(guān)聯(lián)矩陣等非適應(yīng)性分組檢測的相關(guān)概念和背景知識。析取矩陣[12]用于非適應(yīng)分組檢測方案的非法數(shù)字簽名的識別分析；區(qū)組設(shè)計[20]用于構(gòu)造非適應(yīng)性分組檢測方案；關(guān)聯(lián)矩陣[21]用于區(qū)組設(shè)計的矩陣化表示，是區(qū)組設(shè)計研究的一個有力的代數(shù)工具。

定義1d階析取矩陣[12]。對于0-1 矩陣Mt×n，若任意d列的并集不包含其他列向量，即，則稱Mt×n為d階析取矩陣。換句話講，對于任意d+1 列，必然存在至少一行（不妨設(shè)為第i行），使d列的元素mij=0，即并集=0，而

定義2區(qū)組設(shè)計[20]。有限集合X上的任意一個子集族B={B1,…,Bt}為X上的一個區(qū)組設(shè)計，記作D={X,B}。X稱為此設(shè)計的基集，而子集族B中的諸子集Bi(i=1,…,t)則稱為此設(shè)計的區(qū)組。

常見的區(qū)組設(shè)計包括成對平衡設(shè)計（PBD,pairwise balanced design）、可分組設(shè)計（GDD,group divisible design）、橫截設(shè)計（TD,transversal design）、平衡不完全區(qū)組設(shè)計（BIBD,balanced incomplete block design）等[22]，本文主要應(yīng)用橫截設(shè)計進(jìn)行區(qū)組設(shè)計。

定義3橫截設(shè)計[22]。對于區(qū)組設(shè)計D={X,B}，若有限集合X的一個劃分為G={G1,…,G k}（其中Gj,j=1,…,k稱為組），且滿足以下三點(diǎn)。

1) 對任意B∈B，=k。

2) 對任意Gj∈G，=m。

3)X中屬于同一組的不同元素在區(qū)組中的相遇數(shù)λD(x,y)總為零，而屬于不同組的2 個元素x,y的相遇數(shù)λD(x,y)是不依賴于x,y的常數(shù)，即對于任意x,y∈X，x≠y，有

則稱其為橫截設(shè)計，記作TD[k,λ;m]。

定義4關(guān)聯(lián)矩陣[21]。對于區(qū)組設(shè)計D={X,B}，其中有限集合X={x1,…,xn}及其子集族B={B1,…,Bt}，存在 0-1 矩陣Mt×n={mij}，i=1,…,t，j=1,…,n，t表示區(qū)組個數(shù)，n表示基集X元素個數(shù)，且

則稱Mt×n為區(qū)組設(shè)計的關(guān)聯(lián)矩陣。

2 非適應(yīng)性分組檢測模型

根據(jù)分組檢測對象數(shù)量進(jìn)行區(qū)組設(shè)計，構(gòu)建非適應(yīng)性分組檢測模型，關(guān)鍵在于尋找相應(yīng)的析取矩陣，本文首先運(yùn)用拉丁方理論進(jìn)行區(qū)組設(shè)計——橫截設(shè)計，然后證明構(gòu)造的橫截設(shè)計對應(yīng)的關(guān)聯(lián)矩陣是析取矩陣，最后再運(yùn)用析取矩陣進(jìn)行分組檢測，完成非法對象的識別。

2.1 基于拉丁方理論的橫截設(shè)計

橫截設(shè)計是構(gòu)造區(qū)組設(shè)計的重要方法之一，它與正交拉丁方理論有著密切關(guān)系。正交拉丁方是組合設(shè)計的一個重要研究課題，在橫截設(shè)計的遞歸構(gòu)造方法中，正交拉丁方組對于橫截設(shè)計的存在性起著十分關(guān)鍵的作用。下面首先介紹正交拉丁方的一些概念和基本性質(zhì)，然后論證它與橫截設(shè)計的關(guān)系，最后給出正交拉丁方的構(gòu)造方法，從而完成橫截設(shè)計的構(gòu)造。

定義5拉丁方[22]。設(shè)S是一個m元集，若A為S上的一個m×m階陣列（即矩陣），其每一行與每一列都是集合S的一個全排列，則稱A是S上的一個m階拉丁方。

定義6正交拉丁方[22]。對于集合S和S′上的2 個m階拉丁方A=(aij)和B=(bij)，A和B在(i,j)位置上的有序?qū)?aij,bij)∈S×S′稱為一個對子，A和B在全部m2個不同位置上的對子兩兩不同，即=m2，則稱拉丁方A和B正交。若一組m階拉丁方A1,…,At兩兩正交，則稱其為一個正交拉丁方組。

對于矩陣

根據(jù)定義6，顯然H與其轉(zhuǎn)置矩陣G=HT正交。顯然，若A是{1,…,m}上的任一m×m階陣列，則A是m階拉丁方的充要條件是A與H及A與G都正交。

定理1[22]存在TD[k,1;m]的充要條件是存在一個k-2個m階正交拉丁方組。

證明令D=(X,G,B)是個TD[k,1;m]，根據(jù)TD 定義，則對任一B∈B 及任一Gj∈G，有=1，即任一區(qū)組B由每個組中各取一個元素組成。任取劃分G的2 個不同的組G1和G2（劃分的每個組中含有m個元素），由于B中的每個區(qū)組恰好包含了一個G1的元素和一個G2的元素，且由于λ=1，G1的元素和G2的元素在B的每個區(qū)組中總共相遇一次，因此B的區(qū)組數(shù)等于G1中所有元素和G2中所有元素的相遇總次數(shù)，即

因此，B中共有m2個區(qū)組，G1的m個元素和G2的m個元素在B的每個區(qū)組中僅僅相遇一次，故G1和G2元素在區(qū)組設(shè)計B 中組成的有序數(shù)對{(g1,g2)|g1∈G1,g2∈G2}僅僅出現(xiàn)一次可以看成{1,…,m}上2 個正交的陣列，那么G1,…,G k的元素在區(qū)組設(shè)計B中兩兩組成的有序數(shù)對僅僅出現(xiàn)一次可以看成{1,…,m}上兩兩正交的陣列，除了H和G，則一定還存在k-2個正交拉丁方。

反之，若存在k-2 個m階正交拉丁方，加上H和G，便可以構(gòu)造k個兩兩正交的m階陣列組，這些陣列兩兩之間每個元素對僅僅出現(xiàn)一次，照此便可以構(gòu)造出一個TD[k,1;m]。證畢。

然而，并不是任意階的正交拉丁方都是存在的，Bose、Shrikhande 和Parker 三人經(jīng)過共同努力，證明了若n≠2,6則必定存在一對拉丁方。由上述定理可知，在構(gòu)造橫截設(shè)計時，需要盡可能多的拉丁方。根據(jù)有限域存在定理[23]，對于任意素數(shù)冪pτ，存在一個含有pτ個元素的有限域，顯然TD[k,1;m]的約束和有限域的特征非常相似，下面介紹通過有限域構(gòu)造正交拉丁方組的方法。

則 (e1-e2)i=(e1-e2)k。

由于e1≠e2，故(e1-e2)-1，因此i=k，代入可得j=l。

綜上所述，A(1),A(2),…,A(m-1)是兩兩正交的拉丁方組。證畢。

2.2 基于橫截設(shè)計的析取矩陣

析取矩陣是一類二元疊加碼，可以用作分組檢測的一種數(shù)學(xué)模型，廣泛應(yīng)用在信息傳輸中的多路存取信道、分子生物學(xué)、基因遺傳測試、病毒分組檢測等諸多方面，橫截設(shè)計TD[k,1;m]關(guān)聯(lián)矩陣M的轉(zhuǎn)置矩陣具備析取矩陣的特征，以下將從理論上證明這種推斷。

在t行n列的0-1 矩陣M中，Cj表示第j列向量；wj表示第j列向量Cj的重量，即Cj中“1”的個數(shù)；λij表示列向量Ci與Cj的點(diǎn)乘，即Ci與Cj相同行上都為1的個數(shù)，也稱為Ci與Cj相交λij次。

定理3當(dāng)TD[k,;λm]設(shè)計的λ=1 時，其關(guān)聯(lián)矩陣M的轉(zhuǎn)置矩陣MT的λT=0 或1，則MT是k-1階析取矩陣。

證明當(dāng)λ=1 時，TD 區(qū)組設(shè)計對應(yīng)關(guān)聯(lián)矩陣M的任意兩列的內(nèi)積為1，即M的任意兩列僅僅有一次在相同位置（行）都為“1”，則M的任意兩行元素僅僅有一次在相同位置（列）都為“1”，下面用反證法進(jìn)行證明。假設(shè)M的任意兩行元素至少有兩次在相同位置（列）都為“1”，此時M的任意兩列元素至少有兩次在相同位置（行）都為“1”，與λ=1相矛盾，故M的轉(zhuǎn)置矩陣MT的λT=0或1，則=1，此時，由引理1可知MT是k-1（即w-1）階析取矩陣。證畢。

2.3 基于析取矩陣的分組檢測

采用分組檢測進(jìn)行數(shù)字簽名驗(yàn)證，將數(shù)字簽名進(jìn)行分組，分組結(jié)果用關(guān)聯(lián)矩陣Mt×n表示，其中矩陣的列對應(yīng)要檢驗(yàn)的數(shù)字簽名，矩陣的行對應(yīng)分組，Mt×n中元素{mij}的取值參考定義4。

不妨假設(shè)將要進(jìn)行分組批量驗(yàn)證的數(shù)字簽名集合Σ=(σ1,…,σn)的狀態(tài)為X=(x1,…,xn)，其中xi(i=1,…,n)表示每個數(shù)字簽名的實(shí)際狀態(tài)，xi=0表示第i個數(shù)字簽名合法，xi=1表示第i個數(shù)字簽名非法。為了快速進(jìn)行數(shù)字簽名驗(yàn)證，運(yùn)用2.1 節(jié)的橫截設(shè)計對數(shù)字簽名進(jìn)行分組，并行進(jìn)行分組檢測，用Y表示分組檢測結(jié)果，記為Y=(y1,…,yt)，其中yj=0(j=1,…,t)表示本組檢測的數(shù)字簽名集合全部合法，yj=1(j=1,…,t)表示本組檢測的數(shù)字簽名集合至少包含一個非法數(shù)字簽名，它與X和Mt×n的關(guān)系可以表示為

根據(jù)2.2 節(jié)的證明，上述分組批量檢測區(qū)組設(shè)計的關(guān)聯(lián)矩陣Mt×n為d階析取矩陣，當(dāng)數(shù)字簽名集合X中非法數(shù)字簽名的個數(shù)不超過d時，運(yùn)用算法1 便可以確定非法數(shù)字簽名。

算法1非法數(shù)字簽名分組檢測法

3 數(shù)字簽名分組檢測實(shí)施

網(wǎng)絡(luò)的中心節(jié)點(diǎn)每秒接收到大量節(jié)點(diǎn)發(fā)來的消息，為加快消息簽名的驗(yàn)證速度，通常采用“聚合簽名+分組檢測”的方法進(jìn)行數(shù)字簽名的驗(yàn)證，如圖2 所示。首先采用聚合簽名算法將所有來自不同節(jié)點(diǎn)的消息簽名設(shè)計為具有同態(tài)性特征，便于后續(xù)聚合驗(yàn)證作為中心節(jié)點(diǎn)的信息處理中心先將所有消息及其簽名進(jìn)行一次聚合驗(yàn)證，若驗(yàn)證成功，則表明所有消息合法；否則，證明消息集合中至少存在一個非法對象，需要進(jìn)一步采取非適應(yīng)性分組的思想進(jìn)行分組聚合驗(yàn)證，用i表示分組序號，i取遍t個分組，通過分組驗(yàn)證的結(jié)果排除合法對象，從而確定非法對象，當(dāng)出現(xiàn)無法確定的對象時還可以補(bǔ)充進(jìn)行個體認(rèn)證。由此可見，實(shí)現(xiàn)消息簽名批量驗(yàn)證的是聚合簽名算法，識別非法對象依靠分組檢測，不同的分組方案對應(yīng)著不同的識別效率。

圖2 數(shù)字簽名快速驗(yàn)證方法

3.1 聚合簽名

為提高數(shù)字簽名的驗(yàn)證效率，在一般數(shù)字簽名算法的基礎(chǔ)上，楊濤等[8]提出一種具有同態(tài)性結(jié)構(gòu)的變體數(shù)字簽名算法，驗(yàn)證者能夠?qū)碜匀我獠煌?jié)點(diǎn)的多個數(shù)字簽名壓縮合成為與單個數(shù)字簽名幾乎同等大小的短簽名進(jìn)行批量驗(yàn)證，大大減小了多個簽名驗(yàn)證的工作量，這就是聚合簽名。聚合簽名由于其高效性、簡捷性，廣泛應(yīng)用于安全路由協(xié)議、網(wǎng)云信息聚合、日志審計、分布式計算等方面，在諸多信息科技領(lǐng)域發(fā)揮著重要的安全保護(hù)作用，成為近年來被關(guān)注的一個研究熱點(diǎn)。本文采用經(jīng)典的BGLS 聚合簽名算法[19]完成消息簽名的批量驗(yàn)證，下面對該算法進(jìn)行闡述。

設(shè)G1和G2是2 個p階的乘法循環(huán)群（p為素數(shù)），g1和g2分別是G1和G2的生成元；ψ:G1→G2是一個同構(gòu)映射，且ψ(g1)=g2；e:G1×G2→GT是一個雙線性對運(yùn)算；h:{0,1}*→G2是一個雜湊函數(shù)，可以看作一個隨機(jī)預(yù)言機(jī)。

密鑰生成。選擇隨機(jī)數(shù)x∈RZp，計算v=則v∈G1作為用戶的公鑰，x∈Zp作為用戶的私鑰。

簽名生成。對于用戶u i∈U，公鑰為vi，私鑰為xi，需要簽名的消息為Mi∈{0,1}*，可得hi=h(Mi)，σi=。

BGLS 聚合簽名算法的安全性等價于隨機(jī)預(yù)言模型下CDH（computational Diffie-Hellman）問題的安全性。

3.2 實(shí)施步驟

假設(shè)檢測n=m2（m為素數(shù)或素數(shù)冪）個數(shù)字簽名集合，其中含有不超過d=k-1個非法數(shù)字簽名，根據(jù)拉丁方理論便可以構(gòu)造一個橫截設(shè)計TD[k,1;m]，當(dāng)m＞k時，通過km次分組檢測完成m2個數(shù)字簽名的驗(yàn)證，識別出非法數(shù)字簽名，如圖3所示，具體步驟如下。

圖3 數(shù)字簽名分組檢測實(shí)施步驟

步驟1確定分組檢測參數(shù)設(shè)置。根據(jù)需要檢測的數(shù)字簽名集合大小n以及非法對象數(shù)量上限d，確定橫截設(shè)計TD[k,1;m]的參數(shù)(k,m)，如果數(shù)字簽名的總數(shù)及非法對象的個數(shù)不滿足上述要求，可以進(jìn)行適當(dāng)?shù)娜哂嗵畛?，達(dá)到要求。

步驟2構(gòu)造k-2個正交拉丁方。采用定理2構(gòu)造k-2個m階正交拉丁方A(1),…,A(k-2)。

步驟3由H,G,A(1),…,A(k-2)構(gòu)造TD[k,1;m]。

步驟4編寫TD[k,1;m]的關(guān)聯(lián)矩陣求出d階析取矩陣

步驟5 按照進(jìn)行分組檢測，通過檢測結(jié)果由算法1 推知非法數(shù)字簽名。

3.3 舉例說明

如果對25 個數(shù)字簽名進(jìn)行驗(yàn)證，據(jù)前期統(tǒng)計估計其中包含非法數(shù)字簽名的數(shù)量不超過2 個，則令n=m2=52，d=k-1=2，則k=3，m=5，確定橫截設(shè)計為TD[3,1;5]。

利用定理2 構(gòu)造一個5 階拉丁方矩陣

連同H和G，按照定理1的方法，由3 個拉丁方一起構(gòu)成一個橫截設(shè)計TD[3,1;5]，其關(guān)聯(lián)矩陣為25 行15 列矩陣M25×15，轉(zhuǎn)置后得到15 行25 列0-1 矩陣其中每列有3 個“1”，每行有5 個“1”，如圖4 所示。

根據(jù)定理3可知，0-1矩陣TM為2 階析取矩陣。圖4 中的矩陣25 列表示需要驗(yàn)證的25 個數(shù)字簽名，15 行表示25 個數(shù)字簽名分成的15 個分組，矩陣中(i,j) 處的元素“1”表示j列的數(shù)字簽名屬于i行的分組；否則，表示不在此分組。析取矩陣的性質(zhì)表明，按照圖4 中分組方案進(jìn)行批量驗(yàn)證，可以通過15 次分組檢測對25 個數(shù)字簽名完成不超過2 個非法對象的識別。

為了說明分組方案在數(shù)字簽名批量驗(yàn)證中的使用思路，不妨假設(shè)第3、6 個數(shù)字簽名是非法的，在圖4 中用方框表示，按照分組方案調(diào)用聚合簽名算法完成15 個分組的批量驗(yàn)證，得到檢測結(jié)果Y=(1,1,0,0,0,1,0,1,0,0,0,1,1,0,0)T，由于15×25M是2 階析取矩陣，Y中的“0”表示本組檢測中所有數(shù)字簽名均為合法，根據(jù)算法1，采用排除法可以依次確定合法數(shù)字簽名x11、x12、x13、x14、x15、x16、x17、x18、x19、x20、x21、x22、x23、x24、x25、x2、x7、x4、x9、x5、x10、x1、x8，如圖4 中下劃線所示；根據(jù)析取矩陣的性質(zhì)可知，剩下的簽名x3、x6便為非法數(shù)字簽名。

圖4 15 個數(shù)字簽名的分組驗(yàn)證的分組情況

4 性能分析

本節(jié)通過理論證明和仿真實(shí)驗(yàn)，對本文算法進(jìn)行了可行性和復(fù)雜度分析，并對非法數(shù)字簽名數(shù)量估計不準(zhǔn)的情況討論了方案的容錯性；同時借助開源的雙線性對計算函數(shù)庫，編程實(shí)現(xiàn)了BGLS 聚合簽名方案和本文算法，仿真驗(yàn)證了數(shù)字簽名分組檢測方案。結(jié)果表明，在相同安全要求下，本文算法相較于逐一驗(yàn)證具有高效性，即使與經(jīng)典的二分法檢測相比也具有明顯的效率優(yōu)勢。

4.1 理論證明

1) 可行性分析

根據(jù)算法1的排除法可知，本文算法是通過分組檢測結(jié)果中合法結(jié)果（即檢測結(jié)果為“0”分組）選出合法數(shù)字簽名，然后取合法數(shù)字簽名對應(yīng)的余集作為可疑簽名集U=XV，若≤d則確定非法數(shù)字簽名。之所以能夠識別非法數(shù)字簽名，是因?yàn)殛P(guān)聯(lián)矩陣的析取性，下面根據(jù)析取矩陣的特性，對其進(jìn)行證明。

定理4群組認(rèn)證關(guān)聯(lián)矩陣是d階析取矩陣，則由分組檢測的結(jié)果Y通過算法1 可以識別不超過d個非法數(shù)字簽名。

2) 復(fù)雜度分析

本文算法對n個數(shù)字簽名進(jìn)行驗(yàn)證，初步估計非法數(shù)字簽名的數(shù)量不超過d個。下面對本文算法的復(fù)雜度進(jìn)行分析。

定理5 本文算法進(jìn)行分組檢測，通過個分組完成n個數(shù)字簽名進(jìn)行驗(yàn)證，非法數(shù)字簽名識別算法（算法1）的時間復(fù)雜度為其中d為非法數(shù)字簽名的數(shù)量上限，且d?n。

證明要完成n個數(shù)字簽名進(jìn)行驗(yàn)證，根據(jù)3.2 節(jié)中的實(shí)施步驟，首先基于拉丁方構(gòu)造了用于分組檢測的析取矩陣MT，它的行數(shù)為km，列數(shù)為m2，由于k=d+1，n=m2，則

另外，當(dāng)分組批量驗(yàn)證完成后，需要通過算法1運(yùn)用排除法完成非法數(shù)字簽名的識別，只有分組批量驗(yàn)證為“0”的分組才參與排除法，不妨用t0表示批量驗(yàn)證Y=(y1,y2,…,ykm)中為“0”的分組，根據(jù)橫截設(shè)計的“0”“1”分布特征，關(guān)聯(lián)矩陣MT的每列元素“1”的個數(shù)為k，分組批量驗(yàn)證結(jié)果Y=(y1,y2,…,ykm)便為MT的所有非法數(shù)字簽名對應(yīng)列的布爾和，因此結(jié)合非法數(shù)字簽名的數(shù)量上限d，可知Y中“0”的個數(shù)滿足

3) 容錯性分析

容錯性是指當(dāng)非法數(shù)字簽名數(shù)量估計不準(zhǔn)確時，分組檢測方案識別非法數(shù)字簽名的能力變化情況。顯然當(dāng)非法數(shù)字簽名的實(shí)際數(shù)量d′≤d時，關(guān)聯(lián)矩陣MT為d階析取矩陣的分組檢測方案識別能力沒有變化，因此重點(diǎn)討論d′＞d的情況，此時分組驗(yàn)證的結(jié)果Y=(y1,y2,…,ykm)便為所有d′列元素的布爾和。因?yàn)殛P(guān)聯(lián)矩陣MT為d階析取矩陣，所以無法通過算法1 準(zhǔn)確識別非法數(shù)字簽名，卻可以確定一個包含所有非法數(shù)字簽名的更大的可疑對象集合，此時可以采用圖1的方法對可疑對象進(jìn)行逐一驗(yàn)證，從而完成非法數(shù)字簽名的識別。具體舉例如下，參照圖4的關(guān)聯(lián)矩陣，需要驗(yàn)證的數(shù)字簽名個數(shù)仍為25，初步估計其中非法者的個數(shù)不超過2 個，但實(shí)際第3、11、17 個數(shù)字簽名是非法的，利用上述分組檢測得到檢測結(jié)果Y=(1,0,1,1,0,1,1,1,0,0,0,0,1,0,1)T，由于15×25M是2 階析取矩陣，Y中的“0”表示本組檢測中所有數(shù)字簽名均為合法，采用排除法可以依次確定合法數(shù)字簽名x6、x7、x8、x9、x10、x21、x22、x23、x24、x25、x4、x14、x19、x5、x15、x20、x1、x18、x2、x6、x12、x16，剩下的數(shù)字簽名x3、x11、x13、x17都為可疑對象；此時剩下的數(shù)字簽名數(shù)量超過3，證明非法數(shù)字簽名數(shù)量估計偏少，2 階析取的關(guān)聯(lián)矩陣無法完成非法數(shù)字簽名的確定。如果剩余簽名數(shù)量和初始估計的簽名數(shù)量相差較大，則需要重新設(shè)計分組檢測方案；否則，便可以逐一認(rèn)證剩下的簽名，確定非法對象。因此，逐一驗(yàn)證x3、x11、x13、x17便可以完成所有數(shù)字簽名的驗(yàn)證。

4.2 仿真比較

為檢驗(yàn)本文算法的實(shí)際性能，在處理器為Intel Core i5-4200 2.5 GHz、內(nèi)存為4 GB的筆記本電腦的虛擬機(jī)VMware Workstation Pro 上安裝Linux Ubantu20 操作系統(tǒng)，在Python 3.9 編程環(huán)境下基于GMP（GNU multiple precision）和PBC（pairing-based cryptography）配置pypbc 雙線性對匹配加密庫，雜湊函數(shù)采用SHA-256，仿真環(huán)境配置如圖5 所示。

圖5 仿真環(huán)境配置

基于BGLS 聚合簽名方案進(jìn)行數(shù)字簽名的批量處理，以數(shù)字簽名的數(shù)量n及其所含非法數(shù)字簽名的上限d作為分組的依據(jù)，采用3.2 節(jié)的步驟進(jìn)行分組檢測，使用算法1 進(jìn)行非法對象的識別，部分仿真結(jié)果如表1 所示。

表1 數(shù)字簽名分組檢測部分仿真結(jié)果

分組檢測的完成時間主要與分組檢測次數(shù)相關(guān)，當(dāng)數(shù)字簽名的數(shù)量、非法數(shù)字簽名的數(shù)量增加時，分組個數(shù)必然增加，如圖6 所示。隨著分組檢測次數(shù)的增加，完成數(shù)字簽名驗(yàn)證的時間也在增加，正如表1 所示。另外，從仿真實(shí)驗(yàn)中發(fā)現(xiàn)，當(dāng)數(shù)字簽名的總數(shù)n不變，但非法數(shù)字簽名的數(shù)量增加到接近n/3 時，分組檢測的效果低于逐一驗(yàn)證的效率，與文獻(xiàn)[12]結(jié)論一致。

圖6 分組檢測次數(shù)與數(shù)字簽名的數(shù)量、非法數(shù)字簽名的數(shù)量的關(guān)系

非適應(yīng)性分組檢測方案與序貫性分組檢測方案比較，一個重要區(qū)別在于分組平行處理，本文仿真采用Thread 函數(shù)進(jìn)行平行檢測處理，如表2所示。當(dāng)數(shù)字簽名的數(shù)量和非法數(shù)字簽名的數(shù)量分別為n和d時，列出逐一驗(yàn)證、二分法驗(yàn)證和本文算法在不同處理器數(shù)量時的最大檢測數(shù)量。逐一驗(yàn)證需要對每個簽名進(jìn)行一次驗(yàn)證，驗(yàn)證次數(shù)為n，在p個處理器工作的情況下，可以將數(shù)字簽名分為p個分組，需要次檢測；二分法驗(yàn)證采用折半查找法，每次需要次檢驗(yàn)，只能檢測一個非法數(shù)字簽名，d個非法數(shù)字簽名需要次檢驗(yàn)，在p個處理器工作的情況下，可以將數(shù)字簽名分為p個分組，分別進(jìn)行折半查找，需要次檢測；本文算法通過個分組完成n個數(shù)字簽名中d個非法數(shù)字簽名識別，在p個處理器工作的情況下，可以將數(shù)字簽名分為個分組同時進(jìn)行，需要次驗(yàn)證。

本文算法采用并行處理的設(shè)計思想，為便于驗(yàn)證的同時進(jìn)行處理，設(shè)計了個獨(dú)立并行的分組進(jìn)行驗(yàn)證數(shù)字簽名。從表2 可以看出，單個處理器時二分法驗(yàn)證效率最高，達(dá)到O(logn)，而本文算法的僅比逐一驗(yàn)證的O(n)較好一些。當(dāng)多個處理器同時處理時，所有算法都可以并行處理，不管是逐一驗(yàn)證、二分法驗(yàn)證還是本文算法的檢驗(yàn)效率都有所提高，本文算法的效率提升明顯，提高到單個處理器時的p倍，而二分法驗(yàn)證提高了logn p倍，顯然（通常n＞p）。

表2 數(shù)字簽名分組檢測比較

如圖7 所示，將本文算法與逐一驗(yàn)證和二分法驗(yàn)證進(jìn)行比較發(fā)現(xiàn)，當(dāng)單個處理器串行驗(yàn)證時，二分法驗(yàn)證有相對較好的表現(xiàn)，同等數(shù)量的數(shù)字簽名需要的驗(yàn)證次數(shù)最少；當(dāng)多個處理器并行驗(yàn)證時，在非法數(shù)字簽名數(shù)量d=8、處理器個數(shù)p=100的情況下，雖然逐一驗(yàn)證和二分法驗(yàn)證可以用多個處理器同時進(jìn)行驗(yàn)證，效率有所提升，但是隨著數(shù)字簽名的數(shù)量增多，本文算法表現(xiàn)出較強(qiáng)的效率優(yōu)勢。當(dāng)數(shù)字簽名的總數(shù)大于3 000 時，本文算法與逐一驗(yàn)證相比才體現(xiàn)出優(yōu)勢，在多處理器保障的條件下，本文算法分組檢測的次數(shù)隨著數(shù)字簽名總數(shù)的變化不大，基本上保持在8 附近，與二分法驗(yàn)證、逐一驗(yàn)證相比，具有最少的驗(yàn)證次數(shù)，效率最高。隨著數(shù)字簽名的數(shù)量不斷增大，尤其是的增大，當(dāng)多處理器并行驗(yàn)證時本文算法會表現(xiàn)出更多優(yōu)勢。

圖7 分組檢測次數(shù)與數(shù)字簽名的數(shù)量的關(guān)系

5 結(jié)束語

數(shù)字簽名的非適應(yīng)性分組驗(yàn)證是為提高網(wǎng)絡(luò)中心節(jié)點(diǎn)數(shù)字簽名的驗(yàn)證效率，將組合設(shè)計理論與聚合簽名理論相結(jié)合，以橫截設(shè)計理論為基礎(chǔ)設(shè)計數(shù)字簽名分組方案，以聚合簽名理論為方法完成數(shù)字簽名的批量分組驗(yàn)證，實(shí)現(xiàn)數(shù)字簽名的并行快速驗(yàn)證。它通常應(yīng)用于傳感器網(wǎng)、交通網(wǎng)、物聯(lián)網(wǎng)等具有海量節(jié)點(diǎn)信息需要安全驗(yàn)證，且消息時敏性強(qiáng)的無線網(wǎng)絡(luò)環(huán)境。本文基于組合數(shù)學(xué)的拉丁方理論設(shè)計了數(shù)字簽名分組方案，并以經(jīng)典的BGLS 聚合簽名理論進(jìn)行數(shù)字簽名的批量驗(yàn)證，構(gòu)建了一個以次數(shù)完成n個數(shù)字簽名驗(yàn)證的非適應(yīng)性數(shù)字簽名分組驗(yàn)證方案。該方案與逐一認(rèn)證相比具有較高驗(yàn)證效率；在多處理器保障的條件下，與序貫類分組方案相比具有驗(yàn)證次數(shù)少、效率高的優(yōu)勢。但本文研究未考慮數(shù)字簽名在信道中的傳輸錯誤問題，需要進(jìn)一步研究加入檢錯糾錯機(jī)制，增強(qiáng)分組檢測的容錯性能。