格上两方口令认证密钥交换协议研究综述

舒 琴，王圣宝，胡 斌，路凡义

(杭州师范大学信息科学与技术学院，浙江 杭州 311121)

0 绪论

口令认证密钥交换(password-based authenticated key exchange，PAKE)协议假设通信实体之间预先共享一个低熵口令(password)，并通过该口令使通信双方或多方在不安全的信道上相互认证并协商出一个可在之后的会话中使用的会话密钥.由于口令便于记忆，具有良好的用户友好性，PAKE协议被广泛研究和部署.

随着量子计算机的发展，理论上，传统基于数论的底层困难问题大多可在多项式时间内被解决[1-3]，因此基于这些困难问题构造的PAKE协议将不再安全，构建后量子PAKE协议迫在眉睫.基于格(lattice)上难题构造的PAKE协议具有较高的渐进效率、可并行计算以及抗量子攻击等优点，因此格上PAKE协议具有非常大的研究价值.

根据协议参与方的数目，可将PAKE协议分为两方PAKE(two-party，2PAKE)协议、三方PAKE协议以及群组PAKE协议.本文主要归纳和总结近年来格上2PAKE协议的研究和发展现状，并着重从安全性和效率两方面对现有协议进行分析与比较.

1 背景知识

1.1 标准格和理想格

格理论最初作为一种密码分析工具被引入到密码学中.格，又称标准格，是线性空间Rn上n个线性无关向量v1,…,vn组成的点的集合，表示为L={a1v1+…+anvn|ai为整数}，其中v1,…,vn被称为格基.

1.2 LWE和RLWE

2005年，Regev[5]提出了带误差学习(learning with errors，LWE)问题，指出求解LWE问题可以规约到求解格上最坏情况困难问题，如最短线性向量无关问题.

定义1(LWE分布)：对于正整数n≥1，q≥2，设为n维q阶整数群，χγ为q上以γ为标准差，0为分布中心，r为半径的高斯离散分布.设固定矩阵s∈为秘密值，在q上的LWE分布As,χγ通过均匀随机地选择矩阵进行采样，并得到采样结果(a,b=s·a+e(modq)).

定义2(LWE问题)：给定多项式个独立样本(ai,bi)∈q，任意概率多项式时间(probabilistic polynomial-time，PPT)算法A能够区分样本是取自LWE分布As,χγ还是均匀独立地取自q的优势可忽略.

2010年，Lyubashevsky等[4]提出了基于理想格的环上误差学习(ring learning with errors，RLWE)问题，指出求解RLWE问题的难度可以量子规约到求解格上最坏情况困难问题.

定义3(RLWE分布)：设R为上阶数为n的多项式环，Rq=R/qR为以正整数q为模的商环，χγ为R上以γ为标准差，0为分布中心，r为半径的高斯离散分布.设固定向量s∈Rq为秘密值，在Rq×Rq上的RLWE分布As,χγ通过均匀随机地选择向量a∈Rq，e∈χγ进行采样，并得到采样结果(a,b=s·a+e(modq)).

定义4(判定RLWE问题)：给定多项式个独立样本(ai,bi)∈Rq×Rq，PPT算法A能够区分样本是取自RLWE分布As,χγ还是均匀随机地取自Rq×Rq的优势可忽略.

1.3 平滑投射函数

2002年，Cramer和Shoup[6]首次构造出平滑投射函数(smooth projective hash functions，SPHF)，它是一种定义在NP类语言L上的特殊哈希证明系统，其中X为一个集合，L⊂X.通常包含5个关键函数：

·HashKG(L,param) 产生一个私有散列密钥hsk；

· ProjKG(hsk,(L,param),W) 产生一个公开映射密钥hpk；

· Hash(hsk,(L,param),W) 计算散列值v∈G，W包含消息及其标记的密文；

· ProjHash(hpk,(L,param),W,ω) 计算映射散列值v’∈G，其中ω为W∈L的证据.

SPHF需要满足正确性和平滑性：

· 正确性 若L为NP类语言，ω为W∈L的证据，对于所有的(hsk,hpk)对，满足ProjHash(hpk,(L,param),W,ω)=Hash(hsk,(L,param),W).

· 平滑性 若L为NP类语言，hpk=ProjKG(hsk,(L,param)，W∈RXL，v是由Hash(hsk,(L,param),W)计算得出还是从G上随机选取计算不可区分.因此，除非拥有ω，否则即使知道hpk和W也无法计算出v.

1.4 误差纠错码

由于(R)LWE问题固有的误差问题，2PAKE协议双方无法得到完全相同的会话密钥.为解决这一问题，Katz等[7]提出使用误差纠错码(error-correcting code，ECC)使双方计算出相同的会话密钥.ECC包括编码函数ECC(·)和译码函数ECC-1(·).

令ECC：{0,1}l→{0,1}n，A随机选择或计算出一个会话密钥sk∈{0,1}l，计算c=ECC(sk)，Δ=tk⊕c，其中tk为A计算出带误差的会话秘密.之后将Δ发送给B.B收到Δ后计算sk=ECC-1(tk′⊕Δ)，其中tk′为B计算出的带误差的会话秘密.最后，通信双方得到一致的会话密钥sk.

1.5 Ding式误差调和机制

2012年，Ding等[8]首次提出误差调和机制(简称Ding式REC)，具体描述如下：

对于奇数q，在(R)LWE分布中采用偶数误差采样(例如计算b=s·a+2e(modq))，使通信方得到近似相等的值.定义区间}.对于w,v∈q，w=v+2e(modq)，定义两个函数：

(2)模函数Mod2(·):q×{0,1}→{0,1}如

定义5(Ding式REC的正确性)：假设通信双方分别拥有v∈q和w=v+2e(modq)∈q，其中一方发送信号比特σ=Cha(v)后，双方均对v和w应用模函数Mod2(·)，当且仅当|e|

2 格上2PAKE协议

图1 2PAKE系统模型图Fig.1 2PAKE system model

2PAKE系统模型图如图1所示.2PAKE协议适用于客户端-服务器环境，参与者为一个客户端和一个服务器，其中，客户端持有口令PW，服务器持有PW或一个与PW相关的值，两者通过口令交换认证信息建立会话密钥.构造格上2PAKE协议的思路主要有两种，思路一为结合基于格上难题的公钥加密方案(public key excryption，PKE)和SPHF构造格上2PAKE协议；思路二是将现有基于数论难题的2PAKE协议的底层困难问题替换为格上难题，即将传统2PAKE协议改进为格上2PAKE协议.

2.1 构造思路一：基于PKE和SPHF构造

图2 Katz-2PAKE协议描述Fig.2 The description of Katz-2PAKE protocol

2009年亚密会上，Katz等[7]将Cramer和Shoup[6]提出的SPHF改进为基于LWE问题的近似平滑投射函数(approximate SPHF，ASPHF).相较于SPHF，ASPHF只需要满足近似正确性.同时，他们基于Gentry和Peikert等[9-10]的工作构造了首个基于LWE问题的PKE方案，该方案在标准模型下具有IND-CCA安全.最后，他们将该PKE方案与ASPHF应用到KOY/GL框架[11]上，构建出了第一个格上三轮2PAKE协议，称为Katz-2PAKE，协议描述如图2所示，其安全性在通用字符串(common reference string model，CRS)模型[12]下予以证明.

2011年，Ding等[13]指出ASPHF无法直接应用于JG/GK框架[14]，他们对JG/GK框架[14]作出改进后，基于其构造了一个新的格上三轮2PAKE协议，称为Ding-2PAKE.Ding-2PAKE中的客户端应用了Gentry等[9]提出的基于LWE问题的PKE及其相应的ASPHF，该PKE在标准模型下具有IND-CPA安全.Ding-2PAKE中的服务器应用了Peikert[10]提出的PKE，该PKE同样基于LWE问题且在标准模型下具有IND-CCA安全.2010年，Groce和Katz[14]指出基于CCA安全的格上PKE构造的SPHF会增加2PAKE协议的复杂度.Ding-2PAKE中使用的ASPHF基于CPA安全的PKE构造，相较于Katz-2PAKE而言更加简洁.

2017年亚密会上，Zhang等[15]首先对ASPHF做出改进，构造出具有强平滑性的非适应ASPHF.随后，在随机预言(random oracle，RO)模型下，他们构造了一个高效的非交互式零知识(non-interactive zero-knowledge，NIZK)证明[16].在NIZK证明的基础上，他们提出了一个新的可拆分PKE方案.最后，基于该PKE和非适应性ASPHF，他们在RO模型下构造出一个高效的格上两轮2PAKE协议，称为Zhang-2PAKE.Zhang等认为Zhang-2PAKE的效率将O(logn)倍高于Katz-2PAKE的效率.

2018年，Li等[17]指出Zhang-2PAKE依赖于RO模型下的NIZK证明，安全性不能完全得到保证.因此，他们构造了首个不使用NIZK证明的格上两轮2PAKE协议，称为Li-2PAKE，协议描述如图3所示.对客户端和服务器，他们分别构造了一个新的格上SPHF：客户端的称为MP-SPHF，适用于Micciancia和Peikert[18]提出的基于LWE问题、标准模型下IND-CCA安全的PKE；服务器端的称为Reg-SPHF，适用于Regev等[5]提出的基于LWE问题、标准模型下IND-CPA安全的PKE.之后，他们将MP-SPHF和Reg-SPHF应用于Abdalla等[19]设计的PAKE框架，构造出Li-2PAKE，并在Bellare-Pointcheval-Rogaway(简称BPR)模型[20]下证明其安全性.

图3 Li-2PAKE协议描述Fig.3 The description of Li-2PAKE protocol

2019年，Karbasi等[21]对SPHF进行改进，构造出首个基于RLWE问题的SPHF，称为Ring-SPHF.基于Ring-SPHF，他们构造了一个基于理想格的三轮2PAKE协议，称为Karbasi-2PAKE.在客户端应用Lyubashevsky等[22]构造的基于RLWE问题、标准模型下CPA安全的PKE；在服务器端应用了Peikert[23]构造的基于RLWE问题、标准模型下CCA安全的PKE.

2.2 基于思路一构造的2PAKE的对比

表1给出了采用思路一(基于PKE和SPHF)构造的格上2PAKE协议的性能对比.从表1可以看出，在安全方面，Katz-2PAKE中的会话密钥由客户端随机选择后发送给服务器，而Zhang-2PAKE中的会话密钥则由服务器随机选择后发送给客户端，它们均不是由两端协商得出的，存在安全隐患——会话密钥的安全性仅依赖于某一端随机数的安全.此外，表中除了Karbasi-2PAKE基于理想格上的RLWE问题，其余都是基于标准格上的LWE问题.2016年，Bos等[24]指出，相较于标准格，理想格具有更高的计算效率和存储效益，但是附加的环结构无法保证基于其提出问题的困难性.在效率方面，Ding-2PAKE、Li-2PAKE和Karbasi-2PAKE应用的2PAKE框架都将某一端使用的安全组件PKE的安全需求由CCA安全降为CPA安全.众所周知，对于协议框架来说，对所需组件的安全性要求越低，则实例化的协议越高效.其中，Ding-2PAKE和Karbasi-2PAKE在服务器端未构造SPHF，可使协议的运行效率有所提高.另外，Zhang-2PAKE和 Li-2PAKE具有较少的通信轮数，且Li-2PAKE无需处理LWE问题固有的误差问题，能节省部分计算时间.总体上，Li-2PAKE在现有基于PKE和SPHF构造的格上2PAKE协议中表现突出.基于PKE和SPHF构造的2PAKE协议可从如下3个方面提高安全性及效率：1)对于安全需求较高的协议在标准格上基于LWE问题构造，避免在理想格上构造；2)降低协议中安全组件PKE的安全需求；3)减少SPHF的构造数量或提高SPHF的计算效率.

表1 采用思路一构造的格上2PAKE性能对比Tab.1 Performance comparison of 2PAKE from lattices constructed by idea one

2.3 构造思路二：改进现有基于数论的2PAKE协议

图4 RLWE-PAK协议描述Fig.4 The description of RLWE-PAK protocol

图5 RLWE-SRP协议描述Fig.5 The description of RLWE-SRP protocol

2.4 基于思路二构造2PAKE的对比

表2给出了采用思路二(改进现有基于数论的2PAKE协议)构造的格上2PAKE协议及两个经典的基于数论的2PAKE协议的性能对比，这两个基于数论的2PAKE协议为SRP协议[28]和J-PAKE协议[30].其中PLWE-PAK和RLWE-PPK的计算时间数据来自文献[31]，其余数据来自文献[27]，测试平台相同.在表2中，C代表客户端，S代表服务器；C→S代表客户端给服务器发送消息，S→C代表服务器给客户端发送消息.

表2 采用思路二构造的格上2PAKE性能对比Tab.2 Performance comparison of 2PAKE from lattices constructed by idea two

从表2上可以看出，虽然在通信开销上，3个基于格的2PAKE协议普遍高于SRP和J-PAKE，但是在安全性和计算效率方面，这3个基于格的2PAKE协议都优于SRP和J-PAKE.总体上，基于思路二构造的格上2PAKE协议参数尺寸合理、计算高效、实用性较高.

3 总结与展望

格上口令认证密钥交换是近年来密码协议领域的一个新兴研究方向，近年来它在两方协议方面有了长足的发展.我们从构造思路出发，将现有协议分为如下两类：基于公钥加密方案和平滑投射函数的构造以及将现有协议基于传统的困难问题替换为格上难题的构造.从总结与分析可以看出，基于LWE和RLWE问题构造的口令认证密钥交换协议，其通信量合理、计算高效，是后量子认证密钥交换协议的主流方向.

与此同时，现阶段在这个研究方向上也存在大量的开放性问题.例如，现有协议中的口令普遍以明文或口令的哈希形式存储在服务器上，这将导致当服务器信息泄露后，敌手可实施伪装攻击；另外，现有格上2PAKE协议中，基于PKE与SPHF构造的协议还缺少部署实现，协议的实用性缺乏验证.因此，如何避免将口令直接或间接存储在服务器上，以及如何进一步提高格上2PAKE协议的计算及通信效率是未来值得研究的方向.