無(wú)證書的多接收者匿名簽密方案

祁正華，吳振國(guó)，王夢(mèng)殊

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

0 引 言

對(duì)于傳統(tǒng)的基于公鑰的加密體制中存在的密鑰及證書的管理問題，Shamir提出了基于身份的公鑰密碼體制，一度成為眾多學(xué)者研究的熱點(diǎn)，目前已有很多基于身份的加密、簽密方案被提出[1-4]，但基于身份的密碼體制中的方案存在一個(gè)嚴(yán)重的問題即密鑰托管的問題。Al-Riyami和Paterson提出了一個(gè)沒有證書的公鑰密碼體制，無(wú)證書密碼體制很好解決了上述兩種密碼體制當(dāng)中存在的問題，國(guó)內(nèi)外學(xué)者相繼提出了很多適用于網(wǎng)絡(luò)傳輸、無(wú)線傳感等新型網(wǎng)絡(luò)傳輸環(huán)境下無(wú)證書加密、簽密算法[5-10]。

多接收者簽密是指將消息經(jīng)過(guò)簽密之后發(fā)送給多個(gè)授權(quán)接收者的過(guò)程。國(guó)內(nèi)外很多學(xué)者提出了多種新的多接收者簽密方案，然而大多簽密機(jī)制[2-4,11]都是基于身份的密碼系統(tǒng)，其中存在密鑰托管的問題，文獻(xiàn)[4]是多接收者單一消息簽密；文獻(xiàn)[11]中收件人的標(biāo)識(shí)列表或密文標(biāo)記列表是密文的一部分，因此簽密容易暴露收件人的身份；文獻(xiàn)[12]是聚合簽密方案，是多對(duì)一模式，文獻(xiàn)[13,14]都是周的方案，文獻(xiàn)[15,16]需要計(jì)算索引，且是單一消息通信模式，若進(jìn)行多消息發(fā)送模式，效率低下；文獻(xiàn)[17-20]部分存在匿名不公平性問題，也就是說(shuō)，整個(gè)加密過(guò)程中只考慮到接收者的匿名性問題而忽略了發(fā)送者匿名性問題。

針對(duì)以上方案存在的問題，本文提出一種無(wú)證書多接收者匿名簽密方案，方案同時(shí)保證了發(fā)送者和接收者的匿名性，并且具有較高的解簽密效率和較低的通信開銷，采用Lagrange插值公式和離散對(duì)數(shù)(DL)問題來(lái)證明文中的保密性，具有不可偽造性和匿名性。

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

1.1 離散對(duì)數(shù)問題及Lagrange插值多項(xiàng)式

離散對(duì)數(shù)問題(discrete logarithm problem，DLP)對(duì)于給定的A,B∈G， 通過(guò)計(jì)算找到等式B=nA成立的整數(shù)n， 其中G是階數(shù)為素?cái)?shù)q的循環(huán)群。

1.2 無(wú)證書多接收者簽密方案的安全模型

基于無(wú)證書的簽密方案一般會(huì)面臨兩種攻擊：第一種攻擊類型是惡意用戶A1。 攻擊者A1并不知道用戶的主密鑰，但是他能夠?qū)戏ㄓ脩舻墓€進(jìn)行替換；第二種攻擊類型是惡意的KGC攻擊者A2， 這一類敵手雖然能夠掌握系統(tǒng)主密鑰，攻擊者A2與攻擊者A1恰好相反，他有能力知道用戶的主密鑰，但是無(wú)法替換用戶的公鑰。我們通過(guò)以下的幾個(gè)定義來(lái)簡(jiǎn)單說(shuō)明多消息多接收者簽密方案的安全模型。

定義1 第一種攻擊類型的機(jī)密性：如果不存在上述的第一種惡意攻擊用戶A1能夠在有界多項(xiàng)式時(shí)間內(nèi)以顯著優(yōu)勢(shì)贏得以下游戲，那么就可以稱在適應(yīng)性選擇密文攻擊下該多接收者簽密方案滿足不可區(qū)分性。

系統(tǒng)建立：我們假設(shè)挑戰(zhàn)者為D， 第一種惡意攻擊敵手為A1，將params發(fā)送給A1。

第一輪詢問：A1可以對(duì)D產(chǎn)生以下的詢問：

私鑰生成查詢：A1輸入任意用戶及其身份信息 (Xi,IDi) 進(jìn)行問詢，挑戰(zhàn)者通過(guò)私鑰生成算法得到這個(gè)用戶的私鑰SKi=(xi,yi)， 然后將這個(gè)私鑰反饋給敵手A1。

替換公鑰查詢：A1輸入任意用戶及其公鑰信息(IDi,PKi),PKi=(Xi,Yi)， 挑戰(zhàn)者根據(jù)查詢到的該用戶的公鑰選取另一個(gè)公鑰PK′i=(X′i,Y′i)， 將這個(gè)用戶的原始公鑰替換為新選取的替換公鑰。

簽密查詢：A1根據(jù)需要查詢的明文集合M={m1,m2,…,mk}， 所有的接收者U={ID1,ID2,…,IDk} 的公鑰信息及簽密者身份IDA的私鑰信息，對(duì)D進(jìn)行簽密查詢，D則生成有關(guān)簽密者IDA， 接收者IDi∈U(i∈{1,2,…,k})， 公鑰PKi的密文σ=Signcryption(params,M,U,SKA)， 然后將這個(gè)密文反饋給A1。

解簽密查詢：A1根據(jù)需要查詢的密文σ， 所有的接收者的私鑰信息及簽密者身份的公鑰信息，對(duì)D進(jìn)行解簽密查詢，D根據(jù)以上信息通過(guò)解簽密算法Unsigncryption(params,M,U,SKA) 將密文σ還原成明文消息集合M， 然后將還原出的明文消息集合M反饋給A1。

猜測(cè)：A1進(jìn)行與上述多個(gè)詢問類似地多項(xiàng)式有界次詢問，但不能夠?qū)λ薪邮照弋?dāng)中的任意接收者進(jìn)行私鑰查詢和對(duì)密文σ進(jìn)行解簽密查詢。完成上述過(guò)程后，輸出一個(gè)b′作為對(duì)b的猜測(cè)，若b′=b， 那么說(shuō)明A1獲得本次游戲的勝利，取得游戲勝利優(yōu)勢(shì)為AdvCMRS(A1)=|Pr[b′=b]-0.5|。

定義2 第二種攻擊類型的機(jī)密性：如果不存在上述的第二種惡意攻擊用戶A2， 能夠在有界多項(xiàng)式時(shí)間內(nèi)以顯著優(yōu)勢(shì)贏得以下游戲，那么就可以稱在適應(yīng)性選擇密文攻擊下該多接收者簽密方案滿足不可區(qū)分性。

第二輪查詢：A2實(shí)施與第一輪相同的查詢，但不包括第一輪的第二個(gè)查詢。

私鑰生成查詢：A2輸入任意用戶及其身份信息 (Xi,IDi)， 挑戰(zhàn)者通過(guò)私鑰生成算法得到這個(gè)用戶的私鑰SKi=(xi,yi)， 然后將這個(gè)私鑰反饋給A2。

解簽密查詢：A2根據(jù)需要查詢的密文σ，所有的私鑰信息及簽密者身份的公鑰信息，對(duì)挑戰(zhàn)者D進(jìn)行解簽密查詢，挑戰(zhàn)者D通過(guò)解簽密算法Unsigncryption(params,σ,U,SKA) 將密文σ還原成明文消息集合M， 然后將還原出的明文消息集合M反饋給A2。

最后敵手A2進(jìn)行和階段一相同的挑戰(zhàn)和猜測(cè)。

定義3 第一種攻擊類型的不可偽造性：如果不存在上述的第一種惡意攻擊用戶A1能夠在有界多項(xiàng)式時(shí)間內(nèi)以顯著優(yōu)勢(shì)贏得以下游戲，那么就可以稱在適應(yīng)性選擇密文攻擊下該多消息多接收者簽密方案滿足不可偽造性。

系統(tǒng)建立：我們假設(shè)挑戰(zhàn)者為D， 第一種惡意攻擊敵手為A1， 挑戰(zhàn)者運(yùn)行初始化算法，將生成的公共系統(tǒng)參數(shù)反饋給敵手。

訓(xùn)練：A1對(duì)挑戰(zhàn)者實(shí)施如第一輪詢問相同的查詢。

定義4 第二種攻擊類型的不可偽造性：如果不存在上述的第二種惡意攻擊用戶A2能夠在有界多項(xiàng)式時(shí)間內(nèi)以顯著優(yōu)勢(shì)贏得以下游戲，那么就可以稱在適應(yīng)性選擇密文攻擊下該多消息多接收者簽密方案滿足不可偽造性。

系統(tǒng)建立：我們假設(shè)挑戰(zhàn)者為D， 第二種惡意攻擊敵手為A2， 挑戰(zhàn)者運(yùn)行初始化算法，將生成的公共系統(tǒng)參數(shù)反饋給敵手。

訓(xùn)練：A2對(duì)挑戰(zhàn)者實(shí)施如第二輪詢問相同的查詢。

2 無(wú)證書多接收者簽密方案

本文提出的簽密方案分為以下5個(gè)階段：

(2)用戶公鑰提取階段：用戶IDi根據(jù)隨機(jī)選取的xi， 生成公鑰Xi=xiH3(IDi)；

(4)多接收者簽密階段：用戶UA對(duì)發(fā)送給IDi消息mi簽密如下：

2)計(jì)算拉格朗日差值多項(xiàng)式

4)計(jì)算hi,2=H2(IDA,VA,XA,Zi)， 其中Zi=(b+yA)(Yi+Ppubhi1)，Wi=(IDA‖mi)⊕hi2；

5)計(jì)算Ri=H4(IDA‖mi)；

6)計(jì)算Si=b+(XA+yA)Ri， 這樣σi=(VA,T1,T2,…,Tn,Wi,Si) 為uA對(duì)IDi消息mi的簽密。最后形成的密文消息是δ={T1,T2,…,Tn,VA,W1,W2,…,Wn,S1,S2,…,Sn}, 然后以廣播的形式發(fā)送給每一位接收者。

(5)解簽密階段：IDi對(duì)uA發(fā)送的簽密進(jìn)行解簽密，步驟如下：

2)計(jì)算(IDA‖mi)=Wi⊕hi2；

3)計(jì)算hi1=H1(IDi,Xi,Yi)；

4)計(jì)算Ri=H4(IDA‖mi) 并通過(guò)等式對(duì)SiP=VA+(XAP+YA+ppubhi1)Ri進(jìn)行驗(yàn)證，若正確則輸出對(duì)應(yīng)消息 (IDA‖mi)， 否則無(wú)效。

正確性驗(yàn)證：

對(duì)接收到密文進(jìn)行如下驗(yàn)證：

如果：SiP=[b+(XA+YA)Ri]P=VA+(XAP+YAPpubhi1)Ri則驗(yàn)證正確，接收對(duì)應(yīng)消息(IDA‖mi)。

3 安全性分析及效率分析

3.1 安全性證明

在隨機(jī)預(yù)言機(jī)模型下，對(duì)于本文所提出的無(wú)證書的多消息多接收者匿名簽密算法的安全性證明也分別從兩種類型的攻擊下進(jìn)行機(jī)密性和不可偽造性這兩個(gè)方面的證明。

第一輪查詢：

公鑰替換查詢：敵手A1想要獲得用戶IDk的公鑰替換查詢，挑戰(zhàn)者D在Lpk中查找 (IDk,xk,PKk)， 然后將替換的 (IDk,*,PK′k) 插入到Lpk中，最后把結(jié)果反饋給敵手。

解簽密查詢：敵手A1通過(guò)挑戰(zhàn)者D對(duì)簽密 (1≤i≤n) 的解簽密進(jìn)行查詢，挑戰(zhàn)者對(duì)L1進(jìn)行查詢，若L1中包含IDk所對(duì)應(yīng)的元組且IDk≠IDi， 那么挑戰(zhàn)者進(jìn)行解簽密算法，對(duì)等式SkP=VA+(XAP+YA+Ppubhk1)Ri進(jìn)行判斷，如果成立則返回給A1成功，否則返回失敗。如果L1中存在IDk， 且IDk=IDi， 那么在L2中存在與IDi對(duì)應(yīng)的元組 時(shí)，D返回給A1成功，否則返回失敗。若L1中不存在關(guān)于IDk的元組，那么在L2中存在IDk元組 時(shí)，D返回給A1成功，否則返回失敗。qu表示A1能夠進(jìn)行解簽密詢問的最多次數(shù)。

第二輪查詢： 敵手實(shí)施和第一輪查詢相同的步驟，但不包括H1-查詢、私鑰查詢和解簽密查詢。

證明：過(guò)程與定理1的方法類似。

查詢：敵手實(shí)施定理1中一樣的兩輪查詢。

證明：過(guò)程與定理2的方法類似。

查詢：敵手實(shí)施定理2中一樣的兩輪查詢。

3.2 機(jī)制分析

針對(duì)本文提出的無(wú)證書的多接收著匿名簽密方案分別從匿名性、多消息簽密以及公開驗(yàn)證這3個(gè)方面進(jìn)行機(jī)制分析。

(1)匿名性

本文方案同時(shí)保護(hù)了發(fā)送者身份和各個(gè)接收者身份的匿名性。發(fā)送者匿名性的實(shí)現(xiàn)是將發(fā)送者的身份信息插入到Wi中，只有授權(quán)的合法接收者才能夠通過(guò)簽密密文知道發(fā)送者的身份信息；接收者匿名性的實(shí)現(xiàn)是將接收者的身份信息插入到拉格朗日插值多項(xiàng)式當(dāng)中，并且其它接收者也無(wú)法得知除自己以外的其它接收者的身份信息。

(2)多消息簽密

本文所提出的多簽密算法不僅可以將同一個(gè)消息發(fā)送給多個(gè)接收者，也可以將多個(gè)不同的消息發(fā)送給不同的接收者，實(shí)現(xiàn)方法是將需要簽密的明文信息插入到Wi當(dāng)中，滿足當(dāng)前網(wǎng)絡(luò)通信多消息發(fā)送的需求。

(3)公開驗(yàn)證性

3.3 效率分析

將本文提出的簽密方案與參考文獻(xiàn)[13-20]提出的方案進(jìn)行效率分析對(duì)比，主要從解簽密的運(yùn)算量以及簽密方案后的密文長(zhǎng)度兩個(gè)方面來(lái)分析，解簽密的運(yùn)算量主要影響解簽密過(guò)程的效率，密文的長(zhǎng)度直接影響密文傳輸?shù)耐ㄐ砰_銷和系統(tǒng)存儲(chǔ)。本文方案和其它方案中簽密及解簽密過(guò)程中計(jì)算耗時(shí)比較大的主要有3個(gè)運(yùn)算，分別是雙線性對(duì)運(yùn)算、指數(shù)運(yùn)算和點(diǎn)乘運(yùn)算，為了描述方便，將這3個(gè)運(yùn)算分別用Ed、Ex和Mt表示，其中計(jì)算時(shí)間規(guī)則如下，Ed>Ex和Ed>Mt。

從表1可以看出，文獻(xiàn)[13,17]在進(jìn)行單消息簽密時(shí)的計(jì)算效率較高，但在進(jìn)行多簽密運(yùn)算時(shí)，其解簽密效率會(huì)隨著解簽密人數(shù)的增加而增加，從而導(dǎo)致效率低下。本文中簽密方案可進(jìn)行多消息簽密，且無(wú)需雙線性對(duì)運(yùn)算，文獻(xiàn)[15,16]在解簽密過(guò)程中均需要運(yùn)用雙線性對(duì)運(yùn)算，大大增加了運(yùn)算量；文獻(xiàn)[18]在簽密過(guò)程中需要對(duì)每個(gè)不同的接收者的身份信息進(jìn)行索引計(jì)算，降低了簽密的速率；而文獻(xiàn)[19]雖然在簽密和解簽密過(guò)程中的計(jì)算量較小，但是該方案無(wú)法對(duì)多個(gè)消息同時(shí)進(jìn)行簽密；文獻(xiàn)[20]在簽密中需要使用雙線性對(duì)運(yùn)算，并且運(yùn)算量較大。由此得知，本文設(shè)計(jì)出的多接收者匿名簽密方案具有更高的簽密和解簽密效率。

表1 簽密方案運(yùn)算量比較

表2 簽密方案密文長(zhǎng)度比較

綜上所述，本文方案與現(xiàn)有的簽密機(jī)制相比較，在完成多消息多接收者簽密的同時(shí)，具有較高的解簽密計(jì)算效率和較低的通信開銷。

4 結(jié)束語(yǔ)

本文對(duì)比以前的多接收者簽密方案，保證方案在隨機(jī)預(yù)言機(jī)模型下具有可證安全性的基礎(chǔ)上，采用拉格朗日插值方法提出了無(wú)證書的多接收者匿名簽密方案，該方案在簽密過(guò)程中不需要雙線性對(duì)運(yùn)算且是多消息多接收者簽密，具有較高的解簽密計(jì)算效率和較低的通信開銷，方案具有匿名性、公開驗(yàn)證性、機(jī)密性和不可偽造性。對(duì)于移動(dòng)支付、無(wú)限網(wǎng)絡(luò)傳輸以及金融行業(yè)等和敏感信息傳輸方面的行業(yè)具有較強(qiáng)的實(shí)用價(jià)值。