基于理想格的通用可組合兩方口令認證密鑰交換協議

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

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

1 引言

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

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

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

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

2 預備知識

2.1 理想格

2.2 環上帶誤差學習問題

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

2.3 Peikert式誤差調和機制

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

2.4 安全模型

本文設計的協議的安全性在Canetti等人[11]提出的UC框架下，結合Canetti-Rabin[19]提出的具有聯合狀態的UC(Joint state UC，JUC)定理，使用UC混合模型證明。

3 基于理想格的兩方PAKE協議

3.1 協議描述

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

3.1.1 初始化階段

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

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

3.2 方案的正確性

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

4 安全性證明

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

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

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

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

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

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

表1 UC框架不可區分性證明概覽

引理 2 游戲 G1和游戲G 2對于任意環境 Z都是計算不可區分的。

引理 4 游戲G 3與游戲G 4對于任意環境 Z都是計算不可區分的。

5 效率分析

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

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

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

6 結束語

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