歐海文 施 瑞 王佳琳

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

0 引 言

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

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

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

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

1.2 涉及的格中定義

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

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

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

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

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

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

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

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

2 簽密方案

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

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

(3) Hash函數(shù)：

H2:{0,1}n→Σ

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

2.2 設(shè)置秘密值

2.3 部分私鑰提取

2.4 設(shè)置私鑰

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

2.5 設(shè)置公鑰

用戶(hù)計(jì)算自身公鑰T=T0+T1-T2(modq)，并將其發(fā)送給KGC，KGC收到該公鑰后將其作為該用戶(hù)的公鑰公布出來(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詢(xún)問(wèn)。I輸入(S2i,IDi,T1i)，隨機(jī)抽取將h0返回給I，并將元組(S2i,IDi,T1i,h0)插入列表L0中。

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

(3) H3詢(xún)問(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詢(xún)問(wèn)。I輸入(i,IDi)：查詢(xún)列表LID獲得IDi的公鑰Ti，接著執(zhí)行下述操作：

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

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

H0、H1、H2、H3詢(xún)問(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)。

其余詢(xún)問(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ò)程類(lèi)似于定理3的證明，通過(guò)敵手II和挑戰(zhàn)者的互動(dòng)游戲完成，具體如下：

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

5 性能及效率分析

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

表1 方案性能分析表

本文方案與現(xiàn)有的格基無(wú)證書(shū)密碼(簽名/加密)方案[15-16]的密鑰生成方式不同，不依賴(lài)于格基陷門(mén)生成算法，用到一個(gè)Hash函數(shù)，并進(jìn)行了簡(jiǎn)單的矩陣線性運(yùn)算，耗時(shí)較少。本文方案為第一個(gè)格基無(wú)證書(shū)簽密方案，簽密過(guò)程不依賴(lài)于原像抽樣算法，運(yùn)算效率較高。若忽略對(duì)稱(chēng)加密的運(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ú)陷門(mén)簽名方案，本文提出了第一個(gè)基于格理論的無(wú)證書(shū)簽密方案，在隨機(jī)預(yù)言模型下對(duì)方案的正確性及安全性給予證明。本文提出的格基無(wú)證書(shū)簽密體制是基本密碼體制，而研究匿名多接收者簽密、代理簽密等特殊的格基無(wú)證書(shū)簽密體制，是進(jìn)一步研究的方向。