一個改進的多消息多接收者混合簽密方案

李亞榮，李 虓，葛麗霞，何明星

1.西華大學 理學院，成都 610039

2.西華大學 計算機與軟件工程學院，成都 610039

1 引言

隨著互聯網技術的日漸成熟，人類進入大數據時代，網絡技術給人們帶來了的便利的同時，也帶來了前所未有的安全性挑戰。密碼學是信息安全的核心，為信息安全提供了重要的理論支持。簽密是繼簽名和加密之后又一個新的密碼學原語，于1997年被Zheng等人[1]提出。簽密能在一個邏輯步驟內同時實現簽名和加密兩種功能，能同時提供機密性、完整性、認證性和不可否認性四種安全性質。此后，大量的的簽密方案[2-5]被陸續提出。

在實際網絡應用傳輸中，經常需要廣播一條或者多條消息給多個接收者。多接收者簽密以加密且認證的方式廣播一個或多個消息給多個接收者，每個接收者用自己的私鑰獨自解簽密從而獲得消息。多接收者簽密解決了使用傳統公鑰算法安全分發多消息、組播密鑰時需要多次加密傳輸的問題。然而，在已有的多接收者簽密方案[6-8]中還存在著一些問題，比如發送方和接收者的身份匿名性、解密公平性等等。為了解決身份的匿名性，2011年，龐遼軍等人[9]基于拉格朗日內插值多項式提出一個匿名的多接收者簽密方案。2015年，Pang等人使用新的多項式技術來代替拉格朗日插值多項式，提出了一個新的匿名的基于身份的多接收者簽密方案[10]，將接收者的身份信息進行混合，保證接收者的身份匿名性。

多接收者簽密實例中，有時需要給不同的接收者發送不同的消息，消息長度會很大。公鑰加密技術運算速度較慢，適合加密短消息，而對稱加密技術運算速度較快，可以加密長消息。混合加密技術是公鑰加密技術和對稱加密技術的結合，可以實現對長消息的加密，在實際的安全通信中，使用混合加密會更安全高效。

混合簽密最早于2004年由Cramer等人[11]提出，其對混合簽密作了形式化的定義。2005年，Dent等人[12]給出了混合簽密的具體算法和安全模型的形式化定義。2013年，黎仁峰等人[13]提出一種多方混合簽密方案，但方案一次只能發送同一個消息給多個接收者。2016年，王彩芬針對文獻[13]基于離散對數提出了一個改進的方案[14]，改進方案通過一次廣播發送多條消息給多個接收者。

2 M-DLHSC方案及其安全性分析

2.1 M-DLHSC方案回顧

2016年，王彩芬等人提出一個基于離散對數的多消息多接收者混合簽密方案[14]，這里簡記為M-DLHSC方案。方案簡介如下：

系統設置G1是中生成元為g、階為素數q的循環群。密鑰生成中心（KGC）定義了4個Hash函數：G1；一個密鑰導出函數最后KGC公開系統參數：params={G1,q,h1,h2,h3,h4,KDF}。

密鑰生成算法KGC隨機選擇n),計算生成n名接收者的公/私鑰對(pkri,skri)，其中，將(pkri,skri)發送給接收者并公開 pkri。

簽密算法給定(params,pks,sks,pkr1,pkr2,…,pkrn)，發送者按照如下步驟簽密n條消息給n名接收者：

（1）從G1中均勻隨機選擇r,r1，其中

（2）計算δ=gr1modp；

（7）計算φ=(φ1,φ2,…,φn)，其中

（10）計算 K=KDF(r)；

（11）計算C=Enck(M)；

解簽密算法接收者執行以下算法：

（2）計算 β′=h4(φ′0,φ)；

（3）驗證β'=β是否成立，如果成立，則說明密文σ確實由合法的發送者發出，且φ'0=φ0，如果不成立，則停止通信；

（5）計算 K=KDF(r)；

（6）計算 M=DecK(C)；

2.2 M-DLHSC方案的安全性分析

M-DLHSC方案[14]存在密鑰泄露問題，任一合法接收者都可以通過計算得到發送者的私鑰，具體分析如下。

合法接收者 IDi收到密文 σ=(C,ω)=(C,φ,β,x,δ)后：

（1）運行解簽密算法步驟（1）～（6），得到消息 M 和r；

M-DLHSC方案[14]被攻擊的主要原因是方案的不可偽造性證明中的DL實例選擇有錯誤。離散對數困難性（DL）假設，即尋找 a( 0 ≤a ≤q ) )，使得 ga=d 成立，這里a的值是事先未知的。而在 M-DLHSC方案[14]證明中，DL實例中的d被設定成了d=φ0，而φ0是算法中的已有的值(φ0=gt)，t值是可以事先算出來的。也就是說這里所選的DL實例不是困難性問題。

3 改進的多消息多接收者混合簽密方案

針對M-DLHSC方案[14]中存在的密鑰泄露問題，本文基于雙線性對提出了一個基于身份的混合簽密方案。方案具體如下：

系統設置該算法由密鑰生成中心（KGC）完成。輸入參數1k，輸出系統主密鑰s，KGC保密s。 G1是生成元為P、階為素數q的循環加群，k是安全參數。KGC定義4個Hash函數：，雙線性映射：，一個密鑰導出函數最后KGC公開系統參數：e,KDF}。

密鑰生成算法該算法生成用戶的密鑰，由KGC完成。KGC計算用戶IDi的公鑰QIDi=H1(IDi)和私鑰

簽密算法該算法為n個接收者生成簽密，由簽密者IDS完成。

（9）密鑰封裝ω=(φ,U,Y,V)；

（10）輸出簽密密文σ=＜C,ω＞。

驗證算法接收者收到密文σ=＜C,ω＞后，計算h=H4(C,U,φ,Y)并驗證等式

是否成立。如果不成立，則拒絕接受該簽密；否則接受該簽密。

解簽密算法接收者執行以下算法：

（3）計算 M=DecK(C)；

4 正確性及安全性分析

4.1 正確性證明

4.2 安全性分析

在隨機預言機模型[15]下，改進方案的機密性和不可偽造性分別由定理1和定理2給出。

4.2.1 機密性

證明C接收一個隨機的Gap-BDH問題實例（P,aP,bP,cP,T)，他的目標是判斷T=e(P,P)abc。C作為子程序并扮演游戲中A的挑戰者。

初始階段C設定Ppub=aP（C并不知道a，a扮演系統主密鑰），將系統參數 params=＜e,G1,G2,q,P,Ppub,H1,H2,H3,H4＞發送給敵手A。A接收到系統參數后，選擇n個挑戰身份L1,L2,L3,L4這4張列表分別跟蹤A對預言機H1,H2,H3和H4的詢問，且L1,L2,L3,L4最初為空。

階段1A向C進行如下詢問和挑戰：

H1詢問對于第 i次非重復 H1(IDi)詢問，i∈[1,qH1]，如果 L1中存在元組，則返回 QIDi，否則C做如下步驟：如果 IDi∈TID*，那么C回答H1(IDi)=bP，并將插入列表L1中（其中表示C不知道b的值）；否則，C選擇隨機數，計算并返回QIDi給A。

密鑰提取詢問對于每次新的IDi詢問，如果IDi∈TID*，那么C不能回答這個詢問，模擬終止；否則C查找列表 L1得到 Qi和 ηi，計算并返回私鑰。

H2詢問C首先查找列表L2，如果存在包含詢問目標的元組，則返回相應的輸出結果給A；否則，C選擇一個恰當的隨機數作為應答結果返回給A，并將包含詢問和相應的值存入輸出列表中。

H3詢問對于每次新的H3(Ti)的詢問C檢查列表L3，如果 L3中存在元組 (IDi,Ti,μi)，則返回 μi。如果L3中不存在這樣的元組，C使DBDH預言機檢查元組(aP,bP,cP,Ti)。如果該預言機返回“真”，結束游戲，因為C已經獲得e(P,P)abc=Ti；否則C隨機選擇并將(IDi,Ti,μi)插入列表L3中。

H4詢問C首先查找列表L4，如果存在包含詢問目標的元組，則返回相應的輸出結果給A；否則，C選擇一個恰當的隨機數作為應答結果返回給A，并將包含詢問和相應的值存入輸出列表中。

簽密詢問A發起對發送者IDS，接收者及的多消息簽密詢問。C通過密鑰提取詢問獲得身份IDS對應的私鑰SIDS，通過公鑰詢問獲得所有接收者的公鑰。運行算法Signcryption(params,，最后將密文σ發送給A。

解簽密詢問A選擇一個接收者身份對一個密文σ=(C,ω)發起詢問，C執行以下的步驟：

（1）執行解簽密的驗證部分，如果驗證方程不成立，那么返回錯誤符號這個過程可能需要進行公鑰詢問和H4詢問。

挑戰A決定何時進入挑戰階段。A生成兩個等長的明文消息和m′n}。C選擇一個簽密者IDS（其私鑰為SIDs=aQIDs=ηs?aP=ηsPpub），并隨機選擇，其中 γ∈{0,1}，對n個挑戰身份作如下步驟構造一個挑戰密文：

（1）C設置Y*=cP；

（4）隨機選取 μi∈{0,1}l，i=1,2,…,n,r1∈{0,1}l以及

（6）K=KDF(r1)，C=EncK(M)；

（7）計算 h=H4(C,U,φ,Y)；

（8）計算 U*=r2Ppub, V*=(r2+h)SIDS；

（10）最終生成一個目標密文 σ*=＜C*,ω*＞，并將密文σ*返回給A。

階段2A可以像階段1那樣執行多項式有界次適應性詢問。C像在階段1那樣回答這些詢問，但是不能發起對挑戰身份信息的私鑰提取詢問，以及對挑戰密文σ*的解簽密詢問。

猜測A輸出猜測值γ′∈{0,1}，游戲結束。如果A能以ε的優勢猜出γ′=γ，那么C就可以計算e(SID*i,Y)=e(sQID*i,Y)=e(abP,cP)=e(P,P)abc=T，從而解決了Gap-BDH問題。

下面分析C的優勢。如果下列事件發生，C模擬失敗：

E1：A對目標身份IDj(j∈{1,2,…,n})執行了私鑰提取詢問。

E2：A通過H3的詢問就得到DBDH問題實例的正確解答。

4.2.2 不可偽造性

證明C接收一個隨機的CDH問題實例(P,aP,bP)，它的目標是計算abP。C把A作為子程序并扮演A的挑戰者。

初始階段C設定Ppub=aP（C并不知道a，a扮演系統主密鑰），將系統參數 params=＜e,G1,G2,q,P,Ppub,H1,H2,H3,H4＞發送給A。敵手A選擇挑戰身份IDS。

階段1A接收到系統參數后，向C進行如下詢問和挑戰：

H1詢問對于第i次非重復H1(IDi)詢問，i∈[1,qH1]，如果L1中存在元組(IDi,QIDi,ηi)，則返回QIDi，否則C做如下步驟：如果IDi=IDS那么C回答H1(IDi)=bP，并將插入列表L1中（其中⊥表示C不知道b的值）；否則，C選擇隨機數，計算QIDi=ηiP并返回QIDi給A。

密鑰提取詢問對于每次新的IDi詢問，C查找L1得到QIDi和ηi。如果IDi=IDS，那么C不能回答這個詢問，模擬終止；否則計算 Si=aQIDi=a?ηiP=ηi?aP=ηiPpub，并返回給A。

H2、H3、H4詢問C首先查找列表 L2、L3、L4，如果存在包含詢問目標的元組，則返回相應的輸出結果給A；否則，C選擇一個恰當的隨機數作為應答結果返回給A，并將包含詢問和相應的值存入輸出列表中。

簽密詢問A發起對發送者 IDl，接收者及 M={m1,m2,…,mn}的多消息簽密詢問。C可以通過私鑰提取詢問獲得身份IDl對應的私鑰SIDl，通過公鑰詢問獲得其他環成員公鑰和接收者公鑰，然后運行算法Signcryption(params,M,SIDl,{QID*i}),最后將簽密密文σ發送給A。

偽造敵手A對挑戰身份IDS按下面的方式偽造一個挑戰密文。

如果這個偽造是成功的，A贏得游戲。

如果A能以不可忽略的優勢ε在時間t內產生相應簽密密文贏得游戲，根據分叉引理，C可以重復A行為，通過控制隨機預言機H4的輸出，在時間2t內輸出簽密密文σ*和σ*′。注意這里，顯然，就解決了CDH問題。

下面分析C的優勢：

（1）如果事件E1發生，C模擬失敗：E1：A對目標身份IDS執行了私鑰提取詢問。顯然

（2）敵手在偽造簽名時，需要在G1中尋找V*滿足等式e(V*,P)=e(QIDS,U*+hPpub)的V*。此概率小于等于1/q。

5 結束語

本文分析了王彩芬等人的基于離散對數的多消息多接收者混合簽密方案[9]的安全性，發現該方案存在著密鑰泄露問題。在基于身份的密碼體制下，提出了一個改進的多消息多接收者混合簽密方案。改進的方案解決了王彩芬等人的方案[9]的缺陷，其機密性和不可偽造性在隨機預言機模型下得到了證明。