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

李 晨，祁正華

(南京郵電大學 計算機學院、軟件學院，江蘇 南京 210003)

0 引 言

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

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

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

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

1.1 困難問題假設(shè)

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

1.2 聚合簽密

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

1.3 算法定義

將無證書的聚合簽密簡化為五個部分，如下：

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

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

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

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

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

1.4 安全模型

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

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

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

2 改進的無證書聚合簽密方案

無證書聚合簽密包含5個算法：

(1)初始化。

(2)用戶密鑰生成。

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

(3)部分私鑰生成。

(4)聚合簽密。

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

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

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

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

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

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

(5)解簽密。

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

3 安全性分析

3.1 正確性

(1)驗證正確性。

ki=xi(Xb+Yb+Ppubh1b)=

xi(xbP+rbP+sPh1b)=

Xi(xb+rb+sh1b)=

(2)驗證合法性。

3.2 安全性

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

(1)詢問階段。

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

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

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

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

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

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

部分密鑰生成詢問：對于

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

私鑰生成詢問：對于

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

公鑰生成詢問：對于

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

公鑰替換詢問：

簽密詢問：

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

解簽密查詢：

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

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

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

(2)偽造階段。

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

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

(3)分析。

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

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

部分密鑰生成詢問：對于

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

解簽密查詢：

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

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

(2)偽造階段。

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

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

(3)分析。

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

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

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

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

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

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

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

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

3.3 性能分析

3.3.1 公開驗證性

3.3.2 不可否認性

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

3.3.3 無需密鑰托管

密鑰托管又稱密鑰恢復(fù)，因為部分私鑰由用戶單獨生成，信任方需要解決DL問題才能獲取到用戶的秘密值。無證書的簽密方案中的KGC不存在類似PKG的密鑰托管問題，這一點是無證書簽密方案的優(yōu)點之一。

3.4 效率分析

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

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

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

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

4 結(jié)束語

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