0 概述

认证密钥交换(Authenticated Key Exchange, AKE)协议可使通信方在有主动敌手的信道上建立安全的共享会话密钥, 同时实现彼此身份的相互认证, 在后续的对称密码中能够保证数据的完整性和真实性。目前多数AKE协议的安全性依赖于大整数分解和离散对数的Diffie-Hellman^[1]困难问题, 随着量子计算技术的发展, 此类问题在多项式时间算法下是可解的, 这将给现有协议带来安全威胁。格上构造的公钥密码体制因其运算简单、可并行性和抗量子攻击的优点, 将在后量子时代成为最有效的解决方案之一, 基于格的AKE协议因此成为学术界的研究热点。

基于格的AKE协议^[2-4]可以抵抗量子攻击, 解决经典困难问题下协议的安全性问题, 但不能降低通信复杂度并实现认证。文献[5]在标准模型下构造高效的口令认证密钥交换协议, 但该协议不能抵抗量子攻击。文献[6]基于LWE构造了无环密钥交换协议, 虽然该协议可以抵抗量子攻击, 但无法实现客户和服务器的相互认证。文献[7]提出一个基于理想格的密钥交换协议, 使通信方以显著概率计算得到一个相同的会话密钥, 然而该协议提取的会话密钥只具有高熵, 并不是均匀分布的, 虽然通信方可以利用随机提取器得到均匀分布的共同比特, 但这会降低协议的效率。文献[8]提出一种基于理想格的密钥封装机制(Key Encapsulation Mechanism, KEM), 文献[9]在此基础上结合一种简单的低带宽协调技术提出一种变形的错误协调机制, 结合环LWE困难问题构造密钥交换协议, 使加密方案的密文长度缩短了近两倍, 通信方可以直接得到均匀的共同比特。

文献[10]结合Peikert式错误协调机制构造了适用于TLS协议的Diffie-Hellman式密钥交换协议, 并给出具体的实现参数, 其中会话密钥能达到较高的量子安全级别, 但错误协调机制模数较大, 使得通信量较大, 降低了协议的效率。文献[11]基于R-LWE困难问题, 利用格解码算法结合中心二项分布提出了NewHope密钥交换协议, 优化了文献[10]的密钥交换协议, 扩大了可容忍的错误范围, 减少了模数, 节省了通信量。文献[12]提出的NewHopeSimple方案, 使用加密的构造方法代替调和技术, 降低了协议的计算复杂度。文献[13]基于加密的构造方法提出抗选择密文攻击安全的Kyber系列密钥封装算法, 其采用密钥压缩技术对需要发送的公钥和密文进行压缩, 降低了通信量。

随着格密码的快速发展, 密钥交换协议的效率已得到大幅提高, 但目前多数协议都是Diffie-Hellman式密钥交换协议^{[7, 10, 14-16]}, 只能提供被动安全性, 不能实现相互认证, 也不能抵抗中间人攻击, 而实际应用中必须要考虑网络上的主动攻击者。因此, 构造认证密钥交换协议来抵御主动攻击是研究趋势所向, 而基于KEM方案构造认证密钥交换协议是一种可行的方法。

文献[17]在NTRU格Diffie-Hellman式密钥交换协议的基础上, 结合带消息恢复功能的签名算法与KEM方案实现协议的认证性。与传统签名算法相比, 该方案既增加了安全性又提高了通信效率。文献[18]将具有CCA安全和CPA安全的KEM方案相结合, 提出了适用于格的可认证密钥交换协议的通用架构, 即GC协议, 其将KEM方案作为基本的设计原语, 在CK⁺模型下是可证明安全的。文献[19]提出的CCA安全的密钥封装机制, 可由基本的CPA安全的密钥封装机制获得, 使用这一方法, Kyber构造了具有认证性的密钥交换协议Kyber.AKE。文献[20]设计了格上基于R-LWE的三方PAKE协议, 实现了通信方的显式认证, 可避免两方认证密钥交换协议的局限性, 但该协议存在会话密钥的不一致性问题。

为实现Diffie-Hellman式密钥交换协议的认证性并使其能够抵抗量子攻击, 本文结合带消息恢复功能的签名算法, 基于R-LWE构造一个KEM方案。在协议执行时采样随机种子生成协议双方的公共参数, 防止攻击者利用固定公共参数攻击协议, 以保证前向安全性。发送方选择定比特长的随机字符串, 每4个元素使用Encode函数^[12]编码其中的一个比特, 编码后的环元素可容忍更大的错误, 从而降低模数, 缩减通信量。此外, 在保证密文恢复完整性的前提下对密文元素使用Compress压缩函数进行压缩, 减轻服务器的传输负荷, 同时利用带有消息恢复功能的签名算法实现协议的认证性。

1 相关知识

引理1  令$ \boldsymbol{X} \in \mathbb{R}^{n \times m}$为一个带有参数s的δ-亚高斯随机矩阵。存在一个常数C>0, 对于任何t≥0, 有$s_{1}(\boldsymbol{X}) \leqslant C \cdot s \cdot(\sqrt{m}+\sqrt{n}+t) $。

引理2  设$\mathit{\Lambda} \subset \mathbb{R}^{n} $是一个格, 对于ε∈(0, 1), 令r≥η_ε(Λ), 则对于任何c∈span(Λ), 得到$ \Pr \left[ {\parallel {D_{\mathit{\Lambda} + c, r}}\parallel \ge r\sqrt n } \right] \le {2^{ - n}} \cdot \frac{{1 + \varepsilon }}{{1 - \varepsilon }}$。

引理3 (剩余散列)   设H是一个2-universal的, 从定义域X到值域Y的哈希函数簇, 则对于均匀独立选取的h←H和h(X)←X, (h, h(X))在H×Y上是$ \frac{1}{2} \sqrt{\boldsymbol{Y} / \boldsymbol{X}}$均匀分布的。

引理4  对于任意的秘密值 $s \geqslant \omega(\sqrt{1 \mathrm{b} n}) $ , 有$\mathop {\Pr }\limits_{e \leftarrow \chi {{\mathbb{Z}}_n},s} \, [||x||>s\sqrt{n}]\le {{2}^{-n}} $。

1.1 密文压缩算法

密文压缩技术是减少用户通信量的有效方法, 其对密文元素进行压缩, 丢掉密文元素的低位比特, 即部分噪音信息。在保证密文恢复完整性的前提下, 有效减少通信量, 减轻服务器的传输负荷。将密文元素从${{\mathbb{Z}}_{q}} $映射到$ {{\mathbb{Z}}_{2d}}$上, 其中d < lbq。

定义1  一个密文压缩算法包括2个多项式时间算法, 即压缩算法Compress_q(x, d)和解压缩算法Decompress_q(x, d)。

1) 压缩函数:

$ \text { Compress }_{q}(x, d)=\left\lfloor\left(2^{d} / q\right) \cdot x\right\rfloor \bmod ^{+} 2^{d} $

其中, $ x \in \mathbb{Z}_{q}, d \in \mathbb{N}^{*}, \text { Compress }_{q}(x, d) \in\{0, 1, \cdots, $ $ \left. {{2^d} - 1} \right\}$, 满足$ d <\lceil\operatorname{lb} q\rceil$。

2) 解压缩函数:

$ \text { Decompress }_{q}(c, d)=\left\lceil\left(q / 2^{d}\right) \cdot c\right\rceil $

其中, $c \in\left\{0, 1, \cdots, 2^{d}-1\right\}, d \in \mathbb{N}^{*} $, 满足$ d <\lceil\operatorname{lb} q\rceil$。

引理5  令$c=\text{Compres}{{\text{s}}_{q}}(x, d), {{x}^{\prime }}=\text{Compres}{{\text{s}}_{q}}(c, d) $, 满足$ \left|x^{\prime}-x \bmod ^{\pm} q\right| \leqslant B_{q}=\left[\frac{q}{2^{d+1}}\right]$, 其中, $\left|x^{\prime}-x \bmod ^{\pm} q\right| \leqslant B_{q}=\left[\frac{q}{2^{d+1}}\right] $在B_q上服从均匀分布, 且在B_q－1上此分布整数大小相等。

1.2 带消息恢复的签名算法

文献[14]提出带消息恢复的签名算法, 其中每一个用户都有一对密钥, 即一个需要公开的公钥和一个需要秘密保存的私钥。当用户需要对某个消息m进行签名产生对应的数字签名Sig时, 即需要使用自己的私钥和消息m=(m₁‖m₂)进行签名运算, 运算结果就是签名值。签名值只需要消息m中的部分消息m₂表示。任何人都可以使用该用户的公钥来恢复消息和验证签名是否正确, 并且没有人能够在用户私钥未知的前提下伪造出一个合法的消息签名对。此算法可解决签名消息过长的问题。

定义2   1个带消息恢复的签名算法包括3个多项式时间算法, 即签名密钥生成算法SigKeyGen(1^λ)、签名算法Sig((f, g), m=(m₁‖m₂))和验证算法Ver(h, σ=(s₁, s₂, m₂))。

1) 签名密钥生成算法SigKeyGen(1^λ):{f, g←D_f, h←f/g mod q}得到(K_s, K_v)=(g, h)。

2) 签名算法Sig((f, g), m=(m₁‖m₂)):{t=(m₁+F(H′(m)) mod q‖H′(m))s₁, s₂←D_s满足(f/g)s1+s₂=t mod q, 得到σ=(s₁, s₂, m₂)。

3) 验证算法Ver (h, σ=(s₁, s₂, m₂)):(t₁‖t₂)←hs₁+s₂ mod q, m₁←t₁－F(t₂) mod q, 若(s₁, s₂) ‖ < B并且H′(m₁‖m₂)=t₂, 则接受; 否则拒绝。

1.3 Encode函数与Decode函数

定义3 ^[10]   用户A选取v∈{0, 1}ⁿ环元素k, 即每4个${{\mathbb{Z}}_{q}} $元素中编码v的一个比特, 用户B根据收到的k′, 取在{0, 1, …, q－1}范围中的4个系数减去$ \lfloor q / 2\rfloor$, 累积它们的绝对值, 若得到的结果小于q则v_i取1, 否则取0。可容忍更大的错误, 从而降低了模数, 缩减了通信量。Encode函数和Decode函数的具体描述如下:

Encode(v∈0, 1ⁿ)

输入k

对于i从0到n－1循环执行:

$ {{\text{k}}_{\text{i}}}\leftarrow {{\text{v}}_{\text{i}}}\cdot \left\lfloor \text{q}/2 \right\rfloor $;

${{\text{k}}_{\text{i}+\text{n}}}\leftarrow {{\text{v}}_{\text{i}}}\cdot \left\lfloor \text{q}/2 \right\rfloor $;

$ {{\text{k}}_{\text{i}+2\text{n}}}\leftarrow {{\text{v}}_{\text{i}}}\cdot \left\lfloor \text{q}/2 \right\rfloor $;

输出k

$\text { Decode }\left(\mathrm{k}^{\prime} \in \mathbb{R}_{\mathrm{q}}\right) $

输入k′, 对于i从0到n－1循环执行:

$\mathrm{t} \leftarrow \sum\limits_{\mathrm{j}=0}^{3}\left|\mathrm{k}_{\mathrm{i}}^{\prime}+\mathrm{n} \cdot \mathrm{j}-\lfloor\mathrm{q} / 2\rfloor\right| $;

若t < q则k′_i←1;

否则k′_i←0;

输出k′

1.4 AKE协议安全模型

模型中的参与者包含有限元素的集合P_i和攻击者A。参与者之间的通信网络被攻击者A完全控制, 攻击者A可以任意地窃听、重放、插入消息。协议参与者刻画为预言机Π_{i, j}^s表示参与者i与参与者j进行会话的第s个实例。

模型中会话密钥的安全性通过模拟者和攻击者之间的游戏定义。首先攻击者A选择一定数量的诚实参与者, 通过提供攻击者以下查询来建模攻击者的能力:

1) Send(Π_{i, j}^s, M)。攻击者A向预言机Π_{i, j}^s发送消息M。Π_{i, j}^s按照协议规范做出对消息M的应答, 接受(Accept)或拒绝(Refuse)本次会话。

2) Reveal(Π_{i, j}^s)。收到此查询, 预言机Π_{i, j}^s返回已经完成的会话密钥, 如果该预言机返回的状态不是已接受(Accepted), 则返回空值符号⊥。

3) Corrupt(i)。攻击者A通过此查询来腐化参与者i。要求被询问的协议参与者返回参与者i的长期私钥, 同时称参与者i被腐化(Corrupted)。

4) Test(Π_{i, j}^s)。在某个时刻, 攻击者A可以向一个新鲜的预言机Π_{i, j}^s发送Test查询。预言机Π_{i, j}^s随机选择b∈{0, 1}回答此查询。若b=1, 则令K←Reveal(Π_{i, j}^s)并返回K; 否则返回会话密钥空间{0, 1}^λ的一个随机值, λ表示会话密钥的位长度, 攻击者只可以发送一次Test查询。

如果2个预言机Π_{i, j}^s和Π_{i, j}^s′在一次协议运行完成后, 具有相同的会话标识, 则称它们互为匹配会话。

通过模拟一个挑战者与攻击者之间的游戏定义AKE协议的安全性。游戏分为以下4个阶段:

第1阶段  攻击者A可以进行任意除Test以外的查询, 预言机并给出相应答案。

第2阶段  在游戏的某一时刻, 攻击者A对一个新鲜的预言机Π_{i, j}^s进行Test查询。预言机Π_{i, j}^s随机选择b∈{0, 1}回答此查询。若b=1, 则令K←Reveal(Π_{i, j}^s), 并返回K; 否则返回会话密钥空间{0, 1}^λ的一个随机值, λ表示会话密钥的位长度。

第3阶段  攻击者A仍然可以进行任意除Test以外的查询, 预言机给出相应答案, 但攻击者询问受到协议会话新鲜性约束, 即预言机Π_{i, j}^s满足:1)攻击者没有向预言机Π_{i, j}^s及其匹配会话Π_{i, j}^s′进行Reveal查询; 2)参与者j都没有被腐化, 则称预言机Π_{i, j}^s是新鲜的。

第4阶段  攻击者A结束游戏, 输出猜测值b′。

对于任意攻击者A, 如果A赢得上述游戏的优势$\mathrm{Adv}_{\mathrm{A}}=\left|2 \operatorname{Pr}\left[b^{\prime}=b\right]-1\right| $是可忽略的, 则称该认证密钥协商协议是安全的。

2 算法设计及方案构造

认证密钥交换协议包括2个阶段, 即系统建立阶段Setup和会话密钥的协商阶段KeyExchange。

2.1 系统建立阶段

H₁和H₂分别是在{0, 1}^l₁和{0, 1}^l₂上的抗碰撞哈希函数, 通信双方分别使用带消息恢复功能的签名算法, 选取{f, g←D_f, h←f/g mod q}, 生成自己的签名密钥对:

$ \begin{array}{*{35}{l}} \operatorname{Sig}\operatorname{KeyGen}\left( {{1}^{\lambda }} \right)\to \left( {{K}_{\text{SA}}}, {{K}_{\text{VA}}} \right)=\left( {{g}_{\text{A}}}, {{h}_{\text{A}}} \right) \\ \operatorname{SigKeyGen}\left( {{1}^{\lambda }} \right)\to \left( {{K}_{\text{SB}}}, {{K}_{\text{VB}}} \right)=\left( {{g}_{\text{B}}}, {{h}_{\text{B}}} \right) \\ \end{array} $

2.2 会话密钥的协商阶段

用户U_A和用户U_B通过交换公共信息来协商出一个共享的会话密钥, 具体过程如下:

1) 用户U_A随机选取种子参数ρ←{0, 1}ⁿ, 获取公共参数a←Sam(ρ), 采样s, e←χ_α, 计算环元素$ b=a s+e \in \mathbb{R}_{q}$, 将环元素b分为(b₁‖b₂)作签名消息, 用带消息恢复功能的签名算法对(b₁‖b₂)进行签名, 得到t=(b₁+F(H′(b))mod q‖H′(b)), 采样s₁, s₂←D_s, 使其满足(f_A/g_A)s₁+s₂=t mod q。生成签名值Sig (K_SA, (b₁‖b₂))→(s₁, s₂, b₂)=σ₁, 其中σ₁包含可恢复全部消息的b₂, 最后将签名值σ₁和种子ρ发送给用户U_B。

2) 用户U_B收到σ₁、ρ后, 使用验证算法得到(t₁‖t₂)←h_As₁+s₂mod q, b₁←t₁－F(t₂) mod q验证并恢复得到Ver(K_VA, σ₁)→(b₁‖b₂)=b, 同时根据验证算法中的要求验证用户U_A发送的信息是否满足要求, 若(s₁, s₂)‖ < B同时满足H′(b₁‖b₂)=t₂, 若不满足要求则终止并输出⊥, 反之用户U_B根据收到的种子参数ρ, 计算a←Sam(ρ), 采样选择s′, e′, e″←χ_α, 计算u=as′+e′。选取v←{0, 1}ⁿ, 并利用Encode编码函数将v编码成环元素k= $ \text { Encode }\left(H_{1}(v)\right) \in \mathbb{R}_{q}$, 接着使用编码后得到的k加密计算得到环元素c=bs′+e″+k∈_q, 使用哈希函数得到Auth←H₂(σ₁, (u, c), k), 将计算得到的Auth和密文(u, c)水平拼接得到C-←((u, c)‖Auth), 用带消息恢复功能的签名算法对C-进行签名:首先, 令$ \left(\bar{C}_{1} \| \bar{C}_{2}\right)=\overline{\mathrm{C}}$, 选取$ s_{1}^{\prime}, s_{2}^{\prime} \leftarrow D_{s}$, 计算得到$t^{\prime}=\left(\bar{C}_{1}+F\left(H^{\prime}(\bar{C})\right) \bmod q \| H^{\prime}\left(\bar{C}_{1}\right)\right) $, 使其满足$ \left(f_{\mathrm{B}} / g_{\mathrm{B}}\right) s_{1}^{\prime}+s_{2}^{\prime}=t^{\prime} \bmod$。得到签名值Sig(K_SB, $ \left.\left(\bar{C}_{1} \| \bar{C}_{2}\right)\right) \rightarrow\left(s_{1}^{\prime}, s_{2}^{\prime}, \bar{C}_{2}\right)=\sigma_{2}$, 其中σ₂包含可恢复全部消息的$ \bar{C}_{2}$, 将σ₂、Auth发送给用户U_A, 最后计算得到会话密钥$ S K_{\mathrm{B}} \leftarrow H_{1}\left(\sigma_{1}, \sigma_{2}, H_{1}(v)\right)$。

3) 用户U_A收到σ₂、Auth后, 使用验证算法得到$ \left(t_{1}^{\prime} \| t_{2}^{\prime}\right) \leftarrow h_{\mathrm{B}} s_{1}^{\prime}+s_{2}^{\prime} \bmod q, \bar{C}_{1} \leftarrow t_{1}^{\prime}-F\left(t_{2}^{\prime}\right) \bmod q$验证并恢复得到$ \operatorname{Ver}\left( {{K}_{\text{VA}}}, {{\sigma }_{1}} \right)\to \left( {{{\bar{C}}}_{1}}\|{{{\bar{C}}}_{2}} \right)=\bar{C}=(u, c)$, 同时并根据验证算法中的要求验证用户U_A发送的信息是否满足要求, 验证(s′₁, s′₂)‖ < B与$ H^{\prime}\left(\bar{C}_{1} \| \bar{C}_{1}\right)=t_{2}^{\prime}$, 若不满足要求则终止并输出⊥, 反之则计算k′=c－us, 使用哈希函数验证$ \text{Auth} \stackrel{?}{=}H_{2}\left(\sigma_{1}, (u, c), k^{\prime}\right)$, 若不满足要求则终止并输出⊥, 反之则使用解码函数Decode(k′)计算得到H₁(v), 最后使用哈希函数得到会话密钥SK_A←H₁(σ₁, σ₂, H₁(v))。

若按照上述协议执行, 最终交易双方得到相同的会话密钥, 即SK_A=SK_B, 具体的交换过程如图 1所示。

3 安全性分析 3.1 正确性证明

若用户U_A和用户U_B诚实地运行协议, 那么双方获得相同的密钥$S K_{\mathrm{A}}=S K_{\mathrm{B}} $成立。

证明  用U_A计算得到$ k^{\prime}=c-u s=c-a s s^{\prime}-e^{\prime} s$, 用户U_B计算得到$k=c-b s^{\prime}-e^{\prime \prime}=c-a s s^{\prime}-e^{\prime} s^{\prime}-e^{\prime \prime} $, 即$k=k^{\prime}+e^{\prime} s-e s^{\prime}-e^{\prime \prime} $, 令$ e_{2}=e^{\prime} s-e s^{\prime}-e^{\prime \prime}$, 其中${{s}^{\prime }}, e, {{e}^{\prime }}, {e}''\leftarrow {{\chi }_{\alpha }} $, 根据引理4, 得到$\left|e_{2}\right| \leqslant 8 \cdot(\alpha q \sqrt{n})· (\alpha q \sqrt{n})=8(\alpha q) \cdot n \leqslant \frac{q}{4}-2$, 由定义3可知, 取k′在{0, 1, …, q－1}范围中的4个系数减去$ \lfloor q / 2\rfloor$, 累积其绝对值, 即$t \leftarrow \sum\limits_{j=0}^{3}\left|v_{i}+n \cdot j-\lfloor q / 2\rfloor\right| $。又因为$k=k'+e_{2}, \sum\limits_{j=0}^{3}\left|v_{i}+k^{\prime} \cdot j-\lfloor q / 2\rfloor+\right| e_{2}|| \leqslant \frac{q}{4}+1+\left|e_{2}\right| \leqslant \frac{q-1}{2}$, 即Decode(k′)=Decode(k)=H₁(v), 所以$S K_{\mathrm{A}}=S K_{\mathrm{B}} $。证毕。

3.2 安全性证明

设n是安全参数, $ \alpha <(\operatorname{lb} n / n)^{1 / 2}, q=1 \bmod m$是一个多项式有界的素数且$\alpha q \geqslant \omega(\sqrt{\operatorname{lb} n}) $。若RLWE_{q, χ}是困难问题, 则本文方案在标准模型下是CK安全的。

证明:通过一系列得模拟游戏, 证明通信内容不会泄露秘密的信息, 并证明通信双方交换的密钥与随机数不可区分。设sid^*表示测试会话标示符, 攻击者A尝试区分会话密钥SK和均匀随机密钥SK′, 定义攻击者A赢得游戏的优势为:

$ \operatorname{Adv}(\mathrm{A})=\left|\operatorname{Pr}\left[b^{\prime}=1 \mid b=1\right]-\operatorname{Pr}\left[b^{\prime}=1 \mid b=0\right]\right| $

游戏G₀  最初的游戏是对所有拥有签名密钥对(K_s, K_v)的诚实用户的攻击。在游戏中, 攻击者A发送消息M进行询问使模拟器使用他的密钥应答。当攻击者使用Test-query对模拟器进行查询, 模拟器随机选取b∈{0, 1}回答查询, 若b=1, 返回真实密钥给A; 否则返回sk←0, 1^l₁。根据定义有:Adv_AKE^fs-ind=Adv_G0(A)=Pr[b′=1|b=1]－Pr[b′=1|b=0]。

游戏G₁  此游戏与游戏G₀基本相同, 不同之处在于:模拟器P选取s′_b, e′_b, e″_b←χ_α, 选取$s_{a}, e_{a}, \longleftarrow \chi_{\alpha} $, 计算$u=a s_{b}^{\prime}+e_{b}^{\prime} $, 选取k∈{0, 1}ⁿ, 计算$ c=b s_{b}^{\prime}+e_{b}^{\prime \prime}+a \times k \in \mathbb{R}_{q}$, 选取$ \mathrm{Auth} \leftarrow \mathbb{R}_{q}$按照协议计算出σ₂、并将σ₂、Auth发送给攻击者A。

在签名方案的强不可伪造性下, 此修改不会改变攻击者A的优势。一旦伪造文件被发现, 不需要运行完整个协议, 签名方案立即被破坏。同时, c的分布与其他一般分布不可区分, 所以, 猜测出$ c=b s_{b}^{\prime}+e_{b}^{\prime \prime}+a \times k$的概率可以忽略。因为$c=a\left(s_{a} s_{b}^{\prime}+k\right)+e_{b}^{\prime \prime}+e_{a} $, 根据引理2可知, $ {s}_{a} {s}_{b}^{\prime}+{k}$的分布与χ_α的分布小于4ε, 基本可以忽略, 则游戏G₁中c的分布接近游戏G₀中c的分布, 即A无法区分。若RLWE_{q, χ}是困难问题, 则:

$ \left| {{{{\mathop{\rm Adv}\nolimits} }_{{{\rm{G}}_{\rm{1}}}}}({\rm{A}}) - {{{\mathop{\rm Adv}\nolimits} }_{{{\rm{G}}_{\rm{0}}}}}({\rm{A}})} \right| \le {\mathop{\rm negl}\nolimits} (n) $

游戏G₂  此游戏与游戏G₁基本相同, 不同之处在于:模拟器P选取$ u \leftarrow \mathbb{R}_{q}, k \in\{0, 1\}^{n}$, 选取$C \leftarrow \mathbb{R}_{q} $, 计算$ \text { Auth } \leftarrow H_{2}\left(\sigma_{1}, (u, c), k\right)$, 按协议计算σ₂←Sig(K_SB, ((u, c), Auth)), 选取SK_B←(0, 1)ⁿ, 并将σ₂、Auth发送给攻击者A。将游戏G₂中随机选取的SK_B代替游戏G₁中的最终密钥, 在满足带消息恢复功能签名验证算法条件下, 得到验证后的信息满足(s₁, s₂)‖ < B和H′(m₁‖m₂)=b₂, 并得到(((u, c), Auth)←Ver(K_VB, σ₂)的输出统计接近均匀分布, 游戏与游戏计算不可区分, 有$ \left| {{{{\mathop{\rm Adv}\nolimits} }_{{{\rm{G}}_2}}}({\rm{A}}) - {{{\mathop{\rm Adv}\nolimits} }_{{{\rm{G}}_1}}}({\rm{A}})} \right| \le {\mathop{\rm negl}\nolimits} (n)$。会话状态完全随机化, 则敌手不能通过Test询问获得任何优势。

游戏G₃  此游戏与游戏G₂基本相同, 不同之处在于:A可以重放之前的数据。为抵抗重放攻击, 需要猜测哪个会话将要被测试, 通过密钥生成算法和加密算法产生:(K_d^*, K_e^*)←KEMKeyGen(1^λ)和(c^*, k^*)←Enc(K_e^*), 嵌入一个特定的元组(K_d^*, K_e^*, c^*, k^*)。通过第q₁次的Send-query猜测第一次发送的K_e^*的时间, 通过第q₂次的Send-query查询c^*被发送回来的时间。确切而言, 之前的测试会话涉及密钥对(K_e^*, c^*), 第一个数据σ₁^*是对第q₁次的Send-query的重放, c^*包含在σ₁^*输出到第q₂次的Send-query。

模拟器P生成一个特定的元组(K_d^*, K_e^*, c^*, k^*), 并猜测q₁, q₂←{1, 2, …, q_s}, q_s是Send-query次数的上限。如果Send-query的输入是σ₁^*, 则除了第q₁次的Send-query用一个签名的K_e^*来回答和第 q₂次的Send-query用一个签名的(c^*, Auth^*)来回答, 其他所有的查询都像往常一样回答。如果输入的Send-query不是σ₁^*, 则中止模拟并输出一个随机的b₀。概率大于1/q_s²的概率, 则猜测是正确的。

通过以上方法, 模拟器P可以检测出是否攻击者A存在重放攻击, 攻击者A无法获得这些猜测信息, 因为模拟器P仍然存在使用K_d^*用于完成协议的执行, 所以重放攻击无效, 有$ \left| {{{{\mathop{\rm Adv}\nolimits} }_{{{\rm{G}}_3}}}({\rm{A}}) - {{{\mathop{\rm Adv}\nolimits} }_{{{\rm{G}}_2}}}({\rm{A}})} \right| \le {\mathop{\rm negl}\nolimits} (n)$。

游戏G₄  此游戏与游戏G₃基本相同, 不同之处在于:不再使用K_d^*来进行模拟。只有第一个生成σ₁^*的实例才会使用K_d^*, 因此攻击者A会发送其他的σ₁^*。在重放的情况下, A不能提出Reveal或Test查询, 但对于模拟器P, K_AS可以在没有K_d^*的情况下进行模拟。所以游戏G₄中A的优势相比于游戏G₃可忽略不计, 即$\left| {{{{\mathop{\rm Adv}\nolimits} }_{{{\rm{G}}_4}}}({\rm{A}}) - {{{\mathop{\rm Adv}\nolimits} }_{{{\rm{G}}_3}}}({\rm{A}})} \right| \le {\mathop{\rm negl}\nolimits} (n) $。

游戏G₅  此游戏与游戏G₄基本相同, 不同之处在于:对于第一次发送σ₁^*的特定会话, 在A提出Reveal或Test查询的情况下, 当k′≠k解密失败时, 即使通过Ver(h, σ=(s₁, s₂, m₂))算法认证匹配, 也会输出sk→⊥。当k′≠k只有在H₂(σ₁, c, k′)=Auth时存在小的差异: $ \operatorname{Adv}_{\mathrm{G}_{4}}(\mathrm{A}) \leqslant \mathrm{Adv}_{\mathrm{G}_{3}}(\mathrm{A})+\frac{1}{2^{l_{2}}}$。

定义标记CorrectGuess来表示是否sk→⊥解密失败或者sk₁←sk₂解密成功, 模拟器P不会显式地计算CorrectGuess的值。有:

$ \begin{array}{l} {{\mathop{\rm Adv}\nolimits} _{{{\rm{G}}_5}}}({\rm{A}}) = \mid \mathop {\Pr }\limits_{{{\rm{G}}_5}} \left[ {{b^\prime } = 1 \wedge {\rm{ CorrectGuess }}\mid b = 1} \right] - \\ \mathop {\Pr }\limits_{{{\rm{G}}_5}} \left[ {{b^\prime } = 1 \wedge {\rm{ CorrectGuess }}\mid b = 0} \right]\mid = \\ \mid \mathop {\Pr }\limits_{{{\rm{G}}_4}} \left[ {{b^\prime } = 1 \wedge {\rm{ CorrectGuess }}\mid b = 1} \right] - \\ \mathop {\Pr }\limits_{{{\rm{G}}_4}} \left[ {{b^\prime } = 1 \wedge {\rm{ CorrectGuess }}\mid b = 0} \right]\mid \end{array} $

标记CorrectGuess对游戏G₅的比特b′无影响, 这两个事件是独立的:Adv_G5(A)=Adv_G4(A)/2。

游戏G₆  此游戏与游戏G₅基本相同, 不同之处在于:模拟器P不需要K_d^*, 因此, 生成元组(K_e^*, c^*, k^*)来稍微修改游戏G₅, 同样, 元组中的数值由(K_d^*, K_e^*)←KEMKeyGen(1^λ)和(c^*, k^*)←Enc(K_e^*)生成的, 所以得到Adv_G6(A)-Adv_G5(A)≤negl(n)。

游戏G₇  此游戏与游戏G₆基本相同, 不同之处在于:模拟器不需要k^*, 只给出元组(K_e^*, c^*), 模拟器P设置Auth←{0, 1}^l₂和sk²←{0, 1}^l₁。只有攻击者A要求将实际封装的密钥k^*到H₁或H₂, 否则其与真实协议是完美的无法区分。

在最后的游戏中, 测试会话的会话密钥是真实随机的, 因此与随机的情况没有区别:Adv_G7(A)=0。

通过以上游戏, 可知攻击者A的优势是可忽略的。证毕。

4 性能分析

本节对所提出的格上基于KEM的认证密钥交换协议方案进行性能分析, 性能主要体现在3个方面:

1) 发送方选择定比特长的随机字符串, 将这个随机字符串中每4个元素使用Encode函数编码其中的一个比特, 编码后的环元素可容忍更大的错误, 从而降低了模数, 缩减了通信量。

2) 使用Compress压缩函数, 对密文元素进行压缩, 在保证密文恢复完整性的前提下, 有效减少通信量, 减轻服务器的传输负荷。

3) 利用带消息恢复功能的签名算法, 对方案中发送消息进行签名, 在发送的过程中, 用户双方只需要发送消息的部分值, 有效降低了传输过程中的通信量。

定义环$\mathbb{R}_{q}=\mathbb{Z}_{q}[X] /\left(X^{n}+1\right) $, 设置n=1 024, q=12 289。从认证性、困难假设和构造方式等方面与同类协议进行比较。方案效率由计算复杂度和通信量组成。计算复杂度主要考虑向量乘法和抽样。通信量考虑发送字节总数。与文献[6, 10]方案的分析对比结果如表 1所示。

本文方案和所对比的方案均为标准模型下构造。由表 1可以看出, 在通信量方面, 本文方案采用Encode函数和Compress压缩函数, 大幅缩短了密文的尺寸, 有效降低了通信代价, 同时使用带消息恢复功能的签名算法, 在保证协议认证性的同时, 也降低了通信量, 与文献[10]方案相比, 本文协议不但可实现相互认证, 降低了通信量同时避免使用计算复杂的调和机制而使用计算简单的加密机制, 方案计算更加简洁高效。本文协议的封装和解封装采用R-LWE困难假设, 与文献[6]相比, 解决了密文尺寸过长的问题。

综上可知, 与同类方案相比, 本文方案具有较低的通信量, 计算复杂度也在可接受范围内。因此, 从方案的效率参数和计算效率分析, 本文协议更具有实际应用价值。

5 结束语

认证密钥交换协议被广泛应用于互联网安全协议和传输层安全协议中, 可有效提高实体间的通信效率。本文基于R-LWE困难假设, 以加密的构造方法代替Peikert错误协调机制, 提出一种基于KEM的认证密钥交换协议。将KEM和带消息恢复功能的数字签名相结合, 实现协议的认证性, 同时降低需要发送的签名密文长度, 大幅减少通信量。利用格上基于R-LWE问题构造的密码系统具有密钥、密文尺寸小的优点, 可提高AKE协议效率, 并且有效抵抗量子攻击。本文方案基于R-LWE困难假设构造, 而LWE的安全性较R-LWE更为稳健, 下一步将考虑在维持较低通信量的情况下, 基于LWE构造强安全的认证密钥交换方案。