高效安全的無證書聚合簽密方案

李 晨，祁正華

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院、軟件學(xué)院，江蘇 南京 210003)

0 引 言

Shamir開創(chuàng)了基于身份的公鑰密碼體制[1]，降低了因交換公鑰產(chǎn)生的泄密風(fēng)險(xiǎn)。文獻(xiàn)[2]提出了簽密的概念，同時(shí)完成了簽名和加密的操作，大大提高了效率。Al-Riyami又于2003年[3]提出無證書的簽密方案，解決了公鑰證書管理及驗(yàn)證問題，同時(shí)因?yàn)榭姑荑€托管的優(yōu)點(diǎn)而被廣泛關(guān)注。Barbosa等[4]在Al-Riyami的基礎(chǔ)上提出了新的無證書簽密方案并給出了安全模型。Qi[5]提出了一種可證安全的無證書環(huán)簽密方案，展現(xiàn)了無證書簽密體制的優(yōu)勢(shì)。同時(shí)Qi[6]又設(shè)計(jì)了兩種可證明安全的聚合簽密方案[7]。聚合簽密能將多個(gè)密文進(jìn)行聚合且提供批量驗(yàn)證，提升了傳輸效率，聚合簡(jiǎn)化了多個(gè)消息的驗(yàn)證。適用在大規(guī)模分布式通信的多對(duì)一模式下，尤其伴隨著5G的推廣使用，可穿戴設(shè)備和智能家居所生成的記錄，都需要各個(gè)相應(yīng)的實(shí)體進(jìn)行簽密，映射為多對(duì)一的情況，也就是聚合簽密，它非常適用于帶寬和計(jì)算資源有限的物聯(lián)網(wǎng)應(yīng)用。

2010年，Zhu[8]優(yōu)化了簽密過程并給出了一種新的無證書簽密方案，因其無雙線性對(duì)，大大提高了效率，但是被Zhou[9]證明不滿足不可偽造性和機(jī)密性。2017年，Wang[10]在此基礎(chǔ)上提出了一個(gè)更安全的不使用雙線性對(duì)的無證書簽密方案。這一點(diǎn)給了文中簽密方案一定的啟示。

2017年，Wang[11]提升了計(jì)算效率，利用了Zhou[9]的安全模型進(jìn)行證明，優(yōu)化并給出了一個(gè)高效的簽密方案，文中簽密方案利用了同樣的安全證明模型，在隨機(jī)預(yù)言機(jī)模型下同樣滿足不可偽造性。

1 相關(guān)基礎(chǔ)

1.1 困難問題假設(shè)

定義1：離散對(duì)數(shù)問題。

1.2 聚合簽密

聚合簽密[4]是一種類似于聚合簽名的概念，即：給定n個(gè)用戶IDi∈U(1≤i≤n，U為用戶集合)，一一對(duì)應(yīng)于消息mi∈M(M為消息集合)的n個(gè)簽密，各自簽密完成后交給一個(gè)信任的聚合簽密角色，將這些簽密聚合并成一條簽密。接收方收到這個(gè)聚合的簽密時(shí)，只需要驗(yàn)證一次就可以確定簽密的安全性，然后可以按照需要單獨(dú)解密某一用戶的密文。這樣更具靈活性而且縮短了簽密的長(zhǎng)度，擴(kuò)展了聚合簽名的實(shí)用性。聚合簽密在低帶寬低效率的多發(fā)送者環(huán)境中應(yīng)用廣泛。

1.3 算法定義

將無證書的聚合簽密簡(jiǎn)化為五個(gè)部分，如下：

(1)初始化(Setup)。給定一個(gè)安全的參數(shù)k,PKG計(jì)算出系統(tǒng)的公開參數(shù)params和系統(tǒng)的主密鑰s。

(2)用戶密鑰生成(private-Key-Extract)。根據(jù)用戶的身份IDi，用戶設(shè)置私鑰xi，計(jì)算出對(duì)應(yīng)的公鑰Xi，并發(fā)送給KGC。

(3)部分私鑰生成(partial-Key-Extract)。輸入身份信息IDi，PKG利用主密鑰s計(jì)算出相應(yīng)身份的公鑰Yi和私鑰yi，并通過安全信道傳送給用戶。

(4)聚合簽密(Signcryption)。聚合簽密由n個(gè)用戶組成，輸入公開參數(shù)params，用戶身份信息和對(duì)應(yīng)的公鑰對(duì)和私鑰對(duì)，相應(yīng)對(duì)應(yīng)的信息mi，計(jì)算聚合簽密。

(5)解簽密(un-Signcryption)。輸入聚合簽密，公開參數(shù)params，用戶身份信息和對(duì)應(yīng)的公鑰對(duì)和私鑰對(duì)，進(jìn)行驗(yàn)證和解簽密。

1.4 安全模型

無證書聚合簽密方案將面臨兩類敵手的攻擊。

(1)若敵手無法掌握系統(tǒng)的主密鑰，但其具有替換合法用戶公鑰的能力，則此類敵手為惡意用戶，記為A1。

(2)若敵手可掌握系統(tǒng)的主密鑰，但其不具有替換合法用戶公鑰的能力，則此類敵手為惡意KGC，記為A2。

2 改進(jìn)的無證書聚合簽密方案

無證書聚合簽密包含5個(gè)算法：

(1)初始化。

(2)用戶密鑰生成。

對(duì)于用戶Ui：隨機(jī)選取秘密值xi計(jì)算Xi=xiP，將身份標(biāo)識(shí)IDi和公開參數(shù)Xi返回給KGC。

(3)部分私鑰生成。

(4)聚合簽密。

用戶Ui對(duì)發(fā)送給IDB的消息mi進(jìn)行簽密，然后發(fā)送給聚合簽密者(UAgg)。

①用戶Ui執(zhí)行以下操作：

計(jì)算h1b=H1(IDb,Xb,Yb)和ki=xi(Xb+Yb+Ppubh1b)；

計(jì)算h2i=H2(IDi,IDb,Ri)和Si=(aih2i)-1(xi+yi)；

加密Wi=(IDi‖mi)⊕H3(IDb,aiXb,ki)，生成Ui對(duì)IDB的消息mi的簽密σi=(R,Ri,Si,Wi)。

②聚合簽密者UAgg收到n個(gè)用戶IDi∈U(1≤i≤n,U為用戶集合)的n個(gè)簽密σi=(R,Ri,Si,Wi)；

(5)解簽密。

接收者IDB對(duì)接收到的σ=<{Ri,Wi},S>進(jìn)行解簽密，步驟如下：

3 安全性分析

3.1 正確性

(1)驗(yàn)證正確性。

ki=xi(Xb+Yb+Ppubh1b)=

xi(xbP+rbP+sPh1b)=

Xi(xb+rb+sh1b)=

(2)驗(yàn)證合法性。

3.2 安全性

定理1：文中的無證書聚合簽密方案在隨機(jī)預(yù)言模型且離散問題難解的情況下，在適應(yīng)性選擇消息攻擊下具有不可偽造性(EUF-CMA)。

(1)詢問階段。

H1查詢：對(duì)于h1i=H1(IDi,Xi,Yi)

輸入IDi,Xi,Yi查詢h1i，如果不存在相應(yīng)的數(shù)據(jù)，T1隨機(jī)選取h1i使表L1中不存在相應(yīng)的數(shù)據(jù)，并添加到表L1，同時(shí)返回h1i給A1。

H2查詢：對(duì)于H2i=H2(IDi,IDb,Ri)

輸入IDi,IDb,Ri查詢H2i，如果不存在相應(yīng)的數(shù)據(jù)，T1隨機(jī)選取xi計(jì)算Xi=xiP，通過對(duì)IDi和Xi進(jìn)行部分密鑰生成詢問得到其對(duì)應(yīng)的，添加到Lsk，返回SKi=(xi,yi)給A1并且添加到列表Lpk。

H3查詢：對(duì)于h3=H3(IDb,aiXb,ki)

輸入IDb,aiXb,ki查詢h3，如果不存在相應(yīng)的數(shù)據(jù)，T1隨機(jī)選取h3進(jìn)行私鑰生成查詢和公鑰生成查詢，獲得xi,Xb和Yb,計(jì)算ki=xi(Xb+Yb+Ppubh1b)，使得表L3中不存在相應(yīng)的，并添加相應(yīng)的到表L3，同時(shí)返回h3給A1。

部分密鑰生成詢問：對(duì)于

輸入IDi查詢yi，Yi，如果不存在相應(yīng)的數(shù)據(jù)，如果IDi≠IDj，T1隨機(jī)選取yi，h1i計(jì)算Yi=yiP-Ppubh1i，添加到表Lk，返回(yi，Yi)給A1，如果表L1中不存在相應(yīng)的數(shù)據(jù)，則添加到表L1中；如果IDi=IDj，T1隨機(jī)選取yi，h1i令Yj=rknowP(rknow是已知的隨機(jī)數(shù))，添加到表Lk，返回(yj,Yj)給A1，如果表L1中不存在相應(yīng)的數(shù)據(jù)，則添加到表L1。

私鑰生成詢問：對(duì)于

輸入IDi查詢xi,yi，如果不存在相應(yīng)的數(shù)據(jù)，T1隨機(jī)選取xi計(jì)算Xi=xiP，通過對(duì)IDi和Xi進(jìn)行部分密鑰生成詢問，得到對(duì)應(yīng)的，添加到表Lsk，返回SKi=(xi，yi)給A1。

公鑰生成詢問：對(duì)于

輸入IDi查詢Xi,Yi，如果不存在相應(yīng)的數(shù)據(jù)，T1隨機(jī)選取xi計(jì)算Xi=xiP，通過對(duì)IDi和Xi進(jìn)行部分密鑰生成詢問獲知相應(yīng)的，添加到表Lpk，返回PKi=(Xi,Yi)給A1，同時(shí)添加到表Lsk。

公鑰替換詢問：

簽密詢問：

輸入，如果存在某一個(gè)IDi=IDj，則T1結(jié)束，終止游戲；否則，T1對(duì)每一個(gè)ID都隨機(jī)選取ai計(jì)算Ri=aiP，Si=(aih2i)-1(xi+yi)按照簽密算法進(jìn)行簽密，構(gòu)造簽密集合σi=(R,Ri,Si,Wi),聚合生成簽密σ=<{Ri,Wi},S>返回給A1。

解簽密查詢：

輸入σ=<{Ri,Wi},S>，T1查詢表L1：

②如果表Lpk中存在IDi所對(duì)應(yīng)的數(shù)據(jù)且IDi=IDj，則當(dāng)表L2中存在IDi相對(duì)應(yīng)的時(shí)，T1返回True給A1，否則返回False；

③如果表Lpk中不存在IDi所對(duì)應(yīng)的數(shù)據(jù)，則當(dāng)表L2中存在IDi對(duì)應(yīng)的時(shí)，T1返回True給A1，否則返回False。

(2)偽造階段。

敵手對(duì)每一個(gè)發(fā)送者的身份i都有相同的概率。進(jìn)行有界多項(xiàng)式次上述詢問后，A1輸出聚合簽密σ= <{Ri,Wi},S>，其中至少包含一個(gè)IDi未進(jìn)行部分密鑰生成詢問和私鑰生成詢問和一個(gè)mi未進(jìn)行簽密詢問。

①如果所有的IDi(1≤i≤n)中都不包含IDj，游戲停止。

(3)分析。

證明：假設(shè)算法T2作為離散對(duì)數(shù)問題的解決者，輸入的(P,bP)中b是未知的，目的是得到b，T2作為游戲的挑戰(zhàn)者，運(yùn)行Setup算法，生成公開參數(shù)params=,令Ppub=bP，將params發(fā)送給敵手A2，維護(hù)的表和引理1里T2維護(hù)的表大體一致(除去公鑰替換)。T2選擇身份IDj作為其猜測(cè)的挑戰(zhàn)身份，則T2選擇其猜測(cè)的身份IDj的概率為

(1)詢問階段與引理1中的相應(yīng)詢問相同除了部分密鑰生成詢問和解簽密查詢。

部分密鑰生成詢問：對(duì)于

輸入IDi查詢yi，Yi，如果不存在相應(yīng)的數(shù)據(jù)，如果IDi≠IDj，T2隨機(jī)選取yi，h1i計(jì)算Yi=yiP-Ppubh1i，添加到表Lk，返回(yi，Yi)給A2，同時(shí)添加到表L1中；如果IDi=IDj，T2隨機(jī)選取yi，h1i令Yj=bP，添加到表Lk，返回(yj,Yj)給A2，同時(shí)添加到表L1。

解簽密查詢：

輸入σ=<{Ri,Wi},S>，T2查詢表L1：

②如果表Lpk中存在IDi所對(duì)應(yīng)的且IDi=IDj，則當(dāng)表L2中存在IDi相對(duì)應(yīng)的時(shí)，T2返回True給A2，否則返回False。

(2)偽造階段。

敵手對(duì)每一個(gè)發(fā)送者的身份i都有相同的概率。進(jìn)行多項(xiàng)式次上述詢問后，A1輸出聚合簽密σ=<{Ri,Wi},S>，其中至少包含一個(gè)IDi未進(jìn)行部分密鑰生成詢問和私鑰生成詢問和一個(gè)mi未進(jìn)行簽密詢問。

①如果對(duì)于所有的IDi(1≤i≤n)，都有IDi≠IDj，就將游戲中止。

(3)分析。

定理2：文中的無證書聚合簽密方案在隨機(jī)預(yù)言模型且離散問題難解的情況下，在適應(yīng)性選擇密文攻擊下具有不可區(qū)分性(IND-CCA2)。

引理3：在隨機(jī)預(yù)言模型下，若不存在敵手A1在下面的游戲中能以不可忽略優(yōu)勢(shì)獲勝，那么稱該方案具有不可區(qū)分性。

證明：初始化和Hash表的游戲都和引理1類似，T3為離散對(duì)數(shù)問題的解決者并選擇身份IDj作為其猜測(cè)的挑戰(zhàn)者身份。

詢問：敵手A1詢問過程與引理1相似。

階段一：詢問階段結(jié)束之后，A1隨機(jī)選擇生成兩個(gè)長(zhǎng)度相等的消息m1和m2來接受挑戰(zhàn)。T3隨機(jī)選擇η∈{0,1}并將mη作為輸入生成挑戰(zhàn)簽密σ*，返回給敵手A1。

引理4：在隨機(jī)預(yù)言模型下，若不存在敵手A2在下面的游戲中能以不可忽略優(yōu)勢(shì)獲勝，那么稱該方案具有不可區(qū)分性。

證明：初始化和Hash表的游戲都和引理1類似，T4為離散對(duì)數(shù)問題的解決者并選擇身份IDj作為其猜測(cè)的挑戰(zhàn)者身份。

詢問：敵手A2詢問過程與引理2相似。

3.3 性能分析

3.3.1 公開驗(yàn)證性

3.3.2 不可否認(rèn)性

由以上證明可以得出文中的聚合簽密方案具有不可偽造性和公開驗(yàn)證性，可以得出該方案同樣具有不可否認(rèn)性。

3.3.3 無需密鑰托管

密鑰托管又稱密鑰恢復(fù)，因?yàn)椴糠炙借€由用戶單獨(dú)生成，信任方需要解決DL問題才能獲取到用戶的秘密值。無證書的簽密方案中的KGC不存在類似PKG的密鑰托管問題，這一點(diǎn)是無證書簽密方案的優(yōu)點(diǎn)之一。

3.4 效率分析

計(jì)算開銷和密文長(zhǎng)度是影響算法效率的兩個(gè)主要因素。在聚合簽密中，密文中絕大部分的存儲(chǔ)空間占用都是用戶的身份信息和密文，參與驗(yàn)證的參數(shù)空間占用并不多。文中方案的密文中除去每一個(gè)用戶的{Ri,Wi}(其中包含身份信息，密文長(zhǎng)度)之外，參與驗(yàn)證的參數(shù)只有一個(gè)|G|，所以只對(duì)比簽密和解簽密的計(jì)算開銷。影響計(jì)算開銷效率的主要運(yùn)算是橢圓曲線點(diǎn)乘運(yùn)算、雙線性對(duì)運(yùn)算和指數(shù)運(yùn)算，分別用字母S，P和E表示。表1給出了新方案與當(dāng)前效率較高的其他聚合簽密方案的比較情況。

表1分析了5種聚合簽密方案的計(jì)算效率。其中S、P、E三種運(yùn)算中，雙線性對(duì)運(yùn)算和指數(shù)運(yùn)算復(fù)雜程度都有點(diǎn)乘運(yùn)算的幾十倍之多。聚合簽密中，因大量的信息需要簽密，每增加一次對(duì)運(yùn)算或者指數(shù)運(yùn)算都將大大增加計(jì)算負(fù)擔(dān)。方案[12-16]無論在簽密或者解簽的過程中都有至少n倍的對(duì)運(yùn)算，因此計(jì)算負(fù)載較大。文中方案相較于表中列出的其他四種方案，沒有雙線性對(duì)和指數(shù)的運(yùn)算，但是在解簽密中的驗(yàn)證過程中點(diǎn)乘次數(shù)稍多。運(yùn)算方案對(duì)比于表中的幾個(gè)聚合簽密方案更為高效。

表1 無證書聚合簽密方案的比較

文中方案的解密運(yùn)算中，參與驗(yàn)證的計(jì)算量為3n，還原密文只需要n，所以接收方在驗(yàn)證安全性之后，可以根據(jù)需要還原某一所需的發(fā)送方的密文。雖然文中方案在群上的點(diǎn)加和點(diǎn)乘運(yùn)算上與參與聚合的發(fā)送方呈線性增加的關(guān)系，但是其運(yùn)算效率還是遠(yuǎn)遠(yuǎn)高于對(duì)運(yùn)算。

4 結(jié)束語

提出了一個(gè)新的無證書無雙線性對(duì)的聚合簽密方案。從機(jī)密性、不可偽造性、公開驗(yàn)證性、不可否認(rèn)性和密鑰托管問題這五個(gè)方面進(jìn)行了安全性分析，并將該方案與目前計(jì)算效率較高的無證書聚合簽密方案進(jìn)行了比較，結(jié)果表明該方案是一個(gè)安全高效的無證書聚合簽密簽密方案。