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

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

1 引言

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

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

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

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

2 預備知識

2.1 理想格

2.2 環(huán)上帶誤差學習問題

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

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

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

2.4 安全模型

本文設計的協(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é)議具有如下兩個優(yōu)勢：(1)基于RLWE難題、采用文獻[15]改進的誤差調(diào)和機制，被密碼學界普遍認為可以抵抗量子攻擊；(2)新協(xié)議中，服務器不直接存儲用戶的口令，而只存儲服務器ID及用戶口令的哈希值HPW=H0(S||PW)。實際應用中，“單口令多用途”現(xiàn)象比較普遍，即用戶往往針對許多不同的應用服務器使用相同的口令。該改進避免了當服務器淪陷后，敵手可直接獲得用戶口令，從而可向其他服務器冒充為用戶的風險。

3.1.1 初始化階段

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

3.1.2 相互認證及密鑰交換階段

3.2 方案的正確性

圖1 RLWE-CAPAKE的相互認證及密鑰交換過程

4 安全性證明

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

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

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

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

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

游戲 G1：理想攻擊者S 模擬隨機預言機和加解密預言機。

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

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

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

5 效率分析

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

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

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

6 結(jié)束語

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