韓益亮，王眾

（武警工程大學(xué)密碼工程學(xué)院，陜西 西安 710086）

1 引言

公鑰密碼技術(shù)是網(wǎng)絡(luò)通信安全的核心技術(shù)，當(dāng)前常用的公鑰密碼方案基于整數(shù)分解、離散對數(shù)、橢圓曲線離散對數(shù)等困難問題。Shor[1]提出了一種可以在量子計算機上運行的算法，能夠解決整數(shù)分解、離散對數(shù)等問題，這給傳統(tǒng)公鑰密碼帶來了嚴(yán)重威脅，一旦實用化量子計算機出現(xiàn)，傳統(tǒng)公鑰密碼就不再安全。整數(shù)分解和離散對數(shù)等問題都可歸結(jié)為交換群的隱含子群問題，這類問題在量子計算機上可在多項式時間內(nèi)求解，而在經(jīng)典計算機上最好的算法仍然是指數(shù)級的。目前，一般認(rèn)為抗量子計算攻擊的密碼體制有如下幾種[2]：基于多變量的密碼體制[3]、基于格的密碼體制[4]、基于編碼的密碼體制[5]以及基于Hash 函數(shù)的密碼體制[6]等。這些密碼體制之所以能夠抵抗量子計算攻擊，是因為它們建立在NP 完全問題（NP-complete problem）之上，量子計算機相比經(jīng)典計算機對此類問題并沒有明顯優(yōu)勢[7]?；诰幋a的密碼是目前比較受關(guān)注的一種抗量子密碼，所依賴的困難問題是一般線性碼的譯碼問題，主要思路是向碼字中加入錯誤向量或根據(jù)糾錯碼的校驗矩陣計算伴隨式，在生成矩陣或校驗矩陣未知時該問題為NP 完全問題，且尚未發(fā)現(xiàn)該問題能歸結(jié)為隱含子群問題，因而可以作為抗量子公鑰算法比較好的候選方案之一。1978 年，Mceliece[8]最早利用Goppa 碼的性質(zhì)提出了第一個編碼密碼方案，通常被稱為McEliece 方案。1986年，Niederreiter[9]提出了McEliece 方案的對偶體制，即Niederreiter 方案。上述2 種方案在安全性上完全等價，但是Niederreiter 方案相比McEliece 方案具有更高的傳信率。2001 年，Courtois 等[10]提出了基于編碼密碼的簽名方案——CFS 方案。2013 年，Mathew 等[11]通過密鑰構(gòu)造的改變使CFS 簽名方案的密鑰量減少，提高了簽名方案的使用效率。為了解決編碼密碼密鑰量大的問題，用其他碼字來代替Goppa 碼已經(jīng)成為一種趨勢，但是這會對方案的安全造成影響，這種影響已經(jīng)出現(xiàn)在基于準(zhǔn)循環(huán)（QC,quasi-cyclic）碼[12]、低密度奇偶校驗（LDPC,low density parity check）碼[13]、準(zhǔn)循環(huán)低密度奇偶校驗（QC-LDPC,quasi-cyclic low-density parity-check）碼[14]、卷積碼[15]等碼字的第一代McEliece 變體方案中。還有一些使用QC-LDPC 碼[16]、準(zhǔn)循環(huán)中密度奇偶校驗（QC-MDPC,quasi-cyclic medium-density parity-check）碼[17]等碼字的變體方案，能夠在不損壞安全性的前提下較好地達到密鑰壓縮的目的，例如2017 年Deneuville 等[18]提出的Ouroboros 密鑰交換協(xié)議、2018 年Baldi 等[19]提出的LEDAkem 密鑰封裝機制等。2018 年，Eaton等[20]還提出通過多次加密的方式使編碼密碼方案的安全性達到IND-CCA2（indistinguishability under adaptive chosen-ciphertext attack）的安全級別。

另一方面，保密和認(rèn)證是信息安全的2 個主要目標(biāo)，在公鑰密碼領(lǐng)域，通常用加密技術(shù)來實現(xiàn)保密，用數(shù)字簽名來實現(xiàn)認(rèn)證。當(dāng)需要同時滿足保密和認(rèn)證的要求時，通常的做法是先“簽名”再“加密”或者先“加密”再“簽名”，但這種方法效率不高，同時也無法確保安全性。Zheng[21]提出了在一個邏輯步驟內(nèi)同時實現(xiàn)加密與簽名功能的密碼技術(shù)，能夠提高效率和安全性。當(dāng)系統(tǒng)中同時存在多種安全需求時，韓益亮等[22]提出的廣義簽密能夠在簽名方案、加密方案以及簽密方案三者之間自適應(yīng)地轉(zhuǎn)換，能夠單獨或者同時提供保密和認(rèn)證功能，更有效地節(jié)省系統(tǒng)資源。公鑰密碼是簽密技術(shù)的基礎(chǔ)，但是公鑰密碼存在一類密鑰托管問題。2003 年，Al-Riyami 等[23]首次提出無證書密碼體制，該體制的重點為密鑰的管理，其將用戶的私鑰分成兩部分：一部分由密鑰生成中心（KGC,key generator center）生成，另一部分則由用戶生成，這樣就緩解了密鑰托管問題。2008 年，Barbosa 等[24]將簽密與無證書密碼體制相結(jié)合，使無證書密碼體制可以在一個邏輯步驟內(nèi)完成加密與簽名操作。同年，Selvi 等[25]將無證書簽密方案推廣到多接收者模型中。目前，已經(jīng)提出的各種簽密方案大多基于整數(shù)分解、離散對數(shù)、橢圓曲線離散對數(shù)等困難問題，也不能抵抗量子計算攻擊。

本文通過對編碼密碼進行研究，設(shè)計了一個多接收方的廣義簽密方案。首先采用QC-LDPC 碼借鑒文獻[20]中密鑰封裝機制中的加密方法，提出一種能夠滿足IND-CCA2 的加密方案，在加密方案的基礎(chǔ)上設(shè)計了一個多接收方的簽密方案；然后進行改進得到一個基于編碼密碼的廣義簽密方案。

2 相關(guān)知識

2.1 校驗子譯碼問題

給定一個(n,k)維的線性碼，已知該碼的最小漢明距離為d，其校驗矩陣為，糾錯能力為t，滿足d=2t+1。給定向量，尋找一個錯誤向量，使其漢明重量滿足wt(e)≤t，且與向量v以及矩陣H滿足方程v=eHT，尋找錯誤向量e的問題即為校驗子譯碼問題（SD,syndrome decoding problem）。

校驗子譯碼問題已被證明是NP 完全問題，尚未發(fā)現(xiàn)該問題能歸結(jié)為隱含子群問題。該問題是基于編碼的密碼所依賴的困難問題。

2.2 Mceliece 方案

Mceliece[8]于1978 年提出一個基于Goppa 碼的密碼方案，該方案是第一個基于編碼的加密方案。目前，采用Goppa 碼的McEliece 方案仍是較為安全的方案。下面將具體介紹該方案的參數(shù)生成以及加解密過程。

參數(shù)生成。選擇一個(n,k)維的線性碼，該碼的最小漢明距離為d，其生成矩陣為，能糾錯重量為t的信息，滿足d=2t+1。選擇一個k×k階的二元隨機非奇異矩陣M和一個n×n階的二元隨機置換矩陣P。那么，該方案的公鑰為重量t以及矩陣Gpub=MGP，私鑰為矩陣G、M、P以及譯碼算法β。

解密過程。首先對密文c右乘置換矩陣P的逆，即cP-1=mMG+eP-1。對cP-1進行譯碼操作消除錯誤向量eP-1，進而得到右乘私鑰矩陣M的逆即可得明文m。

2.3 CFS 簽名方案

基于McEliece 方案，2001 年Courtois 等[10]提出CFS 簽名方案，該方案是目前為數(shù)不多的安全的編碼簽名方案。CFS 簽名方案的初始化、簽名與驗證過程如下。

初始化過程。取C是有限域GFq上線性(n,k,d)Goppa 碼，n=2a，d=2t+1，k=n-at。(n-k)×n階矩陣H為二元(n,k,d)Goppa 碼的校驗矩陣，隨機選取GF(2)上的可逆矩陣S，其階為(n-k)×(n-k)，再選取置換矩陣T，其階為n×n。選擇一個散列函數(shù)。Goppa 碼的快速譯碼算法為βHt()，σ為待簽名消息。將公開，將(S,T,H,βHt())保密。

簽名過程如下。

1)計算σ的散列值m，m=h(σ)。

2)在集合{0,1,2,…} 中選擇一個i，計算mi=S-h1(m||i)，找到一個最小的i0使βHt(mi)存在，則mi0=S-1h(m||i0)。

3)令v=βHt(mi0)，簽名即為 (i0||vT)。

驗證過程如下。

1)計算a=h(h(σ)||i0)，。

2)如果a=b，則簽名成功；否則失敗。

2.4 多接收方簽密與廣義簽密

根據(jù)文獻[26]，多接收方簽密方案由以下步驟組成：系統(tǒng)參數(shù)生成、部分密鑰生成、用戶密鑰生成、簽密過程和解簽密過程。

1)系統(tǒng)參數(shù)生成。由密鑰生成中心（KGC）進行，輸入一個秘密參數(shù)φ，進而返回系統(tǒng)參數(shù)τ。

2)部分密鑰生成。由KGC 進行，KGC 首先產(chǎn)生系統(tǒng)密鑰λ，然后輸入λ和τ，產(chǎn)生部分公鑰P和部分私鑰S。

3)用戶密鑰生成。輸入公共參數(shù)τ、部分公鑰P、部分私鑰S以及用戶的身份信息IDU，用戶U執(zhí)行該算法產(chǎn)生自己的公鑰PU和私鑰SU。

4)簽密過程。由發(fā)送方A執(zhí)行，輸入公共參數(shù)τ、明文m、A的身份信息IDA、私鑰SA以及接收者組L的公鑰信息，最終輸出簽密文c。

5)解簽密過程。由接收者B執(zhí)行，輸入公共參數(shù)τ、簽密文c、A的身份信息IDA、A的公鑰PA，以及接收者B的身份信息IDB與私鑰SB，若驗證通過則最終解密得到明文m，否則解簽密失敗。

多接收方的廣義簽密與多接收方的簽密過程大致類似，不同之處在于需要再定義一個區(qū)分函數(shù)f(x)來實現(xiàn)簽名方案、加密方案以及簽密方案這三者之間的轉(zhuǎn)換。區(qū)分函數(shù)往往通過用戶的公鑰進行判斷，進而實現(xiàn)轉(zhuǎn)換的功能，具體來講即當(dāng)發(fā)送方A與接收者B均有公私鑰時為簽密方案，當(dāng)發(fā)送方A沒有公私鑰而接收者B擁有時為加密方案，當(dāng)接收者B沒有公私鑰而發(fā)送方A擁有時為簽名方案，當(dāng)收發(fā)雙方均無公私鑰時為普通的傳信過程。

2.5 多接收方簽密的安全模型

參考文獻[26-27]可以得到適用于本文多接收方簽密方案的安全模型。從機密性與不可偽造性入手，針對多接收方的簽密方案，存在以下2 種類型的攻擊者：可以替換用戶公鑰信息但是不能獲得KGC 的主密鑰，用攻擊者α1表示；可以獲取KGC的主密鑰但是不能替換其他用戶公鑰的攻擊者，用α2表示。

定義1機密性1。在攻擊游戲1 中，沒有一個攻擊者α能夠在多項式時間內(nèi)以不可忽略的優(yōu)勢贏得IND-CCA2-1 游戲，則說明該基于編碼的多接收方簽密方案滿足適應(yīng)性選擇密文攻擊下的不可區(qū)分性。

攻擊者在IND-CCA2-1 游戲中需滿足以下3個限制：不能對挑戰(zhàn)密文進行解簽密詢問，不能對挑戰(zhàn)者的私鑰進行詢問，不能對系統(tǒng)的主密鑰進行詢問。

定義2機密性2。在攻擊游戲2 中，沒有一個攻擊者α能夠在多項式時間內(nèi)以不可忽略的優(yōu)勢贏得IND-CCA2-2 游戲，則說明該基于編碼的多接收方簽密方案滿足適應(yīng)性選擇密文攻擊下的不可區(qū)分性。

攻擊者在IND-CCA2-2 游戲中需要滿足以下3 個限制：不能對挑戰(zhàn)密文進行解簽密詢問，不能對挑戰(zhàn)者的私鑰進行詢問，不能對系統(tǒng)的主密鑰進行替換。

定義3不可偽造性1。在攻擊游戲1 中，沒有一個攻擊者α能夠在多項式時間內(nèi)以不可忽略的優(yōu)勢贏得EUF-CMA（existential unforgeability against adaptive chosen messages attack）-1 游戲，則說明該基于編碼的多接收方簽密方案滿足適應(yīng)性選擇消息攻擊下的不可偽造性。

攻擊者在EUF-CMA-1 游戲中需滿足以下2 個限制：不能對挑戰(zhàn)者的私鑰進行詢問，不能對系統(tǒng)的主密鑰進行詢問。

定義4不可偽造性2。在攻擊游戲2 中，沒有一個攻擊者α能夠在多項式時間內(nèi)以不可忽略的優(yōu)勢贏得EUF-CMA-2 游戲，則說明該基于編碼的多接收方簽密方案滿足適應(yīng)性選擇消息攻擊下的不可偽造性。

攻擊者在EUF-CMA-2 游戲中需滿足以下2 個限制：不能對挑戰(zhàn)者的私鑰進行詢問，不能對系統(tǒng)的主密鑰進行替換。

3 方案描述

3.1 多接收方的通信模型

具有多個接收方的一對多通信是當(dāng)前最普遍的通信模式之一，如網(wǎng)絡(luò)廣播、多播等。在無線局域、物聯(lián)網(wǎng)等網(wǎng)絡(luò)環(huán)境下，也存在著許多一對多通信的方式。這種具有多個接收方的一對多通信由于其自身的開放性、智能化以及計算環(huán)境的復(fù)雜性帶來了許多安全問題，最明顯的是用戶隱私的安全問題[28]。多接收方通信中的身份認(rèn)證問題同樣重要，通過有效的消息認(rèn)證、設(shè)備認(rèn)證，才能夠防止冒名頂替和否認(rèn)行為[29]。計算機系統(tǒng)需要根據(jù)不同用戶的性質(zhì)來提供不同的訪問控制策略以有效地對用戶隱私、數(shù)據(jù)安全以及身份進行保護。圖1 為多接收方通信模型。

1)當(dāng)發(fā)送方無密鑰以及接收用戶組存在無密鑰成員時，發(fā)送方將不能對待簽密消息m進行簽名以及加密的操作，相當(dāng)于直接把消息發(fā)送給接收用戶組。由于對明文進行了處理，使合法的系統(tǒng)用戶（設(shè)備）才能得到明文m。這種情況適用于普通用戶（設(shè)備），即沒有自己公私鑰的用戶（設(shè)備）與普通的用戶或者設(shè)備組之間進行密級較低的通信，傳輸?shù)男畔τ谙到y(tǒng)用戶（設(shè)備）是公開的，而對于非系統(tǒng)用戶（設(shè)備）是加密的。

2)當(dāng)發(fā)送方有密鑰而接收用戶組存在無密鑰成員時，相當(dāng)于純簽名的過程。當(dāng)接收用戶組收到該信息后，可以利用系統(tǒng)私鑰來解密得到明文m，再對簽名s驗證，確保信息來自對應(yīng)的發(fā)送方且明文未被篡改。這種情況適用于發(fā)送方是高級的用戶、計算機系統(tǒng)或者設(shè)備，而接收組是普通的用戶或者設(shè)備，進而防止對高級用戶（設(shè)備）所傳輸?shù)男畔⑦M行篡改，以及對其冒名頂替，保障了可認(rèn)證性。

圖1 多接收方通信模型

3)當(dāng)發(fā)送方?jīng)]有密鑰而接收用戶組中的成員均有密鑰時，相當(dāng)于純加密的過程。接收組收到該信息后利用各自的私鑰以及系統(tǒng)私鑰進行解密操作即可得到明文消息m。這種情況適用于發(fā)送方為普通用戶或者計算機系統(tǒng)，其所發(fā)出的消息只想讓指定的接收組收到，且接收方為高級的用戶或者設(shè)備。這就保障了在多接收方的開放環(huán)境下數(shù)據(jù)傳輸?shù)臋C密性。

4)當(dāng)接收用戶組中的成員、發(fā)送方都有各自密鑰時，該方案即為一個簽密方案。只有擁有相應(yīng)私鑰的接收者可以對信息進行解簽密。解簽密的過程是接收組中的成員運用自己的私鑰以及系統(tǒng)私鑰進行解密得到明文，再利用發(fā)送方的公鑰通過m對簽名進行驗證。這種情況適用于收發(fā)雙方均為高級的用戶、設(shè)備，進行密級較高的保密通信。

綜上分析可知，當(dāng)一個系統(tǒng)用戶或者設(shè)備給其他多個接收者發(fā)送信息時，可以根據(jù)接收組成員的公私鑰的存在情況自適應(yīng)地實現(xiàn)多接收方的簽密、加密與簽名的轉(zhuǎn)換。若接收組成員中有一個沒有公鑰即為簽名過程或者是普通傳輸過程，若接收組成員中都有公鑰即為簽密或者加密的傳輸過程。本文所提廣義簽密方案需要實現(xiàn)不同安全級別的訪問控制，而非系統(tǒng)用戶則得不到任何信息。

3.2 多次加密的McEliece 方案

根據(jù)文獻[20]，一般編碼密碼方案的安全性達不到IND-CCA2 的安全級別，但文獻[20]給出了一種加密方法使編碼密碼的安全性能夠達到IND-CCA2 的安全級別。該加密方法是將待加密信息運用編碼加密的方式進行多次加密產(chǎn)生多個密文，對這些密文進行解密，只有當(dāng)這些密文全部解密失敗時返回錯誤值⊥，這樣可以有效避免譯碼錯誤對安全性的影響。本節(jié)多次加密的McEliece 方案采用QC-LDPC 碼，并以這種多次加密的方式來構(gòu)造方案，以增加方案的安全性。

參數(shù)及密鑰生成。取Ω是有限域GFq上 (n,k,d)階的QC-LDPC 碼，n=2a，d=2t+1，k=n-at。其生成矩陣為，隨機選取GF(2)上的可逆矩陣S，其階為k×k；再選取置換矩陣P，其階為n×n。計算公鑰為=SGP，私鑰即為矩陣(S,G,P)以及譯碼算法βt()。另設(shè)一錯誤向量生成函數(shù)以及二進制數(shù)字的循環(huán)左移函數(shù)。

根據(jù)文獻[20]密鑰封裝中的加密方式，基于QC-LDPC 碼構(gòu)造多次加密的McEliece 方案。

加密過程中，每加密一次產(chǎn)生一個新的錯誤向量ei來加密。解密過程中，需要對所有密文進行解密操作，譯碼成功則保留下來，所有密文譯碼不成功則解密失敗，最終得到明文，根據(jù)明文m以及公鑰并利用之前的加密算法進行加密操作，得到一組密文來與原密文組C進行比較，每組都相同則解密成功，可以得到明文m。這種加密方法大大降低了譯碼錯誤所帶來的安全性影響，這也是本文構(gòu)造多次加密的McEliece 方案最主要的原因。

3.3 多接收方簽密方案

本節(jié)將依托3.2 節(jié)中的多次加密的McEliece 方案以及CFS 簽名方案并參考文獻[26]，構(gòu)造一個具有抗量子計算能力的多接收方簽密方案。

1)系統(tǒng)參數(shù)建立

取Ω是有限域GFq上 (n,k,d)階的QC-LDPC碼，n=2a，d=2t+1，k=n-at。其生成矩陣為，校驗矩陣為，譯碼算法為βt()。設(shè)置 2 個安全函數(shù)h1與h2，h1:{0,1}*→{0,1}n-k，h2:{0,1}*→{0,1}k。如3.2 節(jié)中方案的參數(shù)及密鑰生成過程，再設(shè)置錯誤向量生成函數(shù)X:{0,1}*→{e|e∈,wt(e)≤t} 以及二進制數(shù)字的循環(huán)左移函數(shù)PRF。公開(n,k,t,h1,h2)。

2)部分密鑰生成

①KGC 根據(jù)QC-LDPC 碼Ω隨機選擇GF(2)上的k×k階可逆矩陣S，以及(n-k)×(n-k)階可逆矩陣M，再選取n×n階置換矩陣P。KGC 的系統(tǒng)公鑰為Gpub=SGP和Hpub=MHP，Gpub與加密有關(guān)，Hpub與簽名有關(guān)。系統(tǒng)私鑰為(S,G,P,M,βt())，這里不再將QC-LDPC 碼的校驗矩陣H寫入私鑰組，因為根據(jù)碼的性質(zhì)，有了生成矩陣便可根據(jù)GHT=0求得校驗矩陣。

② KGC 根據(jù)QC-LDPC 碼Ω隨機選擇GF(2)上的k×k階可逆矩陣S0，以及(n-k)×(n-k)階可逆矩陣M0，再選取n×n階置換矩陣P0。計算G0=S0GpubP0，H0=M0HpubP0，則部分公鑰為(G0,H0)，部分私鑰為(S0S,G,PP0,M0M,βt())。KGC 通過秘密信道將部分私鑰傳遞給合法用戶，并公開自己的系統(tǒng)公鑰。

3)用戶密鑰生成

①用戶U取得KGC 的部分公鑰和部分私鑰，并隨機選擇GF(2)上的k×k階可逆矩陣SU，以及(n-k)×(n-k)階可逆矩陣MU，再選取n×n階置換矩陣PU。計算GU=SUG0PU，HU=MUH0PU，則部分公鑰為 (GU,HU)，部分私鑰為(SUS0S,G,PP0PU,MUM0M,βt())。F0代表采用系統(tǒng)公鑰加密,Fi代表采用用戶i的公鑰加密。

② 用戶U將公鑰FU（FU即為(GU,HU)）傳回KGC。

4)簽密

身份為IDA的用戶A，將傳輸給用戶組L={ID1,ID2,…,ID?}。首先向KGC 查詢得到用戶組L的公鑰信息，進行如下操作。

②Y=h1(m||IDA||x)。

③在集合{0,1,…} 中選擇一個a，并計算，找到一個最小的a0使βt(Ya)存在，則

④令v=βt(Ya0)，s=(a0||vPA)。

⑤對于IDi，i=1,2,…,?，計算qi=h2(IDi)。

⑥Wi=Fi(m⊕r⊕qi)。

⑦對于用戶組L，計算=F0(L)。

⑧ 生成簽密文σ=(s,W1,W2,…,W?,,x)。

5)解簽密

用戶IDi，i=1,2,…,?，收到σ=(s,W1,W2,…,W?,,x)后進行如下計算。

正確性分析。當(dāng)簽密與解簽密過程正確時則說明簽密方案正確。用戶IDi(i=1,2,…,?)收到σ=(s,W1,W2,…,W?,,x)后，首先利用系統(tǒng)私鑰提取出自己的那一部分密文，再利用系統(tǒng)私鑰求解出隨機數(shù)，然后就可以利用自己的私鑰來求解密文，即。由于已知、c和qi，因此可以求出明文。擁有了明文后，可運用發(fā)送方A的公鑰進行下一步的驗證，根據(jù)CFS簽名方案，當(dāng)且僅當(dāng)時，才可得到正確的明文。

3.4 基于編碼密碼的多接收方廣義簽密方案

本節(jié)基于編碼密碼的多接收方廣義簽密方案仍然是依托3.2 節(jié)中多次加密的McEliece 方案以及CFS 簽名方案，在3.3 節(jié)基于編碼密碼的多接收方簽密方案的基礎(chǔ)上加以改進而構(gòu)造的，因此其參數(shù)、部分密鑰以及用戶密鑰的生成都與3.3 節(jié)中基本相同，只是在參數(shù)生成時多構(gòu)造一個安全函數(shù)h3:{0,1}*→{0,1}k。

3.4.1 區(qū)分函數(shù)構(gòu)造以及簽密與解簽密過程

1)定義區(qū)分函數(shù)f(x)

區(qū)分函數(shù)實現(xiàn)簽名、加密或簽密功能三者之間轉(zhuǎn)換，往往以用戶是否存在公鑰來進行判斷。當(dāng)用戶的公鑰GU=?時即為不存在公私鑰，則f(x)=0，此處0 代表k維零向量；當(dāng)用戶的公鑰GU≠?時即存在公私鑰時，則f(x)=1，此處1代表k維單位向量。因此區(qū)分函數(shù)可表示如下。

2)簽密

身份為IDA的用戶A，將m∈F2k傳輸給用戶組L={ID1,ID2,…,ID?}。首先向KGC 查詢得到用戶組L的公鑰信息，進行如下操作。

3)解簽密

判斷η與ξ是否相等，相等則驗證通過獲得正確明文，否則接收失敗。

3.4.2 正確性分析

當(dāng)用戶IDi(i=1,2,…,?)收到σ=(s,W1,W2,…,W?,c1,c2,…,c?,,x)后，最終得到的密文組有以下4種形式：(s,Wi,ci,x)、(?,Wi,ci,x)、(s,m⊕h3(r),ri,x)、(?,m⊕h3(r),ri,x)。

當(dāng)收發(fā)雙方都擁有公私鑰時，密文組為(s,Wi,ci,x)。接收者利用自己的私鑰解密得到隨機數(shù)，利用系統(tǒng)私鑰進行解密得到隨機數(shù)，進而可以利用求解得出明文，將該明文利用CFS 簽名方案中的驗證方法進行驗證：等式成立則說明獲得了正確的信息。

當(dāng)發(fā)送方?jīng)]有公私鑰而接收方有時，密文組為(?,Wi,ci,x)，接收方收到密文組后，利用自己的私鑰進行解密得到隨機數(shù)，利用系統(tǒng)私鑰進行解密得到隨機數(shù)，再利用求解得出明文。

當(dāng)發(fā)送方擁有公私鑰而接收方不具有時即為簽名方案，不同于普通簽名，只有系統(tǒng)中的合法用戶才可以得到正確的信息，此時的密文組為(s,m⊕h3(r),ri,x)，接收方收到密文后，可以直接獲取隨機數(shù)，再利用系統(tǒng)私鑰進行解密得到隨機數(shù)，進而可以利用求解得出明文，最后利用與第一種情況相同的方法進行驗證即可。

當(dāng)收發(fā)雙方均無公私鑰時，相對于直接傳輸明文，發(fā)送方只對明文用系統(tǒng)公鑰進行了加密，當(dāng)接收方為系統(tǒng)用戶時，便可利用系統(tǒng)私鑰進行解密最終獲得明文。

3.5 廣義簽密方案自適應(yīng)性

根據(jù)多接收方廣義簽密的模型[30]并結(jié)合上述方案的構(gòu)造可以看出，當(dāng)發(fā)送方向某一用戶組發(fā)送信息時，根據(jù)發(fā)送方以及接收用戶組的密鑰擁有情況存在以下4 種情況。

1)發(fā)送方以及接收用戶組均無密鑰。根據(jù)3.4節(jié)中的簽密過程可以看出，簽密的步驟②即簽名過程將不再進行，而步驟⑤所得的Wi即為m⊕h3(r)，說明合法的系統(tǒng)用戶作為接收方可以直接得到明文。這種情況下，合法的系統(tǒng)用戶均無自己的密鑰，也即普通系統(tǒng)設(shè)備與用戶之間進行的一般的通信過程。這種過程與3.1 節(jié)所設(shè)計的多接收方通信模型的第一種情況相適應(yīng)。

2)發(fā)送方有密鑰，而接收用戶組中存在沒有密鑰的成員。此時，根據(jù)3.4 節(jié)中的簽密過程可以看出，簽密的步驟②即簽名過程將進行，但是由于接收用戶組中存在無密鑰成員，因此κ=f(G1)f(G2)…f(G?-1)f(G?)=0，步驟⑤所得的Wi即為m⊕h3(r)。說明簽名功能得到實現(xiàn)但未進行加密，合法的系統(tǒng)接收用戶均可以對發(fā)送方的簽名進行驗證，并得到明文。這種安排是根據(jù)文獻[30]中提到的安全性，防止發(fā)送方向用戶組發(fā)送信息時，存在有的用戶得到加密后的信息，而有的用戶得到未加密信息，造成明密文對比，使攻擊者可以進行分析而造成漏洞。這種情況與3.1 節(jié)所設(shè)計的通信模型的第二種情況相適應(yīng)，即高級的系統(tǒng)用戶或者設(shè)備向存在普通用戶或設(shè)備的接收用戶、設(shè)備組傳輸信息，接收組可以對信息來源以及信息是否被篡改進行確認(rèn)。

3)發(fā)送方?jīng)]有密鑰，而接收用戶組中的成員均有密鑰。根據(jù)3.4 節(jié)中對簽密過程的描述可以看出，簽密的步驟②即簽名的過程將跳過，但是由于接收用戶組成員均有密鑰，因此Wi=m⊕h3(r)⊕h2(ri⊕qi)，只有接收用戶組中的第i個成員使用自己的密鑰，才可以對Wi=m⊕h3(r)⊕h2(ri⊕qi)進行正確解密，再利用系統(tǒng)密鑰處理得到明文。這種情況與3.1 節(jié)中通信模型的第三種情況相適應(yīng)，普通系統(tǒng)用戶或者設(shè)備向高級的接收用戶、設(shè)備組發(fā)送信息，只有該接收用戶、設(shè)備組能夠?qū)π畔⑦M行正確解密，得到對應(yīng)的明文。

4)發(fā)送方以及接收用戶組均有密鑰。3.4 節(jié)中的全部過程將進行，即簽密功能的實現(xiàn)。這種情況與3.1 節(jié)通信模型的第四種情況相適應(yīng)，高級的系統(tǒng)用戶或設(shè)備與另一組高級的用戶、設(shè)備進行高安全級別的通信。

綜上所述，3.4 節(jié)所設(shè)計的多接收方廣義簽密方案可以與3.1 節(jié)所設(shè)計的多接收方通信模型相適應(yīng)。

4 安全性分析

本文多接收方的簽密以及廣義簽密方案是一脈相承的，因此第4 節(jié)的安全性分析主要是從廣義簽密方案出發(fā)，對具有簽密功能的廣義簽密方案入手，分析方案的機密性以及不可偽造性，證明過程在文獻[26-27,31]的基礎(chǔ)上進行。

4.1 機密性

1)游戲類型1

定理1 在隨機預(yù)言機模型下，假設(shè)存在一個IND-CCA2 的攻擊者α1，能夠以優(yōu)勢贏得如下定義的游戲（定義1 中的游戲），那么就存在一個算法β，它解決SD 問題的優(yōu)勢ε如式(2)所示，其中算法β作為攻擊者α1在游戲中的挑戰(zhàn)者，而α1則作為β的子程序。

證明給定一個SD 問題實例x=F(r)，挑戰(zhàn)者成功求解出r即可。

qSC、qDSC、qh1、qh2、qh3分別代表攻擊者α1所能進行的簽密詢問、解簽密詢問，以及對隨機預(yù)言機h1、h2以及h3的詢問的最大次數(shù)，qS、qP、qR分別代表私鑰詢問、公鑰詢問以及公鑰替換詢問的最大次數(shù)。為了方便回答詢問，并設(shè)立2 個詢問列表List1、List2，來對以上詢問進行記錄。

①游戲初始化。β根據(jù)QC-LDPC 碼Ω隨機選擇 GF(2)上的k×k階可逆矩陣S和(n-k)×(n-k)可逆矩陣M，選取n×n階置換矩陣P。KGC的系統(tǒng)公鑰為Gpub=SGP和Hpub=MGP，系統(tǒng)私鑰為(S,G,P,M,βt())，根據(jù)QC-LDPC 碼Ω隨機選擇GF(2)上的k×k階可逆矩陣S0和(n-k)×(n-k)階可逆矩陣M0，選取n×n階置換矩陣P0。計算G0=S0GpubP0，H0=M0HpubP0，則部分公鑰為(G0,H0)，部分私鑰為(S0S,G,PP0,M0M,βt())。β將公共參數(shù)(n,k,t,h1,h2,h3)發(fā)送給攻擊者α1，并保留自己的系統(tǒng)密鑰。攻擊者α1給出目標(biāo)用戶組

② 詢問階段。攻擊者α1可以向挑戰(zhàn)者β進行如下詢問。

h1詢問。輸入元組，查看表List1，如果存在相應(yīng)記錄Yi則返回該記錄；若不存在則隨機選取一個Yi，將其以及用戶對信息m簽密產(chǎn)生的密文與簽名存入表List1，并返回Yi。

2h詢問。有以下幾種情況。輸入進行詢問時，對表List2進行查詢是否有相應(yīng)記錄qi，存在則返回，不存在則隨機選擇一個qi存入List2，并將用戶的公鑰、私鑰以及一個記錄用戶公鑰是否被替換的標(biāo)識?（?=0表示未被替換，?=1表示被替換）一同記錄下來，返回qi。輸入(ri,qi)進行詢問，同樣先對表 List2進行查詢是否有相應(yīng)記錄，存在則返回，該記錄存在的概率很小，為，不存在則隨機選擇一個記錄在List2，并將用戶的公鑰、私鑰以及一個記錄用戶公鑰是否被替換的標(biāo)識?一同記錄下來，返回

h3詢問。輸入隨機數(shù)r詢問時，返回值如果存在相應(yīng)記錄，則返回，但這種概率存在的可能極小，為。因為是對隨機數(shù)查詢，所以查詢過的概率很小。

私鑰詢問。攻擊者輸入用戶IDi，若該用戶存在于目標(biāo)用戶組中，則挑戰(zhàn)者β丟棄該詢問；否則，β查找List2。首先查看該用戶的替換標(biāo)識?檢查其公鑰是否被替換，若未被替換，則返回該用戶私鑰(SiS0S,G,PP0Pi,MiM0M,βt())；若被替換，則β向α1詢問用戶IDi的私鑰參數(shù)。最終返回攻擊者(SiS0S,G,PP0Pi,MiM0M,βt())。

公鑰詢問。攻擊者輸入用戶IDi，首先查詢List2中是否有相應(yīng)記錄，存在則返回Fi；否則選擇隨機矩陣(Si,Pi,Mi)，并進行相應(yīng)計算產(chǎn)生對應(yīng)公鑰Fi。把該值更新記錄到表List2中并返回。

公鑰替換詢問。輸入二元組(IDi,)進行詢問，首先查詢List2，若存在記錄(IDi,Fi)，則使用替換Fi，并更新標(biāo)識?；若沒有對應(yīng)公鑰，則對IDi進行公鑰詢問，得到新公鑰后，再進行替換詢問。

簽密詢問。輸入元組(m,IDs,L={IDR1,IDR2,…,IDR?})，若IDs存在于身份集合L中，或L中有元素存在于目標(biāo)身份集合L*中，β丟棄此次詢問；若IDs不在目標(biāo)身份集合L*中，則可以知道發(fā)送方的私鑰，并在List1、List2中記錄。進行本文的簽密算法，得到相應(yīng)的簽密文σ=(s,W1,W2,…,W?,c1,c2,…,c?,,x)。如果在目標(biāo)身份集合中，則挑戰(zhàn)者無法獲知發(fā)送方的私鑰，可通過以下方法來進行簽密：β詢問List2，得到IDs的公私鑰，選擇隨機數(shù)r用公鑰加密得到FS(r)→x，再進行h1詢問以及簽名算法得到簽名s。β隨機選擇qi，對List2進行查詢得到記錄(IDRi,?Ri)，首先查看替換標(biāo)識，檢查公鑰是否被替換，未被替換則進行h2詢問以及加密算法，得到密文Wi與用戶組標(biāo)識；否則進行公鑰替換詢問與公鑰詢問，并將該記錄存入表List2，若表List2中已經(jīng)存在了相應(yīng)記錄則說明模擬簽密失敗。由β返回給攻擊者α1簽密文。模擬簽密失敗的概率為

解簽密詢問。輸入簽密文σ，發(fā)送方以及接收者身份IDS、IDR。首先提取出對應(yīng)接收者的簽密文(s,Wi,,ci,x)，若該接收者屬于目標(biāo)用戶組，則β知道該接收者的私鑰，便可進行解密算法求出明文；否則需要查看List1中是否有該簽名s以及密文iW的記錄，若沒有相應(yīng)記錄則β拒絕該簽密文。再看表List2，若沒有關(guān)于接收者IDR的用戶標(biāo)識、公私鑰、替換標(biāo)識的記錄，β也拒絕該簽密文。當(dāng)對密文解密時，運用系統(tǒng)私鑰以及接收者私鑰進行解密得到明文m，利用簽名驗證算法與該信息m對簽名s進行驗證，當(dāng)且僅當(dāng)簽名驗證成功時，可獲得正確明文m，否則解簽密失敗。一個有效的密文被拒絕的概率為。

③挑戰(zhàn)階段。攻擊者α1提供2 個k維的消息1m、m2以及發(fā)送方IDS，且發(fā)送方不在目標(biāo)用戶身份集合L*中，向β進行詢問。β選擇一個消息mb，其中b∈{0,1}，并發(fā)送給目標(biāo)用戶組。β進行如下操作進而利用CFS 算法產(chǎn)生簽名s*。產(chǎn)生簽名后，由β產(chǎn)生相應(yīng)的密文，具體方法如下：由β進行操作，得到密文，最終的簽密文為

④詢問階段。攻擊者α1仍可進行如階段②的詢問，但是不能為接收者向挑戰(zhàn)密文σ*進行詢問。

⑤猜測階段。α1輸出1 bit作為猜測。如上所述，若α1猜測成功，那么必須通過h1詢問得到密文，β在List1中隨機選擇一個記錄且包含正確簽名、密文的概率為。最后將β輸出的r,ri作為SD 問題的解。

根據(jù)以上分析，β成功即攻擊者α1輸出正確比特的概率需要考慮以下幾個因素。首先設(shè)攻擊者α1成功這件事為E，其概率為。設(shè)E1表示挑戰(zhàn)者對目標(biāo)用戶組中的私鑰進行詢問，E2表示發(fā)送方以及存在一個接收者屬于目標(biāo)用戶組，若這2 個事件發(fā)生，β自動放棄此次詢問；E3表示挑戰(zhàn)者β在進行h2詢問時，List2中的相應(yīng)記錄出現(xiàn)了碰撞情況，則簽密模擬失敗，其概率為。E4表示一個有效簽名被拒絕，其概率為。E5表示β在表List1中隨機選擇一個記錄且包含了正確元素，其概率為。所以概率為Pr[E ∩ E1∩E2∩E3∩ E4∩E5]。β成功解決SD 問題的優(yōu)勢ε為

定理1 證畢。

2)游戲類型2

定理2在隨機預(yù)言機模型下，假定存在一個IND-CCA2 的攻擊者α2，它能夠以優(yōu)勢贏得定義2 中的游戲，那么就存在一個算法β，它解決SD 問題的優(yōu)勢ε如式(3)所示，其中算法β作為攻擊者α2在游戲中的挑戰(zhàn)者，而α2則作為β的子程序。

證明在游戲類型2 中，不同于游戲類型1，攻擊者α2可以獲得系統(tǒng)主密鑰信息，但是不能對用戶的公鑰進行替換，對于定理2 的證明與定理1 的證明類似，易得定理2 成立。證畢。

4.2 不可偽造性

1)游戲類型1

定理3在隨機預(yù)言機模型下，假設(shè)存在一個EUF-CMA 的攻擊者α1，它能夠以優(yōu)勢贏得如下定義的游戲（定義3 中的游戲），那么就存在一個算法β，它解決SD 問題的優(yōu)勢υ如式(4)所示，其中算法β作為攻擊者α1在游戲中的挑戰(zhàn)者，而α1則作為β的子程序。

證明給定一個編碼密碼中的問題實例(HS=MSH0PS,H0)，β需要求出MS,PS。

①游戲初始化。同4.1 節(jié)中游戲類型1 中的①。

②詢問階段。與4.1 節(jié)中游戲類型1 中的②相似，不同之處在于最后的解簽密詢問換為了驗證詢問，具體詢問過程如下。輸入簽密文σ、發(fā)送方身份IDS、接收者身份IDR。首先提取出對應(yīng)接收者的簽密文，若該接收者屬于目標(biāo)用戶組，則β知道該接收者的私鑰，可以進行解密算法求出明文，否則需要查看List1中是否有該簽名s以及用戶組的記錄，若沒有相應(yīng)記錄則β拒絕該簽密文。若List2中沒有關(guān)于接收者IDR的用戶標(biāo)識、公私鑰、替換標(biāo)識的記錄，β也拒絕該簽密文。當(dāng)對密文解密時，運用系統(tǒng)私鑰以及接收者私鑰進行解密得到明文m，利用簽名驗證算法與該信息m對簽名s進行驗證。一個有效的密文被拒絕的概率為。

③偽造階段。攻擊者α1輸出偽造的簽密文，其中發(fā)送方IDS是屬于目標(biāo)身份用戶組L*的，接收者IDRi中至少有一個是屬于L*的。

通過上述的分析可知，若攻擊者α1偽造簽密文成功，需要通過h2詢問得到發(fā)送方IDS的私鑰MS,PS，β需要在List2中隨機選擇一個記錄且包含了正確元素MS,PS，概率為。將正確記錄中的MS,PS作 為β對問題實例(HS=MSH0PS,H0)的求解。設(shè)攻擊者α1偽造的簽名σ*通過驗證這件事為 E，其概率為。設(shè)E1表示挑戰(zhàn)者對目標(biāo)用戶組中的私鑰進行詢問，設(shè)E2表示發(fā)送方以及存在一個接收者屬于目標(biāo)用戶組中，若這2 個事件發(fā)生β會自動放棄此次詢問。設(shè)E3表示挑戰(zhàn)者β在進行h2詢問時，List2中的相應(yīng)記錄出現(xiàn)了碰撞情況，則簽密模擬失敗，其概率為。設(shè)E4表示一個有效簽名被拒絕，其概率為。設(shè)E5表示β在表List1中隨機選擇一個記錄且包含了正確元素，其概率為。所以概率為Pr[E ∩ E1∩ E2∩ E3∩ E4∩E5]。β解決SD 問題的優(yōu)勢υ為

證畢。

2)游戲類型2

定理4在隨機預(yù)言機模型下，假設(shè)存在一個EUF-CMA 的攻擊者α2，它能夠以優(yōu)勢贏得如下定義的游戲（定義4 中的游戲），那么就存在一個算法β，它解決SD 問題的優(yōu)勢υ如式(5)所示，其中算法β作為攻擊者α2在游戲中的挑戰(zhàn)者，而α2則作為β的子程序。

證明在游戲類型2 中，不同于游戲類型1，攻擊者α2可以獲得系統(tǒng)主密鑰信息，但是不能對用戶的公鑰進行替換，對于定理4 的證明與定理3 的證明類似，易得定理4 成立。證畢。

5 效率分析

5.1 加密方案效率

本文的多接收方簽密方案以及廣義簽密方案是在3.1 節(jié)中提出的多次加密McEliece 方案基礎(chǔ)上進行構(gòu)造的。由3.1 的加密方案可以看出，該方案采用的是 QC-LDPC 碼，該碼相比于Goppa 碼等其他碼字存儲起來消耗更少的空間，且具有更高的傳信率。另一方面，雖然該方案進行了多次加密，但是采用同一個碼字產(chǎn)生的同一個公鑰，解密也采用該碼字產(chǎn)生的同一個私鑰，因此多次加密的McEliece 方案能夠保持與采用QC-LDPC 碼的普通McEliece 方案同樣的密鑰存儲量，且能夠滿足更高的安全需求。具體比較如表1 所示。

由表1 可以看出，采用Goppa 碼的McEliece方案所選用的Goppa 碼維度相比(QC-LDPC)-M 以及多次加密的McEliece 方案小許多，盡管如此，采用Goppa 碼的McEliece 方案的公鑰量為67 072 B，相比另外兩者6 048 B 的公鑰量還是大了許多，而且能夠加密的明文量僅為524 bit，相比另外兩者的12 096 bit 少了許多。通過公鑰量一欄還可以看出，多次加密的McEliece 方案雖然采用多次加密的方法降低對譯碼錯誤的影響，從而具有了更高的安全性，但是與普通的采用QC-LPDC 碼的McEliece 方案的密鑰量相同，正如之前所述，這是由于多次加解密所采用的密鑰是相同的，因此多次加密的McEliece 方案具有較好的性能。其中b代表多次加密的次數(shù)，即產(chǎn)生的密文數(shù)量。

5.2 多接收方的簽密與廣義簽密方案效率

3.3 節(jié)與3.4節(jié)的簽密和廣義簽密方案在參數(shù)生成以及系統(tǒng)密鑰和用戶密鑰的生成上是相同的，因此從多接收方的廣義簽密分析方案的密鑰量相等即可。取(16 128,12 096)維的QC-LDPC 碼進行如表2 所示的比較。

由表2 對比分析可以看出，本文的多接收方廣義簽密方案不僅可以實現(xiàn)簽密功能以及在簽名、加密、簽密方案三者之間的自適應(yīng)轉(zhuǎn)換，而且相比先簽名后加密方案在私鑰量上減少了31 752 KB，這些減少量的存在是由于CFS 簽名方案與多次加密-M方案在置換矩陣P上的共用。先簽名后加密方案與本文廣義簽密方案的密文量都是16 128(b+2)bit，相比直接將二者相加的密文量多了16 128 bit，這是因為還存在使用系統(tǒng)公鑰加密產(chǎn)生的密文x，但這保證了系統(tǒng)用戶以外的用戶無法獲知系統(tǒng)內(nèi)部的信息。通過表2 可以看出，本文多接收方廣義簽密方案具有較好的使用前景。

表1 方案性能對比

表2 密鑰量對比

將本文多接收方的廣義簽密方案與其他多接收方簽密方案進行效率比較，如表3 所示。其中，?代表多接收方用戶數(shù)量。由表3 可以看出，本文的廣義簽密方案相比Li 等[32]方案、朱輝等[33]方案、Selvi 等[25]方案，沒有復(fù)雜的指數(shù)運算以及雙線性對運算，而本文方案多了矩陣運算。指數(shù)運算以及雙線性對運算相比矩陣運算的效率較低，且消耗更多的資源，因此本文方案沒有復(fù)雜的指數(shù)運算以及雙線性對運算，這是提高效率的一大優(yōu)勢，由于是基于編碼密碼進行廣義簽密方案的構(gòu)造，因此能夠抵抗量子計算機攻擊，這也是相比基于傳統(tǒng)公鑰密碼構(gòu)造簽密方案的優(yōu)勢之一。

表3 簽密方案效率對比

6 結(jié)束語

本文提出了能夠滿足IND-CCA2 安全的多次加密McEliece 方案，該加密方案采用QC-LDPC碼進行構(gòu)造且多次加密與解密所采用的都是同一對公私鑰，因此能夠在保證密鑰儲存量合適的前提下達到更高的安全級別。依托多次加密的McEliece 方案與CFS 簽名方案，提出基于編碼的多接收方的簽密方案，進而在該簽密方案的基礎(chǔ)上進行改進提出了基于編碼的多接收方的廣義簽密方案。新的廣義簽密方案在機密性方面滿足IND-CCA 2 安全，在不可偽造性方面滿足EUF-CMA 安全。本文廣義簽密方案在密鑰量以及密文量方面具有一定優(yōu)勢，而且相比基于傳統(tǒng)公鑰密碼的多接收方簽密方案沒有復(fù)雜的雙線性對運算以及指數(shù)運算。最后將該多接收方的廣義簽密與多接收方通信模型相結(jié)合能夠?qū)崿F(xiàn)對不同安全級別用戶的訪問控制，能夠滿足系統(tǒng)的多種安全需求。