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]，提出了一个格基扩展版本协议，称为RLWE-SRP。另外，RLWE-SRP采用了由Ding等人^[14]所提出的误差调和机制。但是，该机制效率较低，使得协议双方提取出的共同比特只是具有高熵，而并非均匀分布，需要一个随机提取器来获得均匀的值。相比而言，Peikert^[15]于2014年提出的改进误差调和机制能够使协议双方所提取的共同比特满足均匀分布。

采用Peikert式误差调和机制，本文提出一个更高效的具有通用可组合性的格基2PAKE协议，称为RLWE-CAPAKE，并在UC框架下证明其安全性。新协议的设计思想来源于Abdalla等人^[16]于2008年提出的CAPAKE协议。新协议既保持了CAPAKE协议的优势，又能抵抗量子攻击。

2.   预备知识

2.1   理想格

格是线性空间${R_n}$上n个线性无关向量${{{v}}_{\rm{1}}},{{{v}}_{\rm{2}}}, ··· ,{{{v}}_{{n}}}$组成的点的集合，表示为${{L}} = \{ {a_1} \cdot {{{v}}_{{1}}} + {a_2} \cdot {{{v}}_{\rm{2}}} + ··· +$${a_n} \cdot {{{v}}_{{n}}}|{a_i}$为整数$\}$，其中${{{v}}_{\rm{1}}},{{{v}}_{\rm{2}}},··· ,{{{v}}_{{n}}}$称为格基。理想格^[17]则是具有特殊环结构的格。理想${\cal{I}}$是环$R = {\mathbb{Z}}[x]/f\left( x \right)$的一个商环，其中$f\left( x \right)$为首一整数多项式。$n$阶整数群${Z^n}$上${\cal{I}}$的集合便是理想格。相较于格，理想格可以使用一个向量表示一个$n$维格，大大降低了空间复杂度；理想格的特殊代数结构可以进行快速运算，大大降低了时间复杂度。最近，张洋等人^[18]提出的理想格上格基的快速三角化算法有助于进一步降低运算的时间复杂度。

2.2   环上带误差学习问题

2010年，Lyubashevsky等人^[17]提出了基于理想格的环上带误差学习(Ring Learning With Errors, RLWE)问题，并指出求解RLWE问题的难度可以量子规约到求解近似最短向量问题。被密码学界普遍认为能够抵抗量子攻击。

定义1　(RLWE分布)：设$R$为$\mathbb{Z}$上阶数为$n$的多项式环，${R_q} = R/qR$为以正整数$q$为模的商环，${\chi _\gamma }$为$R$上以$\gamma$为标准差，0为分布中心，$r$为半径的高斯离散分布。设固定向量${{s}}$为秘密值，在${R_q} \times {R_q}$上的RLWE分布${A_{s,{\chi _\gamma }}}$通过均匀随机地选择向量${{a}} \in {R_q}$, ${{e}} \in {\chi _\gamma }$进行采样，并得到采样结果$({{a}},{{b}} = {{s}} \cdot {{a}} + {{e}}(od q))$。

定义2　(判定RLWE问题)：给定多项式个独立样本$({{{a}}_{{i}}},{{{b}}_{{i}}}) \in {R_q} \times {R_q}$，任意PPT算法$A$能够区分样本取自RLWE分布${A_{s,{\chi _\gamma }}}$还是均匀随机地取自${R_q} \times {R_q}$的优势可忽略。

2.3   Peikert式误差调和机制

RLWE问题固有的误差问题会导致通信双方无法得到完全相同的会话密钥。为解决这一问题，Ding等人^[14]在2012年首次提出误差调和机制(称为Ding式误差调和机制)。2014年，Peikert^[15]指出Ding式误差调和机制中协议双方提取出的共同比特只是具有高熵，而并非均匀分布，需要一个随机提取器来获得均匀的值，这会带来较大的效率损失。他提出一个改进的误差调和机制(Peikert式误差调和机制)，该机制中协议双方提取的共同比特均匀分布。Peikert式误差调和机制具体描述如下：

对于偶数模数$q \!\ge\! 2$，定义${\mathbb{Z}_q} \!=\! \left\{\!\! - \dfrac{q}{2},··· ,0, ··· ,\dfrac{q}{2} - 1\!\!\right\}$及3个区间：${I_0}: = \left\{ 0,1,··· ,\left\lfloor \dfrac{q}{4}\right\rceil - 1\right\}$, ${I_1}: = \Big\{ - \left\lfloor {\dfrac{q}{4}} \right\rfloor ,$$···, - 1\Big\} (od q)$, $E: = \Big[ - \dfrac{q}{8},\dfrac{q}{8}\Big) \cap \mathbb{Z}$，其中$\Big\lfloor \dfrac{q}{4} \Big\rceil$和$\left\lfloor {\dfrac{q}{4}} \right\rfloor$为${\mathbb{Z}_q}$上的两个陪集，$\left\lfloor \dfrac{q}{4} \right\rceil = \left\lfloor {\dfrac{q}{4} + \dfrac{1}{2}} \right\rfloor \in \mathbb{Z}$。对于${{v}} \in {\mathbb{Z}_q}$, ${{w}} = {{v}} + {{e}}(od q)$，定义3个函数：

定义3　(交叉取整函数)${\langle \cdot \rangle _{q,2}}:{\mathbb{Z}_q} \to {\mathbb{Z}_2}$ 如$b = {\langle {{v}}\rangle _{q,2}}: = \left\lfloor {\dfrac{4}{q} \cdot {{v}}} \right\rfloor (od 2)$；

定义4　(模取整函数)${\lfloor \cdot \rceil_{q,2}}:{\mathbb{Z}_q} \to {\mathbb{Z}_2}$ 如${\lfloor {{v}} \rceil _{q,2}}: =\left\lfloor \dfrac{2}{q} \cdot {{v}} \right\rceil$；

定义5　(调和函数)${\rm{rec}} ({{w}},b):{\mathbb{Z}_q} \times {\mathbb{Z}_2} \to {\mathbb{Z}_2}$ 如${\rm{rec}} ({{w}},b): = \left\{ {\begin{array}{*{20}{c}} {0,{{w}} \in {I_b} + E(od q)} \\ {1,{{w}} \notin {I_b} + E(od q)} \end{array}} \right.$。其中，${\mathop{\rm rec}\nolimits} ({{w}},$${\langle {{v}}\rangle _{q,2}}) = {\lfloor {{v} \rceil}_{q,2}}$。

对于奇数模数$q$，可定义随机翻倍函数${\rm{dbl}} ( \cdot ):$${\mathbb{Z}_q} \to {\mathbb{Z}_{2q}}$，如${{\bar v}} = {\rm{dbl}} ({{v}}) = 2{{v}} - {{\bar e}}$，其中${{\bar e}} \in \mathbb{Z}$。${{\bar e}}$模2后均匀随机且与$v$独立，$2{{w}} = {{\bar v}} + (2{{e}} + {{\bar e}})$$(od 2q) \in {\mathbb{Z}_{2q}}$。

2.4   安全模型

本文设计的协议的安全性在Canetti等人^[11]提出的UC框架下，结合Canetti-Rabin^[19]提出的具有联合状态的UC(Joint state UC，JUC)定理，使用UC混合模型证明。

定义6　(混合模型下的安全实现) 给定混合模型下的$n$方协议$\pi$以及理想功能${\cal{F}}$，如果对于任意概率多项式时间(Probabilistic Polynomial Time, PPT)混合敌手${\cal{H}}$都存在PPT理想攻击者${\cal{S}}$，使得对于任意环境${\cal{Z}}$，在和混合敌手${\cal{H}}$及协议$\pi$交互后输出1的概率分布与在和理想攻击者${\cal{S}}$及理想功能${\cal{F}}$交互后输出1的概率分布是多项式不可区分的，则称协议$\pi$在混合模型下UC安全地实现了理想功能${\cal{F}}$。

3.   基于理想格的两方PAKE协议

3.1   协议描述

相较于Abdalla等人^[16]提出的CAPAKE协议，本文提出的新协议具有如下两个优势：(1)基于RLWE难题、采用文献[15]改进的误差调和机制，被密码学界普遍认为可以抵抗量子攻击；(2)新协议中，服务器不直接存储用户的口令，而只存储服务器ID及用户口令的哈希值${\rm{HPW}} = {H_0}(S||{\rm{PW}} )$。实际应用中，“单口令多用途”现象比较普遍，即用户往往针对许多不同的应用服务器使用相同的口令。该改进避免了当服务器沦陷后，敌手可直接获得用户口令，从而可向其他服务器冒充为用户的风险。

3.1.1   初始化阶段

用户加入系统时，需向服务器注册。用户$U$将其口令${\rm{PW}}$及服务器ID即$S$输入哈希函数${{\rm{H}} _0}( \cdot )$计算得到${\rm{HPW}}$，同时从商群${R_q}$中均匀随机选择公共参数${{a}}$，将用户ID即$U$, ${\rm{HPW}}$及${{a}}$通过安全信道发送给服务器$S$。$S$收到$U$的注册信息后将$\langle U,{\rm{HPW}} ,{{a}}\rangle$添加到存储在数据库中的列表${\cal{L}}$上，本文设定外部敌手无法获得服务器内部信息。

3.1.2   相互认证及密钥交换阶段

用户和服务器每次会话会自动生成一个会话ID，会话ID为ssid的用户和服务器相互认证及密钥交换的过程如下，其中具体的计算如图1所示：

图 1  RLWE-CAPAKE的相互认证及密钥交换过程

下载: 全尺寸图片 幻灯片

(1) $U \to S:{\rm{M}} 1 = \{ U,X\}$：$U$输入$S,{\rm{PW}}$，再次计算${\rm{HPW}}$，均匀随机地从商群${R_q}$中选择其私钥${s}_{x}$、从高斯离散分布${\chi _\gamma }$中选取误差${{{e}}_{{x}}},{{e}}_{{x}}^{{'}}$，计算其公钥${{X}} = {{a}} \cdot {{{s}}_{{x}}} + {{{e}}_{{x}}} \in {R_q}$，最后将$U$和${{X}}$发送给$S$。

(2) $S \to U:{\rm{M}} 2 = \{ S,{Y^*}\}$：收到${\rm{M}} 1$后，$S$首先检测${{X}}$是否在商群${R_q}$内，若不在，则退出该次会话；若在，则均匀随机地从${R_q}$中选择其私钥${s}_{y}$、从${\chi _\gamma }$中选取误差${{{e}}_{{y}}},{{e}}_{{y}}^{{'}}$，计算其公钥${{Y}} = {{a}} \cdot {{{s}}_{{y}}} + {{{e}}_{{y}}} \in {R_q}$。随后利用${{X}}$生成带误差的中间秘密值${{v}} = {{X}} \cdot {{{s}}_{{y}}} +$${{e}}_{{y}}^{{'}} \in {R_q}$，对${{v}}$使用随机翻倍函数${\rm{dbl}} ( \cdot )$得到${{\bar v}}$，对${{\bar v}}$使用交叉取整函数${\langle \cdot \rangle _{2q,2}}$得到$\sigma$，对${{\bar v}}$使用模取整函数${[ \cdot ]_{q,2}}$得到不带误差的中间秘密值${K_s}$。$S$使用对称密钥$({\rm{ssid}} ||{\rm{HPW}} )$加密${{Y}}$以及$\sigma$得到${Y^*}$，最后将$S$和${Y^*}$发送给$U$。

(3) $S \to U:{\rm{M}} 3 = \{ {\rm{Auth}}\}$：收到${\rm{M}}2$后，$U$首先用$({\rm{ssid}} ||{\rm{HPW}} )$解密${Y^*}$得到$Y||\sigma$，再利用${{Y}}$生成带误差的中间秘密值${{w}} = {{Y}} \cdot {{{s}}_{{x}}} + {{e}}_{{x}}^{{'}} \in {R_q}$，随后结合$\sigma$对${{w}}$使用调和函数${\rm{rec}} (2{{w}},\sigma )$得到不带误差的中间秘密值${K_u}$。之后，$U$使用哈希函数${{\rm{H}} _1}( \cdot )$、${{\rm{H}} _2}( \cdot )$分别计算认证因子${\rm{Auth}} = {{\rm{H}} _1}({\rm{ssid}} \parallel U\parallel S\parallel {{X}}\parallel {{Y}}\parallel$${K_u})$、会话密钥${{\rm{SK}} _u} = {{\rm{H}} _2}({\rm{ssid}} \parallel U\parallel S\parallel {{X}}\parallel {{Y}}\parallel {K_u})$，最后将${\rm{Auth}}$发送给$S$。

(4) ${{\rm{SK}} _s} = {{\rm{H}} _2}({\rm{ssid}} \parallel U\parallel S\parallel {{X}}\parallel {{Y}}\parallel {K_s}{\rm{)}} =$${{\rm{SK}} _u}$：收到${\rm{Auth}}$后，$S$使用${{\rm{H}} _1}( \cdot )$计算得到${{\rm{Auth}} ^*} =$${{\rm{H}} _1}({\rm{ssid}} \parallel U\parallel S\parallel {{X}}\parallel {{Y}}\parallel {K_s})$并与${\rm{Auth}}$比较。若相等，$S$计算会话密钥${{\rm{SK}} _s} = {{\rm{H}} _2}({\rm{ssid}} \parallel U\parallel S\parallel {{X}}\parallel$${{Y}}\parallel {K_s})$；否则，$S$发出错误信息。

3.2   方案的正确性

若$U$和$S$诚实地运行协议，他们将以显著的概率得到${{\rm{SK}} _s} = {{\rm{SK}} _u}$。协议中：

令${{{e}}^{{*}}} = {{{e}}_{{y}}} \cdot {{{s}}_{{x}}}{\rm{ + }}{{e}}_{{x}}^{{'}} - {{{e}}_{{x}}} \cdot {{{s}}_{{y}}} - {{e}}_{{y}}^{{'}} \in {R_q}$，则${{w}} = {{v}} + {{{e}}^{{*}}}$，令${{\bar v}} = 2{{v}} - {{\bar e}} = 2({{w}} - {{{e}}^{{*}}}) - {{\bar e}} =$ $2{{w}} -$$(2{{{e}}^{{*}}} + {{\bar e}}) \in {\mathbb{Z}_{2q}}$。由文献[15]的等式(2.1)、事实2.1、事实2.4可知，$2{{{e}}^{{*}}} + {{\bar e}}$的解码基的所有系数不在区间$[ - q/4,q/4)$内的概率可忽略。根据文献[15]的声明3.2：对于偶数$q$，存在${{v}} \in {\mathbb{Z}_q}$, ${{e}} \in E$满足${{w}} = {{v}} + {{e}}$，则${\mathop{\rm rec}\nolimits} ({{w}},{\langle {{v}}\rangle _{q,2}}) = {\lfloor {{v} \rceil}_{q,2}}$。因此，$U$和$S$诚实地运行协议，得到${{\rm{SK}} _s} \ne {{\rm{SK}} _u}$的概率可忽略。

4.   安全性证明

定理1：在考虑适应性敌手的条件下，本文协议在(${{\cal{F}}_{{\rm{RO}}}}$, ${{\cal{F}}_{{\rm{IC}}}}$)混合模型中能够UC安全地实现理想功能${\cal{F}}_{{\rm{pwKE}}}^{{\rm{CA}}}$的多会话扩展$\hat {\cal{F}}_{{\rm{pwKE}}}^{{\rm{CA}}}$。

根据定义6可知，证明定理1即可证明协议RLWE-CAPAKE在混合模型下UC安全地实现了理想功能$\hat {\cal{F}}_{{\rm{pwKE}}}^{{\rm{CA}}}$，即具有UC安全性。本节定义了一个序列游戏来证明定理1，这个序列游戏中理想攻击者逐步为挑战者模拟出协议中参与者的所有交互和输出。如果模拟出的信息和真实协议不可区分，那么就将真实环境下的协议安全问题规约到了理想模型中的协议安全问题。证明中使用了3个理想功能：Hofheinz等人^[20]提出的随机预言功能${{\cal{F}}_{{\rm{RO}}}}$, Liskov等人^[21]提出的理想密码功能${{\cal{F}}_{{\rm{IC}}}}$以及基于口令的认证密钥交换理想功能${\cal{F}}_{{\rm{pwKE}}}^{{\rm{CA}}}$^[16]。为了节省篇幅，上述3个理想功能的具体描述省略。

表1给出了利用这些游戏证明不可区分性的简要过程，${\cal{A}}$为与协议RLWE-CAPAKE实体交互的敌手，${\cal{S}}$为与理想功能$\hat {\cal{F}}_{{\rm{pwKE}}}^{{\rm{CA}}}$交互的理想攻击者。${\cal{S}}$利用一个模拟的挑战者${\cal{A}}$去攻击协议RLWE-CAPKE，试图获得攻击理想功能$\hat {\cal{F}}_{{\rm{pwKE}}}^{{\rm{CA}}}$的优势。${\cal{S}}$为${\cal{A}}$模拟出一系列预言机，${\cal{S}}$把${\cal{Z}}$的输入传递给${\cal{A}}$，把${\cal{A}}$的输出作为${\cal{S}}$的输出使${\cal{Z}}$可以读取。设${\cal{H}}$为(${{\cal{F}}_{{\rm{RO}}}}$, ${{\cal{F}}_{{\rm{IC}}}}$)混合模型下敌手，与RLWE-CAPAKE实体交互时即为${\cal{A}}$，与理想功能$\hat {\cal{F}}_{{\rm{pwKE}}}^{{\rm{CA}}}$交互时即为${\cal{S}}$。这个序列游戏中游戏${\rm{G}} 2$是考虑${\cal{A}}$未执行查询，直接猜测出${K_u}$意外获胜的情况。游戏${\rm{G}} 3$和${\rm{G}} 5$分别考虑了在第${\rm{S}}4$步之前未被攻陷和客户端已经被攻陷这两种情况。混合模型下，攻击者${\cal{H}}$和协议的用户实例通过下述查询进行交互：

表 1  UC框架不可区分性证明概览

游戏	模型	游戏					模拟器	挑战者
		U1	U2	U3	U4	哈希与加解密
${\rm{G}} 0$	现实	真实	真实	真实	真实	真实	协议	${\cal{A}}$
${\rm{G}} 1$	混合	真实	真实	真实	真实	模拟	${\cal{H}}$	${\cal{A}}$
${\rm{G}} 2$	混合	真实	真实	真实	真实	模拟	${\cal{H}}$	${\cal{A}}$
${\rm{G}} 3$	混合	真实	真实	真实	模拟	模拟	${\cal{H}}$	${\cal{A}}$
${\rm{G}} 4$	混合	模拟	真实	模拟	真实	模拟	${\cal{H}}$	${\cal{A}}$
${\rm{G}} 5$	混合	真实	真实	真实	模拟	模拟	${\cal{H}}$	${\cal{A}}$
${\rm{G}} 6$	混合	真实	模拟	真实	模拟	模拟	${\cal{H}}$	${\cal{A}}$
${\rm{G}} 7$	理想	模拟	模拟	模拟	模拟	模拟	${\cal{S}}$	${\cal{A}}$

下载: 导出CSV 

| 显示表格

(1)TestPwd查询：参与者完全被模拟时，验证某一方的口令是否为想要的那个口令；

(2)NewKey查询：参与者完全被模拟且口令未泄露时，验证两方是否拥有相同的口令；

(3)GoodPwd查询：参与者未完全被模拟时，验证某一方的口令是否为想要的那个口令；

(4)SamePwd查询：参与者未完全被模拟且口令未泄露时，验证两方是否拥有相同的口令。

具体证明过程如下：

游戏 ${\rm{G}} 0$：该游戏是环境${\cal{Z}}$与现实世界的敌手${\cal{A}}$及RLWE-CAPAKE协议的实例在随机预言模型以及理想密码模型下进行交互。

游戏 ${\rm{G}} 1$：理想攻击者${\cal{S}}$模拟随机预言机和加解密预言机。

(1)在随机预言模型下，${\cal{S}}$维持一个长度为${q_H}$的列表${\varLambda _{\cal{H}}}$，用于提供随机预言机${{\cal{H}}_0}$, ${{\cal{H}}_1}$, ${{\cal{H}}_2}$的查询应答。对于一个Hash查询${{{H}} _n}(q)$($n$= 0或1或2)，如果在${\varLambda _{\cal{H}}}$中存在$(n,q,r)$记录，则返回$r$；否则，随机选取一个$r \in {\{ 0,1\} ^{{l_{{{\cal{H}}_n}}}}}$，如果${\varLambda _{\cal{H}}}$已经存在$(n, * ,r)$记录则中止查询，否则在${\varLambda _{\cal{H}}}$中添加$(n,q,r)$记录并返回$r$。

(2)在理想密码模型下，${\cal{S}}$维持一个长度为${q_{\cal{E}}} + {q_{\cal{D}}}$的列表${\varLambda _{{\rm{ED}}}} = \{ ({\rm{ssid}} ,X,{\rm{HPW}} ,Y||\sigma ,{{{s}}_{{a}}}, {{{e}}_{{a}}},$${\cal{E}},{Y^*})\} \cup \{ ({\rm{ssid}} ,X,{\rm{HPW}} ,Y||\sigma ,{{{s}}_{{a}}},{{{e}}_{{a}}},{\cal{D}},{Y^*})\}$来提供具有如下属性的加解密预言机查询应答：(a) 对同一口令的同一问题的查询，回答一致；(b) 任一口令的模拟方案加解密是可置换的；(c) 不同口令对应的密文不同。其中${{{s}}_{{a}}},{{{e}}_{{a}}}$用于在解密查询时构造$Y||\sigma$。对于一个加密查询${{\cal{E}}_{{\rm{ssid}} ||{\rm{HPW}} }}(Y||\sigma )$，如果${\varLambda _{{\rm{ED}}}}$中存在$({\rm{ssid}} ,X,{\rm{HPW}} ,Y||\sigma , * , * , * ,{Y^*})$记录则返回${Y^*}$；否则，随机选取${Y^*} \in {G^*} = G\{ 1\}$，如果${\varLambda _{{\cal{E}}{\cal{D}}}}$中存在$( * , * , * , * , * , * , * ,{Y^*})$记录则中止查询，否则在${\varLambda _{{\rm{ED}}}}$中添加$({\rm{ssid}} ,X,{\rm{HPW}} , \bot ,Y||\sigma , \bot , \bot ,{\cal{E}},{Y^*})$并返回${Y^*}$，其中$\bot$代表此处无需用到该值。对于一个解密查询${{\cal{D}}_{{\rm{ssid}} ||{\rm{HPW}} }}({Y^*})$，如果在${\varLambda _{{\rm{ED}}}}$中存在$( * , * ,{\rm{HPW}} ,Y||\sigma , * , * , * ,{Y^*})$记录就返回$Y||\sigma$；否则，随机选择${s}_{s}\in {R}_{q}$, ${{{e}}_{{s}}} \in {\chi _\gamma }$, ${{e}}_{{s}}^{{'}} \in {\chi _\gamma }$，计算${{Y'}} = a \cdot {{{s}}_{{s}}} + {{{e}}_{{s}}} \in {R_q}$, ${{v'}} = X \cdot {{{s}}_{{s}}} + {{e}}_{{s}}^{{'}} \in {R_q}$, ${{\bar v'}}{ \leftarrow _r}{\rm{dbl}} ({{v'}}) \in {R_{2q}}$及$\sigma '{ \leftarrow _r}{\langle {{\bar v'}}\rangle _{2q,2}} \in {\{ 0,1\} ^n}$，如果${\varLambda _{{\rm{ED}}}}$中存在$( * , * , * ,Y||\sigma , * , * , * , * )$记录则中止查询，否则在${\varLambda _{{\rm{ED}}}}$中添加$({\rm{ssid}} ,X,{\rm{HPW}} ,Y'||\sigma ',{{{s}}_{{s}}},{{{e}}_{{s}}},{\cal{D}},Y{'^*})$并返回$Y||\sigma$。上面出现的两种终止查询情况是为了满足不同的口令对应不同的密文这一属性。证毕

引理 1　游戏${\rm{G}} 0$和游戏${\rm{G}} 1$对于任意环境${\cal{Z}}$都是计算不可区分的。

证明：根据哈希函数的抗碰撞性，对于$r \ne r'$, ${\cal{A}}$得到${{{H}} _n}(r) = {{{H}} _n}(r')$($n$= 0或1或2)的概率是可忽略的。根据RLWE判定问题，${\cal{A}}$成功区分$Y'$是取自RLWE分布${A_{s,{\chi _\gamma }}}$还是${R_q} \times {R_q}$的概率可忽略。对于$Y \ne Y'$, $\sigma \ne \sigma '$, ${Y^*} \ne Y{'^*}$, ${{\cal{E}}_{{\rm{ssid}} ||{\rm{HPW}} }}(Y'||\sigma ')$和${{\cal{E}}_{{\rm{ssid}} ||{\rm{HPW}} }}(Y||\sigma )$得到相同的密文${Y^*}$的概率及${{\cal{D}}_{{\rm{ssid}} ||{\rm{HPW}} }}$$(Y{'^*})$和${{\cal{D}}_{{\rm{ssid}} ||{\rm{HPW}} }}({Y^*})$得到相同的$Y||\sigma$的概率也是可忽略的。因此${\cal{A}}$无法在PPT内区分游戏${\rm{G}} 0$和游戏${\rm{G}} 1$。证毕

游戏 ${\rm{G}} 2$：此游戏与游戏${\rm{G}} 1$基本相同，不同之处在于如果现实世界敌手${\cal{A}}$在未执行任何查询的情况下成功猜测出${K_u}$，则理想攻击者$S$中止模拟随机预言机和加解密预言机。

引理 2　游戏 ${\rm{G}} 1$和游戏${\rm{G}} 2$对于任意环境${\cal{Z}}$都是计算不可区分的。

证明：现实世界敌手${\cal{A}}$在未执行任何查询的情况下成功猜测出${K_u}$发生的概率是可忽略的，故${\cal{A}}$无法在PPT内区分游戏${\rm{G}} 1$和游戏${\rm{G}} 2$。证毕

游戏 ${\rm{G}} 3$：假定${\cal{S}}$有能力掌控协议前3轮的双方参与者，可知道两参与者的口令，而敌手可通过完全获得参与者的内部存储器来攻陷参与者。如果在第${\rm{S}}4$步之前没有发生攻陷，${\cal{S}}$模拟两方参与者模拟协议的执行。如果在第${\rm{S}}4$步最开始，两方参与者仍然都没有被攻陷，且所有的消息都是预言机产生的，则${\cal{S}}$执行SamePwd查询，验证两方口令是否相同。如果两方口令相同，${\cal{S}}$在密钥空间中随机选择一个密钥$K$并发送给两方参与者；否则，${\cal{S}}$在密钥空间中随机选择一个密钥单独发给客户端，服务器则只收到错误信息。如果在第${\rm{S}}4$步之前某一方参与者已经被攻陷，${\cal{S}}$将不执行任何操作。

引理 3　游戏${\rm{G}} 2$和游戏${\rm{G}} 3$对于任意环境${\cal{Z}}$都是计算不可区分的。

证明：当两方参与者的口令相同时，此游戏与游戏${\rm{G}} 2$不可区分；当两方参与者的口令不同时，除了碰撞外，此游戏中协议的第${\rm{S}}4$步的一次执行与现实世界模型中协议的第${\rm{S}}4$步的一次执行不可区分。由哈希函数的抗碰撞性可知，发生碰撞的概率可忽略，故${\cal{A}}$无法在PPT内区分游戏${\rm{G}} 2$和游戏${\rm{G}} 3$。证毕

游戏 ${\rm{G}} 4$：${\cal{S}}$在不获得客户端口令的情况下，从协议的最开始模拟未被攻陷的客户端：在第${\rm{U}} 1$步，${\cal{S}}$模拟客户端选择随机数${{{s}}_{{x}}} \in {R_q},{{{e}}_{{x}}} \in {\chi _\gamma }$并计算相应的$X$发送给服务器；在第${\rm{U}} 3$步，若${\cal{S}}$模拟的客户端仍然未被攻陷，则它不能发起对${Y^*}$的解密查询。随后，如果客户端收到的消息都是预言机生成的，${\cal{S}}$通过${\cal{H}}{{\rm{'}}_1}$查询获取${\rm{Auth}} = {{H}} {'_1}({\rm{ssid}} \parallel U\parallel S\parallel$$X\parallel {Y^*})$，其中${\cal{H}}{{\rm{'}}_1}$为${\cal{S}}$的私有随机预言机。如果客户端收到的信息不是预言机生成的，分两种情况进行操作：(1)若服务器被${\cal{A}}$攻陷，则${\cal{S}}$可以得到服务器的口令(此时的模拟器为${\cal{H}}$，它同时具有${\cal{A}}$和${\cal{S}}$两种身份)，或者如果${Y^*}$已在加密查询下被${\cal{A}}$获取，${\cal{S}}$可利用加解密查询列表${\varLambda _{{\cal{E}}{\cal{D}}}}$恢复出服务器使用的口令。随后，在接收${Y^*}$时，${\cal{S}}$进行GoodPwd查询，若口令正确，${\cal{S}}$通过${{\cal{H}}_1}$查询获取${\rm{Auth}} = {{{H}} _1}$$({\rm{ssid}} \parallel U\parallel S\parallel X\parallel Y\parallel {K_u})$；否则，通过${\cal{H}}{{\rm{'}}_1}$查询获取${\rm{Auth}} = {{H}} {'_1}({\rm{ssid}} \parallel U\parallel S\parallel X\parallel {Y^*})$。(2)如果${Y^*}$未在加密查询下被${\cal{A}}$获取过，${\cal{S}}$模拟客户端通过${\cal{H}}{{\rm{'}}_1}$查询获取$\rm{Auth}$=${{H}} {'_1}({\rm{ssid}} \parallel U\parallel S\parallel X\parallel {Y^*})$。但是若${\cal{A}}$询问了以${\rm{ssid}} \parallel U\parallel S\parallel X\parallel Y\parallel {K_u}$或${\rm{ssid}} \parallel U\parallel S\parallel$$X\parallel Y\parallel {K_s}$为输入的${{\cal{H}}_0}$或${{\cal{H}}_1}$查询会使得游戏中止。

在第${\rm{U}} 3$步，在${\cal{S}}$模拟的客户端仍未被${\cal{A}}$攻陷时，如果由${\cal{H}}{{\rm{'}}_1}$查询获取${\rm{Auth}}$且没有攻陷发生在任何一方，则${\cal{S}}$通过${\cal{H}}{{\rm{'}}_0}$查询获取${{\rm{SK}} _u}$。如果由${{\cal{H}}_1}$查询获取${\rm{Auth}}$，或由${\cal{H}}{{\rm{'}}_1}$查询获取${\rm{Auth}}$但之后发生了攻陷，则${\cal{S}}$通过${{\cal{H}}_0}$查询获取${{\rm{SK}} _u}$。如果在此步${\cal{S}}$模拟的客户端被攻陷，${\cal{S}}$可以得到内部状态${{{s}}_{{x}}}$, ${{{e}}_{{x}}}$及${\rm{HPW}}$，从而可以计算出$Y||\sigma$，接下来，${\cal{S}}$重新执行预言机获取${\rm{Auth}} = {{{H}} _1}({\rm{ssid}} \parallel U\parallel S\parallel X\parallel Y\parallel {K_u})$和${{\rm{SK}} _u} = {{{H}} _2}({\rm{ssid}} \parallel U\parallel S\parallel X\parallel Y\parallel {K_u})$。

在第${\rm{S}}4$步，若服务器被攻陷，且${\cal{S}}$进行GoodPwd查询后口令正确，${\cal{S}}$重新执行预言机获取${\rm{Auth}} = {{{H}} _1}({\rm{ssid}} \parallel U\parallel S\parallel X\parallel Y\parallel {K_s})$和${{\rm{SK}} _s} = {{{H}} _2}$$({\rm{ssid}} \parallel U\parallel S\parallel X\parallel Y\parallel {K_s})$。当且仅当${\cal{A}}$在攻陷之前询问了以${\rm{ssid}} \parallel U\parallel S\parallel X\parallel Y\parallel {K_u}$或${\rm{ssid}} \parallel U\parallel S\parallel$$X\parallel Y\parallel {K_s}$为输入的${{\cal{H}}_0}$或${{\cal{H}}_1}$查询，${\cal{A}}$能够对游戏${\rm{G}} 4$与游戏${\rm{G}} 3$进行区分。

引理 4　游戏${\rm{G}} 3$与游戏${\rm{G}} 4$对于任意环境${\cal{Z}}$都是计算不可区分的。

证明：${\cal{A}}$未在加密查询下并且获取过${Y^*}$的情况下知道相应的${s}_{y}$和${{{e}}_{{y}}}$的概率可忽略，${\cal{A}}$在第${\rm{S}}4$步攻陷服务器之前询问了以${\rm{ssid}} \parallel U\parallel S\parallel X\parallel Y\parallel {K_u}$或${\rm{ssid}} \parallel U\parallel S\parallel X\parallel Y\parallel {K_s}$为输入的${{\cal{H}}_0}$或${{\cal{H}}_1}$查询的概率也可忽略，故${\cal{A}}$无法在PPT内区分游戏${\rm{G}} 3$与游戏${\rm{G}} 4$。证毕

游戏 ${\rm{G}} 5$：在该游戏中，${\cal{S}}$模拟在第${\rm{S}} 4$步中没被攻陷的服务器。分如下两种情况：

(1)如果在第${\rm{S}} 4$步之前没有攻陷发生，且所有的信息都是预言机产生的，则${\cal{S}}$之后的操作与${\rm{G}} 3$中的操作相同。

(2)如果在第${\rm{S}} 4$步之前客户端已经被${\cal{A}}$攻陷，或者某一信息不是预言机产生的(比如${\cal{A}}$已经通过解密${Y^*}$获得$Y$)，${\cal{S}}$恢复出服务器已使用过的口令，并验证客户端发送的${\rm{Auth}}$是否正确。如果${\rm{Auth}}$正确，${\cal{S}}$询问关于服务器的GoodPwd查询，若口令正确，服务器会获得和客户端同样的密钥，否则，会获得一条错误信息。如果${\rm{Auth}}$不正确，服务器会获得一条错误信息。

若服务器在第${\rm{S}} 4$步被${\cal{A}}$攻陷，${\cal{S}}$恢复出服务器的口令，查询列表${\varLambda _{{\cal{E}}{\cal{D}}}}$找到该口令相应的信息发送给${\cal{A}}$。当${\cal{A}}$意外猜测到了$Y$时，${\cal{A}}$可在客户端发送完${\rm{Auth}}$之后模仿客户端，此时游戏中止。

引理 5　游戏${\rm{G}} 4$和游戏${\rm{G}} 5$对于任意环境${\cal{Z}}$都是计算不可区分的。

证明：${\cal{A}}$意外猜测到$Y$的概率可忽略，故${\cal{A}}$无法在PPT内区分游戏${\rm{G}} 4$和游戏${\rm{G}} 5$。证毕

游戏 ${\rm{G}} 6$：${\cal{S}}$从协议开始模拟未被攻陷的服务器。在第${\rm{S}} 2$步，${\cal{S}}$随机选择一个未执行过加密查询的${Y^*}$发送给客户端。如果在之后服务器被${\cal{A}}$攻陷，${\cal{S}}$利用列表${\varLambda _{{\cal{E}}{\cal{D}}}}$获得相应的${{{s}}_{{y}}}$, ${{{e}}_{{y}}}$及$Y||\sigma$并发送给${\cal{A}}$。如果一直到游戏的最后两参与者仍未被攻陷，与游戏${\rm{G}} 3$不同，他们会得到一个共享的基于口令的会话密钥。参与者之一被攻陷的情况与游戏${\rm{G}} 4$和游戏${\rm{G}} 5$中的描述相同，且游戏的执行不依赖${Y^*}$的值。

引理 6　游戏${\rm{G}} 5$和游戏${\rm{G}} 6$对于任意环境${\cal{Z}}$都是计算不可区分的。

证明：游戏${\rm{G}} 3$, ${\rm{G}} 4$和${\rm{G}} 5$中可能中止情况发生的概率都是可忽略的，故${\cal{A}}$无法在PPT内区分游戏${\rm{G}} 5$和游戏${\rm{G}} 6$。证毕

游戏 ${{\rm{G}}7}$：${\cal{S}}$从协议开始模拟未被攻陷的客户端和服务器，其中将游戏${\rm{G}} 6$中使用的混合模型下的GoodPwd查询和SamePwd查询分别替换为理想模型下的TestPwd查询和NewKey查询，若游戏中止或终止都会告知${\cal{A}}$。

引理 7　游戏${\rm{G}} 6$和游戏${\rm{G}} 7$对于任意环境${\cal{Z}}$都是计算不可区分的。

证明：如果两方参与者拥有相同的${\rm{ssid}}$，相对的角色(客户端和服务器)并且有相同的($X,{Y^*}$)对，则称两方参与者拥有匹配会话。如果客户端和服务器拥有匹配会话，则他们会得到相同的会话密钥：如果两方都未被攻陷，则他们的会话密钥与实验${\rm{G}} 3$中相同；如果客户端未被攻陷，服务器被攻陷，他们的会话密钥与游戏${\rm{G}} 4$中相同；如果客户端被攻陷，则他们的会话密钥与游戏${\rm{G}} 5$相同。如果客户端和服务器未拥有匹配会话，他们的($X,{Y^*}$)对或${\rm{Auth}}$必有不同，两方拥有相同的($X,{Y^*}$)对的概率以$q_\varepsilon ^2/q$为上界，这个概率可忽略，其中${q_\varepsilon }$为向预言机加密查询的次数。故${\cal{A}}$无法在PPT内区分游戏${\rm{G}} 6$和游戏${\rm{G}} 7$。证毕

由于游戏${\rm{G}} 7$与理想功能$\hat {\cal{F}}_{{\rm{pwKE}}}^{{\rm{CA}}}$中的客户端和服务器拥有完全一致的行为，因此游戏${\rm{G}} 7$与理想功能$\hat {\cal{F}}_{{\rm{pwKE}}}^{{\rm{CA}}}$对于任意环境${\cal{Z}}$都是概率多项式不可区分的。进一步综合引理1至引理7可知，对于任意环境${\cal{Z}}$，在和混合敌手${\cal{H}}$及新提出协议的实例交互后输出1的概率分布与在和理想攻击者${\cal{S}}$及理想功能$\hat {\cal{F}}_{{\rm{pwKE}}}^{{\rm{CA}}}$交互后输出1的概率分布是计算不可区分的。定理1证毕。

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协议的性能比较

协议	通信开销	环运算次数	安全模型	难题假设	误差调和
RLWE-PAK	$2n\;{\log _2}\;q + n$	4	BPR模型	RLWE	Ding式REC
RLWE-SRP	$2n\;{\log _2}\;q + n$	5	UC模型	RLWE	Ding式REC
本文协议	$2n\;{\log _2}\;q + n$	4	UC模型	RLWE	Peikert式REC

下载: 导出CSV 

| 显示表格

6.   结束语

本文提出了一个基于RLWE问题的2PAKE协议，并在UC框架下详细证明了其安全性。新协议采用了更加高效的误差调和机制。通过与现有相关协议进行比较，结果表明了新协议具有更高的安全性和计算效率。