基于RLWE认证密钥协商算法的设计

Design of Authenticated Key Agreement Algorithm Based on RLWE

摘要: 密钥协商算法允许参与者在非安全信道中交换信息共同协商会话密钥用于保密通信，是密码学中最关键技术之一。本文基于RLWE困难问题，利用四舍五入密钥共识算法，Filtering引理及哈希函数，设计了一个新的基于RLWE困难问题的认证密钥协商算法。新的认证密钥协商算法具有高效与可证明安全的特点。

Abstract: Key agreement algorithm allows participants to exchange information in the open channel to gener-ate a secure temporary session key to ensure secret communication, which is one of the key tech-nologies in cryptography. In this paper, a novel authenticated key agreement algorithm based on RLWE difficulty problem is proposed using rounded key consensus algorithm, filtering lemma and hash function. The new authenticated key agreement algorithm is proved to be efficient and prova-bly secure.

1. 引言

格是一种建立在偏序集合上的代数结构，起源于1611年开普勒提出的关于容器内堆放等半径小球所达最大密度的猜想。后来格作为一种密码分析工具用于攻击破解密码体制 [1] [2]。1996年，美国布朗大学的Jeffrey Hoffstein、Jill Pipher和Joseph H. Silverman三位数学教授发明了一种公钥密码体制NTRU [3]。2009年，Gentry基于格密码构造了首个全同态密码方案 [4]，格密码得到极大的发展。2015年美国国家标准研究和技术研究学院发布了“后量子密码报告” [5]。报告表明，由于计算机运算速度的不断提高，现有的公钥密码在未来面临着极大的挑战。NIST在全球范围内征集后量子密码算法标准。具有抗量子计算的格密码公被认为最具竞争力的后量子算法。尤其近几年格密码得到快速发展，许多优秀的研究成果 [6] [7] [8] 如雨后春笋一般出现。

近几年国内在后量子密码算法研究方面也取得了很大的进展。2018年6月，由国家密码管理局指导，中国密码学会同密码行业标准化技术委员会，商用密码检测中心共同组织实施，全国密码算法设计竞赛开始，历时一年半，于2019年12月分别遴选出公钥密码算法和分组密码算法一、二、三等奖 [9]。

国内外格密码发展一片欣欣向荣，产生很多优秀的算法。 [10] [11] 等论文直接使用格困难问题设计密钥封装方案，具有高效与可证明安全性的特点。J. W. Bos，L. Ducas，E. Kiltz，T. Lepoint等人提出了一种基于CCA安全加密的可认证密钥交换通用结构 [12]，在此论文中提到了一种通用的数字签名方案，具有简单直接的特点，但签名过程较为繁琐效率低，且有私钥泄露的风险，不具备完全向前保密性。 [13] [14] 提出将密钥共识机制与RLWE困难问题相结合的方案，此类方案较为成熟，现在仍未发现有效的破解方案，丰富了密钥封装方案的思路。但是这些密钥协商方案没有认证的功能，也就是在密钥协商过程中没有对双方的身份和收到的消息进行认证。

本文基于RLWE困难问题，结合数字签名技术，设计了一种更加安全高效的具有认证功能的密钥协商算法。算法仅用一对密钥对进行加密处理，通过中止技术来解决私钥泄露问题。由于在签名方案中，不存在交互，因此签名者不需要将中止的签名包含到最终签名中。如果签名者需要中止，他只需重新运行协议，直到获得正确范围内的签名。这样可以提高签名效率，从而保证通信的安全性，高效性，真实性，不可抵赖性和完整性。

2. 基础知识

2.1. 定义与符号

本文将用粗体小写字母表示矢量，大写字母表示矩阵。比如，a₁，a₂是Zⁿ的两个元素， $A=\left(a_1,a_2\right)$ 。默认情况下，所有向量都是列向量。对于一个向量a (或矩阵A)，我们用a^T (或A^T)表示它的转置。对于实数 $x\in R$ ，我们使用 $\lfloor x\rfloor$ 表示向下取整，即 $\lfloor x\rfloor$ 表示不大于x的最大整数。定义x的四舍五入表示：，当x为向量、矩阵或者多项式运算时，上面所定义的四舍五入和向下取整均是对分量或系数进行的运算。

设 $Z$ 是有理整数环，设 $R=Z\left[X\right]/\left({\Phi }_m\left(X\right)\right)$ 是第m个割圆数域的整数环， ${\Phi }_m\in Z\left[X\right]$ 是m次割圆多项式。本文中采用 ${\Phi }_m=x^n+1$ ， $n=2^r$ ， $r>0$ ， $m=2n$ 。本文规定q是素数且 $q\equiv 1\left(\mathrm{mod}2n\right)$ ， $R_q=R/qR\cong Z_q\left[X\right]/\left(X^n+1\right)$ ，其中 $Z_q=Z/qZ$ 。 $y\leftarrow R_q$ ，表示y的每个分量或系数均独立地服从分布 $R_q$ ，且y的系数属于集合 $\left[-\left(q-1\right)/2,\left(q-1\right)/2\right]$ 。用符号 $x^{\prime }=x\mathrm{mod}q$ ，q为正整数，表示 $x^{\prime }$ 的系数属于集合 $\left[0,q-1\right]$ ， $x^{\prime }=x{\mathrm{mod}}^{\pm }q$ ，q为正整数，表示 $x^{\prime }$ 的系数范围属于集合 $\left[-\lfloor \left(q-1\right)/2\rfloor ,\lfloor \left(q-1\right)/2\rfloor \right]$ 。a的无穷范数写做 ${\Vert a\Vert }_{\infty }$ ，对于 $A=\left(a_1,a_2,\cdots ,a_m\right),{\Vert A\Vert }_{\infty }={\max }_i{\Vert a\Vert }_{\infty }$ 。最后本文采用与Kyber [12] 原算法中同样的噪声分布B_η，其定义如下：

$\left(a_1,\cdots ,a_{\eta },b_1,\cdots ,b_{\eta }\right)\leftarrow {\left(0,1\right)}^{2\eta }$ 输出 ${\displaystyle \underset{i=1}{\overset{\eta }{\sum }}\left(a_i-b_i\right)}$ (1)

2.2. 格

定义：设 $x_1,x_2,\cdots ,x_m$ 是n维空间 $R^n$ 上线性无关的向量，m维格 $L\left(x_1,x_2,\cdots ,x_m\right)$ 是由向量 $x_1,x_2,\cdots ,x_m$ 生成的一个向量集，形式表示为

$L\left(x_1,x_2,\cdots ,x_m\right)={\displaystyle \underset{i=1}{\overset{m}{\sum }}{a}_i{x}_i,a_i\in Z}$ (2)

其中， $\left\{x_1,x_2,\cdots ,x_m\right\}$ 是格L的一组基，记为 $\text{Dim}\left(L\right)=m$ ，(m, n)分别为格L的维数和秩，当m = n时称为格L是满秩。同样的一个格可以采用不同的基底来表示，但是从m维格中选出m个线性无关的向量却不一定能成为这个格的一组基。一个格基通过左乘一个特定矩阵可以转化成另一个格基，这个特定的矩阵是由整数构成，且其行列式为±1。因此格具有离散性和格基多样性。

2.3. 基于格的困难性假设

2009年REGEV O首先提出了LWE (learning with errors)问题 [15]，是对最坏情况格困难问题如GAPSVP和SIVP的一个简化，并证明LWE的安全性基于GAPSVP和SIVP最坏情况的困难问题，近年来它已经成为很多密码应用的基础。

LWE可看作随机线性码的译码问题，给出如下定义： $x\in Z_p^n$ 是某个向量矩阵，存在矩阵 $Q\in Z_p^{m\times n}$ ，使得 $y=Qx+e$ ，e是一个服从 $e\in Z_p^m$ 的干扰信号，LWE问题就是已知Q和y，求x。由于LWE在实际生产应用过程中效率较低，Lyubashevsky，C. Peikert和 O. Regev在LWE的基础上变形出了一种效率更高，安全性和复杂性规约为SVP问题的新问题R-LWE (Learning with Errors over Rings) 困难问题 [16]。R-LWE问题和LWE问题的定义很相似，可以视为一个样本结构固定了的LWE问题。现R-LWE困难问题是基于格密码学一个活跃的研究领域，在这个困难问题上产生了很多优秀成果 [17] [18] [19]。

2.4. 基于格R-LWE的数字签名算法

数字签名是一种以电子形式给一个消息签名的过程，只有消息发送方可以对自己信息进行签名，任意知道公钥的验证者都可以对其进行验证。数字签名可以起到身份认证，保证信息完整性，不可否认性以及匿名性等作用，具有不可伪造性和不可抵赖性。

一个数字签名的形式化定义如下：

系统初始化过程：数字签名含有基本元素为(P, M, K, S, V)，其中P为消息集，M为签名集，K为密钥集合，S为签名算法集合，V为验证算法集合。

签名产生过程： $k\in K$ 对于每一个消息 $p\in P$ 和 $m\in M$ ，存在 $si{g}_k\in S$ ， $si{g}_k:P\to M$ 。将签名消息组(p, m)发送给消息验证者进行验证。

签名认证过程：对于每一个 $k\in K$ 存在一个相应的验证算法 $ve{r}_k\in V$ ，对收到的签名消息组进行验证， $ve{r}_k:P\times M\to \left\{T,F\right\}$ ，

$ve{r}_k\left(p,m\right)=\{\begin{array}{l}T,m=si{g}_k\left(p\right)\\ F,m\ne si{g}_k\left(p\right)\end{array}$ (3)

若 $ve{r}_k\left(p,m\right)=T$ ，则签名验证通过，签名有效，否则签名无效。

本文要用的是基于格R-LWE的数字签名方案。构造格的数字签名算法大部分分为两种途经，一种是利用限门函数 [20] 进行设计的，另一种是基于Fiat-Shamir方法进行转化，后者具有简单高效的特点，因此成为这个算法的首要选择方案。由于格的特殊代数结构，如果直接输出算法的签名，会泄露密钥，为解决这个问题VadimLyubashevsky提出“异常终止”的概念 [21]。中止协议的目的是，验证方可以选择中止协议，以保护有关其密钥的一些信息。本文使用的是均匀分布拒绝抽样格签名，使用的技术为Filtering引理。

Filtering引理，即涉及均匀分布的拒绝抽样算法。只有签名者输出的签名当且仅当落在一个固定的区间之内，签名的输出分布就会服从该区间上的均匀分布，故不会泄露私钥的信息。

Filtering引理定义：设k是一个正整数， $a\in \left\{v\in Z^k:{\Vert v\Vert }_{\infty }\le A\right\}$ ，随机均匀地选取 $b\leftarrow \left\{v\in Z^k:{\Vert v\Vert }_{\infty }\le B\right\}$ ，其中B > A。设随机变量c = a + b，那么c服从于集合 $\left\{v\in Z^k:{\Vert v\Vert }_{\infty }\le B-A\right\}$ 的均匀分布。

基于格R-LWE的数字签名算法的步骤如下：

签名者

密钥产生Gen:

$\left(s,e\right)\leftarrow S_{\eta }^{L\times 1}\times S_{\eta }^{L\times 1}$ ，且其系数服从某个窄的分布

$a\leftarrow R_q^{L\times L}$

$t:=as+e\in R_q^{L\times 1}$

返回公钥 $pk=\left(a,t\right)$ 和私钥 $sk\left(s,e\right)$ 验证者

事实上，

$\begin{array}{c}a{z}_1+z_2-tc=a\left(sc+y_1\right)+ec+y_2-tc=asc+a{y}_1+ec+y_2-tc\\ =\left(as+e\right)c+a{y}_1+y_2-tc=tc+a{y}_1+y_2-tc=a{y}_1+y_2=w\end{array}$

故， $H\left(w,\mu \right)=H\left(a{z}_1+z_2-tc,\mu \right)$

本方案的安全性主要取决于它的可靠性和在哈希函数中发现冲突的难度，只要我们设置合适的参数，以目前的已知技术在哈希函数中寻找冲突是不可行的。

2.5. 密钥协商机制

密钥协商机制是指两人或者多人，在不需要可信第三方的情况下，所有参与者在一个开放网络环境中，利用自己长期密钥对等信息，通过某种密钥协商协议，生成一个共享的临时会话密钥。密钥协商协议是一类极其重要的基础性安全协议。现存的比较高效成熟的密钥协商机制主要是利用 RSA公钥体制、传统椭圆曲线公钥体制ECC和Diffie-Hellman密钥协商体制来实现的。这些传统的算法大都基于大数分解问题，椭圆曲线等数学问题。随着量子的不断发展，计算速度的不断加快，这些算法抵制不了量子计算机时代的带来。基于后量子密码的密钥协商问题也成为热门话题。本文使用的是密钥共识与格困难问题相结合的方法，在这里我们先介绍一种带噪音的四舍五入密钥共识算法。

密钥共识算法KC如下定义：

KC = (parameters, com, che)，其中参数 $\text{parameters}=\left(q,r,b,e,aupa\right)$ ，q控制安全性和效率，r控制共识密钥的范围，b控制带宽，e控制错误率，aupa表示辅助参数，且满足 $2re\le q\left(1-1/b\right)$ ， $r\ge 2$ ， $b\le q$ ， $0\le e\le \left|q/2\right|$

KC算法正确性证明：对于任意 ${\sigma }_1,{\sigma }_2\in Z_q$ ，且 ${\left|{\sigma }_1-{\sigma }_2\right|}_q\le e$ ，都有 $k_1=k_2$ 。

证明：假设 ${\left|{\sigma }_1-{\sigma }_2\right|}_q\le e$ ，存在 $\theta \in Z$ 并且 $\delta \in \left[-e,e\right]$ 使得 ${\sigma }_2={\sigma }_1+\theta q+\delta$ 。从算法KC的第5行到第7行可知，存在 ${\theta }^{\prime }\in Z$ ，使得 $\alpha {\sigma }_1+w+{\theta }^{\prime }{q}^{\prime }={\sigma }_A=k_1\beta +v^{\prime }$ 。从α和β的定义中，我们有 $\alpha /\beta =r/q$ 。将这两个等式带入到Che (算法1的第15行)中k₂的等式中可知

注意到 $\left|v^{\prime }/\beta -v^{″}/b\right|=\left|v^{\prime }b-\beta v^{″}\right|/\beta b\le 1/2b$ ，故

$\left|\left(v^{\prime }/\beta -v^{″}/b\right)-w/\beta +\alpha \delta /\beta \right|\le 1/\left(2b\right)+\alpha /\beta \left(e+1/2\right)$

由假设的条件 $2re\le q\left(1-1/b\right)$ ,我们可以得到右边的严格小于1/2，因此，在取整之后，有 $k_1=k_2$ 。

KC算法安全性证明：当变量满足，k₁，v是相互独立且k₁均匀分布，因此KC算法具有安全性。

证明：定义一个映射，显然f满足一一映射关系，有KC算法第7行可以知道，因此服从中均匀分布。所以服从中均匀分布，且相互独立，而v只受影响不受k₁影响，可证明k₁，v是相互独立且k₁均匀分布。

3. 基于RLWE认证密钥协商算法

根据我们在预备知识中介绍的数字签名与密钥协商的知识，本文提出一个基于格的可认证密钥协商方案，方案介绍如下：

密钥生成：这里使用种子seed生成矩阵

(1) R_q的系数

(2)随机生成私钥

(3)生成公钥

数字签名验证：

Initiator → Responder

(1)使用密钥对对Initiator公钥进行数字签名

(2)，对Y₁进行验证

Responder → Initiator

(1)， 使用临时密钥对和V进行数字签名

(2)

密钥协商：

(1),

(2)

(3)

(4)

(5)

(6)

总流程图如下所示：

Initiator Responder

R_q的系数

公钥和私钥

为对数字签名返回值

为返回的辅助验证信号，c为返回HASH值

通过验证算法继续，未通过算法中断，重新开始

4. 算法分析

4.1. 正确性分析

由第二章方案流程图可知：

。

故

因为我们均随机取自均匀二项分布，他们都是很小的取值，因此可以确定，由1.5可知，当我们密钥共识的两个输入值距离，时，就可以推出。密钥共识算法的正确性与安全性已证，请看1.5。

4.2. 安全性分析

1) CCA2可证明安全。我们在这里设计一个游戏G0

Game G0：

在此游戏中，任意一个敌手A都不能以绝对的优势可以分辩出和那个是算法产生的，那个是随机选取的，即绝对值是可忽略的。

2) 已知密钥安全：对于参与多个协议的参与者，一次共享密钥的泄露不会影响其他共享密钥的安全进行，换句话说，攻击者A无法根据本次的共享密钥得出参与者的其他共享密钥，称为该方案满足已知密钥安全。

此方案共享密钥的生成不仅与参与者的公钥和私钥有关，且与含噪声的四舍五入KC协议有关，K₁，K₂是在一个范围内近似相同，所以攻击者即使知道共享密钥的值，也不能推测出关于密钥对的相关信息，即满足已知密钥安全。

3) 可抵抗中间人攻击：由于数字签名的存在，此算法可以抵抗中间人攻击。此数字签名具有安全性与不可复制性。有主动性敌手，在不知道私钥的情况下，没有办法攻击成功。由于数字签名特点，也使这个算法具有了密钥泄露伪装安全，即在一方长期泄露密钥的情况下，仍没有办法通过数字签名认证，从而实现共享密钥生成。

4) 密钥控制安全：由于本方案中密钥的建立是由所有参与者的密钥对信息共同参与生成，因此共享密钥的生成是具有随机性和不可预测性，任何一个参与者或者敌手都不能把共享密钥设定为某个确定的值，此方案符合密钥控制安全。

4.3. 效率分析

本方案是在环格的基础上设计的一个带数字签名的密钥协商方案，相对于标准格，R-LWE相对于LWE 允许在相同通信量的情况下传输更大的消息。此方案中使用的基于RLWE的密钥协商协议与其他协议方案相比较，相应计算量和通信量明显减少，是一种简洁高效的后量子PAKE协议，这里 [14] 对此密钥协商方案有详细效率分析。而我们在前面讲过，CCA 安全公钥加密的认证密钥交换通用构造在数字签名部分具有效率低的缺点，而我们改进使用基于R-LWE带异常终止的数字签名，相对于其他数字签名具有更好安全性与高效性。因此整个方案相对于使用CCA 安全公钥加密的认证密钥交换通用构造效率更高。

5. 总结

本文是在阅读大量相关文献后设计的一个在格R-LWE困难问题上可认证密钥协商方案。该方案使用了密钥协商与数字签名，具有安全性，高效性，真实性，不可抵赖性和完整性的特点，但仍存在着效率以及实用性的问题，下一步准备把这个方案与现实场景相结合，提高它的实际工作效率，实现这个方案的价值。

基金项目

国家自然科学基金(61370188)；北京市教委科研计划一般项目(KM202010015009)；北京市教委科研计划资助(No. KM202110015004)；北京印刷学院博士启动金项目(27170120003/020)；BIGC Project (Ec202007)。