無證書的多接收者匿名簽密方案

祁正華，吳振國，王夢殊

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

0 引 言

對于傳統的基于公鑰的加密體制中存在的密鑰及證書的管理問題，Shamir提出了基于身份的公鑰密碼體制，一度成為眾多學者研究的熱點，目前已有很多基于身份的加密、簽密方案被提出[1-4]，但基于身份的密碼體制中的方案存在一個嚴重的問題即密鑰托管的問題。Al-Riyami和Paterson提出了一個沒有證書的公鑰密碼體制，無證書密碼體制很好解決了上述兩種密碼體制當中存在的問題，國內外學者相繼提出了很多適用于網絡傳輸、無線傳感等新型網絡傳輸環境下無證書加密、簽密算法[5-10]。

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

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

1 相關基礎

1.1 離散對數問題及Lagrange插值多項式

離散對數問題(discrete logarithm problem，DLP)對于給定的A,B∈G， 通過計算找到等式B=nA成立的整數n， 其中G是階數為素數q的循環群。

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

基于無證書的簽密方案一般會面臨兩種攻擊：第一種攻擊類型是惡意用戶A1。 攻擊者A1并不知道用戶的主密鑰，但是他能夠對合法用戶的公鑰進行替換；第二種攻擊類型是惡意的KGC攻擊者A2， 這一類敵手雖然能夠掌握系統主密鑰，攻擊者A2與攻擊者A1恰好相反，他有能力知道用戶的主密鑰，但是無法替換用戶的公鑰。我們通過以下的幾個定義來簡單說明多消息多接收者簽密方案的安全模型。

定義1 第一種攻擊類型的機密性：如果不存在上述的第一種惡意攻擊用戶A1能夠在有界多項式時間內以顯著優勢贏得以下游戲，那么就可以稱在適應性選擇密文攻擊下該多接收者簽密方案滿足不可區分性。

系統建立：我們假設挑戰者為D， 第一種惡意攻擊敵手為A1，將params發送給A1。

第一輪詢問：A1可以對D產生以下的詢問：

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

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

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

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

猜測：A1進行與上述多個詢問類似地多項式有界次詢問，但不能夠對所有接收者當中的任意接收者進行私鑰查詢和對密文σ進行解簽密查詢。完成上述過程后，輸出一個b′作為對b的猜測，若b′=b， 那么說明A1獲得本次游戲的勝利，取得游戲勝利優勢為AdvCMRS(A1)=|Pr[b′=b]-0.5|。

定義2 第二種攻擊類型的機密性：如果不存在上述的第二種惡意攻擊用戶A2， 能夠在有界多項式時間內以顯著優勢贏得以下游戲，那么就可以稱在適應性選擇密文攻擊下該多接收者簽密方案滿足不可區分性。

第二輪查詢：A2實施與第一輪相同的查詢，但不包括第一輪的第二個查詢。

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

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

最后敵手A2進行和階段一相同的挑戰和猜測。

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

系統建立：我們假設挑戰者為D， 第一種惡意攻擊敵手為A1， 挑戰者運行初始化算法，將生成的公共系統參數反饋給敵手。

訓練：A1對挑戰者實施如第一輪詢問相同的查詢。

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

系統建立：我們假設挑戰者為D， 第二種惡意攻擊敵手為A2， 挑戰者運行初始化算法，將生成的公共系統參數反饋給敵手。

訓練：A2對挑戰者實施如第二輪詢問相同的查詢。

2 無證書多接收者簽密方案

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

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

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

2)計算拉格朗日差值多項式

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

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

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

(5)解簽密階段：IDi對uA發送的簽密進行解簽密，步驟如下：

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

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

4)計算Ri=H4(IDA‖mi) 并通過等式對SiP=VA+(XAP+YA+ppubhi1)Ri進行驗證，若正確則輸出對應消息 (IDA‖mi)， 否則無效。

正確性驗證：

對接收到密文進行如下驗證：

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

3 安全性分析及效率分析

3.1 安全性證明

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

第一輪查詢：

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

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

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

證明：過程與定理1的方法類似。

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

證明：過程與定理2的方法類似。

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

3.2 機制分析

針對本文提出的無證書的多接收著匿名簽密方案分別從匿名性、多消息簽密以及公開驗證這3個方面進行機制分析。

(1)匿名性

本文方案同時保護了發送者身份和各個接收者身份的匿名性。發送者匿名性的實現是將發送者的身份信息插入到Wi中，只有授權的合法接收者才能夠通過簽密密文知道發送者的身份信息；接收者匿名性的實現是將接收者的身份信息插入到拉格朗日插值多項式當中，并且其它接收者也無法得知除自己以外的其它接收者的身份信息。

(2)多消息簽密

本文所提出的多簽密算法不僅可以將同一個消息發送給多個接收者，也可以將多個不同的消息發送給不同的接收者，實現方法是將需要簽密的明文信息插入到Wi當中，滿足當前網絡通信多消息發送的需求。

(3)公開驗證性

3.3 效率分析

將本文提出的簽密方案與參考文獻[13-20]提出的方案進行效率分析對比，主要從解簽密的運算量以及簽密方案后的密文長度兩個方面來分析，解簽密的運算量主要影響解簽密過程的效率，密文的長度直接影響密文傳輸的通信開銷和系統存儲。本文方案和其它方案中簽密及解簽密過程中計算耗時比較大的主要有3個運算，分別是雙線性對運算、指數運算和點乘運算，為了描述方便，將這3個運算分別用Ed、Ex和Mt表示，其中計算時間規則如下，Ed>Ex和Ed>Mt。

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

表1 簽密方案運算量比較

表2 簽密方案密文長度比較

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

4 結束語

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