一個(gè)格基無(wú)證書簽密方案

歐海文 施 瑞 王佳琳

1(北京電子科技學(xué)院密碼科學(xué)與技術(shù)系 北京 100070)2(西安電子科技大學(xué)通信工程學(xué)院 陜西 西安 710071)

0 引 言

簽密是一個(gè)基本密碼學(xué)原語(yǔ)[1]，它能同時(shí)滿足加密和簽名兩種密碼體制的安全性要求，即同時(shí)實(shí)現(xiàn)信息的保密性和不可偽造性。基于公鑰基礎(chǔ)設(shè)施(PKI)的簽密體制證書管理較為復(fù)雜，基于身份的簽密體制需考慮密鑰托管問(wèn)題，無(wú)證書密碼體制[2]的提出解決了上述兩種密碼體制存在的缺陷。Farshim等[3]于2008年提出了第一個(gè)無(wú)證書簽密方案，此后國(guó)內(nèi)外研究者增加了對(duì)無(wú)證書簽密體制的關(guān)注，并于近年來(lái)提出了多種無(wú)證書簽密方案[4-9]。但現(xiàn)有的無(wú)證書簽密方案的安全性均建立在傳統(tǒng)數(shù)論假設(shè)的難解性之上，而隨著量子計(jì)算的不斷發(fā)展，促使我們不斷去探索能夠抗量子攻擊的簽密體制。

近年來(lái)迅速發(fā)展的格基密碼體制能夠有效地抵抗量子攻擊，文獻(xiàn)[10-11]均為已有的格基簽密方案，而這些方案以格上的陷門生成算法和原像抽樣算法為基礎(chǔ)，計(jì)算開銷較大。路秀華等[12]于2016年提出了一種無(wú)陷門格基簽密方案，有效地改善格基密碼體制中由于陷門生成算法和原像抽樣算法而使得算法計(jì)算復(fù)雜的問(wèn)題。2019年，Wang等[13]提出了無(wú)陷門格上基于身份的簽密方案。文獻(xiàn)[14-16]將格理論與無(wú)證書密碼體制相聯(lián)系，構(gòu)造出格基無(wú)證書加密或簽名方案。本文利用Galbraith等[17]提出的簽名方案及路秀華等[12]的無(wú)陷門格基簽密方案，結(jié)合無(wú)證書密碼體制，提出了第一個(gè)格基無(wú)證書簽密方案。

1 基礎(chǔ)知識(shí)

1.1 符號(hào)說(shuō)明

1.2 涉及的格中定義

1.3 無(wú)證書簽密方案及安全模型[18]

文獻(xiàn)[18]詳細(xì)地給出了無(wú)證書簽密方案的形式化定義及其安全模型。其中，無(wú)證書簽密方案的通信模型如圖1所示。

圖1 無(wú)證書簽密方案的通信模型

其中，m為明文，σ為密文，IDi為用戶i的身份信息，(PKi,Si)為用戶i的公私鑰對(duì)，(xi,Di)分別為用戶i的秘密值信息及其部分私鑰。

圖2 類型I適應(yīng)性選擇密文攻擊游戲

圖3 類型II適應(yīng)性選擇密文攻擊游戲

圖4 類型I適應(yīng)性選擇消息攻擊游戲

圖5 類型II適應(yīng)性選擇消息攻擊游戲

2 簽密方案

2.1 系統(tǒng)建立：由KGC執(zhí)行

(2) 設(shè)置一個(gè)安全的理想對(duì)稱加密算法(Ek,Dk)，其中k∈Σ。

(3) Hash函數(shù)：

H2:{0,1}n→Σ

H3:{0,1}*×{0,1}*→Π

2.2 設(shè)置秘密值

2.3 部分私鑰提取

2.4 設(shè)置私鑰

用戶收到(T2,U2)后，首先驗(yàn)證A·U2=T0-T2(modq)是否成立。若成立，用戶將U2作為部分私鑰，計(jì)算全部私鑰S=U2+S1。

2.5 設(shè)置公鑰

用戶計(jì)算自身公鑰T=T0+T1-T2(modq)，并將其發(fā)送給KGC，KGC收到該公鑰后將其作為該用戶的公鑰公布出來(lái)。

2.6 簽 密

2.7 解簽密

接收者收到密文C=(μ,v1,v2)，進(jìn)行如下操作：

3 正確性分析

4 安全性分析

4.1 保密性

定理1在隨機(jī)預(yù)言模型下，若判定性LWE問(wèn)題是困難的，則該方案具有IND-CLSC-CCA2-I安全。

證明如果存在敵手I能夠攻破上述方案的IND-CLSC-CCA安全，則挑戰(zhàn)者可利用I的攻擊解決判定性LWE問(wèn)題實(shí)例(A,T*)，即能判定出T*來(lái)自下述兩種情況：

① 服從均勻分布；

(1) H0詢問(wèn)。I輸入(S2i,IDi,T1i)，隨機(jī)抽取將h0返回給I，并將元組(S2i,IDi,T1i,h0)插入列表L0中。

(2) H2詢問(wèn)。I輸入τi，隨機(jī)抽取h2τi←Σ，令h2τi=H2(τi)，將(τi,h2τi)插入列表L2中，并將h2τi返回給I。

(3) H3詢問(wèn)。I輸入(τi,μi)，隨機(jī)抽取hτi,μi←Π，令hτi,μi=H3(τi,μi)，將(τi,μi,hτi,μi)插入L3列表中，并將hτi,μi返回給I。

① 若IDi=ID*，則Si=⊥，Ti=T0+T1i-T2i(modq)，然后把元組(IDi,(⊥,⊥),E1i,Ti)插入列表LID中，更新列表L0中的元組(S2i,IDi,T1i,h0)。

(9) H1詢問(wèn)。I輸入(i,IDi)：查詢列表LID獲得IDi的公鑰Ti，接著執(zhí)行下述操作：

定理2若判定性LWE問(wèn)題在隨機(jī)預(yù)言模型下是困難的，則該方案具有IND-CLSC-CCA2-II安全。

證明該定理的證明過(guò)程類似于定理1的證明過(guò)程，通過(guò)敵手II與挑戰(zhàn)者之間的互動(dòng)游戲完成，具體如下：

H0、H1、H2、H3詢問(wèn)同定理1。

① 若IDi=ID*，則Si=⊥，計(jì)算T2i=A·h0i+E0，則Ti=T0+T1i-T2i(modq)，然后把元組(IDi,(⊥,⊥),E1i,Ti)插入列表LID中，更新列表L0中的元組(S2i,IDi,T1i,h0i)。

其余詢問(wèn)也同定理1一樣。

4.2 不可偽造性

定理3若SIS問(wèn)題在隨機(jī)預(yù)言模型下是困難的，則該方案具有EUF-CLMS-CMA-I安全。

證明如果存在敵手I能夠攻破上述方案的EUF-CLMS-CMA安全，則挑戰(zhàn)者可利用I的攻擊解決SIS問(wèn)題實(shí)例即能找到非零向量e′∈Zn，e″∈Zm，使得Ae′+e″=0(modq)。挑戰(zhàn)者和敵手I的具體交互過(guò)程如下所示：

1) 初始階段。同定理1證明中的初始階段一樣。

定理4若SIS問(wèn)題在隨機(jī)預(yù)言模型下是困難的，則該方案具有EUF-CLMS-CMA-II安全。

證明該定理的證明過(guò)程類似于定理3的證明，通過(guò)敵手II和挑戰(zhàn)者的互動(dòng)游戲完成，具體如下：

1) 初始階段。同定理2證明中的初始階段一樣。

5 性能及效率分析

本文方案與現(xiàn)有的無(wú)證書簽密方案[4,8]相比，能夠有效抵抗量子攻擊。具體如表1所示。其中“Y”表示具有某種特性，“N”表示不具有某種特性。

表1 方案性能分析表

本文方案與現(xiàn)有的格基無(wú)證書密碼(簽名/加密)方案[15-16]的密鑰生成方式不同，不依賴于格基陷門生成算法，用到一個(gè)Hash函數(shù)，并進(jìn)行了簡(jiǎn)單的矩陣線性運(yùn)算，耗時(shí)較少。本文方案為第一個(gè)格基無(wú)證書簽密方案，簽密過(guò)程不依賴于原像抽樣算法，運(yùn)算效率較高。若忽略對(duì)稱加密的運(yùn)算量，則簽密密文增量為2nlogq。若記Csample為進(jìn)行高斯抽樣時(shí)的運(yùn)算量，Cm_mul為進(jìn)行矩陣相乘時(shí)的運(yùn)算量(忽略矩陣求和運(yùn)算量)，則簽/解簽密運(yùn)算量及密鑰尺寸如表2所示。

表2 本文方案運(yùn)算量及公私鑰尺寸表

6 結(jié) 語(yǔ)

結(jié)合格上簽密方案和格基無(wú)陷門簽名方案，本文提出了第一個(gè)基于格理論的無(wú)證書簽密方案，在隨機(jī)預(yù)言模型下對(duì)方案的正確性及安全性給予證明。本文提出的格基無(wú)證書簽密體制是基本密碼體制，而研究匿名多接收者簽密、代理簽密等特殊的格基無(wú)證書簽密體制，是進(jìn)一步研究的方向。