基于中國剩余定理的前向安全的聚合簽名方案

韋性佳，蘆殿軍

(青海師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，青海 西寧 810008)

0 引 言

隨著時代的發(fā)展，信息安全問題目前已經(jīng)成為制約中國乃至全球經(jīng)濟發(fā)展的重要問題。隨著中國第一部《密碼法》的頒布，信息安全領(lǐng)域的發(fā)展迎來了新的機遇和挑戰(zhàn)。

數(shù)字簽名作為信息安全領(lǐng)域的重要內(nèi)容之一，已經(jīng)成為國內(nèi)外研究的熱點課題之一[1-2]。

聚合簽名作為一種多方參與的數(shù)字簽名方案，在保障數(shù)據(jù)的安全傳遞與高效存儲方面具有較強的實踐價值[3-4]。聚合簽名的概念最早由Boneh等人[5]在2003年的歐密會上提出，并且基于雙線性對技術(shù)構(gòu)造了第一個抗存在性偽造的聚合簽名方案，對聚合簽名的發(fā)展具有深遠的影響。但是Shao等人[6]通過安全性分析指出Boneh等人的方案在安全性方面存在漏洞，可以被模擬敵手攻擊。Cheon等[7]提出了第一個基于身份的聚合簽名方案，將身份信息作為驗證工具，提高了方案的安全性。近年來，區(qū)塊鏈與云計算技術(shù)的不斷發(fā)展，聚合簽名已經(jīng)廣泛應(yīng)用于許多現(xiàn)實領(lǐng)域，2018年苑超等人[8]將區(qū)塊鏈中共識算法的改進算法dBFT為研究對象，結(jié)合聚合簽名技術(shù)以及雙線性映射技術(shù)對該算法的共識過程進行優(yōu)化，有效降低了區(qū)塊鏈系統(tǒng)簽名的空間復(fù)雜度，為區(qū)塊鏈的發(fā)展提供了重要的實踐依據(jù)。2020年楊小東等人[9]針對車載自組網(wǎng)(VANET)中的隱私泄露和簽名驗證效率較低等問題，結(jié)合聚合簽名技術(shù)，提出了一種基于身份聚合簽名的車載自組網(wǎng)消息認證方案，有效縮短了車輛對通信消息的認證響應(yīng)時間。

在實踐應(yīng)用中，由于敵手計算能力的提升以及簽名成員的變動導(dǎo)致簽名過程是動態(tài)的，在這個背景下，前向安全性理論由此產(chǎn)生。1997年，Anderson[10]首次提出了前向安全性理論,解決了傳統(tǒng)數(shù)字簽名中因秘密的被動或主動泄露對系統(tǒng)安全所帶來的隱患問題。1999年，Bellare和Miner[11]提出了第一個具有前向安全性質(zhì)的數(shù)字簽名方案，為前向安全性理論的進一步發(fā)展奠定了基礎(chǔ)。隨著前向安全性理論的不斷發(fā)展，各種前向安全的數(shù)字簽名方案不斷提出[12-14]。2018年，王巖等人[15]基于中國剩余定理提出了一種動態(tài)門限簽名方案，該方案實現(xiàn)了簽名私鑰的前向安全性，能有效地抵抗移動攻擊，同時具有較高的效率與實踐價值。同年，Jihye K等人[16]提出了一種前向安全的順序聚合簽名方案，該方案可以有效地應(yīng)用于計算機審核日志的安全管理中，為計算機網(wǎng)絡(luò)安全提供了重要的安全保障。2019年，洪璇等人[17]基于中國剩余定理提出一種前向安全的群簽名方案，為該文提供了重要的研究思路。

但是，目前將前向安全性結(jié)合到聚合簽名方案中的文獻相對較少，由于聚合簽名具有較強的實踐價值，該文基于中國剩余定理提出了一種具有前向安全性質(zhì)的聚合簽名方案，方案的簽名，驗證過程基于橢圓曲線循環(huán)群，能有效降低數(shù)據(jù)的存儲空間。同時，在隨機預(yù)言模型下，方案具有抗存在性偽造的特性。

1 基礎(chǔ)知識

1.1 雙線性映射

令(G1,+)，(G2,·)是兩個循環(huán)群，且|G1|=|G2|=q(q是大素數(shù))，P是G1的生成元，存在雙線性映射e:G1×G1→G2滿足下列的性質(zhì)：

(1)雙線性性：

有如下的性質(zhì)：

(i)e(aP,bQ)=e(P,Q)ab;

(ii)e(P,Q1+Q2)=e(P,Q1)e(P,Q2)。

(2)非退化性：?P∈G1，使得e(P,P)≠1。

(3)可計算性：?P,Q∈G1，存在有效的算法能夠計算e(P,Q)。

1.2 橢圓曲線離散對數(shù)問題(ECDLP問題)

1.3 計算性Diffie-Hellman(CDH)問題

1.4 強RSA問題與假設(shè)

強RSA假設(shè)：在不清楚N的因子分解的前提下，強RSA問題是難于求解的。

1.5 前向安全性理論

前向安全性理論：(1)參與者首先通過可信中心的廣播信息得到驗證子秘密SPi；(2)通過秘密信道從可信中心得到并保密自己的初始子秘密Si0；(3)將秘密的有效期分為T個時間段，1,2,…,T。在整個有效期內(nèi)驗證子秘密SPi保持不變，但第j個時段子秘密Sij隨著時間段j的改變而變換，具體如下：進入第j個時段時，參與者首先通過非交互式方式計算出Sij=f(Si(j-1))，其中f是一個單向函數(shù)(類似于Hash函數(shù))，在計算出Sij后，參與成員Hi立即刪除前一時間段的子秘密Si(j-1)，這樣就保證了即使攻擊者獲得了第j個時段的子秘密Sij后也不能獲得Si0,Si1,…,Si(j-1)的任何信息。

密鑰更新流程如圖1所示。

圖1 密鑰更新流程

2 方案的構(gòu)造

2.1 系統(tǒng)初始化

(1)PKG:密鑰分配中心；

(2){P1,P2,…,Pn}：簽名用戶集合；

(3)G1：有限域上的乘法循環(huán)群，G2：橢圓曲線上的加法循環(huán)群，P：G2的生成元；

(4)抗碰撞的哈希函數(shù)H1,H2:{0,1}*×G2→G1；

(5)T時間周期，分為1,2,…,T時間段；

2.2 私鑰生成運算

(i)Pi,j=xi,jP，i=1,2,…,n;j=0,1,2,…,T；

(ii)yi,0=H1(Pi,0,IDi)，公開(Pi,j,yi,0)；

(iii)PKG收到(Pi,j,yi,0)后：

(a)利用這n個同余方程式計算c：

利用中國剩余定理可以計算該同余方程組的解為：

(b)PKG計算P(i)=qiP，ki=syi,0，(i=1,2,…,n)公開P(i)，秘密保存ki，通過秘密信道發(fā)送給用戶Pi。

2.3 簽名運算

(i)Ui=riP;

(ii)hi=H2(mi,IDi,Ui);

(2)則σi,j=(Ui,Vi,j)就是用戶Pi在第j個時間段對消息mi的簽名。

2.4 聚合簽名運算

(1)聚合簽名者首先驗證n個單一簽名σi,j=(Ui,Vi,j)的有效性，通過檢驗如下n個等式是否成立：

e(P,Vi,j)=e(hiPi,j+Ui,Ppub),i=1,2,…,n

(2)如果上述等式都有效，則聚合者計算：

(ii)則σj=(U,Vj)就是第j個時間段對消息m={m1,m2,…,mn}的聚合簽名。

2.5 聚合驗證運算

驗證者收到聚合簽名σj=(U,Vj),m={m1,m2,…,mn},ID={ID1,ID2,…,IDn}后：

(1)計算hi=H2(mi,IDi,Ui)；

(2)驗證等式：

2.6 簽名者的加入

2.7 簽名者撤銷

2.8 密鑰更新

3 方案的正確性與安全性

3.1 方案的正確性

定理1：方案在聚合簽名階段的驗證是正確的，即等式：e(P,Vi,j)=e(hiPi,j+Ui,Ppub),i=1,2,…,n成立。

e(xi,jP,hiPpub)e(riP,(syi,0)-yi,0P)=

e(xi,jP,hiPpub)e(riP,sP)=

e(xi,jhiP,Ppub)e(Ui,Ppub)=

e(Ui+xi,jhiP,Ppub)

證畢。

3.2 方案的安全性

定理3：方案具有前向安全性。

定理4：方案實現(xiàn)了可信中心與簽名用戶的雙向驗證。

可信中心與簽名用戶的雙向驗證分為兩個方面：

第一：可信中心的誠實性。對于簽名用戶Pi要驗證可信中心PKG的誠實性，通過如下的等式：

第二：簽名用戶的誠實性。對于可信中心PKG要驗證簽名用戶Pi的誠實性，通過如下的過程：

(1)可信中心計算PC=cP，然后公開PC;

定理5：在隨機預(yù)言模型下，假設(shè)存在一個敵手A以不可忽略的優(yōu)勢ε攻破了該方案，則存在一個算法C，以優(yōu)勢ε'>ε+negl(n)內(nèi)解決CDH問題。

證明：由定理可知，敵手A通過調(diào)用算法C，在一個概率多項式時間內(nèi)解決了CDH難題。假設(shè)(aP,bP)是橢圓曲線加法循環(huán)群G1上CDH難題的一個實例，則算法C的目標就是輸出該CDH問題的解abP：

(1)C維護三張列表L1,L2,Elist分別保存對H1,H2,私鑰的詢問，然后C運行系統(tǒng)初始化算法，定義系統(tǒng)的公鑰Ppub=aP，生成系統(tǒng)參數(shù)Ω={e,G1,G2,P,Ppub,H1,H2,T}，并將其發(fā)送給敵手A；

(2)敵手A收到系統(tǒng)參數(shù)后，執(zhí)行如下詢問：

(i)H1詢問。

(ii)H2詢問。

(iii)私鑰解析詢問。

(iv)簽名詢問。

最終，C輸出abP作為對敵手A的挑戰(zhàn)的應(yīng)答,因此C解決了CDH難題的一個實例。

定理6：方案可以抗存在性偽造。

由定理5可知，假設(shè)存在敵手以不可忽略的優(yōu)勢偽造了該方案的簽名，則說明CDH也能以不可忽略的優(yōu)勢被解決，當時CDH問題是一個難解問題，故不存在敵手C在多項式時間內(nèi)能破解該方案，因此方案是抗存在性偽造。

4 效率分析

本方案的效率與文獻[18]進行比較，如表1所示，其中TS表示標量乘法,TE表示雙線性運算,TR表示指數(shù)運算，|G1|加法循環(huán)群的階。

表1 方案效率比較

通過比較發(fā)現(xiàn)，該文在簽名階段與驗證階段相較文獻[18]效率相對較高，同時提出的方案簽名的長度是固定的，而文獻[18]簽名長度不固定，隨著簽名人數(shù)的增加呈現(xiàn)線性增長，這也體現(xiàn)了聚合簽名方案的優(yōu)勢：能有效降低數(shù)據(jù)的存儲空間。

5 結(jié)束語

目前結(jié)合中國剩余定理構(gòu)造的聚合簽名方案相對較少，由于聚合簽名方案的優(yōu)越性，該文在文獻[15,17]的基礎(chǔ)上，基于中國剩余定理，提出了一種新的具有前向安全性質(zhì)的聚合簽名方案。然后對方案的安全性與正確性進行了詳細的分析，在隨機預(yù)言模型下證明了方案抗存在性偽造，同時實現(xiàn)了簽名方案的可撤銷性，簽名用戶與可信中心的雙向驗證性以及簽名信息的前向安全性等特性。最后通過方案的效率分析，證明方案具有較好的運行效率。