王 眾, 韓益亮

武警工程大學(xué)密碼工程學(xué)院, 西安710086

1 背景

1997 年, Zheng 提出了“簽密” 的概念[1], 簽密方案可以在一個邏輯步驟內(nèi)完成加密以及認(rèn)證的功能,相比于傳統(tǒng)的先“加密” 后“簽名” 或者先“簽名” 后“加密” 的方案能夠消耗更少的資源, 也易于操作.簽密方案雖然具有加密與簽名的功能, 但是簽密方案、加密方案以及簽名方案三者還是有所不同甚至是互斥的, 因?yàn)楹灻芊桨敢笫瞻l(fā)雙方都需要具有密鑰, 而加密方案只要求接收方有密鑰, 簽名方案只要求發(fā)送方有密鑰, 三者是不能相互轉(zhuǎn)換的.2006 年, 韓益亮等人提出了廣義簽密的概念[2], 實(shí)現(xiàn)了簽密、加密與簽名三者之間自適應(yīng)的轉(zhuǎn)換.現(xiàn)有的廣義簽密方案基本都是基于離散對數(shù)問題、橢圓曲線離散對數(shù)問題來進(jìn)行構(gòu)造的, 但是在量子技術(shù)快速發(fā)展的今天, 基于經(jīng)典數(shù)論問題的公鑰密碼方案將不再安全可靠, 那么提供一種在量子時代進(jìn)行安全防護(hù)的方案就顯得十分必要.

目前已知的抗量子計算攻擊的密碼體制有以下四種, 分別是基于Hash 函數(shù)的密碼體制、基于多變量的密碼體制、基于編碼的密碼體制以及基于格的密碼體制[3].其中, 基于編碼的密碼具有抗量子計算特性的同時, 還具有加解密過程簡單、易于操作的特點(diǎn).該密碼體制是在有限域上多元多項(xiàng)式環(huán)上定義和運(yùn)算的, 此類密碼體制的算法核心是對一種糾錯碼 C 的應(yīng)用, 主要的特征即為添加一個錯誤到碼字中或根據(jù)碼 C 的校驗(yàn)矩陣計算伴隨式.最早的基于編碼的密碼體制是由 McEliece 在 1978 年提出的, 它是對Goppa 碼的生成矩陣進(jìn)行變換來進(jìn)行隱藏而產(chǎn)生公鑰[4].Niederreiter 在 1986 年又提出基于Goppa 碼的 Niederreiter 密碼體制[5], 它則是對 Goppa 碼的校驗(yàn)矩陣進(jìn)行變換, 兩種密碼體制在安全性上是對等的.Courtois 等在 2001 年提出了基于校驗(yàn)子譯碼困難問題的簽名方案—CFS 方案[6], Mathew 等人在2013 年通過密鑰構(gòu)造的改變使得 CFS 簽名方案的密鑰量減少[7].為了能夠彌補(bǔ)編碼密碼密鑰量大的特點(diǎn), 用其他碼字來代替Goppa 碼已經(jīng)成為一種趨勢, 但是這也會帶來一些安全上的弊端, 這些弊端已經(jīng)出現(xiàn)在基于準(zhǔn)循環(huán)碼 (QC)[8]、LDPC 碼[9]、QC-LDPC 碼[10]、準(zhǔn)二進(jìn)制碼 (QD)[11]、卷積碼[12]等碼字的第一代 McEliece 變體方案中.還有一些使用 QC-LDPC 碼[13]、QC-MDPC 碼[14]等碼字的一些變體方案能夠在不損壞安全性的前提下良好地達(dá)到密鑰壓縮的目的, 如2017 年Jean-Christophe 等人提出的Ouroboros 密鑰交換協(xié)議[15], 2018 年 Baldi 等人提出的 LEDAkem 密鑰封裝機(jī)制[16]等.

本文將繼續(xù)研究基于編碼的密碼體制, 借鑒文獻(xiàn) [16]的相關(guān)加密方法, 提出基于 QC-LDPC 碼的抗量子廣義簽密方案, 為后量子時代復(fù)雜的網(wǎng)絡(luò)環(huán)境提供強(qiáng)有力的保障.第 2 節(jié)將對相關(guān)理論知識進(jìn)行介紹, 第3 節(jié)詳細(xì)描述本文方案, 第4 節(jié)進(jìn)行安全性分析, 第5 節(jié)對效率進(jìn)行分析, 最后第6 節(jié)總結(jié)全文.

2 相關(guān)知識

2.1 SD問題

校驗(yàn)子譯碼問題(syndrome decoding problem): 給定一個(n,k) 維的線性碼, 它的最小漢明距離為d, 該碼的校驗(yàn)矩陣為它的糾錯能力為 t 且 t 滿足方程 d = 2t+1.當(dāng)給定一個向量時, 尋找一個錯誤向量它的漢明重量要小于等于 t, 且與向量v 以及矩陣H 滿足方程v =eHT, 尋找錯誤向量e 這個問題已被證明為NP 困難問題.

2.2 廣義簽密

廣義簽密, 可以實(shí)現(xiàn)簽名、加密以及簽密三者之間的自適應(yīng)轉(zhuǎn)換.一個廣義簽密方案 GSC=(Gen,SC, DSC) 包含三個算法.首先是隨機(jī)化的密鑰生成算法Gen(X,1k)→(SDKX, VEKX), 通過輸入安全參數(shù)k, 來產(chǎn)生用戶x 的密鑰對, SDK 為私鑰用于簽名與解密, VEK 為公鑰, 用于認(rèn)證與加密.然后是概率性的簽密算法 SC(m, SDKS, VEKR) →θ, 輸入待簽密消息 m, 與發(fā)送者的私鑰 SDKS和接受者的公鑰 VEKR, 輸出簽密文 θ.最后是確定性的解簽密算法 DSC(θ, SDKR, VEKS) →m ∪ ⊥, 輸入簽密文 θ,發(fā)送者公鑰以及接受者私鑰, 輸出消息m 或者⊥, 其中⊥代表非法明文.

當(dāng)發(fā)送者S 沒有密鑰時, 整個廣義簽密方案相當(dāng)于一個加密方案ENC=(Gen, Enc, Dec).

簽密算法即為:

解簽密算法即為:

當(dāng)接受者R 沒有密鑰時, 整個廣義簽密方案為簽名方案SIG=(Gen,Sig,Ver).

簽密算法即為:

解簽密算法為:

其中T 代表簽名合法, 而⊥代表非法簽名.若說明一個廣義簽密方案GSC=(Gen, SC, DSC) 是正確可行的當(dāng)且僅當(dāng)DSC(SC(m,SDKS,VEKR),SDKR,VEKS)=m.

有關(guān)廣義簽密方案的安全性主要涉及兩方面.機(jī)密性: 自適應(yīng)攻擊者獲取關(guān)于密文內(nèi)容的任何部分信息在計算上是不可行的.自適應(yīng)攻擊者可以是發(fā)送者和接收者以外的任何一方.不可偽造性: 自適應(yīng)偽造者在計算上是不可行的, 他們可能是不被信任的接收者, 并且允許查詢發(fā)送者的簽密算法, 偽裝發(fā)送者以創(chuàng)建真實(shí)的密文.當(dāng)廣義簽密方案在簽密模式下運(yùn)行時, 必須滿足這兩個安全概念.在僅加密模式下運(yùn)行時只需要機(jī)密性, 并且在僅簽名模式下運(yùn)行時只需要不可偽造性.

2.3 簽密安全模型

根據(jù)文獻(xiàn)[17,18], 可以得到本文基于編碼方案所需的安全模型, 使用下述的攻擊游戲進(jìn)行說明.

定義1如果在下面的攻擊游戲中, 攻擊者能夠取得勝利的優(yōu)勢是可以忽略的, 那么說明此基于編碼的廣義簽密方案在選擇明文攻擊下滿足IND-CPA 安全.

該機(jī)密性游戲包含以下三個階段:

(1) 挑戰(zhàn)者選擇合適參數(shù), 運(yùn)行密鑰生成算法, 產(chǎn)生發(fā)送方以及接收方的公私鑰對 (pkS,skS)、(pkR,skR), 并將公鑰對(pkS,pkR) 以及發(fā)送方的私鑰skS發(fā)送給攻擊者.

(2) 攻擊者向挑戰(zhàn)者提交兩個合法明文(m1,m2), 以及挑戰(zhàn)收發(fā)雙方的公鑰對(pkS,pkR), 挑戰(zhàn)者收到挑戰(zhàn)明文對后, 通過隨機(jī)選擇1 bit b, 將明文mb以及挑戰(zhàn)收發(fā)雙方的公鑰對(pkS,pkR) 發(fā)送給簽密預(yù)言機(jī), 進(jìn)行簽密操作產(chǎn)生密文n, 并將該密文返回給挑戰(zhàn)者, 再由其返回給攻擊者.

(3) 攻擊者最后輸出1 bit b1.

當(dāng)b1=b 時, 攻擊者贏得該游戲, 其優(yōu)勢為:

定義2如果在下面的攻擊游戲中, 攻擊者能夠取得勝利的優(yōu)勢是可以忽略的, 那么說明此基于編碼的廣義簽密方案在適應(yīng)性選擇消息攻擊下滿足EUF-CMA 安全.

該不可偽造性游戲包含以下三個階段:

(1) 挑戰(zhàn)者選擇合適參數(shù), 運(yùn)行密鑰生成算法, 產(chǎn)生發(fā)送方以及接收方的公私鑰對對 (pkS,skS)、(pkR,skR), 并將公鑰對 (pkS,pkR) 以及發(fā)送方的公鑰 pkS發(fā)送給攻擊者, 將發(fā)送方的公私鑰對(pkS,skS) 發(fā)送給簽密預(yù)言機(jī).

(2) 攻擊者進(jìn)行簽密詢問和驗(yàn)證詢問, 驗(yàn)證密文是否合法.

(3) 攻擊者產(chǎn)生挑戰(zhàn)消息 m, 以及偽造的簽密文 n, 向挑戰(zhàn)者提交 (m,n,pkS,skS), 挑戰(zhàn)者運(yùn)行解簽密算法解簽密(n,skR,pkS), 并輸出結(jié)果m, 如果之前攻擊者都未對(m,pkS,skS) 進(jìn)行過簽密詢問, 則說明攻擊者偽造成功, 其優(yōu)勢為:

2.4 CFS簽名方案

Courtois, Finiasz 和 Sendrier 提出的基于 Niederreiter 密碼體制的 CFS 簽名方案是為數(shù)不多的安全編碼基簽名方案.具體的初始化與簽名驗(yàn)證過程如下:

初始化過程: 取 C 是有限域 GFq上線性 (n,k,d)Goppa 碼, n = 2a, d = 2t + 1, k = n ?at.(n ?k)×n 階矩陣 H 為二元 (n,k,d)Goppa 碼的校驗(yàn)矩陣, 隨機(jī)選取 GF(2) 上的可逆矩陣 S, 其階為(n ?k)×(n ?k), 再選取置換矩陣 T, 其階為 n×n.設(shè)一個哈希函數(shù)即將任意長度的 0, 1 串映射到長度為 n ?k 的 0, 1 串上.Goppa 的快速譯碼算法為 βHt(), σ 為待簽名消息.將公開, 將 (S,T,H,βHt()) 保密.

簽名過程:

(1) 計算 σ 的哈希值 m:m=h(σ) .

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

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

驗(yàn)證過程:

(2) 如果a=b, 則簽名成功, 否則失敗.

2.5 LEDAkem方案 [16]

2018 年Baldi 等人提出的基于QC-LDPC 碼的密鑰封裝方案采用的是Niederreiter 密碼體制, 具體的密鑰生成、加解密過程如下:

密鑰生成: 首先輸入循環(huán)塊的尺寸 p, 則循環(huán)塊大小為 p×p, 輸入 QC-LDPC 碼的校驗(yàn)矩陣 H 中循環(huán)塊的數(shù)量 n0, 數(shù)字 dv代表矩陣 H 的行/列重量, 向量 v = (v0,v1,··· ,vn0?1) 代表由個循環(huán)塊Qi,j所組成的矩陣Q 的行/列重量.具體表示如下,

矩陣H 由個循環(huán)塊組成, 其維度為p×pn0.矩陣Q 如下所示,

矩陣Q 的行列重量如下所示可知, 其每行每列的重量相等為

其私鑰SK 即為(H,Q), 公鑰PK 進(jìn)行如下運(yùn)算可得,

得到矩陣 L 再利用 Ln0?1, 對其做運(yùn)算即可得公鑰 PK, 矩陣 Ml.

加密過程: 將明文 m 轉(zhuǎn)換為長度為 n, 重量為 t 的錯誤向量 e, 其中 t 滿足 QC-LDPC 碼的糾錯重量.對其運(yùn)用公鑰進(jìn)行運(yùn)算即得密文s.

解密過程: 運(yùn)用私鑰對密文進(jìn)行如下處理.

3 基于編碼密碼的抗量子廣義簽密方案

3.1 方案構(gòu)造

i.密鑰生成: 在有限域 GFq上隨機(jī)選取 (n,k,d) 的 QC-LDPC 碼, n = 2a, d = 2t+1, k = n ?at.其譯碼算法為βHt(), 允許的最大重量為t, (n ?k)×n 階矩陣H 為QC-LDPC 碼的校驗(yàn)矩陣, 隨機(jī)選取GF(2) 上的可逆矩陣 S, 其階為 (n ?k)×(n ?k), 再選取置換矩陣 T, 其階為那么用戶U 的公鑰即為其中MlU為2.4 節(jié)中所描述方案中的矩陣Ml, 用于加密.對應(yīng)的私鑰為矩陣 QU, HU, S, T.再定義兩個 Hash 函數(shù)

ii.定義區(qū)分函數(shù) f(x): 根據(jù)用戶 U 是否存在密鑰來進(jìn)行賦值操作.當(dāng)用戶 U 的公鑰時,則 f(x) = 0, 其中 0 代表 n 維零向量; 當(dāng)用戶 U 的公鑰時, 則函數(shù) f(x) = 1, 其中 1 代表 n維單位向量.

iii.簽密過程(GSC): R 代表接收者, S 代表發(fā)送者, 待簽密消息為n 維m.符號表示在集合中隨機(jī)選取一個元素, ⊕表示異或運(yùn)算, ||表示級聯(lián)運(yùn)算.

3.2 自適應(yīng)性

(1) 當(dāng)收發(fā)雙方均無密鑰時.由上述對方案的描述可知, 發(fā)送方 S 將不能對待簽密消息 m 進(jìn)行簽名以及加密的操作, 所發(fā)送的三元組(s,c1,c2) 即為(?,r,m), 相當(dāng)于直接把消息發(fā)送給了接收者.這種沒有任何保密措施的情況適用于匿名用戶與匿名計算機(jī)系統(tǒng)或者傳感器之間進(jìn)行通信, 并且傳輸?shù)男畔⑹枪_的.

(2) 當(dāng)發(fā)送方 S 有密鑰而接收方 R 無密鑰時, 此時相當(dāng)于純簽名的過程.發(fā)送方 S 所發(fā)送的三元組即為(s,r,m), s 即為利用發(fā)送方私鑰進(jìn)行操作所得到的關(guān)于消息m 的簽名.當(dāng)接收方收到該三元組后,即可利用r 和m 進(jìn)行如解簽密過程步驟(3) 中所示的驗(yàn)證方式, 來驗(yàn)證簽名s 是否合法.這種情況適用于發(fā)送方S 是確定性的用戶或是已經(jīng)注冊認(rèn)證的用戶、計算機(jī)系統(tǒng)或者傳感器, 而接收方R 則是匿名用戶或者設(shè)備.進(jìn)而防止對所傳輸?shù)男畔⑦M(jìn)行篡改, 以及對用戶或者設(shè)備的冒名頂替, 保障了可認(rèn)證性.

(3) 當(dāng)發(fā)送方 S 沒有密鑰而接收方 R 有密鑰時, 此時相當(dāng)于純加密的過程.發(fā)送方 S 運(yùn)用接收方 R的公鑰MlR對隨機(jī)數(shù)r 加密后, 再利用加密結(jié)果對消息m 進(jìn)行加密, 輸出的三元組即為(?,c1,c2).接收者收到該三元組后利用自己的私鑰進(jìn)行解密操作即可得明文消息m.這種情況適用于發(fā)送方S 為匿名用戶、計算機(jī)系統(tǒng)或者傳感器, 它所發(fā)出的消息只想讓指定的接收方 R 收到, 且R 為確定的用戶或已經(jīng)注冊認(rèn)證的用戶或者設(shè)備.

(4) 當(dāng)接收方 R, 發(fā)送方 S 都有各自密鑰時, 該方案即為一個簽密方案.發(fā)送方發(fā)送的三元組即為(s,c1,c2), 其中 s 為發(fā)送者 S 用自己的私鑰進(jìn)行運(yùn)算所得到的簽名信息, c1,c2為發(fā)送者 S 運(yùn)用接受者R 的公鑰進(jìn)行運(yùn)算所得到的加密信息, 只有擁有相應(yīng)私鑰的接收者 R 可以對信息進(jìn)行解密.解簽密的過程是接收者運(yùn)用自己的私鑰對c1,c2, 進(jìn)行解密得到r,m, 再利用發(fā)送者 S 的公鑰通過r,m 對簽名進(jìn)行驗(yàn)證.這種情況適用于收發(fā)雙方均為確定的用戶或已經(jīng)注冊驗(yàn)證的用戶、設(shè)備之間進(jìn)行信息的保密通信.

綜上分析可知, 本文的廣義簽密方案, 能夠?qū)崿F(xiàn)在加密方案、簽名方案以及簽密方案三者之間自適應(yīng)的轉(zhuǎn)換, 并且基于編碼密碼理論, 能夠在后量子時代為越發(fā)復(fù)雜的網(wǎng)絡(luò)環(huán)境提供強(qiáng)有力的保障.

4 安全性分析

對本文廣義簽密方案進(jìn)行安全性分析從兩個方面入手: 一是對簽密信息的機(jī)密性進(jìn)行分析; 二是對簽密信息的不可偽造性進(jìn)行分析.這樣不論是純粹的簽名過程還是純粹的加密過程的安全性都可以包含在內(nèi), 機(jī)密性從 IND-CPA 安全入手, 不可偽造性從 EUF-CMA 安全入手, 證明過程在文獻(xiàn) [17–19]的基礎(chǔ)上進(jìn)行, 游戲模型如圖1 所示.

圖1 攻擊游戲模型Figure 1 Attack game model

4.1 不可偽造性

從隨機(jī)數(shù)的選取, 游戲模擬成功的概率, 以及對SD 困難問題進(jìn)行成功求解來對所得簽密文進(jìn)行驗(yàn)證的角度, 對攻擊者成功偽造簽密文的概率進(jìn)行分析.

定理1在隨機(jī)預(yù)言機(jī)模型下, 假定存在一個EUF-CMA 的攻擊者 α, 它能夠以優(yōu)勢贏得如下定義的游戲, 那么就存在一個算法β, 它解決SD 問題的優(yōu)勢表示如下:

qSC,qDSC,qh1,qh2分別代表攻擊者α 所能進(jìn)行的簽密詢問、解簽密詢問、以及對隨機(jī)預(yù)言機(jī)h1和h2的詢問的最大次數(shù).為了方便回答這四種詢問, 并分別設(shè)立四個詢問列表來對詢問進(jìn)行記錄.

證明:給定一個本文廣義簽密方案的SD 問題實(shí)例, 攻擊者α 為攻擊算法β 的子程序, 而β 則作為攻擊者α 在挑戰(zhàn)過程中的挑戰(zhàn)者.攻擊者α 可以進(jìn)行以下詢問:

(1) 預(yù)言機(jī) h1詢問: 如 3.1 中對方案描述的那樣, 向預(yù)言機(jī) h1中輸入 (m,r), 首先查詢表, 是否存在相應(yīng)記錄, 不存在則隨機(jī)產(chǎn)生一個入d 值, 并將該值記錄在表中.

(2) 預(yù)言機(jī)h2詢問: 向預(yù)言機(jī)h2中輸入(d,i), 進(jìn)行詢問, 首先查詢中是否存在相應(yīng)的記錄, 不存在則隨機(jī)產(chǎn)生一個值, 并將其記錄在表中.

(3) SC 簽密詢問: 將消息m 輸入 SC 預(yù)言機(jī), 首先查詢 SCList表中是否有對應(yīng)的記錄, 若存在相應(yīng)記錄, 返回給攻擊者 α 該簽密文 n.若沒有, 則先進(jìn)行預(yù)言機(jī) h1詢問, 如 (1) 中所述那樣產(chǎn)生 d 值, 再調(diào)用預(yù)言機(jī)h2, 并進(jìn)行方案中相應(yīng)的簽密操作, 最后產(chǎn)生一個簽密文 n, 記錄在SCList中, 并將其返回給攻擊者α.需要注意的是, 當(dāng)SCList表中沒有相應(yīng)記錄但是預(yù)言機(jī)h1或預(yù)言機(jī)h2存在相應(yīng)記錄時, 簽密模擬的過程則是失敗的.

(4) DSC 解簽密詢問: 輸入簽密文 n, 首先對表 DSCList進(jìn)行查詢, 若存在對應(yīng)的明文 m 則返回給攻擊者α, 若不存在則進(jìn)行方案所述的解簽密過程求解出相應(yīng)的r 值, 再詢問表找到相應(yīng)的記錄, 返回m, 否則說明該簽密文不合法.

不可偽造性攻擊游戲進(jìn)行以下三個階段:

(1) 運(yùn)行系統(tǒng), 選擇合適參數(shù), 產(chǎn)生收發(fā)雙方的公私鑰對.

(2) 攻擊者 α 可以向挑戰(zhàn)者 β 進(jìn)行預(yù)言機(jī) h1詢問、預(yù)言機(jī) h2詢問.

(3) 攻擊者向挑戰(zhàn)者提交挑戰(zhàn)消息m, 以及偽造的簽密文 n, 挑戰(zhàn)者對 n 運(yùn)行解簽密算法求出結(jié)果,若該結(jié)果即為m 且之前沒有對其進(jìn)行過簽密詢問, 則說明攻擊者偽造成功.

首先模擬成功的話, 需要譯碼成功才能產(chǎn)生合適的簽名, 這就取決于選擇合適的i 值, 當(dāng)詢問h2預(yù)言機(jī)輸入 (d,i), i 值總共有 2n?k種可能, 簽密詢問的最大次數(shù)為 qSC, 那么模擬成功的概率為 qSC/2n?k,那么攻擊者成功進(jìn)行預(yù)言機(jī) h2詢問的概率為 Pr[M1]= qSC/2n?k.在成功完成預(yù)言機(jī) h2詢問后, 才能繼續(xù)下面的簽密詢問, 在qh2中的某一次詢問成功后, 繼續(xù)進(jìn)行簽密詢問, 二者都成功的概率為Pr[M2]=(1/(qh2+qSC)).簽密詢問后得到簽名 s 后, 還需要對簽名的正確性進(jìn)行驗(yàn)證, 模擬一個正確的簽名也即能夠通過驗(yàn)證需要破解 SD 問題, 因此該事件的成功概率不會大于成功解決 SD 問題的概率 Pr[M3]≤(此處未在考慮QC-LDPC(n,k,t) 碼的參數(shù)選擇, 方案在構(gòu)造時的參數(shù)選擇一般較大).

綜上所述, 攻擊算法 β 得該游戲的優(yōu)勢 Pβ為:

據(jù)上述分析, 可以看出本文方案滿足EUF-CMA 安全.

4.2 機(jī)密性

從隨機(jī)數(shù)選取, SD 問題的難解性以及游戲模擬的成功概率方面進(jìn)行證明.

定理2在隨機(jī)預(yù)言機(jī)模型下, 假定存在一個IND-CPA 的攻擊者 α, 它能夠以優(yōu)勢贏得如下定義的游戲, 那么就存在一個算法β, 它能夠在多項(xiàng)時間內(nèi)以優(yōu)勢解決SD 問題.

證明:算法 β 得到本文廣義簽密方案的一個 SD 問題實(shí)例 Y = P(X), 攻擊者 α 作為攻擊算法 β的一個子程序, 而β 則作為攻擊者α 在詢問過程中的挑戰(zhàn)者.

具體攻擊過程如下:

階段 1: 算法β 獲得了該SD 問題實(shí)例中的公私鑰對, 并將公鑰發(fā)送給攻擊者α, 攻擊者α 可以向挑戰(zhàn)者β 進(jìn)行三種詢問, 即預(yù)言機(jī)h1詢問、預(yù)言機(jī)h2詢問、SC 簽密詢問.

挑戰(zhàn)階段: 攻擊者 α 向挑戰(zhàn)者 β 提交兩個合法明文 (m1,m2), 挑戰(zhàn)者收到挑戰(zhàn)明文對后, 通過隨機(jī)選擇1bit b, 對明文mb運(yùn)用合法用戶的私鑰進(jìn)行加密產(chǎn)生密文n, 并將該密文返回給攻擊者α.

猜測階段: 攻擊者α 根據(jù)詢問的結(jié)果, 輸出b.

從上述攻擊游戲以及本文方案中可以看出, 即使是對同一個明文m 進(jìn)行加密, 由于隨機(jī)數(shù)r 的選取,使得二者相同的概率極低.通過直接攻擊, 來對SD 問題進(jìn)行運(yùn)算成功的概率是極低的, 因?yàn)? 當(dāng) LRPC碼的維度較大時, SD 問題作為一個困難問題以及編碼密碼體制的理論基礎(chǔ), 是很難被攻破的.因此在多項(xiàng)式時間內(nèi), 不斷地對 (m1,m2) 進(jìn)行簽密詢問, 是難以區(qū)分出 m1與 m2的.還有需要注意的一點(diǎn)就是模擬游戲成功的概率, 在簽密詢問時有可能產(chǎn)生Hash 函數(shù)的碰撞, 導(dǎo)致模擬過程的失敗, 即是向預(yù)言機(jī) h1中輸入 (m,r) 進(jìn)行詢問時, r 值已經(jīng)存在于預(yù)言機(jī) h1的詢問記錄表中.在簽密詢問時, 詢問的最大次數(shù)為qSC, 哈希預(yù)言機(jī)產(chǎn)生的結(jié)果有2n種, 那么產(chǎn)生碰撞的概率即為qSC/2n, 因此記模擬成功為事件 Msuc, 它成功的概率為 (1 ?qSC/2n), 這又進(jìn)一步減少了優(yōu)勢.綜上所述, 攻擊者可以根據(jù)簽密文成功猜得的 mb概率為1/2, 也即:

據(jù)上述分析, 可以看出本文方案滿足IND-CPA 安全.

根據(jù)文獻(xiàn) [20]中的相關(guān)內(nèi)容可知, 由于 LRPC 碼在譯碼時具有不可忽略的錯誤率, 其錯誤率大概為 10?7.這個錯誤率雖然不會對方案的可靠性造成大的影響, 但是成為方案安全性評估所不可忽略的因素, 這也使得很多基于編碼的密碼方案不能滿足 IND-CCA2 安全.文獻(xiàn) [20]還給出了一種將基于 QCMDPC 碼的方案進(jìn)行轉(zhuǎn)換而滿足 IND-CCA2 安全的方法, 那就是將待加密信息利用同一公鑰進(jìn)行多次加密, 進(jìn)而產(chǎn)生關(guān)于明文的一組相互獨(dú)立的密文, 那么在進(jìn)行解密工作時, 只有當(dāng)這些密文都出現(xiàn)譯碼錯誤時, 才會導(dǎo)致方案的錯誤, 這種方法也就將譯碼錯誤率10?7變小為10?7n, 大大減小了譯碼錯誤率對方案安全的影響程度, 根據(jù)文獻(xiàn) [20], n 的取值一般在 3 到 12, 具體細(xì)節(jié)參考文獻(xiàn) [20].本文廣義簽密方案也可以根據(jù)這種對明文信息進(jìn)行多次加密的方法來轉(zhuǎn)換為IND-CCA2 安全, 也即多次運(yùn)行簽密過程中的(1) 到 (3) 步, 相應(yīng)的密文 c2也就變成了一組密文 (c21,c22,··· ,c2n), 相應(yīng)地在解簽密過程中, 就需要對(c21,c22,··· ,c2n) 分別進(jìn)行解簽密, 只有當(dāng)這 n 次解簽密全部出現(xiàn)錯誤時, 方案才會受到譯碼錯誤的影響, 而這發(fā)生的概率是極低的.

5 效率分析

本文方案采用 QC-LDPC 碼進(jìn)行構(gòu)造, 由于 QC-LDPC 碼的準(zhǔn)循環(huán)性以及稀疏性, 因此它的存儲只需要校驗(yàn)矩陣中的非零循環(huán)子矩陣與循環(huán)的位數(shù), 要比 Goppa 碼等碼字的容量小許多, 并具有較高的信息率, 進(jìn)而保障本文方案的密鑰量較小.根據(jù)文獻(xiàn)[16,21]將采用Goppa 碼的Niederreiter 密碼方案與采用 QC-LDPC 碼的 Niederreiter 方案以及采用 QC-LDPC 碼的 LEDAkem 方案進(jìn)行比較, 如表1.

表1 方案性能對比Table 1 Scheme comparison

從表1 可知, 所選 QC-LDPC 碼的n0為4, k0為3, 循環(huán)子矩陣的維度p 值為4032, 因此公鑰量即為p×k0×n0.QC-LDPC 碼在公鑰量的大小以及加密數(shù)據(jù)的處理量和信息率方面都要比傳統(tǒng)Niederreiter密碼方案所采用的 Goppa 碼有較大的提升, 而采用 QC-LDPC 碼的 LEDAkem 方案相比二者在密鑰量方面又有較大的優(yōu)勢.

本文方案在實(shí)現(xiàn)簽名功能時選擇的方法為CFS 簽名方法, 采用經(jīng)過密鑰構(gòu)造改造過的P-CFS[22]簽名方法也可以達(dá)到同樣的效果, 并且能夠選擇更小的參數(shù), 減少方案的密鑰量, 因此在P-CFS 簽名方法下,仍然選擇 (16 128, 12 096) 的 QC-LDPC 碼, 根據(jù)文獻(xiàn) [16,22], 進(jìn)行密鑰量的比較分析, 如表2.

表2 密鑰量對比Table 2 Key Size Comparison

表2 中的簽名加密方案是指先進(jìn)行簽名再進(jìn)行加密的方案, 兩步是分離的, 因此其密鑰量即為簽名方案與加密方案的和.本文廣義簽密方案是將二者進(jìn)行融合, 在私鑰量這一方面, 有部分私鑰是P-CFS 簽名方案與LEDAkem 方案共用的, 因此私鑰量有所下降.綜上分析可知, 本文方案實(shí)現(xiàn)了簽密、簽名、加密三者之間的自適應(yīng)轉(zhuǎn)換, 又由于QC-LDPC 碼與LEDAkem 加密方法的采用, 使得新方案能夠在消耗較少存儲資源的前提下為后量子時代的網(wǎng)絡(luò)通信提供較好的保障作用.

6 結(jié)束語

本文通過對編碼密碼中的 LEDAkem 密鑰封裝機(jī)制以及 CFS 簽名方案進(jìn)行研究, 將二者進(jìn)行結(jié)合,運(yùn)用LEDAkem 密鑰封裝機(jī)制中的加密方法與CFS 簽名的方法進(jìn)行結(jié)合, 進(jìn)而提出了基于編碼密碼的廣義簽密方案.該方案采用QC-LDPC 碼, 保證了密鑰量在適宜范圍內(nèi), 通過安全性分析, 新方案在適應(yīng)性選擇密文攻擊下滿足IND-CCA2 安全, 在適應(yīng)性選擇消息攻擊下滿足EUF-CMA 安全, 并具有能夠在加密方案、簽密方案、簽名方案或者普通通信方式 (未采用保護(hù)措施) 下的自適應(yīng)性轉(zhuǎn)換, 減少了安全防護(hù)的代價, 可以適應(yīng)日益復(fù)雜的通信環(huán)境, 并能夠在后量子時代為網(wǎng)絡(luò)通信提供安全保障.