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

韋性佳，蘆殿軍

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

0 引 言

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

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

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

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

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

1 基礎(chǔ)知識(shí)

1.1 雙線性映射

令(G1,+)，(G2,·)是兩個(gè)循環(huán)群，且|G1|=|G2|=q(q是大素?cái)?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)可計(jì)算性：?P,Q∈G1，存在有效的算法能夠計(jì)算e(P,Q)。

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

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

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

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

1.5 前向安全性理論

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

2.2 私鑰生成運(yùn)算

(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個(gè)同余方程式計(jì)算c：

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

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

2.3 簽名運(yùn)算

(i)Ui=riP;

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

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

2.4 聚合簽名運(yùn)算

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

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

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

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

2.5 聚合驗(yàn)證運(yùn)算

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

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

(2)驗(yàn)證等式：

2.6 簽名者的加入

2.7 簽名者撤銷

2.8 密鑰更新

3 方案的正確性與安全性

3.1 方案的正確性

定理1：方案在聚合簽名階段的驗(yàn)證是正確的，即等式：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：方案實(shí)現(xiàn)了可信中心與簽名用戶的雙向驗(yàn)證。

可信中心與簽名用戶的雙向驗(yàn)證分為兩個(gè)方面：

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

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

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

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

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

(1)C維護(hù)三張列表L1,L2,Elist分別保存對H1,H2,私鑰的詢問，然后C運(yùn)行系統(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難題的一個(gè)實(shí)例。

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

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

4 效率分析

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

表1 方案效率比較

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

5 結(jié)束語

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