格上基于口令的三方认证密钥交换协议

于金霞，廉欢欢，汤永利，史梦瑶，赵宗渠



格上基于口令的三方认证密钥交换协议

于金霞，廉欢欢，汤永利，史梦瑶，赵宗渠

（河南理工大学计算机科学与技术学院，河南 焦作 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)