基于格的非交互式密钥交换协议

邹小花

摘要： 当前网络中广泛使用的交互式密钥交换协议，如SSL协议和TLS协议，由于密钥建立过程的通信量较大，不适合物联网中传感器等资源有限的轻型网络设备使用，因此提出一种基于格的非交互式密钥交换协议。文章基于格理论的环上带误差学习困难性问题，使用Freire等人给出的非交互式密钥交换协议形式化定义和安全模型对协议的安全性进行分析，通过攻击者与挑战者之间的博弈证明了协议的安全性。该协议具有抗量子攻击安全性，能够有效地提升物联网的通信安全。

关键词： 密码学; 密钥; 格; 非交互式密钥交换

中图分类号：TP309          文献标识码：A      文章编号：1006-8228（2021）10-01-04

Non-interactive key exchange based on lattice

Zou Xiaohua

（Science and Technology College of Nanchang Hangkong university， Nanchang， Jiangxi 332020， China）

Abstract： Currently， the interactive key exchange protocols widely used in the network， such as SSL and TLS， are not suitable for the light network equipment with limited resources such as sensors in the Internet of Things because of the large traffic in the key generation process. Therefore， a lattice based non-interactive key exchange protocol is proposed. In this paper， based on the hard problems of R-LWE from lattice theory， the security of the protocol is analyzed by using the formal definition and security model of non-interactive key exchange protocol proposed by Freire et al. And the security of the protocol is proved by the game between the attacker and the challenger. The protocol has anti-quantum attack security and can effectively improve the communication security of the Internet of Things.

Key words： cryptography; key; lattice; non-interactive key exchange

0 引言

保证数据通信安全性最常见同时也是最基本的方法是使用数据加密技术对传输数据进行加密以保证数据传输的机密性。为实现数据加解密，通信双方必须先进行密钥的协商，通常借助于密钥交换协议来实现。大多数存在的密钥交换协议都是基于交互方式，比如SSL协议和TLS协议。这种类型的协议需要在二者之间进行一轮或多轮的通信交互。对于带宽、电量、計算资源受限的轻型网络设备（例如某些物联网结点）而言，使用交互式密钥交换来协商会话密钥代价太大，难以实现长期、多次的协议执行[4]。

为解决上述问题，采用非交互式的密钥交换协议[5]用于计算和产生一个共享的密钥，仅使用私有秘密信息和其他方的公开信息，通信双方不进行交互。它具备了显著的优点，比如节省通信量和带宽。同时，由于此类协议不需要消息交互，降低了攻击者胜利的可能性，有效的加强了密钥建立过程的安全性。

非交互式密钥交换协议来源于Diffie-Hellman协议[6]，协议双方的gx和gy值分别作为公钥，x和y为相对应私钥，然后Diffie-Hellman协议是一个非交互式密钥交换协议。Bernstein提供了一个非交换式密钥交换协议[7]，基于椭圆曲线，并且设计了安全模型。还有进一步的工作是结合基于身份密码学，提供一个基于身份分级的非交互式密钥协商协议[8-10]。在基于身份的密码体系中，私钥产生于密钥生成中心，用户的公钥是它的识别信息，目的是为了解决在PKI体制中管理证书和存储问题。

上述方案的一个严重问题在于未经过严格的安全性模型分析安全性，因此可能存在潜在的安全风险点。Freire和Hofheins等人对非交互协议的安全性进行了系统分析，并给出了严格的形式化定义和安全模型[11]。

上述方案的安全性是基于大整数分解的难点或者离散对数问题。在量子计算机产生后，这些方法将遭到非常大的安全隐患[12]。它是当前的迫切需求。基于格的密码体制是后量子时代密码安全体制的最佳方案[13]。在当前密码学研究领域已经出现了基于格的公钥密码方案[14-15]、密钥交换协议[16]、数字签名方案[17]等密码学本原，但是仍未出现基于格的非交互式密钥交换协议。目前密码学领域的紧迫目标是研究抵抗量子攻击的密码学方案，后量子时代安全密码体制的最重要的方案之一就是基于格的密码体制。

格理论的带误差学习（Learning with Error）困难性问题作为本文使用的底层数学基础，设计一个基于格的非交互式密钥交换协议，并使用Freire等人[11]的安全模型证明协议的安全性。

1 非交互式密钥交换协议的形式化定义和安全模型

使用Freire等人[11]的形式化定义和安全模型对协议进行设计和分析。

1.1 形式化定义

一个非交互式密钥交换协议包括三个算法： CommonSetup，NIKE.KeyGen和SharedKey。同时还包含一个身份标识空间IDS以及一个共享密钥空间SHK。上述各算法的形式化定义为：

- Common Setup：输入安全参数1k，输出系统参数params;

- NIKE.KeyGen：输入params和一个身份标识 [ID∈IDS]， 输出该ID对应用户的密钥对（pk， sk）， 该算法是概率性的，任何用户都可以执行该算法;不失一般性，假设params包含在pk之中;

- SharedKey：输入[ID1∈IDS]和对应的公钥pk1以及[ID2∈IDS]和对应的私钥sk2，输出属于集合SHK的共享密钥，或者输出一个失败符号。

上述非交互式密钥交换协议必须满足参与双方计算出相同共享密钥的正确性要求，即SharedKey（ID1，pk1，ID2，sk2）=SharedKey（ID2，pk2，ID1，sk1）。

1.2 安全模型

非交互密钥交换协议的安全性是通过攻击者A和挑战者C之间的博弈来产生。输入 是以安全参数1k的C，使用CommonSetup算法， 将算法输出的params传递给A。C进一步选择一个随机比特b，并回答A的查询，直到A输出对b的猜测[b]，A可以执行以下查询。

⑴ 注册诚实用户ID 此时C应该注册一个身份标识为ID的诚实用户，并将该用户的pk返回给A。

⑵ 注册被攻陷用户ID A向C提供一个身份标识ID和对应公钥pk，C记录（corrupt， ID， pk）。

⑶ 用户私钥查询 A向C提供一个诚实用户的身份标识ID，C向A返回该用户的sk。

⑷ 共享密钥揭示查询 A向C提供两个身份标識ID1和ID2， 其中至少有一个是诚实用户，另一个可以为被攻陷用户;此时C应用使用一个诚实用户的私钥和另一个用户的公钥执行共享密钥生成算法，并将结果返回给A;此查询中如果两个用户均为诚实用户，则称为诚实揭示，如果一个用户是诚实用户，另一个用户为攻陷用户，则称为攻陷揭示。

⑸ 测试查询 A向C提供两个诚实用户的身份标识ID1和ID2，C根据b的值向A返回ID1和ID2的共享密钥或者一个同等长度的随机值。A输出对b的猜测值[b]。称攻击者A赢得该博弈，若b=[b]，定义攻击者A在该博弈中的优势为。

[AdvAk=Prb=b-12]

若攻击者A赢得的概率和1/2没有显著区别，则认为非交互式密钥交换协议是安全的。

2 格密码学基础

2.1 格

定义1（格） 格是空间Rm上n个线性无关向量，整数线性组合构成的集合为{b1，b2，…，bn}，记为[LB={i=1nxibi|xi∈Z， i=1，2，…， n}]，{b1，b2，…，bn}称为L（B）的基。

定义2（q-元格） 令[q∈Z]，且q为素数，[A∈Zn×mq]为矩阵，[u∈Znq] ，如下格称为q-元格：

[ΛqA=y∈Zm ?s∈Znq， ATs=y （mod q）}];

[Λ⊥qA=y∈ZmA?y=0 （mod q）}];

[ΛuqA=y∈ZmA?y=u （mod q）}].

定义3（离散高斯分布） 格Λ是以c为中心，以σ为参数的离散高斯分布：

[DΛ， σ， （x）=ρσ，c（x）ρσ，c（Λ）=ρσ，c（x）x∈Λρσ，c（x）]

[ρσ，cx=exp （-π|x-c|2σ2）]

定义4（理想格） 令f（x）为不可约多项式，则定义环[Z[x]]为理想格。

2.2 困难问题

格密码学方案的安全性建立在格困难问题上。

定义5（LWE问题） 令q为整数，[s∈Znq]为向量，[Χ=Χ（n）]为[Zq]上的误差分布，随机选择[a∈Znq]，根据分布选择[x←Χ]，并输出[（a，  +x）∈Znq×Zq]，其分布记为[As，Χ]，带误差学习（LWE）问题定义为：以不可忽略的优势区分[As，Χ]和[Znq×Zq]上的随机均匀分布。

定义6（R-LWE问题） 令[fx=xn+1∈Z[x]]，[d， q∈Z]为整数，定义[Rq=Zq[x]f（x）]为模f（x）模q的整数多项式环，[Χ=Χ（n）]为[Rq]上的误差分布，均匀随机选择Rq上的多项式w，并计算ws+e，其中[s∈Rq]是随机均匀选取的秘密值，[e←Χ]是根据误差分布选取的噪声值，ws+e的分布记为[Rq，s，Χ]环上带误差学习（R-LWE） 问题定义为：以不可忽略的优势区分[Rq，s，Χ]和[Rq×Rq]上的随机均匀分布。

2.3 困难假设

基于R-LWE的密码学方案通常都建立在如下的假设基础上：不存在多项式时间（甚至允许攻击者有量子计算能力）的算法解决n维格中的R-LWE问题。

3 基于格的非交互密钥交换协议

3.1 CommonSetup算法

设定R-LWE参数q， n和误差分布[Χ]，其中q和n均为正整数，且n为2的幂，[Rq=Zq[x]f（x）]为模f（x）模q的整数多项式环，[Χ=Χ（n）]为[Zq]上的高斯分布;同时均匀选择[a∈Rq]。

3.2 KeyGen算法

将所有用户根据用户ID按照先后顺序排序为U1，U2，…，Un，…，此算法通过如下步骤为用户Ui生成密钥：

選择[si， ei， e'i←Χ]，计算[bi=asi+ei ∈Rq]，对于每个[j>i]，用户Ui计算

[vij=bjsi+e'i ∈Rq];

[vij=dbl（vij） ∈R2q];

[cij=2q， 2∈{0， 1}n]。

函数[dbl（?）]：ZqàZ2q定义为 dbl（x）=2x-e，e的值按照Pr（e=0）=0.5，Pr（e=1）= Pr（e=-1）=0.5的概率从{0，1，-1}中抽样。此处将[dbl（?）]函数应用在多项式的系数上，每个系数独立使用该函数。

函数[2q， 2]：Z2qàZ2定义为[2q， 2=2xq mod 2]，此处[2q， 2]函数应用在多项式的系数上，每个系数独立使用该函数。

以[si， ei， e'i]作为用户Ui的私钥，bi 和cij序列Ui作为用户的公钥。

3.3 SharedKey算法

假设用户Ui和用户Uj之间要建立共享密钥，不失一般性，假设[j>i]。

Ui按照如下规则进行计算，并以Keyi作为和Uj的共享密钥：

[vij=bjsi+e'i ∈Rq];

[vij=dblvij∈R2q];

Keyi = [vij2q， 2∈{0， 1}n]。

其中函数[?2q， 2]：Z2qàZ2定义为[x2q， 2=xq mod 2]，此处[?2q， 2]函数应用在多项式的系数上，每个系数独立使用该函数。

Uj按照如下规则计算，并以此作为和Ui之间共享的会话密钥。

Keyj = [Re（2bisj， cij）∈{0，1}n]。

其中函数[Re（?， ?）]是这样定义的，先定义集合[I0={0， 1， …， q2-1}]和[I1={-q2， -q2+1， …， -1}]，令[E=-q4， q4]，则

[Rew，b=0， 如果w∈Ib+E mod 2q1，其他情况]

此处[Re（?， ?）]函数应用在多项式的系数上，将n比特串[cij]分拆，每个系数通过[cij]的一个比特独立使用该函数。

4 协议分析

4.1 协议的正确性

为保证密钥协商的正确，要求协议中Keyi = Keyj。

定理1 上述协议SharedKey算法中计算的两个密钥值相等，即Keyi = Keyj 。

证明 首先考虑单比特的情况，令[b=2∈{0，1}]，则必有[v∈Ib∪（q2+Ib）]，因此[v2=0]当且仅当[v∈Ib]，令[e∈E]，w=v+e mod q，根据[Re（?， ?）]函数的定义，必然有Re（w， 2） = [v 2]。

再推广到本方案的多比特情况，由于函数计算是逐系数进行的，因此每个系数之间互相不干扰，且每个系数生成单个密钥比特，因此必然有[Re2bisj， cij=vij2q， 2]。

（证毕）

4.2 协议的安全性

协议的安全性体现在上述攻击者A和挑战者C的博弈中。

定理2 在前述博弈中，若攻击者A取胜的概率和1/2没有显著区别。

证明 要证明本定理，需要证明攻击者无法区分依据协议生成的密钥和一个相同长度的随机值。通过如下一系列博弈变形，对此予以证明。

⑴ 定义博弈1为将测试查询中用户Uj的公钥[bj]设置为从[Rq]内随即均匀选择，而不是通过[bj=asj+ej]计算得出。此博弈中，挑战者C诚实回答攻击者A的查询。由于[bj]是R-LWE值，因此根据R-LWE困难性假设，A无法区分是进行博弈1还是在原博弈中运行。

⑵ 定义博弈2是在博弈1的基础上，进一步令[bi]在[Rq]内随即均匀选择，而不是通过[bi=asi+ei]计算得出，且[vij]在[Rq]内随即均匀选择，而不是通过[vij=bjsi+e'i]计算得出。由于[bi]和[vij]均为R-LWE值，因此根据R-LWE困难性假设，A无法区分是进行博弈2还是原博弈1。

综上所述，A无法区分是在原博弈中运行还是在博弈2中运行，在博弈2中，由于[bi]和[vij]均为随机值，因此所得的密钥也是密钥空间[{0， 1}n]内均匀选取的随机值。故A无法分辨依据协议生成的密钥和一个相同长度的随机值。

（证毕）

5 结束语

目前流行的密钥交换协议在一些轻型网络节点中应用面临的最大的问题是交互过于复杂，这可能会导致大量的通信开销和电量消耗。同时，随着量子计算技术的不断发展，未来量子计算机攻破现有协议安全性的可能性越来越大。因此设计非交互式的抗量子攻击密钥交换协议是十分必要的。

提出一个基于格理论的非交互密钥交换协议，该协议的安全性基于格理论的带误差学习困难性问题，在Freire等人提出的形式化定义以及安全模型中得以证明。该协议具有抗量子攻击安全性，在网络中应用能够有效提升物联网的通信安全性。

参考文献（References）：

[1] Krawczyk H. HMQV： A high-performance secure Diffie-

Hellman protocol[C]//Annual International Cryptology Conference.Springer， Berlin， Heidelberg，2005：546-566

[2] Wagner D， Schneier B. Analysis of the SSL 3.0 protocol

[C]//The Second USENIX Workshop on Electronic Commerce Proceedings，1996.1：29-40

[3] Krawczyk H， Paterson K G， Wee H. On the security of the

TLS protocol： A systematic analysis[M]//Advances in Cryptology-CRYPTO 2013.Springer，Berlin， Heidelberg， 2013：429-448

[4] ?apar， ?.， Goeckel， D.， Paterson， K. G.， Quaglia， E. A.，

Towsley， D.， & Zafer， M. Signal-flow-based 2013. Springer， Berlin， Heidelberg，2013：254-271

[5] 項顺伯，徐兵，柯文德.一种贡献型的动态群密钥交换协议[J].

安徽大学学报（自然科学版），2017.3.

[6] Diffie W.and Hellman M.， New directions in cryptography

[J].IEEE Transactions on Information Theory，1976.22（6）：644-654

[7] Bernstein D J. Cruve 25519： new Diffie-Hellman speed

records [C].//9th International Conference on Theory and Practice in Public Key Cryptography. New York，2006：207-228

[8] Gennaro R， Halevi S， Krawczyk H， et al. Strongly-resilient

and non-interactive hierarchical key-agreement in MANETs[C]. //Computer Security： ESORICS 2008. Springer Berlin Heidelberg，2008：49-65

[9] Guo H， Mu Y， Li Z， et al. An efficient and non-interactive

hierarchical key agreement protocol[J].Computers & Security，2011.30（1）：28-34

[10] Kim H. Non-interactive hierarchical key agreement

protocol over hierarchical wireless sensor networks[C]. In： Computer Applications for Security， Control and System Engineering. Springer Berlin Heidelberg， 2012：86-93

[11] Freire E S V， Hofheinz D， Kiltz E， et al. Non-interactive

key exchange[M]//Public-Key.Cryptography-PKC 2013. Springer， Berlin， Heidelberg，2013：254-271

[12] Lo H K， Spiller T， Popescu S. Introduction to quantum

computation and information[M].World Scientific，1998.

[13] Bernstein D J. Introduction to post-quantum cryptogra-

phy[M]//Post-quantum cryptography.Springer， Berlin， Heidelberg，2009：1-14

[14] Regev O. On lattices， learning with errors， random linear

codes， and cryptography[J]. Journal of the ACM （JACM），2009.56（6）：34

[15] Lyubashevsky V， Peikert C， Regev O. On ideal lattices

and learning with errors over rings[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer， Berlin， Heidelberg，2010：1-23

[16]  Bai S， Galbraith S D. An improved compression

technique for signatures based on learning with errors[C]//Cryptographers' Track at the RSA Conference. Springer， Cham，2014：28-47

[17]  Ding J， Xie X， Lin X. A Simple Provably Secure Key

Exchange Scheme Based on the Learning with ErrorsProblem[J]. IACR Cryptology EPrint Archive，2012：688