基于理想格的通用可組合兩方口令認(rèn)證密鑰交換協(xié)議

舒 琴 王圣寶 路凡義 韓立東 譚 肖

(杭州師范大學(xué)信息科學(xué)與工程學(xué)院 杭州 311121)

1 引言

兩方口令認(rèn)證密鑰交換協(xié)議(Two-Party password-based Authenticated Key Exchange，2PAKE)能夠使得協(xié)議參與者使用低熵、易于記憶的口令(password)協(xié)商生成一個(gè)高熵的會(huì)話密鑰。

目前，大多傳統(tǒng)基于數(shù)論的底層困難問(wèn)題都存在量子解決算法[1，2]。因此，隨著量子計(jì)算機(jī)的發(fā)展，基于這些難題構(gòu)造的密碼協(xié)議或方案正面臨所謂的量子威脅。同時(shí)，應(yīng)對(duì)量子威脅的所謂“后量子密碼”研究方興未艾。其中，基于格(lattice)上難題(簡(jiǎn)稱格基)的2PAKE協(xié)議的研究成為熱點(diǎn)之一。2009年，Katz等人[3]構(gòu)造了首個(gè)格基2PAKE協(xié)議。該協(xié)議的安全性在基于不可區(qū)分的公共參考串(Common Reference String，CRS)模型[4]下得到證明。隨后，Ding等人[5]和Zhang等人[6]各自構(gòu)造出新的格基2PAKE協(xié)議，同樣在CRS模型下證明了安全性。此后，又有多個(gè)格基2PAKE協(xié)議陸續(xù)被提出[7—9]，它們使用的安全模型皆為BPR模型[10]。

CRS模型與BPR模型沒(méi)有考慮到協(xié)議的可組合性以及口令的相關(guān)性。相較而言，通用可組合(Universally Composable，UC)模型[11]則很好地解決了這些問(wèn)題。2017年，Gao等人[12]基于SRP協(xié)議[13]，提出了一個(gè)格基擴(kuò)展版本協(xié)議，稱為RLWESRP。另外，RLWE-SRP采用了由Ding等人[14]所提出的誤差調(diào)和機(jī)制。但是，該機(jī)制效率較低，使得協(xié)議雙方提取出的共同比特只是具有高熵，而并非均勻分布，需要一個(gè)隨機(jī)提取器來(lái)獲得均勻的值。相比而言，Peikert[15]于2014年提出的改進(jìn)誤差調(diào)和機(jī)制能夠使協(xié)議雙方所提取的共同比特滿足均勻分布。

采用Peikert式誤差調(diào)和機(jī)制，本文提出一個(gè)更高效的具有通用可組合性的格基2PAKE協(xié)議，稱為RLWE-CAPAKE，并在UC框架下證明其安全性。新協(xié)議的設(shè)計(jì)思想來(lái)源于Abdalla等人[16]于2008年提出的CAPAKE協(xié)議。新協(xié)議既保持了CAPAKE協(xié)議的優(yōu)勢(shì)，又能抵抗量子攻擊。

2 預(yù)備知識(shí)

2.1 理想格

2.2 環(huán)上帶誤差學(xué)習(xí)問(wèn)題

2010年，Lyubashevsky等人[17]提出了基于理想格的環(huán)上帶誤差學(xué)習(xí)(Ring Learning With Errors，RLWE)問(wèn)題，并指出求解RLWE問(wèn)題的難度可以量子規(guī)約到求解近似最短向量問(wèn)題。被密碼學(xué)界普遍認(rèn)為能夠抵抗量子攻擊。

2.3 Peikert式誤差調(diào)和機(jī)制

RLWE問(wèn)題固有的誤差問(wèn)題會(huì)導(dǎo)致通信雙方無(wú)法得到完全相同的會(huì)話密鑰。為解決這一問(wèn)題，Ding等人[14]在2012年首次提出誤差調(diào)和機(jī)制(稱為Ding式誤差調(diào)和機(jī)制)。2014年，Peikert[15]指出Ding式誤差調(diào)和機(jī)制中協(xié)議雙方提取出的共同比特只是具有高熵，而并非均勻分布，需要一個(gè)隨機(jī)提取器來(lái)獲得均勻的值，這會(huì)帶來(lái)較大的效率損失。他提出一個(gè)改進(jìn)的誤差調(diào)和機(jī)制(Peikert式誤差調(diào)和機(jī)制)，該機(jī)制中協(xié)議雙方提取的共同比特均勻分布。Peikert式誤差調(diào)和機(jī)制具體描述如下：

2.4 安全模型

本文設(shè)計(jì)的協(xié)議的安全性在Canetti等人[11]提出的UC框架下，結(jié)合Canetti-Rabin[19]提出的具有聯(lián)合狀態(tài)的UC(Joint state UC，JUC)定理，使用UC混合模型證明。

3 基于理想格的兩方PAKE協(xié)議

3.1 協(xié)議描述

相較于Abdalla等人[16]提出的CAPAKE協(xié)議，本文提出的新協(xié)議具有如下兩個(gè)優(yōu)勢(shì)：(1)基于RLWE難題、采用文獻(xiàn)[15]改進(jìn)的誤差調(diào)和機(jī)制，被密碼學(xué)界普遍認(rèn)為可以抵抗量子攻擊；(2)新協(xié)議中，服務(wù)器不直接存儲(chǔ)用戶的口令，而只存儲(chǔ)服務(wù)器ID及用戶口令的哈希值HPW=H0(S||PW)。實(shí)際應(yīng)用中，“單口令多用途”現(xiàn)象比較普遍，即用戶往往針對(duì)許多不同的應(yīng)用服務(wù)器使用相同的口令。該改進(jìn)避免了當(dāng)服務(wù)器淪陷后，敵手可直接獲得用戶口令，從而可向其他服務(wù)器冒充為用戶的風(fēng)險(xiǎn)。

3.1.1 初始化階段

用戶加入系統(tǒng)時(shí)，需向服務(wù)器注冊(cè)。用戶 U 將其口令PW及服務(wù)器ID即S 輸入哈希函數(shù)H0(·)計(jì)算得到HPW，同時(shí)從商群Rq中均勻隨機(jī)選擇公共參數(shù)a，將用戶ID即U ， HPW及a通過(guò)安全信道發(fā)送給服務(wù)器 S。S 收到U 的注冊(cè)信息后將〈U，HPW，a〉添加到存儲(chǔ)在數(shù)據(jù)庫(kù)中的列表 L上，本文設(shè)定外部敵手無(wú)法獲得服務(wù)器內(nèi)部信息。

3.1.2 相互認(rèn)證及密鑰交換階段

3.2 方案的正確性

圖1 RLWE-CAPAKE的相互認(rèn)證及密鑰交換過(guò)程

4 安全性證明

(1)TestPwd查詢：參與者完全被模擬時(shí)，驗(yàn)證某一方的口令是否為想要的那個(gè)口令；

(2)NewKey查詢：參與者完全被模擬且口令未泄露時(shí)，驗(yàn)證兩方是否擁有相同的口令；

(3)GoodPwd查詢：參與者未完全被模擬時(shí)，驗(yàn)證某一方的口令是否為想要的那個(gè)口令；

(4)SamePwd查詢：參與者未完全被模擬且口令未泄露時(shí)，驗(yàn)證兩方是否擁有相同的口令。具體證明過(guò)程如下：

游戲 G0：該游戲是環(huán)境 Z與現(xiàn)實(shí)世界的敵手A及RLWE-CAPAKE協(xié)議的實(shí)例在隨機(jī)預(yù)言模型以及理想密碼模型下進(jìn)行交互。

游戲 G1：理想攻擊者S 模擬隨機(jī)預(yù)言機(jī)和加解密預(yù)言機(jī)。

表1 UC框架不可區(qū)分性證明概覽

引理 2 游戲 G1和游戲G 2對(duì)于任意環(huán)境 Z都是計(jì)算不可區(qū)分的。

引理 4 游戲G 3與游戲G 4對(duì)于任意環(huán)境 Z都是計(jì)算不可區(qū)分的。

5 效率分析

本節(jié)從安全性和計(jì)算與通信效率兩方面對(duì)本文所提出的新協(xié)議與Ding等人[7]提出的PAK理想格擴(kuò)展協(xié)議(RLWE-PAK)及Gao等人[12]提出的SRP理想格擴(kuò)展協(xié)議(RLWE-SRP)進(jìn)行比較。Ding式REC代表Ding式誤差調(diào)和機(jī)制，Peikert式REC代表Peikert式誤差調(diào)和機(jī)制。

如表2所示，這3個(gè)協(xié)議均基于RLWE問(wèn)題，且通信開銷也基本相同。RLWE-PAK與本文新協(xié)議的環(huán)運(yùn)算次數(shù)基本相同，但是它的安全性證明基于BPR模型。如前所述，該模型相對(duì)UC模型而言不夠完善。進(jìn)一步，相比RLWE-SRP協(xié)議，雖然兩者都在UC框架下被證明安全性，但是，本文新協(xié)議具有更少的環(huán)運(yùn)算次數(shù)，即具有更高的計(jì)算效率。因此，綜合而言，新協(xié)議具有更高的安全性和更好的效率。

表2 理想格上口令基2PAKE協(xié)議的性能比較

6 結(jié)束語(yǔ)

本文提出了一個(gè)基于RLWE問(wèn)題的2PAKE協(xié)議，并在UC框架下詳細(xì)證明了其安全性。新協(xié)議采用了更加高效的誤差調(diào)和機(jī)制。通過(guò)與現(xiàn)有相關(guān)協(xié)議進(jìn)行比較，結(jié)果表明了新協(xié)議具有更高的安全性和計(jì)算效率。