基于Cocks 身份密碼體制的高效簽密方案

彭長根，張小玉，丁紅發，楊善慧

（1.貴州大學數學與統計學院公共大數據國家重點實驗室，貴州 貴陽 550025；2.貴州大學計算機科學與技術學院，貴州 貴陽 550025；3.貴州大學密碼學與數據安全研究所，貴州 貴陽 550025；4.貴州財經大學信息學院，貴州 貴陽 550025）

1 引言

簽密能在一個邏輯步驟內同時實現加密和簽名，相比于單純地將加密和簽名方案組合，其在計算效率和通信開銷上都具有明顯的優勢。自Zheng等[1]基于橢圓曲線上的離散對數提出第一個簽密方案后，構造安全有效的簽密方案便成為研究熱點，不同的簽密方案也被廣泛地應用于電子支付、移動代理安全等輕量級計算場景。2002 年，Malone-Lee[2]首次提出了基于身份密碼的簽密方案，賦予了簽密方案便捷密鑰管理的優勢。

5G 中除了終端基本的安全需求外，增強型移動寬帶（eMBB,enhance mobile broadband）場景[3]的傳輸效率非常高，終端必須具備高速率的加解密能力。此外，eMBB 場景涉及的敏感信息較多（如個人身份標識、地址信息等），因此終端還需要重視用戶隱私數據的保護，這種場景下需要設計安全高效的密碼算法和認證協議來確保其正常運行。現有的基于身份的簽密方案大多是由雙線性對構造的，利用雙線性對構造的簽密方案在不犧牲安全性的前提下可使用較短的密鑰，但其在簽密過程中需要進行大量復雜的雙線性對運算，會造成高昂的計算開銷，也會降低簽密和解簽密速率。5G 時代的到來，使人們對簽密方案也提出了更高的要求，導致基于雙線性對的簽密方案在類似于上述eMBB 場景下形成了新的應用瓶頸。如何利用新的密碼技術，設計更加高效的簽密方案，為5G 網絡提供安全基礎保障，成為一個極具挑戰的課題。

1997 年，Zheng[4]提出了一種名為簽密的密碼原語，由于其能有效地解決傳統的先簽名后加密方案中計算效率低和通信開銷大的問題，迅速成為研究熱點。2002 年，Shin 等[5]提出了基于數字簽名算法（DSA,digital signature algorithm）的可驗證簽密方案，其簽名通過DSA 進行驗證，但因消息m部分顯式地出現在驗證式中，導致該方案不能滿足語義安全。2017 年，Yu 等[6]提出了一種無配對的無證書簽密方案，該方案在隨機預言機模型中利用計算型 Diffie-Hellman （CDH,computational Diffie-Hellman problem）問題和離散對數（DL,discrete logarithm）問題證明其具有機密性和不可偽造性，但該方案對惡意的密鑰生成中心（KGC,key generation center）和惡意的發送者是不安全的。2019 年，Rezaeibagha 等[7]提出了一個可證明安全的同態簽密方案，該方案證明了同態簽密可推廣到可證明的安全廣播簽密方案，允許在不需要解密的情況下聚合廣播的簽密數據項，但該方案因需要大量的雙線性對運算，導致加解密效率較低?；谏矸莸拿艽a系統具有便捷管理密鑰的優勢，自 2002 年Malone-Lee[2]利用雙線性對構造了首個基于身份的簽密方案以來，基于身份的簽密方案[8-11]就得到各專家學者的廣泛研究。

2003 年，Libert 等[8]指出Malone-Lee[2]的方案不具有語義安全性，同時構造了基于橢圓曲線上雙線性對的簽密方案，但該方案不能同時滿足前向安全性與公開驗證性這2個重要的安全特性。2016年，Wang 等[9]構造了基于多線性映射的聚合簽密方案，該方案在標準模型下可抵抗適應性選擇明文攻擊，但其同樣存在多線性對運算帶來的計算效率不高的問題。2017 年，Reddi 等[10]利用雙線性映射構造了基于身份的群簽密密鑰協商協議，該協議使用簽名對參與的用戶進行認證，并驗證2 個用戶之間傳輸消息的正確性，在物聯網中具有一定的實用性。2018 年，Zhou 等[11]提出了基于身份的廣義代理簽密方案，該方案可以在代理簽密模式下進行公開驗證，并在隨機預言機模型中證明了方案的不可偽造性和機密性，但方案的密文膨脹較大，導致密文空間效率偏低。上述基于雙線性對構造的簽密方案都存在計算效率不高的問題，基于此，專家學者致力于研究減少雙線性配對的次數或直接構造無配對的簽密方案[12-14]。而傳統數論中的雅可比符號的求值運算，因相對于雙線性對運算在計算效率上有較大的優勢，適于解決簽密方案運算效率不高的問題。

基于二次剩余的加密源于2001 年Cocks[12]提出的基于二次剩余的基于身份的加密（IBE,identity-based encryption）方案，該方案加密過程僅需進行簡單的雅可比（Jacobi）符號求值和模的求逆運算，計算執行效率較高，但Cocks[12]對方案的安全性只做了簡單的描述，并未進行詳細證明。2013年，Clear 等[13]將文獻[12]方案的密文視為多項式商環 ZN[x]/(x2?rid)中的元素，在此基礎上，構建了一個強異或運算（XOR,exclusive OR）同態IBE 方案。同年，Dan 等[14]的廣義Cocks 方案自然地將二次剩余推廣到高次剩余，允許一次加密多個比特，加密lbit 明文，得到的密文大小約為2llbNbit，但這種泛化的缺點是密文膨脹規模大。2019 年，Clear等[15]擴展了文獻[14]方案，使其滿足加法同態性，并證明了該方案在隨機預言機模型中的e次剩余假設下是IND-ID-CPA 安全的，但該方案同樣面臨密文膨脹的問題。

1997 年，Chang 等[16]提出了基于二次剩余的數字簽名協議，協議允許任何發送者發送無限量的消息塊，并在每個塊上簽名，解決了基于傳統密碼體制一次只能簽名Nbit 的問題。2007 年，Chai 等[17]利用計算二次剩余的2l根的技術構造基于身份的簽名方案，并在隨機預言機模型中證明其在選擇明文攻擊下具有不可區分性。2015 年，Zhao 等[18]提出了一種有效的部分盲簽名方案，該方案利用二次剩余求值的困難問題在隨機預言機模型中證明了方案的盲性與不可偽造性，其簽名空間被限制在二次剩余類群中。2018 年，Ateniese 等[19]提出了一類基于二次剩余假設的全域哈希簽名方案，構造了2 種不同的方案，一種方案具有簽名唯一的特性，另一種方案在簽名驗證過程中最多進行3 次模乘運算，驗證階段效率較快。可見，基于二次剩余的簽名、加密方案的構造一直是密碼學領域的研究熱點，但尚未有安全高效的簽密方案被設計。如何設計計算效率高、通信成本低的簽密方案仍是一個具有挑戰性的課題。

鑒于上述分析，本文提出了一種基于Cocks 身份密碼體制的高效簽密（CBSC,Cocks IBE signcryption）方案。本文的主要貢獻如下。

1) 構造適合CBSC 方案的安全模型，給出方案保密性和不可偽造性的相關“攻擊?挑戰”游戲的形式化定義。在改進Cocks 基于身份的加密方案的基礎上，利用二次剩余問題構造簽名部分在一個邏輯步驟內完成簽密方案的設計。

2) 在隨機預言機模型下對所提方案的安全性進行證明，將其安全性歸約到數論中的二次剩余判別困難問題，證明了所提方案在適應性選擇密文攻擊下具有不可區分性，在適應性選擇消息下滿足不可偽造性，具有較好的安全性。

3) 效率分析表明，所提方案相較于已有的基于雙線對和橢圓曲線離散對數的簽密方案，由于其不存在復雜的雙線性對運算，且所提方案構造中主要利用運算效率較高的雅可比符號求值運算，故所提方案在計算效率方面具有明顯的優勢。

2 基礎知識

2.1 定義及定理

2.2 Cocks 公鑰密碼方案

Cocks 公鑰密碼[12]是由Cocks 在2001 年提出的一種新的基于二次剩余的身份密碼體制，該方案將用戶的身份等公共已知值作為公鑰，具有優良的性質，計算執行效率較高，可用于構造高效的密碼算法。該算法由Setup、KeyGen、Encrypt和 Decrypt 這4個部分組成。

Setup (1λ)。給定一個安全參數λ，初始化階段生成2 個不同的大素數p,q(p=q=3mod4)，計算N=pq。選擇哈希函數H:輸出主密鑰MSK={p,q}，系統公開參數PP={N,H}。

KeyGen (id,MSK)。計算a=H(id)，滿足r2≡±amodN，計算出返回私鑰sk={r}。

Encrypt (id,x,PP)。用戶Bob 首先生成一個傳輸密鑰，使用對稱加密的方式加密數據，并依次向接收者Alice 發送傳輸密鑰的每個位，步驟如下。

1) 設x是傳輸密鑰的單個位，編碼x為1 或?1。

3 CBSC 簽密方案安全模型形式化定義

本節構造適合CBSC 方案的安全模型，給出方案保密性和不可偽造性的相關“攻擊?挑戰”游戲的形式化定義。通過攻擊游戲的定義，可以對方案的安全性進行更準確的證明。

3.1 保密性定義

游戲由系統初始化階段、詢問階段、挑戰階段和猜測階段4 個階段組成，參與方包括敵手A和挑戰者C，具體步驟如下。

1) 系統初始化階段。輸入安全參數λ，C維護各個列表記錄相應預言機詢問及密鑰生成詢問的數據，同時運行Setup 算法，生成系統主密鑰MSK和公開參數PP，并將公開參數PP 發送給A。

2) 詢問階段。敵手A向挑戰者C發起多項式有界次如下詢問。

①密鑰生成（KeyGen ）詢問。A以身份IDi詢問，C查詢私鑰對應列表，運行KeyGen 算法產生一個對應的私鑰發送給A。

② 簽密（Signcrypt）詢問。A以發送者身份IDs、接收者身份IDr和明文m進行詢問，C計算發送者私鑰，并以相同的輸入向相應的預言機進行簽密詢問，預言機將密文σ返回給挑戰者C，C將發送給A。

③解簽密（Unsigncrypt）詢問。A以發送者身份IDs、接收者身份IDr和合法密文σ進行詢問，C計算接收者私鑰，并以相同的輸入向相應的預言機進行解簽密詢問，預言機將明文m返回給C，C將結果發送給A。

以上詢問可以是自適應的，即執行每一次的詢問時都可以根據前一次詢問時得到的結果進行相應的調整。

3) 挑戰階段

①敵手A選擇2 個明文m0、m1和希望挑戰的身份ID1、ID2，其中ID1和ID2在之前的詢問中都未進行過KeyGen 詢問。

② 挑戰者C隨機選擇b∈R{0,1}，并將消息mb、A指定的發送者ID1的私鑰接收者身份ID2及公共參數PP 作為輸入向預言機進行簽密詢問，返回密文給挑戰者C，C將σ*發送給A。

③A可以繼續像詢問階段那樣進行多項式有界次詢問，但此時對ID1和ID2不能進行KeyGen 詢問，對σ*也不能進行Unsigncrypt 詢問。

4) 猜測階段。A輸出b′∈{0,1}作為對b的猜測，如果b′=b，則A贏得游戲的優勢可以定義為

定義4如果不存在任何多項式有界敵手A以不可忽略的優勢贏得上述游戲，則CBSC 方案可以抵抗適應性選擇密文攻擊（IND-ID-CCA2），即在適應性選擇密文攻擊下具有保密性。

3.2 不可偽造性定義

游戲由系統初始化階段、詢問階段和偽造階段3 個階段組成，游戲雙方仍為敵手A和挑戰者C，具體步驟如下。

1) 系統初始化階段。輸入安全參數λ，C運行Setup 算法，生成系統主密鑰MSK 和公開參數PP，并將公開參數PP 發送給A。

2) 詢問階段。和機密性的詢問階段一樣，A執行多項式有界次相應的KeyGen、Signcrypt、Unsigncrypt 詢問。

3) 偽造階段（Forge Phase）。A輸出元組(σ*,ID1,ID2)作為對明文消息的偽造，挑戰者C將上述元組作為輸入提交給預言機進行解簽密詢問，預言機將密文σ*的解簽密結果返回給挑戰者C，如果密文σ*不是由Signcrypt 詢問產生，ID1未執行過KeyGen 詢問，且的輸出不是失敗符號⊥，則A贏得游戲。A贏得游戲的優勢定義為其的概率Adv(A)=Pr[Awin]。

定義5如果不存在多項式時間敵手A以不可忽略的優勢贏得上述游戲，則稱CBSC 方案在適應性選擇明文攻擊下具有不可偽造性（CBSC-EUFCMA）。

4 CBSC 簽密方案構造

本節提出的CBSC 簽密方案是基于Cocks 的IBE 體制構造的簽密方案，方案的參與者包括PKG和簽密通信雙方ID1,ID2，由4 個算法組成，即系統初始化算法Setup、密鑰生成算法KeyGen、簽密算法Signcrypt 和解簽密算法Unsigncrypt，算法運行過程如下。

首先定義函數

1) 系統初始化算法(1λ)

5 CBSC 簽密方案分析

5.1 正確性

1) 密文σ=(c1,s2)正確性驗證分析。接收者ID2收到密文s2后，有再利用c1和s1計算出c2=H3(c1)⊕s1然后驗證式(4)是否成立。

如果式(4)成立，則簽密過程是可信的，得到的密文σ=(c1,s2)是正確的；否則，發送者在簽密過程中或數據發送過程中存在偽造行為。

2) 解簽密正確性分析。如果接收者ID2收到的是正確的密文σ=(c1,s2)，并且持有合法的解密密鑰，則利用自己的私鑰r2、身份ID2和發送者的公鑰R1，根據c1與c2數值上是否相等，可以得到相應的c0或的值，運行Cocks 密碼體制中的Decrypt算法可以得到m′。

5.2 保密性

下面，定義通過上述模擬的預言機來攻破簽密體制的游戲。

1) 初始化階段。挑戰者C運行Setup 算法，生成系統主密鑰MSK 和公開參數PP，并將PP 發給敵手A。

2) 詢問階段。A通過上述預言機向挑戰者發起多次的KeyGen、Signcrypt 和Unsigncrypt 詢問。

3) 挑戰階段。A輸出2 個消息{m0,m1}，挑戰者C隨機選擇一個比特b，對消息mb計算簽密文σ*，并將σ*發送給A。

4) 第二次詢問階段。敵手A仍可進行各種預言詢問，但不能對將要挑戰的密文σ*進行相應的Unsigncrypt 詢問。

5) 猜測階段。攻擊者A輸出比特b′，經分析知，該模擬等同于敵手A的實際攻擊環境，敵手A只有通過詢問H1-oracle 得到ω，才能猜測成功，定義事件EA為挑戰者C在記錄表中選擇正確記錄ω，則該事件發生的概率為；若由選擇的記錄得到b=b′，則C將能有效判別ω是否為模N的二次剩余。

下面，對挑戰者C成功的概率進行分析，定義事件E表示敵手A在猜測階段成功輸出比特b=b′，事件E′表示模擬成功。在模擬成功并選擇正確記錄的情況下，敵手A輸出正確比特說明挑戰者C可以成功解決困難假設。

定義C成功的優勢為ε′=Pr[E∩E′∩EA]，則有

證畢。

保密性分析表明，敵手A成功攻破CBSC 方案保密性的優勢與一個不可忽略量的乘積不大于挑戰者C成功解決二次剩余假設的優勢。

5.3 不可偽造性

定理3如果在概率多項式時間內存在一個敵手A能夠以的優勢來贏得3.2節的游戲（最多進行次H1詢問、次H2詢問、次H3詢問、qSK次密鑰生成詢問、qSC次簽密詢問、qUSC次解簽密詢問），那么存在一個挑戰者C以的優勢判斷出模N的二次剩余問題，其中

證明設敵手A是攻擊CBSC-EUF-CMA 安全性的攻擊者，定義和LSK這4 個記錄表來記錄相應的預言機詢問和密鑰生成詢問。與保密性分析中定義相同，簽密過程可以看作

在攻擊簽密體制不可偽造性時進行和定理2 詢問階段一樣的多項式有界次詢問，并且其詢問也是適應性的，只是不返回明文消息m。

下面，定義通過上面模擬的預言機來攻破簽密體制的游戲。

1) 初始化階段。挑戰者C運行Setup 算法，生成系統主密鑰MSK 和公開參數PP，并將PP 發給敵手A。

2) 詢問階段。敵手A通過上述預言機發起各種詢問，同定理2 詢問階段相同。

3) 偽造階段。進行上述有界次詢問后，敵手A輸出偽造的密文，假設簽密接收者為R，由機密性分析可知，該模擬等同于敵手A的實際攻擊環境，敵手A必須通過H1詢問和H2詢問來得到消息m*對應的ω*，才能偽造成功，其中定義事件EA為挑戰者C在記錄表中選擇正確記錄ω*，則該事件發生的概率為；若選擇的記錄正確，則C將能有效判別ω*是否為模N的二次剩余。

下面，分析挑戰者C成功的概率，事件E表示敵手A成功偽造一個有效的密文σ*，并通過了驗證，事件E′表示模擬成功。在模擬成功并選擇正確記錄的情況下，敵手A成功偽造有效密文說明挑戰者C可以成功解決困難假設。

定義C成功的優勢為則有

證畢。

不可偽造性分析表明，敵手A成功攻破CBSC方案不可偽造性的優勢與一個不可忽略量的乘積不大于挑戰者C成功解決二次剩余假設的優勢。

已知任意多項式時間的攻擊者都不可能以不可忽略的優勢解決二次剩余假設問題，即可知任意多項式時間的敵手不可能攻破CBSC 方案的保密性和不可偽造性。

6 效率分析

6.1 計算效率分析

目前，缺乏同類基于Cocks 的IBE 密碼體制的簽密方案，本節則將CBSC 方案與其他現有的基于雙線性對[10-11,15-16]及橢圓曲線離散對數[6,13]的方案進行對比分析。由于不同方案的效率運算單位及其耗時不統一，為了能夠使不同方案的簽密與解簽密過程在同一指標下進行效率對比，本節首先基于文獻[14]方案中的數據定義了不同的符號及符號換算，如表1 所示。

表1 符號定義及換算

表1 中，與文獻[14]方案數據相似，為了實現與1 024 bit 的RSA 密鑰相當的安全性，基于雙線性配對的方案在具有嵌入度2 和素數階p的超奇異橢圓曲線上執行Tate 配對，其中形式為p=2159+217+1的160 bit 的Solinas 素數和至少為512 bit 的素數q滿足條件q+1=12pr。為了達到相同的安全性，基于無配對的橢圓曲線方案在上定義為y2=x3+ax2+b的Koblitz 曲線上執行運算，其中a=1且b為一個163 bit 的隨機數?；谂鋵嬙斓姆桨钢?12 bit 隨機數提供的安全性等同于無配對方案中160 bit 隨機數提供的安全性。因此，在本文方案中，假設H i(i=0,1,2,3)的輸出為160 bit，雅可比符號運算為1 024 bit。

由表1 可知，執行一次雙線性配對運算的時間是執行一次模乘運算所需時間的87 倍，而執行一次橢圓曲線標量點乘運算所需時間是執行一次模乘運算所需時間的29 倍，但執行一次雅可比符號運算的時間只有執行一次模乘運算所需時間的6.5 倍。因此，執行一次雙線性對運算相當于可以執行13次雅可比符號運算，執行一次橢圓曲線標量點乘運算相當于可以執行4 次雅可比符號運算。綜上所述，執行雅可比符號運算的計算效率相對較高。

表2 對比了CBSC 方案與其他方案中用戶執行一次簽密操作、一次解簽密操作需花費的計算成本，對比過程忽略了方案中都存在的哈希函數運算以及異或運算。

表2 計算效率比較

分析結果表明，在簽密和解簽密的計算效率上CBSC 方案明顯優于其他方案。一方面，與基于雙線性對的簽密方案[10-11,15-16]相比，由表2 可以看出，文獻[15]方案簽密過程中不需要進行配對運算，解簽密過程只需進行一次配對運算。盡管文獻[15]方案相比于文獻[10-11,16]方案所需的配對數量都要少，但簽密過程所需時間仍是CBSC 方案的13 倍，解簽密過程也需花費CBSC 方案6 倍的時間。因此，由于CBSC 方案主要用到計算量較小的雅可比符號求值和模的求逆運算，在簽密和解簽密的時間上遠小于基于雙線性對的簽密方案；另一方面，與基于橢圓曲線離散對數的簽密方案[6,13]相比，雖然兩者都不存在雙線性對運算，但從表2 可知，簽密過程中文獻[6]方案所需時間仍是CBSC 方案的8 倍，解簽密過程花費時間雖與CBSC 方案相差不大，但也是CBSC 方案的1.5 倍。綜上所述，本文提出的CBSC 方案有較高的計算效率。

6.2 仿真實驗分析

對CBSC 方案進行仿真實驗，在3.60 GHz 的8核64 位Intel(R) Core(TM)i7-4790U 處理器、8 GB內存（RAM）、Windows 7 操作系統的實驗環境進行實驗，選用Visual studio 2017 作為實驗平臺、C++作為實驗編程語言，分別對KeyGen 算法、Signcrypt算法和Unsigncrypt 算法進行模擬運行。使用不同長度的明文消息運行9 次實驗，比較了不同明文消息進行簽密、解簽密的執行時間，以達到對方案的計算效率進行驗證的目的，實驗結果如圖1所示。

圖1 不同明文長度下方案執行時間

圖1 的實驗數據表明，CBSC 簽密方案最耗時的部分是密鑰生成部分，簽密算法的耗時低于解簽密算法耗時，并從某一個初值開始隨消息長度增大呈緩慢的增長趨勢。由于CBSC 簽密方案在簽密過程中除哈希運算外只存在雅可比符號求值運算耗時，而解簽密過程除哈希運算外還存在雅可比符號求值及模的求逆運算的耗時，此外，因為簽密方案中雅可比符號運算及模逆運算計算效率都相對較高，因此方案的簽密、解簽密過程的耗時都相對少。綜上可以得出，實驗結果與理論分析是一致的。

進一步地，類似于文獻[17]，基于表1 一樣的數據設置，在與上述相同的實驗環境下，只是實驗過程采用密碼函數庫miracl 進行操作，得到表1 相關運算操作的單次運行時間，如表3 所示。

表3 相關操作單次運行時間

基于表3，將CBSC 方案用圖1 相同的實驗環境及操作語言與目前較高效的基于雙線性對的簽密方案[10-11,15-16]進行對比，實驗結果如圖2所示。

圖2 與基于雙線性對的方案執行時間對比

圖2 的實驗結果表明，對比基于雙線性對的簽密方案，無論是在簽密算法還是解簽密算法的執行時間都遠少于有雙線性配對運算的簽密方案，簽密過程中相對于時間最短的文獻[15]方案仍然快出接近13 倍的時間，解簽密過程與耗時最少的文獻[10]方案相比仍快出3 倍左右，與6.1 節中理論分析的計算效率結果一致。

同理，基于表3 將CBSC 方案與基于橢圓曲線離散對數的簽密方案[6,13]進行對比并仿真實現，實驗結果如圖3 所示。

圖3 的實驗數據表明，將CBSC 方案與基于橢圓曲線上的離散對數方案對比后，與計算效率較高的文獻[6]方案對比數據發現，解簽密過程雖然耗時相差不大，但簽密過程的耗時顯著減少。綜上可得，該方案的計算效率具有顯著提升。效率分析表明，CBSC 方案適合5G 網絡下的基礎安全保障，特別是類似于eMBB 場景下的安全需求。

圖3 與基于離散對數的方案執行時間對比

7 結束語

本文針對基于雙線性對構造的簽密方案計算開銷大的問題，利用二次剩余判定困難問題，提出了一種基于Cocks 的IBE 體制的高效簽密方案。首先，利用二次剩余問題及雅可比求值運算具體構造該簽密算法，在Cocks 基于身份的加密方案的基礎上結合二次剩余問題構造簽名，在單個邏輯步驟中實現消息的保密性與認證性，該方案適用于對短會話密鑰進行簽密；然后，在隨機預言機模型下對方案的安全性進行證明，將其安全性歸約到數論中的二次剩余判別困難問題，證明了方案滿足保密性和不可偽造性；最后，通過方案分析進行計算效率對比發現，所提方案無論是與已有的基于雙線性對還是橢圓曲線上的離散對數構造的簽密方案相比，都具有較高的計算效率。綜上，本文所提CBSC 方案在確保簽密方案具有基于身份特性的同時，實現了高安全性和高效計算。因此，CBSC 方案的高效性與安全性能為5G 網絡提供了基礎安全保障。