具有固定長度密文的廣播加密方案

國佃利 ，楊鵬飛 ，劉家磊 ，王 萍 ，宋寧寧

(1.中國電子信息產業集團有限公司第六研究所，北京 100083；2.安陽師范學院 軟件學院，河南 安陽 455000；3.中國聯合網絡通信有限公司北京市分公司，北京 100052)

0 引言

廣播作為數據傳輸的重要方式，在有線電視、衛星通信、移動通信、計算機通信中有著廣泛的應用。廣播加密繼承了廣播中“一對多”的數據傳輸形式，是一種在不安全的信道中向指數量級用戶發送密態數據的密碼技術，指定授權集合中的用戶可恢復出加密密鑰，進而完成密態數據轉換。即使全部非授權用戶貢獻出用戶密鑰，也無法通過獲得廣播數據加密密鑰，該廣播加密方案被認為能夠抵抗完全合謀攻擊。

廣播加密方案的安全性可根據攻擊模型定義分為兩種類型：靜態安全性與自適應安全性，滿足上述兩種安全性的方案均能夠抵抗完全合謀攻擊。在靜態安全模型中，攻擊者在知曉系統公鑰前需公布挑戰的授權集合，而自適應安全模型中則沒有類似限制，實現自適應安全性往往需要犧牲部分加解密效率及大幅提升參數擴展量。實時數據廣播加密系統是目前廣播加密最為廣闊的應用方向，如何提升其加解密效率與降低參數擴展量是亟待解決的關鍵問題。

平凡的廣播加密方案的設計結構滿足低存儲空間需求和高安全性，能夠抵抗完全合謀攻擊。然而，平凡的廣播加密方案有著極其龐大的密文擴展量。Fiat 和Naor[1]在1993 年提出了第一個廣播加密方案，在該方案中用戶數量為N，密文擴展量為N(tlog2tlog N)。值得注意的是，該方案僅僅能夠抵抗不超過t 個用戶發起的合謀攻擊。顯然，作者希望通過降低安全等級的方式以尋求降低平凡的廣播加密方案中龐大的密文擴展量。2005 年，Boneh、Gentry 和Waters[2]利用素數階對稱雙線性映射構造了可抵抗完全合謀攻擊的廣播加密方案，密文擴展量與密鑰的擴展量都為O(1)，但系統公鑰擴展量隨著用戶總數N 線性增長。Gentry 和Waters[3]在2009 年提出了新的廣播加密方案，引入了半靜態安全性，期望通過“雙密鑰”策略將半靜態安全性轉化為自適應安全性，該方案的密文的擴展量為O(1)。同年，Waters[4]基于對偶系統加密構造了適應性安全的廣播加密方案，其密文擴展量為O(1)，但系統公鑰和用戶密鑰擴展量都為O(N)。隨后，多個研究人員利用多重線性映射構造了參數擴展量極低的廣播加密方案[5-7]，但隨著胡予濮教授[8]攻破了GGH 多重線性映射密碼方案，基于該方案的廣播加密方案均不再成立，在此不一一介紹。2015 年，Kim 等人[9]提出了基于身份的適應性安全的廣播加密方案，但該方案的系統公鑰和用戶密鑰均隨著最大接收者總數線性增長，也就意味著即使授權集合中僅包含一個用戶，也無法降低依據初始設定的最大接收者數量形成的各類參數擴展量。2019 年與2020 年，Guo 等人[10-11]分別提出了帶認證性質的基于公鑰的廣播加密方案，并分別給出了靜態安全性與自適應安全性證明，由于需要實現對消息發送者的鑒權認證，該方案的密文與密鑰擴展量擴張十分龐大。

本文利用素數階非對稱雙線性映射構造了基于公鑰的廣播加密方案，密文擴展量與用戶密鑰擴展量均為最優化的常數級別，公鑰擴展量隨著系統用戶總數增加線性增長，隨后在標準模型下基于非交互式的安全假設(co-Diffie-Hellman 假設)給出了靜態安全性的證明。

本文首先簡要描述素數階非對稱雙線性映射及co-Diffie-Hellman 安全假設。隨之，提出了一個新的廣播加密方案，并證明了方案的靜態安全性。

1 基礎知識

下面簡要描述素數階非對稱雙線性映射以及判定性co-Diffie-Hellman 問題的定義[12-14]。

1.1 素數階非對稱雙線性映射

映射e：G1×G2→GT為素數階段非對稱雙線性映射，其中G1、G2和GT為3 個階為大素數p的乘法循環群，滿足以下3種特性。

(1)雙線性 特性：對于?g∈G1，?h∈G2和?a，b∈Zp，有等式e(ga，hb)=e(g，h)ab成立。(2)非退化特性：?g∈G1，?h∈G2，滿足e(g，h)≠1。(3)高效計算特性：對于?g∈G1，?h∈G2，能夠高效地計算e(g，h)∈GT。

1.2 判定性co-Diffie-Hellman 問題

利用安全參數λ 素數階非對稱雙線性群生成器輸出3 個階為q的乘法循環群G1、G2和GT，以及非對稱雙線性映射e：G1×G2→GT。給定攻擊者D={G1，G2，GT，e，ga，h，hb，T}，其中g ∈G1，h ∈G2，a，b ∈Zp。通過判定輸出β∈{0，1}區分T 為gab或者為循環群G1中的一個隨機的生成元。

定義1如果判定性co-Diffie-Hellman 問題在多項式時間內是難解的，即不存在多項式時間算法能夠以不可忽略的優勢ε 解決該問題。

2 廣播加密方案

2.1 廣播加密系統定義

廣播加密方案包括以下4 個隨機化算法：Setup，KeyGen，Enc，Dec[13]。

(1)Setup(N，λ)，該算法以用戶總數N 為輸入，輸出結果為公私鑰對。

(2)KeyGen(msk，u)，該算法主私鑰和用戶身份u∈[1，N]為輸入，輸出結果為用戶u的私鑰sku。

(3)Enc(S，PK)，加密算法以授權集合S?[1，N]和公鑰為輸入，輸出結果為(Hdr，K)，其中Hdr 被稱為頭文件，K 為消息加密密鑰。

消息M 利用對稱加密方案在密鑰K 作用下加密為密文C，最后廣播密文為{S，Hdr，C}。

(4)Dec(PK，u，SKu，S，Hdr)，解密算法需要輸入公鑰PK、授權集合S、用戶身份u、用戶密鑰sku以及密文頭文件Hdr。如果u∈S，輸出消息加密密鑰K；否則，輸出⊥。最后，用戶u 利用密鑰K 解密C 獲取廣播消息M。

在解密算法中，對于S?[1，N]以及u∈S，如果(PK，msk)是由Setup(N，λ)生成，sku是由密鑰生成算法KeyGen(msk，u)生成，(Hdr，K)是由加密算法Enc(S，PK)生成，那么Decrypt(PK，S，u，sku，Hdr)=K。

2.2 廣播加密方案構造

本小節在素數階的非對稱雙線性群中構造了一個包含N 個用戶的靜態安全的廣播加密方案，密文與用戶密鑰擴展量為O(1)，公鑰擴展量為O(N)。新構造的靜態安全的廣播加密方案主要包括Setup、KeyGen、Enc、Dec 4 個算法。

(1)Setup(N，λ)，輸入用戶總數N與安全參數λ。算法生成兩個階同為大素數p的雙線性群G1和G2，隨機選取生成元g∈G1，h∈G2，并選取隨機數α，γ∈Zp，同時依次計算hi=h(αi)(i=1，2，…，N，N+2，…，2N)，v∈gγ。最終輸出系統公鑰參數PK={h，h1，h2，…，hN，hN+2，…，h2N，v}以及主私鑰msk={γ，α}。

(2)KeyGen(msk，i)，輸入用戶身份標識i ∈[1，N]，輸出該用戶的私鑰ski=＝g(γαi)。

(3)Enc(S，PK)，廣播者任意選取廣播用戶添加至授權用戶集合S?[1，N]，在加密算法中輸入系統公鑰及授權用戶集合S，隨后加密算法隨機選取數值t∈Zp，并計算消息加密密鑰K與頭文件Hdr，K=e (ski，hN-i+1)t=e(g，h)(tγαN+1)，Hdr=(C0，C1)=

最后，廣播者利用對稱加密算法對廣播內容進行加密，在消息加密密鑰作用下計算得到廣播密文C=SymEnc(M，K)。

(4)Dec(PK，j，skj，S，Hdr)，輸入接收者的身份標識j、接收者私鑰skj、系統公鑰、授權集合S 及密文頭文件Hdr。如果接收者j∈S，解密算法按照如下算式計算消息加密密鑰K；否則，輸出⊥。

如果接收者屬于授權用戶集合，其可利用已得到的消息加密密鑰K 解密廣播密文獲得廣播消息M=SymDec(C，K)。

3 安全性證明

3.1 靜態安全性模型

在靜態安全性模型中，敵手A 被允許適應性地查詢挑戰集合S*外的用戶私鑰，意味著敵手能夠掌握除挑戰集合S*外的所有用戶私鑰，因此隱式地模擬了完全合謀攻擊。具體的靜態安全性模型定義如下所示：

(1)Init，敵手A 公開想要挑戰的目標用戶集合S*。

(2)Setup，挑戰者運行初始化算法Setup(N，λ)，并將算法輸出的系統公鑰PK 發送給敵手A。

(3)Secret Key Queries，隨后敵手A 被賦予查詢用戶私鑰的權利，如果被查詢用戶i ∈S*時，挑戰者立即終止該實驗；否則挑戰者運行密鑰生成算法KeyGen(msk，i)，并將生成用戶密鑰ski發送給敵手A。如果敵手A 重復查詢用戶i的密鑰時，挑戰者不再運行密鑰生成算法，只將已生成的用戶密鑰ski發送給敵手A。

(5)More Secret Key Queries，敵手A 獲取后被允許繼續查詢挑戰集合S*外的用戶密鑰。

(6)Guess，如果挑戰者在密鑰查詢階段沒有終止實驗，敵手A 需返回對比特β的猜測β′∈{0，1}。

如果敵手在Guess 階段返回的猜測β′與挑戰者在Challenge 階段隨機選取的比特β 一致，則意味著敵手A贏得了該實驗，并攻破了廣播加密方案。

定義2令敵手A 能夠贏得廣播加密方案的優勢=|Pr[β′=β]-1/2|，對于任意多項式時間的敵手A，如果是一個關于λ的可忽略的函數，該廣播加密方案可滿足靜態安全性。

3.2 靜態安全性證明

基于上述定義的靜態安全性定義，在標準模型下證明了本文構造的廣播加密方案在判定性co-Diffie-Hellman 假設下滿足靜態安全性。判定性co-Diffie-Hellman假設為一般性靜態安全假設，其與敵手所做的密鑰查詢次數無關，將廣播加密方案的安全性歸約至此類安全性假設更為合理。

定理1如果不存在多項式時間敵手A 能夠以不可忽略的優勢解決判定性co-Diffie-Hellman 問題，本文中構造的廣播加密方案滿足靜態安全性。

證明：本小節利用反證法證明定理1，即如果多項式時間敵手A 可在不可忽略的優勢下攻破新構造的廣播加密方案，那么就能夠依托該敵手打造解決判定性co-Diffie-Hellman 問題的算法B。算法B 通過已取得的{G1，G1，GT，e，ga，h，hb，T}與敵手A 進行多輪次的交互模擬實驗。

首先，敵手A 選取目標用戶集合S*，并將其發送給算法B。值得注意的是，算法B 在該試驗中承擔挑戰者的角色。

隨后，算法B 選取隨機數α∈Zp，并計算hi=h(αi)，i=1，2，…，N，N+2，…，2N。隨后令v=ga，并將計算得到的參數{h，h1，h2，…，hN，hN+2，…，h2N，v}發送給敵手A。由于ga的隨機性隱含了數值a的隨機特性，算法B 使用a 模擬了系統主密鑰，但無法確定其準確數值。即使敵手A對上述公共參數后進行分析，也無法區分其與真實方案中的系統公鑰的差別。

敵手A 在接下來的實驗中被允許查詢目標用戶集合S*外的用戶私鑰，A 可將用戶身份發送給算法B，隨后B 利用已選取的隨機數α∈Zp以及ga計算得到ski=(ga)αi。值得注意的是，如果敵手A 重復查詢同一個用戶的私鑰，算法B 只能返回第一次計算得到的私鑰。

在挑戰階段，算法B 在目標用戶集合S*作用下計算挑戰密文頭及對應的消息加密密鑰：

敵手A 獲取挑戰密文頭與消息加密密鑰后，會根據已得到的信息返回算法B 一個比特值β，算法B 用于解決判定性co-Diffie-Hellman 問題。

通過以上實驗交互，算法B 借助敵手A的能力實現了對于新提出的廣播加密方案的模擬，并在其中嵌入了判定性co-Diffie-Hellman 問題，一旦算法B 能夠以不可忽略的優勢解決判定性co-Diffie-Hellman 問題，那么敵手A 就能夠以同樣的優勢攻破新提出的廣播加密方案。通過反證法得出結論，由于判定性co-Diffie-Hellman 問題在多項式時間內是難解的，因此本文提出的廣播加密方案滿足靜態安全性。

4 結論

本文利用素數階非對稱雙線性映射設計了一個滿足靜態安全性的廣播加密方案，其中密文擴展量與用戶密鑰擴展量均為固定長度，系統公鑰擴展量隨著用戶總數線性增長，隨后給出了形式化的安全性證明。新提出的廣播加密方案系統公鑰擴展量仍十分龐大，在未來的研究中希望通過采用新的密碼學工具及安全假設構造更為安全的廣播加密方案，在保證參數擴展量優化的同時進一步提升安全特性。