格上基于口令的三方認證密鑰交換協議

于金霞，廉歡歡，湯永利，史夢瑤，趙宗渠

?

格上基于口令的三方認證密鑰交換協議

于金霞，廉歡歡，湯永利，史夢瑤，趙宗渠

（河南理工大學計算機科學與技術學院，河南 焦作 454000）

三方口令認證密鑰交換協議允許用戶通過一個服務器在不安全的信道中建立一個受保護的會話密鑰，而現有的格上PAKE協議絕大多數都是針對兩方設計的，無法適用于大規模的通信系統。基于此，提出一種新的格上三方PAKE協議，該協議主要以可拆分公鑰加密體制及其相應的近似平滑投射散列函數為基礎進行構造，并通過在協議中引入消息認證機制的方式來防止消息重放攻擊。與同類協議相比，所提協議減少了通信輪數，提高了效率和協議應用的安全性。

三方密鑰交換；口令認證；LWE問題；可證安全性

1 引言

在基于口令的認證密鑰交換（PAKE, password-based authenticated key exchange）協議中，用戶之間通過共享一個普通的低熵口令來認證通信方身份并進行密鑰交換，最后建立共享的會話密鑰。口令具有簡單易記、操作方便的特點，基于口令的方案可以消除對公鑰基礎設施和安全硬件的依賴，且提高了系統的使用便利性。因此，基于口令的認證密鑰交換協議是目前應用最為廣泛的一種密鑰交換協議[1-7]。

兩方PAKE（2PAKE, two-party PAKE）協議需要每兩個參與者共享一個口令建立會話密鑰，但是這種方案在大量的用戶通信中對口令存儲比較復雜，需要消耗較高的管理成本。而三方PAKE（3PAKE, three-party PAKE）協議使每個用戶只需和服務器共享一個口令來進行認證，解決了2PAKE的局限性。

第一個真正意義上的PAKE協議最早由Bellovin等[1]提出，其安全性的分析采用啟發式方法。2001年，Katz，Ostrovsky和Yung[2]利用CCA2（adaptive chosen-ciphertext attack）安全的加密體制及相應的平滑投射散列（SPH, smooth projection hash）函數進行密鑰交換，提出第一個標準模型下的高效PAKE協議，簡稱KOY協議。2012年，Zhao等[3]基于CDH假設給出了一種可證明安全的3PAKE協議，協議利用陷門測試技術在3eCK模型下給出安全性證明。2015年，Farash等[4]提出了改進的PAKE協議，克服協議不能抵抗離線字典攻擊的不足，且提供了會話密鑰的前向保密性。隨后，密碼學者基于不同密碼學組件設計了不同效率和安全性的PAKE協議[5-6]。

上述協議的安全性證明絕大多數都是依賴于大整數分解和離散對數問題的困難性，這些困難問題已經可以用量子算法在多項式時間內解決。而基于格困難問題的公鑰密碼體制在量子計算下還不存在多項式時間高效求解算法，并且格上的運算是矩陣–向量上的乘法，具備并行計算、效率高的特點。因此，設計一個基于格困難問題的口令認證密鑰交換協議變得尤為重要。

在基于格理論的密碼體制中，對PAKE的研究比較缺乏，直到2009年Katz等[7]才構造出了首個基于格的CCA安全的加密體制及其相應的近似平滑投射散列（ASPH, approximate smooth projection hash）函數，將這些組件與KOY協議[2]以及Gennaro-Lindell協議[8]相結合，提出第一個基于格的2PAKE協議。2011年，Ding等[9]將Katz等[8]提出的加密體制和近似平滑投射函數應用于Groce-Katz框架[10]，提出了一種基于格困難問題假設且效率較高的協議，并且在標準模型下給出此協議安全性證明。2013年，葉茂等[11]利用Katz等[8]提出的公鑰加密體制以及ASPH函數組件，基于LWE問題設計了第一個基于格的3PAKE協議，提高了安全性并滿足大規模通信系統的應用需求，但仍存在通信效率較低的缺陷。2014年，Peiker[12]提出一種基于環上帶誤差學習（RLWE, ring learning with error）的簡單低帶寬調和函數，利用這種技術構造密鑰封裝機制，實現了密鑰交換。2015年，Zhang等[13]基于RLWE困難問題提出2PAKE協議，并給出安全性證明，但不適用于大規模的通信系統。2016年，趙秀鳳等[14]利用格困難問題提出一種密鑰交換協議，但該協議需要密鑰生成中心生成長期私鑰和臨時私鑰，成本花銷大。2017年，Xu等[15]利用DH思想，基于環上LWE（learning with error）問題提出了可證明安全的3PAKE協議，但該協議存在效率低等局限。

2017年，Zhang等[16]將拆分的公鑰加密體制應用于Katz等[7]的3次通信的框架中，提出了基于格困難問題且僅需兩輪通信、效率較高的PAKE協議，但該方案是兩方的口令密鑰交換協議。由于三方PAKE協議建立最終的會話密鑰需要融合所有用戶的信息，那么需要添加函數對用戶端信息進行計算，因此文獻[16]提出的2PAKE協議無法直接應用于三方協議中。另外，三方協議在引入可信服務器后，用戶端與服務器進行通信時會存在消息重放的可能性。

為解決上述協議存在的問題，本文提出一種新的基于LWE問題的三方PAKE協議。主要貢獻有以下兩個方面：1) 在文獻[16]的基礎上，添加偽隨機函數來融合所有用戶端的信息，并且在協議中引入消息認證機制，通過添加會話序列號的方式達到抵抗消息重放的目的，使本文所提三方協議更具有可行性；2) 利用拆分的公鑰加密體制及相應的ASPH函數這兩個組件構造協議，從而提高了通信效率。本文所提協議解決了2PAKE的局限，避免了消息重放攻擊的弱點，具備抗量子攻擊的特點，有較少的通信輪數和更高的通信效率。

2 背景知識

2.1 格的相關知識

2.2 安全模型

本節是在Bellare等[18]所提出模型（簡稱為BPR模型）基礎上給出的本文協議的安全性分析模型。該協議依賴于一個假設：在協議執行之前，可信第三方制定公共參考串（CRS, common reference string）和其他公共參數。

2.3 基于格的公鑰加密體制

基于格的公鑰加密體制具體如下。

2.4 近似平滑投射散列函數

平滑投射散列函數是由Cramer等[21]為實現CCA安全的公鑰加密體制首次提出來的，后來在PAKE協議方面的一些研究[7,22]延伸了這個概念。本文采用文獻[16]構造的基于格的PAKE協議的ASPH函數，此構造[16]根據文獻[7]進行了修改。

3 基于格的三方PAKE協議

3.1 協議描述

本節基于文獻[16]提出的可拆分公鑰密碼體制，利用ASPH函數簇這個組件設計一種格上的基于口令的三方認證密鑰交換協議。協議中的符號說明如表1所示。

表1 基于格的三方協議PAKE協議中的符號說明

圖1 基于格的三方PAKE協議

基于格的三方PAKE協議的兩輪消息認證中，第一輪用戶向服務器發送的密文中包含帶標簽的密文，服務器通過檢驗密文的有效性實現服務器對用戶的顯示認證，在第二輪中實現了用戶對服務器的顯示認證，因此本文協議實現了用戶與服務器的雙向認證。

3.2 安全性證明

本節在2.2節所述的安全模型證明了協議的安全性。

目前已完成與用戶相關的send詢問的修改，同樣地，與用戶相關的send詢問的修改類似于此方式。

4 性能分析

在安全性方面，本文協議在方案中添加會話序列號，提供了更強的消息認證機制，由表2可以看出，與其他協議[11,15-16]相比，本文協議可以抵抗重放攻擊，安全性能更高。

在效率方面，本文協議利用改進的基于格的CCA安全的公鑰加密體制，減少了加密參數，降低了計算代價。由表2可以看出，與其他協議相比[11,15-16]，本文協議的服務器計算開銷和用戶計算開銷都較低。此外，本文協議只需要兩輪通信，通信開銷主要由密文和投射密鑰的大小來決定，而投射密鑰只依賴于散列密鑰，這使本文協議的通信效率提高。

X-PAKE協議提出基于格的3PAKE協議，通信輪數為3輪，消息傳輸量為6條，通信代價主要取決于多項式環和多個散列函數計算得出的值，由于協議需要傳輸的消息量較多，造成通信開銷增大。根據分析和表2數據可得，X-PAKE協議的通信開銷比本文協議大。

Z-PAKE協議是基于格的2PAKE協議，是針對兩方設計的，不適用于大規模的通信系統，協議需要兩輪通信，通信代價主要取決于密文和投射密鑰的大小，本文協議和Z-PAKE協議相比，除了多一個用戶同樣的開銷之外，并沒有增加其他較大的開銷。但是Z-PAKE協議按照傳統的方式實現為3PAKE協議，至少需要4輪通信，即8條消息傳輸量，而本文三方協議只需2輪通信即4條傳輸量。根據分析和表2可得，本文協議的通信開銷較低，還可以抵抗重放攻擊。

以上分析結果表明，本文協議適用于大規模的通信系統，不僅具有抵抗重放攻擊的安全性，還具有較低的通信和計算開銷。因此，本文協議更具有可行性。

表2 4種協議性能比較

5 結束語

本文提出三方的口令認證密鑰交換協議，協議中使用的密碼機制是基于格上的LWE困難問題，在后量子時代具有重要意義。三方的PAKE協議是客戶端–客戶端–服務器的形式，大量用戶只與服務器共享一個口令即可建立共享會話密鑰，因此更符合用戶端到端安全通信的需求。除此之外，本文協議可以有效抵抗攻擊者重放之前的消息，提高了協議應用的安全性。在隨機預言模型下，本文給出了嚴格的安全性證明。相比已有的同類協議，本文協議在通信效率和安全性上均有所提高。本文所設計的格上基于口令的認證密鑰交換協議，口令以明文的形式存儲在服務器上，一旦服務器信息泄露，攻擊者獲得口令后會偽裝成合法用戶與服務器通信，這將對用戶和服務器的數據安全帶來危害。因此，構造一個不讓服務器直接存儲明文口令的格上3PAKE協議是未來的研究方向。

[1] BELLOIN S M, MERRITT M. Encrypted key exchange: password-based protocols secure against dictionary attacks[C]//IEEE Symposium on Research in Security and Privacy. 1992: 72-84.

[2] KATZ J, OSTROVSKY R, YUNG M. Efficient password-authenticated key exchange using human-memorable passwords[M]. Advances in Cryptology-EUROCRYPT. 2001: 475-494.

[3] ZHAO J, GU D. Provably secure three-party password-based authenticated key exchange protocol[J]. Information Sciences, 2012, 184(1): 310-323.

[4] FARASH M S, ISLAM S H, OBAIDAT M S. A provably secure and efficient two-party password‐based explicit authenticated key exchange protocol resistance to password guessing attacks[J]. Concurrency & Computation Practice & Experience, 2015, 27(17): 4897-4913.

[5] ABLALLA M, BENHAMOUDA F, MACKENZIE P. Security of the J-PAKE password-authenticated key exchange protocol[C]//IEEE Symposium on Security and Privacy. 2015: 571-587.

[6] 魏福山, 馬建峰, 李光松, 等. 標準模型下高效的三方口令認證密鑰交換協議[J]. 軟件學報, 2016, 27(9): 2389-2399.

WEI F S, MA J F, LI G S, et al. Efficient three-party password-based authenticated key exchange protocol in the standard model[J]. Journal of Software, 2016, 27(9): 2389-2399.

[7] KATZ J, VAIKUNTANATHAN V. Smooth projective hashing and password-based authenticated key exchange from lattices[M]. Advances in Cryptology-ASIACRYPT. 2009: 636-652.

[8] GENNARO R, LINDELL Y. A framework for password-based authenticated key exchange[C]//International Conference on the Theory and Applications of Cryptographic Techniques. 2003: 524-543.

[9] DING Y, FAN L. Efficient password-based authenticated key exchange from lattices[C]//Seventh International Conference on Computational Intelligence and Security. 2012: 934-938.

[10] GROCE A, KATZ J. A new framework for efficient password-based authenticated key exchange[C]//Proceedings of the 17th ACM conference on Computer and communications security. 2010: 516-525.

[11] 葉茂, 胡學先, 劉文芬. 基于格的三方口令認證密鑰交換協議[J]. 電子與信息學報, 2013, 35(6): 1376-1381.

YE M, HU X X, LIU W F. Password authenticated key exchange protocol in the three party setting based on lattices[J]. Journal of Electronics & Information Technology, 2013, 35(6): 1376-1381

[12] PEIKERT C. Lattice cryptography for the internet[M]. Post-Quantum Cryptography. 2014: 197-219.

[13] ZHANG J, ZHANG Z, DING J, et al. Authenticated key exchange from ideal lattices[M]. Advances in Cryptology - EUROCRYPT. 2015: 719-751.

[14] 趙秀鳳, 高海英, 王愛蘭. 基于RLWE的身份基認證密鑰交換協議[J].計算機研究與發展, 2016, 53(11): 2482-2490.

ZHAO X F, GAO H Y, WANG A L. An identity-based authenticated key exchange protocol from RLWE[J]. Journal of Computer Research and Development, 2016, 53(11): 2482-2490.

[15] XU D Q, HE D B, CHOO K K R. Provably secure three-party password authenticated key exchange protocol based on ring learning with error[C]//IACR Cryptology ePrint Archive. 2017: 360.

[16] ZHANG J, YU Y. Two-round PAKE from approximate SPH and instantiations from lattices[C]//International Conference on the Theory and Application of Cryptology and Information Security. 2017: 37-67.

[17] REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C]//ACM Symposium on Theory of Computing. 2005: 84-93.

[18] BELLARE M, POINTCHEVAL D, ROGAWAY P. Authenticated key exchange secure against dictionary attacks[M]. Advances in Cryptology-EUROCRYPT. 2000: 139-155.

[19] ABE M, CUI Y, IMAI H, et al. Efficient hybrid encryption from ID-based encryption[J]. Designs Codes & Cryptography, 2010, 54(3): 205-240.

[20] RAN C, HALEVI S, KATZ J. Chosen-ciphertext security from identity-based encryption[C]//International Conference on the Theory and Applications of Cryptographic Techniques. 2004: 207-222.

[21] CRAMER R, SHOUP V. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption[C]// International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology. 2002: 45-64.

[22] KATZ J, VAIKUNTANATHAN V. Round-optimal password-based authenticated key exchange[M]. Theory of Cryptography. 2011: 293-310.

Password-based three-party authenticated key exchange protocol from lattices

YU Jinxia, LIAN Huanhuan, TANG Yongli, SHI Mengyao, ZHAO Zongqu

College of Computer Science and Technology, Henan Polytechnic University, Jiaozuo 454000, China

Password-based three-party authenticated key exchange protocol allow clients to establish a protected session key through a server over insecure channels. Most of the existing PAKE protocols on lattices were designed for the two parties, which could not be applied to large-scale communication systems, so a novel three-party PAKE protocol from lattices was proposed. The PAKE protocol was constructed by using a splittable public-key encryption scheme and an associated approximate smooth projective Hash function, and message authentication mechanism was introduced in the protocol to resist replay attacks. Compared with the similar protocols, the new protocol reduces the number of communication round and improves the efficiency and the security of protocol applications.

three-party key exchange, password authentication, LWE problem, provable security

TP309

A

10.11959/j.issn.1000-436x.2018237

于金霞（1974–），女，河南博愛人，博士，河南理工大學教授，主要研究方向為人工智能、信息安全。

廉歡歡（1993–），女，河南沁陽人，河南理工大學碩士生，主要研究方向為信息安全、密碼學。

湯永利（1972–），男，河南孟州人，博士，河南理工大學教授、碩士生導師，主要研究方向為信息安全、密碼學。

史夢瑤（1998–），女，河南許昌人，河南理工大學碩士生，主要研究方向為信息安全、密碼學。

趙宗渠（1974–），男，河南沁陽人，博士，河南理工大學講師，主要研究方向為密碼學、網絡安全、惡意代碼分析。

2018–02–05；

2018–06–09

趙宗渠，zhaozong_qu@hpu.edu.cn

國家密碼管理局“十三五”國家密碼發展基金資助項目（No.MMJJ20170122）；河南省科技廳基金資助項目（No.142300410147）；河南省教育廳基金資助項目（No.16A520013）；河南理工大學博士基金資助項目（No.B2014-044, No.B2016-39）；河南理工大學自然科學基金資助項目（No.T2018-1）

The “13th Five-Year” National Crypto Development Foundation (No.MMJJ20170122), The Project of Science and Technology Department of Henan Province (No.142300410147), The Project of Education Department of Henan Province (No.16A520013), The Doctoral Fund of Henan Polytechnic University (No.B2014-044, No.B2016-39), The Natural Science Foundation of Henan Polytechnic University (No.T2018-1)