CN113094721A - Post-quantum password authentication key exchange method based on modular error learning - Google Patents

Abstract

The invention discloses a post-quantum password authentication key exchange method based on modular error learning, which comprises the following steps: 1) when the client C initiates the key exchange with the server S, the client C obtains the key through calculation

Will be provided with

Sending the data to S; 2) s is calculated to obtain

Using Con (σ)_s) Obtaining a negotiation key k_σAnd a secondary coordination value v, then generating identity verification information k of S and information k 'for verifying the identity of the client and sending the information k' to the server

Sending the data to C; 3) c generating a coordination polynomial

Then according to σ_cV generating its negotiation key k_σ(ii) a Then, after the server identity is verified, self-verification information k' and a session key sk are generated_cAnd sending k' to S; 4) s compares k 'with k' to verify C, if the verification is passed, the session key sk is calculated_s。

Description

Translated fromChinese

一种基于模上错误学习的后量子口令认证密钥交换方法A Post-Quantum Password Authentication Key Exchange Method Based on Modulo Error Learning

技术领域technical field

本发明属于网络安全技术领域，涉及一种口令认证密钥交换方案，特别是涉及一种基于模上错误学习的后量子口令认证密钥交换方法。The invention belongs to the technical field of network security, and relates to a password authentication key exchange scheme, in particular to a post-quantum password authentication key exchange method based on modular error learning.

背景技术Background technique

在不安全的信道上，通信双方遵从某种约定协商出共同密钥的过程称为密钥交换。然而，密钥交换协议自身无法对通信双方身份进行鉴别，因此无法避免中间人攻击带来的威胁。在实践中，通常将身份认证与密钥交换方案相结合。目前常用的认证手段有两种：其一，基于公钥基础设施(PKI)实现认证；其二，基于用户友好的口令实现认证。相比于PKI，采用口令进行认证无需可信第三方的介入、避免额外的存储设备，在密钥管理上更为便捷与灵活。特别是，越来越多的用户通过手持设备来远程访问个人隐私数据，使得口令认证密钥交换协议具有更加广阔的应用前景。On an insecure channel, the process of negotiating a common key between two communicating parties according to a certain agreement is called key exchange. However, the key exchange protocol itself cannot identify the identities of the two communicating parties, so it cannot avoid the threat of man-in-the-middle attacks. In practice, authentication is usually combined with a key exchange scheme. There are two commonly used authentication methods: one is based on public key infrastructure (PKI) to achieve authentication; the other is based on user-friendly passwords to achieve authentication. Compared with PKI, password authentication does not require the intervention of a trusted third party, avoids additional storage devices, and is more convenient and flexible in key management. In particular, more and more users remotely access personal privacy data through handheld devices, which makes password-authenticated key exchange protocols have broader application prospects.

口令认证密钥交换协议的构建模型有两种：基于CRS模型和基于ROM模型。基于CRS模型的方案为实现标准模型的安全性，常采用复杂的哈希证明系统，且其组件的构造与计算通常复杂且低效，实用性不强；基于ROM模型构建的方案则较为简洁和高效，通过合理的参数选取，能够实现安全且高效的协议构建。There are two construction models of password authentication key exchange protocol: based on CRS model and based on ROM model. In order to realize the security of the standard model, the scheme based on the CRS model often uses a complex hash proof system, and the construction and calculation of its components are usually complex and inefficient, and the practicability is not strong; the scheme based on the ROM model is relatively simple and convenient. Efficient, through reasonable parameter selection, safe and efficient protocol construction can be achieved.

基于传统数论难题(大数分解问题和计算离散对数问题)构建的密钥交换协议，由于在量子算法下存在多项式时间的求解算法，其在量子时代将不再适用。目前，量子计算的发展正如火如荼，76个光量子比特的量子计算原型机“九章”已成功构建，因此，量子计算机由理论发展转向实际应用的时代将不再久远。当下，研制出能够抵抗量子计算机攻击的后量子密码学标准成为当前国际密码学研究的热切关注方向。现下，主要有五种较为流行的后量子密码算法，分别为基于编码的密码、多变量密码、基于散列的密码、格密码和同源密码。对于这五种算法而言，基于编码的密码主要用于构造加密方案；多变量密码与基于散列的密码主要用于构建数字签名方案；同源密码是最为新颖的一种，但就其目前的发展形势看，其计算效率相对低下，在发展前景上并不占优势；而由于传统的密码学概念多数都能够在格密码中实现，因此其为最通用的一类密码。格密码之所以具有通用性，是因为其存在几大优势。一，根据现有的理论发展，在量子计算条件下，多种基于格的困难问题还未发现多项式时间的求解算法，这是其能够抵御量子攻击的前提；二，格上密码算法的安全性可以归约到格上困难问题最坏情形下的困难性，因此基于格设计的密码体制具有较高的安全性；三，格上密码的计算仅仅需要向量的加法和乘法以及高斯取样等，运算速率高。The key exchange protocol based on traditional number theory problems (large number decomposition problem and computing discrete logarithm problem) will no longer be applicable in the quantum era due to the existence of a polynomial time solution algorithm under the quantum algorithm. At present, the development of quantum computing is in full swing, and the quantum computing prototype "Nine Chapters" with 76 optical qubits has been successfully constructed. Therefore, the era of quantum computing from theoretical development to practical application will not be long. At present, the development of post-quantum cryptography standards that can resist quantum computer attacks has become a hot focus of current international cryptography research. At present, there are mainly five popular post-quantum cryptographic algorithms, namely code-based ciphers, multivariate ciphers, hash-based ciphers, lattice ciphers and homologous ciphers. For these five algorithms, code-based ciphers are mainly used to construct encryption schemes; multivariate ciphers and hash-based ciphers are mainly used to construct digital signature schemes; homologous ciphers are the most novel one, but at present From the perspective of the development situation, its computational efficiency is relatively low, and it does not have an advantage in development prospects; and because most of the traditional cryptography concepts can be implemented in lattice ciphers, it is the most common type of cipher. Lattice ciphers are universal because of several advantages. First, according to the existing theoretical development, under the conditions of quantum computing, a polynomial time solution algorithm has not been found for many difficult lattice-based problems, which is the premise of its ability to resist quantum attacks; second, the security of the lattice encryption algorithm It can be reduced to the worst-case difficulty of difficult problems on lattices, so the cryptosystem based on lattice design has high security; thirdly, the calculation of ciphers on lattices only requires addition and multiplication of vectors and Gaussian sampling, etc. high rate.

与原始的格上困难问题相比较，错误学习问题(LWE)及其变形问题(Ring-LWE,Module-LWE)在构建密钥交换方案时更方便。Regev在2005年提出了LWE问题，判定型LWE问题的困难性取决于敌手对随机均匀取样

以及LWE取样

的不可区分性。但是，使用LWE问题构建协议时，由于涉及到大矩阵的计算与传输，往往致使方案的通信成本太高、运行效率太低，实用性较差。为了解决错误学习问题构建密码方案的实用性障碍，2010年，Lyubashevsky,Peikert和Regev三人提出了环上错误学习(Ring-LWE)问题，将代数环结构引入错误学习问题，使得通信成本大大降低、性能显著提升。判定型Ring-LWE问题的困难性取决于环上随机均匀取样(a,u)∈R_q×R_q及错误学习取样(a,as+e)∈R_q×R_q的不可区分性。尽管代数结构的引入使密码系统的运行效率得到了明显的提升，但是简单的代数结构同时也引起了对其弱安全性的担忧。2015年，Langlois和Stele对理想格和一般格进行了推广，提出了模上错误学习问题(Module-LWE)。模(Module)是环和向量空间的一般化，判定型Module-LWE问题的困难性则取决于敌手对模上随机均匀取样

及错误学习取样

的不可区分性。在实际的应用中，相较于LWE和Ring-LWE问题，利用Module-LWE来构建密钥交换方案则更加灵活，只需要改变环向量的维度d便可实现安全性与性能的平衡，因此方案具有可复用性及可扩展性。Compared with the original on-lattice hard problem, the learning-by-error problem (LWE) and its variants (Ring-LWE, Module-LWE) are more convenient in constructing key exchange schemes. Regev proposed the LWE problem in 2005. The difficulty of the decision-based LWE problem depends on the adversary's random uniform sampling.

and LWE sampling

indistinguishability. However, when the LWE problem is used to construct a protocol, the calculation and transmission of large matrices are involved, which often leads to high communication costs, low operating efficiency and poor practicability. In order to solve the practical obstacle of constructing a cryptographic scheme due to the error learning problem, in 2010, Lyubashevsky, Peikert and Regev proposed the Ring-LWE problem, which introduced the algebraic ring structure into the error learning problem, which greatly reduced the communication cost. , the performance is significantly improved. The difficulty of the decision-based Ring-LWE problem depends on the indistinguishability of random uniform sampling (a,u)∈R_q ×R_q and erroneous learning sampling (a,as+e)∈R_q ×R_q on the ring. Although the introduction of the algebraic structure has significantly improved the operating efficiency of the cryptosystem, the simple algebraic structure has also raised concerns about its weak security. In 2015, Langlois and Stele generalized ideal lattices and general lattices and proposed the learning on modular error problem (Module-LWE). Module is a generalization of rings and vector spaces, and the difficulty of the decision-based Module-LWE problem depends on the random uniform sampling of the module by the adversary

and error learning sampling

indistinguishability. In practical applications, compared with the LWE and Ring-LWE problems, the use of Module-LWE to build a key exchange scheme is more flexible. It only needs to change the dimension d of the ring vector to achieve a balance between security and performance. Therefore, the scheme It is reusable and extensible.

据前所述，格上的错误学习问题引入了错误项，增加了敌手区分错误取样与随机均匀取样难度的同时，也使得密钥交换的双方只能够得到近似值，如服务器S通过计算得到

而客户端C通过计算只能得到

因此，为了使双方准确的恢复出相同的协商密钥sk，协议构建时需要着重考虑错误协调机制的合理性。目前较为流行的错误协调机制有丁氏错误协调、Peikert错误协调、

格解码以及OKCN/AKCN。丁氏错误协调与Peikert错误协调机制采用的是每个系数协调一个比特，其误差为8/q。由于可允许误差范围太小，因此在参数选择中会导致模数过大，造成协议性能损失。对于

格解码而言，其采用了四个系数来协调一个比特的方式，提高可允许误差为

但是，其只适用于多项式维度为1024的Ring-LWE，并不适用于采用小维度(n＝256)多项式环的Module-LWE问题。OKCN/AKCN算法是丁氏错误协调机制与Peikert错误协调机制的一般化，但提供了高效性边界，使得灵活权衡各参数间的取值并得到更大的容错边界成为可能。实际应用中，OKCN比AKCN具有更优的性能，主要体现在更低的错误率与带宽以及对DH型协议的适用性。As mentioned above, the error learning problem on the lattice introduces an error term, which increases the difficulty for the adversary to distinguish between wrong sampling and random uniform sampling, and also makes the two parties in the key exchange only obtain approximate values.

And client C can only get

Therefore, in order for both parties to recover the same negotiated key sk accurately, it is necessary to focus on the rationality of the error coordination mechanism when constructing the protocol. At present, the more popular error coordination mechanisms include Ding's error coordination, Peikert error coordination,

Grid decoding and OKCN/AKCN. The Ding's error coordination and Peikert's error coordination mechanism adopts one bit for each coefficient coordination, and its error is 8/q. Since the allowable error range is too small, the modulus will be too large in parameter selection, resulting in the loss of protocol performance. for

For lattice decoding, it uses four coefficients to coordinate one bit, and the allowable error is increased to

However, it is only applicable to the Ring-LWE with polynomial dimension of 1024, and is not applicable to the Module-LWE problem with polynomial rings of small dimension (n=256). The OKCN/AKCN algorithm is a generalization of Ding's error coordination mechanism and Peikert's error coordination mechanism, but it provides an efficient boundary, which makes it possible to flexibly weigh the values of various parameters and obtain a larger fault tolerance boundary. In practical applications, OKCN has better performance than AKCN, which is mainly reflected in lower error rate and bandwidth and applicability to DH-type protocols.

综上所述，对构造后量子的口令认证密钥交换协议而言，现有技术中存在如下几点不足：其一，基于格的口令认证密钥交换协议较少，且大多是基于CRS模式设计，运行效率低下，因此被认为只能限制于理论实现，无法应用于现实世界的部署；其二，现存的方案在参数选择、后量子安全性分析及正确性分析上都不够严谨，造成方案的性能及安全性强度都不满足实际应用需求；其三，方案的可复用性及可扩展性不强，现存的方案只能针对一种安全性需求适用，若要实现多种安全性需求，需要重新进行参数选取与分析，导致方案的可扩展性及代码的可复性不强。To sum up, for the post-quantum password-authenticated key exchange protocol, the existing technologies have the following deficiencies: First, there are few lattice-based password-authenticated key exchange protocols, and most of them are based on the CRS mode. The design and operation efficiency are low, so it is considered to be limited to theoretical implementation and cannot be applied to real-world deployment; secondly, the existing schemes are not rigorous enough in parameter selection, post-quantum security analysis and correctness analysis, resulting in schemes The performance and security strength of the solution do not meet the actual application requirements; third, the reusability and scalability of the solution are not strong, and the existing solutions can only be applied to one security requirement. If you want to achieve multiple security requirements , it is necessary to re-select and analyze the parameters, resulting in poor scalability and code reproducibility.

发明内容SUMMARY OF THE INVENTION

针对现有技术中存在的问题，本发明旨在提供一种安全且高效的基于模上错误学习(Module-LWE)的后量子口令认证密钥交换方法，使得通信双方能够在三轮消息交换过后协商出相同的会话密钥，同时，实现双向身份认证。In view of the problems existing in the prior art, the present invention aims to provide a safe and efficient post-quantum password authentication key exchange method based on module-LWE learning, so that both parties can exchange messages after three rounds of message exchange. The same session key is negotiated, and at the same time, two-way authentication is realized.

首先，本方案采用的困难问题是格上的Module-LWE问题。该困难问题通过合理的参数选取能够抵抗量子计算机的攻击，保障量子时代的安全通信。另外，与LWE问题和Ring-LWE问题相比，Module-LWE问题更为灵活，方案设计过程中只需改变多项式向量的维度d便可满足不同安全性与性能需求间的平衡，以应对不同的安全场景。方案的整体设计类似于ROM模式，避免了CRS模型构造过程中由组件设计代来的低效性，使方案更为简洁高效，且能够使用BPR模型来完成其安全性证明，安全性证明的结果为敌手攻击该协议成功的优势并不大于敌手进行在线字典攻击的优势。First, the difficult problem adopted by this scheme is the Module-LWE problem on lattices. This difficult problem can resist the attack of quantum computer through reasonable parameter selection, and ensure the secure communication in the quantum era. In addition, compared with the LWE problem and the Ring-LWE problem, the Module-LWE problem is more flexible. During the design process, only the dimension d of the polynomial vector needs to be changed to meet the balance between different security and performance requirements. security scene. The overall design of the scheme is similar to the ROM mode, which avoids the inefficiency generated by the component design during the construction of the CRS model, making the scheme more concise and efficient, and can use the BPR model to complete its security proof and the result of the security proof. The advantage of successfully attacking the protocol for the adversary is no greater than the advantage of the adversary performing an online dictionary attack.

其次，鉴于本发明采用Module-LWE问题进行协议构建，协议中构建的取样

即模上错误学习取样，因此，为使其错误协调的效率及容错范围实现最优化，本文应用了OKCN算法来进行协调。由于本方案计算得到的协调多项式共有256个系数，每个系数需要协商出1个比特的协商密钥，因此，本方案应当使用每个系数协商1个比特的错误协调机制。通过分析可知，丁氏错误协调与Peikert错误协调的容错范围仅为

而OKCN算法的容错范围为

因此使用OKCN算法进行协商是最优的选择。Secondly, given that the present invention adopts the Module-LWE problem to construct the protocol, the sampling constructed in the protocol

That is, the error learning sampling on the modulo. Therefore, in order to optimize the efficiency of the error coordination and the fault tolerance range, this paper applies the OKCN algorithm to coordinate. Since the coordination polynomial calculated by this scheme has a total of 256 coefficients, and each coefficient needs to negotiate a 1-bit negotiation key, this scheme should use a 1-bit error coordination mechanism for each coefficient negotiated. Through the analysis, it can be seen that the fault tolerance range of Ding's wrong coordination and Peikert's wrong coordination is only

The fault tolerance range of the OKCN algorithm is

Therefore, using the OKCN algorithm for negotiation is the optimal choice.

之前，基于格问题设计的后量子口令认证密钥交换协议中，错误分布通常采用离散高斯取样。然而，离散高斯取样在实际应用中，需要高精度的取值以及消耗空间资源的预计算表，取样效率不高。本发明采用的取样方式为中心二项分布，中心二项分布只需要计算两个01串间的汉明距离便可以实现取样，提升了错误取样的效率并且与离散高斯取样相比方案的安全性几乎不受影响。另外，本发明中，多项式乘法是最为耗时的操作，因此，本发明为进一步提升整个方案的运行效率，在参数选取中多项式的模数q≡1mod2n满足NTT算法的应用条件，因此，本发明利用NTT算法来加速多项式乘法。Previously, in post-quantum password-authenticated key exchange protocols designed based on lattice problems, the error distribution usually adopts discrete Gaussian sampling. However, in practical applications, discrete Gaussian sampling requires high-precision values and a pre-calculation table that consumes space resources, and the sampling efficiency is not high. The sampling method adopted in the present invention is the central binomial distribution. The central binomial distribution only needs to calculate the Hamming distance between two 01 strings to realize sampling, which improves the efficiency of wrong sampling and is more secure than discrete Gaussian sampling. almost unaffected. In addition, in the present invention, polynomial multiplication is the most time-consuming operation. Therefore, in the present invention, in order to further improve the operation efficiency of the entire scheme, the modulus of the polynomial q≡1mod2n in the parameter selection satisfies the application conditions of the NTT algorithm. Therefore, the present invention Use the NTT algorithm to speed up polynomial multiplication.

最后，为了避免后门和all-for-the-price-of-one预计算攻击，本方案在每次密钥交换过程中需生成新的公共矩阵

尽管

的生成为方案的运行引入了额外的计算时间，但是，一方面，在每次密钥交换过程中采用随机的小种子代替大的公共矩阵进行传输，降低了通信成本；另一方面，通过合理的参数选取，本发明提升的运行效率能够抵消生成公共参数消耗的时间成本。Finally, in order to avoid backdoors and all-for-the-price-of-one precomputing attacks, this scheme needs to generate a new public matrix during each key exchange process

although

However, on the one hand, in each key exchange process, a random small seed is used instead of a large public matrix for transmission, which reduces the communication cost; on the other hand, through reasonable According to the parameter selection, the improved operation efficiency of the present invention can offset the time cost consumed by generating public parameters.

附图说明Description of drawings

图1为本发明方法流程图。Fig. 1 is the flow chart of the method of the present invention.

具体实施方式Detailed ways

为了使本发明的目标、技术方案及优势更清晰明了，接下来将参照附图对本方案的细节作出详细说明。In order to make the objectives, technical solutions and advantages of the present invention clearer, the details of the solution will be described in detail below with reference to the accompanying drawings.

1.符号表示1. Symbolic representation

为便于对协议进行表示与描述，首先对协议采用的符号表示进行了定义。整数多项式商环表示为

其中，q为模数，n为多项式次数，

为模数为q的多项式，X表示多项式的变量；一个维度为d∈N⁺的环多项式向量表示为

一个维度为d×d∈N⁺×N⁺的环多项式矩阵表示为

对于向量

和矩阵

分别表示它们的转置。若A为确定性算法，则a:＝Α(b)表示算法Α在输入为b时的值为a；若A为非确定性算法，a←Α(b)表示将算法A的输出赋值给a。S表示集合，x←S表示从集合S中随机选取一个元素x。若χ表示x在集合S上的概率分布，则x←χ表示根据χ从S中取样x。另外，均匀随机取样表示为u～S。对于密钥协商算法，Con(σ)表示调和函数，生成协商密钥k_σ和辅助协调值v；Rec(σ,v)表示协调函数，利用协调多项式σ和辅助协调值v生成协商密钥k_σ。In order to express and describe the protocol conveniently, the symbolic representation adopted by the protocol is firstly defined. The integer polynomial quotient ring is represented as

where q is the modulus, n is the polynomial degree,

is a polynomial of modulus q, X represents the variable of the polynomial; a ring polynomial vector of dimension d∈N⁺ is expressed as

A ring polynomial matrix of dimension d×d∈N⁺ ×N⁺ is expressed as

for vector

and matrix

represent their transposes, respectively. If A is a deterministic algorithm, then a:=Α(b) indicates that the value of algorithm A is a when the input is b; if A is a non-deterministic algorithm, a←Α(b) indicates that the output of algorithm A is assigned to a. S represents a set, and x←S represents a random selection of an element x from the set S. If χ represents the probability distribution of x on the set S, then x←χ represents sampling x from S according to χ. In addition, uniform random sampling is denoted as u to S. For the key agreement algorithm, Con(σ) represents the coordination function, which generates the negotiated key k_σ and the auxiliary coordination value v; Rec(σ, v) represents the coordination function, and uses the coordination polynomial σ and the auxiliary coordination value v to generate the negotiated key k_σ .

2.协议描述2. Protocol description

图1展示了本发明的整体架构。具体的密钥交换过程描述为：Figure 1 shows the overall architecture of the present invention. The specific key exchange process is described as:

1)客户端初始化：客户端C持有口令pw_C，且欲与服务器S之间进行密钥交换。C首先随机选取一个256比特的种子ρ，利用该种子ρ扩展出公共矩阵

然后，根据中心二项分布选取秘密取样

和错误取样

计算得到

最后，计算

以及

将消息

打包后发送给服务器S完成初始化过程。1) Client initialization: Client C holds the password pw_C , and wants to exchange keys with the server S. C first randomly selects a 256-bit seed ρ, and uses the seed ρ to expand the public matrix

Then, secret sampling is chosen according to the central binomial distribution

and error sampling

Calculated

Finally, calculate

as well as

put the message

After packaging, it is sent to the server S to complete the initialization process.

2)服务器初始化及响应：服务器S存储了客户端C的口令哈希值

在收到客户端C的消息流

后，服务器S首先检查消息

的合理性并完成初始化过程：若

协议终止；否则，服务器S先利用公共种子ρ扩展成公共矩阵

根据中心二项分布生成其秘密样本

和错误样本

经过计算得到

接下来，服务器S利用存储的

恢复出

利用

和自身秘密样本

计算得到协调多项式

使用Con(σ_s)函数得到协商密钥k_σ及辅助协调值v；最后，计算

和

并将消息

发送给客户端C。2) Server initialization and response: server S stores the password hash value of client C

After receiving the message flow from client C

After the server S first checks the message

is reasonable and completes the initialization process: if

The protocol is terminated; otherwise, the server S first uses the public seed ρ to expand into a public matrix

Generate its secret samples according to the central binomial distribution

and error samples

obtained by calculation

Next, the server S uses the stored

recover

use

and its own secret sample

Calculated to get the coordination polynomial

Use the Con(σ_s ) function to obtain the negotiated key k_σ and the auxiliary coordination value v; finally, calculate

and

and put the message

Sent to client C.

3)客户端响应并完成：客户端C收到消息后，首先检查

的合理性，即若

C将停止后续计算；否则，C利用

和自身秘密

生成其协调多项式

客户端C根据协调多项式σ_c和辅助协调值v生成协商密钥k_σ＝Rec(σ_s,v)；然后，C通过比较服务器生成的k与自己计算得到的

来验证客户端的身份，若验证通过，则计算

及其会话密钥

并将k′发送给服务器S以验证其身份；否则，终止协议。3) The client responds and completes: After client C receives the message, it first checks

reasonableness, if

C stops subsequent computations; otherwise, C uses

and its own secrets

generate its coordination polynomial

The client C generates the negotiated key k_σ =Rec(σ_s ,v) according to the coordination polynomial σ_c and the auxiliary coordination value v; then, C compares the k generated by the server with the one calculated by itself

To verify the identity of the client, if the verification passes, calculate

and its session key

and send k' to server S to verify its identity; otherwise, terminate the protocol.

4)服务器完成：服务器S通过检查收到的k′与自己计算k″的值来完成客户端身份的验证。若验证通过，则计算会话密钥

至此，双方密钥协商完成。4) The server completes: the server S completes the authentication of the client identity by checking the received k' and the value of k' calculated by itself. If the verification is passed, the session key is calculated

At this point, the key negotiation between the two parties is completed.

双向认证：本方案实现了服务器与客户端的双向认证，从而避免了中间人攻击。1)认证服务器：首先，只有真正拥有客户端口令哈希值的服务器才能够利用消息

恢复出客户端的MLWE取样

从而计算得到近似多项式σ_s，生成验证密钥k；其次，客户端通过检验k的值来完成对服务器的身份认证。2)认证客户端：只有真正的客户端才持有临时秘密

因而才能够计算得到协调多项式σ_c，生成验证密钥k′并交给服务器；服务器通过比较k′与k″的值来完成对客户端的认证。因此，密钥交换完成后，双方得到了相同的会话密钥且完成了彼此的身份认证。Two-way authentication: This solution implements two-way authentication between the server and the client, thereby avoiding man-in-the-middle attacks. 1) Authentication server: First, only the server that actually has the hash value of the client's port token can use the message

Recover the MLWE sample from the client

Thus, the approximate polynomial σ_s is obtained by calculation, and the verification key k is generated; secondly, the client completes the identity authentication to the server by checking the value of k. 2) Authenticating clients: only real clients hold temporary secrets

Therefore, the coordination polynomial σ_c can be calculated, and the verification key k' is generated and given to the server; the server completes the authentication of the client by comparing the values of k' and k". Therefore, after the key exchange is completed, both parties obtain the same Session key and complete each other's authentication.

前向安全性：本方案同时保证了会话的前向安全性，由于每次会话密钥的建立过程中秘密取样

与错误取样

都是随机选取的，独立于其他任何一次的密钥交换。因此，此次密钥交换的会话密钥泄露，并不会对其之前协商的会话密钥的安全性产生影响。该性质也是后量子密钥交换协议设计的考虑因素之一。Forward security: This scheme also ensures the forward security of the session, because secret sampling is performed during the establishment of each session key.

with error sampling

are chosen at random, independent of any other key exchange. Therefore, the leakage of the session key of this key exchange will not affect the security of the previously negotiated session key. This property is also one of the considerations in the design of post-quantum key exchange protocols.

3.协议正确性3. Protocol Correctness

本方案能够正确实施的关键依赖于错误协调机制的正确性。本方案采用的错误协调机制为OKCN算法，该算法由两个函数组成：调和函数(k_s,v)←Con(σ_s)以及协调函数k_c＝Rec(σ_c,v)。调和函数(k_s,v)←Con(σ_s)输入协调多项式σ_s，经过计算输出协商密钥k_σ和辅助协调值v。其中，k_σ与v之间是相互独立的，即v未泄露关于k_σ的任何信息。协调函数k_c＝Rec(σ_c,v)则通过输入多项式σ_c以及另一方发送的辅助协调值v，经过计算来获得其协商密钥k_c。The key to the correct implementation of this scheme depends on the correctness of the error coordination mechanism. The error coordination mechanism adopted in this scheme is the OKCN algorithm, which consists of two functions: the harmonic function (k_s ,v)←Con(σ_s ) and the coordination function k_c =Rec(σ_c ,v). The harmonic function (k_s ,v)←Con(σ_s ) inputs the coordination polynomial σ_s , and outputs the negotiated key k_σ and the auxiliary coordination value v after calculation. Among them, k_σ and v are independent of each other, that is, v does not reveal any information about k_σ . The coordination function k_c =Rec(σ_c ,v) obtains its negotiated key k_c through calculation by inputting the polynomial σ_c and the auxiliary coordination value v sent by the other party.

当两个近似的协调值σ_s与σ_c之间的距离位于错误协调机制OKCN的误差允许范围内时，本方案能够协调出两个相同的协商密钥k_s＝k_c，即When the distance between the two approximate coordination values σ_s and σ_c is within the error tolerance range of the error coordination mechanism OKCN, this scheme can coordinate two identical negotiated keys k_s =k_c , namely

其中，l表示容错范围的最大值。Among them, l represents the maximum value of the fault tolerance range.

根据OKCN的正确性要求，当参数满足2ml≤q(1-1/g)时，通信双方能得到相同的协商密钥。在本发明中，当两个近似值间的距离满足

时，通信双方运行协议能够得到相同的密钥。According to the correctness requirement of OKCN, when the parameter satisfies 2ml≤q(1-1/g), both parties of communication can obtain the same negotiation key. In the present invention, when the distance between the two approximate values satisfies

At the same time, both parties of the communication can obtain the same key by running the protocol.

4.高效实现4. Efficient implementation

(1)参数选择(1) Parameter selection

表1给出了本方案针对128比特的后量子安全性确定的参数集。考虑到一个系数来协商一比特密钥的需求，确定多项式的维度为n＝256。为了应用NTT算法来加速多项式乘法，模数选择为7681≡1mod2n；为了能够满足后量子安全性，选择多项式向量的维度d＝3，其能够实现177比特的安全性；中心二项分布采用β₈；OKCN算法的参数集选择为(m＝2,g＝2⁶,l＝1895)。Table 1 shows the set of parameters determined by this scheme for the post-quantum security of 128 bits. Considering the requirement of one coefficient to negotiate a one-bit key, the dimension of the polynomial is determined to be n=256. In order to apply the NTT algorithm to speed up the polynomial multiplication, the modulus is selected as 7681≡1mod2n; in order to satisfy the post-quantum security, the dimension d=3 of the polynomial vector is selected, which can realize the security of 177 bits; the central binomial distribution adopts β₈ ; The parameter set of the OKCN algorithm is selected as (m=2, g=2⁶ , l=1895).

表1为参数选择表Table 1 is the parameter selection table

(2)NTT算法(2) NTT algorithm

快速数论转换(NTT)是一种应用于基于理想格的密码学的计算工具，主要负责多项式的快速乘法，如在R中计算两个多项式

和

的乘积，可以根据公式

得到，其中，

表示逐点乘法。考虑到单位ω的原根及其方根γ的存在条件，快速数论转换技术的应用需要满足以下两个条件：其一，维度n的选择必须是以2为幂的数，即n＝2ⁱ；其二，模数q必须为质数，且满足q≡1mod2n。Fast Number Theoretical Transformation (NTT) is a computational tool applied to ideal lattice-based cryptography, mainly responsible for fast multiplication of polynomials, such as computing two polynomials in R

and

The product of , can be obtained according to the formula

get, of which,

Represents pointwise multiplication. Considering the existence conditions of the primitive root of the unit ω and its square root γ, the application of fast number theory transformation technology needs to meet the following two conditions: First, the selection of dimension n must be a number that is a power of 2, that is, n=2ⁱ ; Second, the modulus q must be a prime number and satisfy q≡1mod2n.

·快速数论转换正向变换(NTT)Fast Number Theory Transform Forward Transform (NTT)

对于多项式

定义NTT的公式为for polynomial

The formula for defining NTT is

其中，

通过计算得到第n个单位原根的值为ω＝3844，其方根值为

in,

The value of the original root of the nth unit is obtained by calculation, and the value of its square root is ω=3844.

·快速数论转换逆向变换(NTT^-1)· Fast Number Theoretical Transformation Inverse Transform (NTT^-1 )

NTT^-1函数是NTT函数的逆变换，将多项式从NTT域中准确的还原到多项式环域中同样是至关重要的。在逆变换的过程中需要用到n次单位原根的逆ω^-1modq以及方根的逆γ^-1mod q，以及多项式中每个系数都需要乘的标量n^-1mod q。基于此，定义NTT^-1如下The NTT^-1 function is the inverse transformation of the NTT function, and it is also crucial to accurately restore the polynomial from the NTT domain to the polynomial ring domain. In the process of inverse transformation, the inverse ω^-1 modq of the n-th unit primitive root, the inverse γ^-1 mod q of the square root, and the scalar n^-1 mod q that each coefficient in the polynomial needs to be multiplied by are used. Based on this, NTT^-1 is defined as follows

其中，

通过计算得到n^-1＝7651,ω^-1＝6584,γ^-1＝1115。in,

By calculation, n^-1 =7651, ω^-1 =6584, γ^-1 =1115.

(3)哈希函数选择(3) Hash function selection

本发明中用到4个哈希函数H_l(·),l∈{1,2,3,4}。H₁为可扩展输出函数(XOF)，将用户口令pw扩展成为多项式向量

H_l,l∈{2,3}是验证身份的哈希函数；H₄为密钥派生函数(KDF)。本方案选择了由FIPS-202提供的SHAKE-128及SHA3-256作为哈希函数，其具体为，Four hash functions H_l (·), l∈{1, 2, 3, 4} are used in the present invention. H₁ is an extensible output function (XOF), which expands the user password pw into a polynomial vector

H_l ,l∈{2,3} is a hash function for identity verification; H₄ is a key derivation function (KDF). This scheme selects SHAKE-128 and SHA3-256 provided by FIPS-202 as hash functions, which are specifically:

H₁(·)＝SHAKE-128，H₁ (·)=SHAKE-128,

(4)公共矩阵A的生成(4) Generation of public matrix A

本方案使用一个256比特的随机种子ρ作为输入来生成公共矩阵

对于矩阵中每一个多项式元素a_i,j，利用SHAKE-128扩展种子ρ生成大小为16比特的数组，然后采取如下取舍策略：如果数组组成的数字小于q，则将其作为a_i,j的一个系数；否则，丢弃它。This scheme uses a 256-bit random seed ρ as input to generate the public matrix

For each polynomial element a_i,j in the matrix, use SHAKE-128 to expand the seed ρ to generate an array with a size of 16 bits, and then adopt the following selection strategy: if the number of the array is less than q, it is used as the number of a_{i, j} a coefficient; otherwise, discard it.

(5)利用中心二项分布取样(5) Sampling using the central binomial distribution

本方案从二项分布β₈中取样获得秘密取样s以及错误取样e。首先，将一个256比特的随机种子扩展成为包含256个元素的数组，其中每个元素都为16比特；然后，计算每个元素的前8个比特与后8个比特的汉明权重来生成噪声多项式的一个系数。This scheme obtains the secret sample_s and the error sample e from the binomial distribution β8. First, a 256-bit random seed is expanded into an array of 256 elements, where each element is 16 bits; then, the Hamming weights of the first 8 bits and the last 8 bits of each element are calculated to generate noise A coefficient of the polynomial.

(6)消息编码(6) Message encoding

初始化消息是一个三元组

其中，C表示包含32字节的客户端ID，ρ表示32字节的随机种子，

表示含有3个多项式的向量，每个多项式含有256个系数，每个系数包含13个比特。本方案采用小端序的方式将多项式向量

压缩为1248个字节，并与客户端ID及种子连结起来最终得到一个1312字节的初始化消息。服务器响应消息是一个三元组

表示含有3个多项式的向量，每个多项式含有256个系数，每个系数包含13个比特，采用小端序的将其压缩为1248字节；v是具有256个系数，每个系数占据6比特的多项式，同样采用小端序的方式将其压缩为192字节；k为32字节的验证密钥。最后，将上述三部分连结起来压缩成为1472字节的响应消息。The initialization message is a triple

Among them, C represents the client ID containing 32 bytes, ρ represents the random seed of 32 bytes,

Represents a vector containing 3 polynomials, each polynomial contains 256 coefficients, each coefficient contains 13 bits. This scheme uses little-endian order to convert polynomial vectors

Compressed to 1248 bytes and concatenated with the client ID and seed to get a 1312 byte initialization message. The server response message is a triple

Represents a vector containing 3 polynomials, each polynomial contains 256 coefficients, each coefficient contains 13 bits, and it is compressed into 1248 bytes in little-endian order; v is 256 coefficients, and each coefficient occupies 6 bits The polynomial of , and it is also compressed into 192 bytes in little-endian manner; k is the verification key of 32 bytes. Finally, the above three parts are concatenated and compressed into a 1472-byte response message.

以上实施例仅用以说明本发明的技术方案而非对其进行限制，本领域的普通技术人员可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明的精神和范围，本发明的保护范围应以权利要求书所述为准。The above embodiments are only used to illustrate the technical solutions of the present invention rather than limit them. Those of ordinary skill in the art can modify or equivalently replace the technical solutions of the present invention without departing from the spirit and scope of the present invention. The scope of protection shall be subject to what is stated in the claims.

Claims (9)

Translated fromChinese

1.一种基于模上错误学习的后量子口令认证密钥交换方法，其步骤包括：1. A post-quantum password authentication key exchange method based on modular error learning, the steps of which comprise:1)客户端C发起与服务器S的密钥交换时，客户端C首先选取一个256比特的随机数作为种子ρ，通过对其扩展得到公共矩阵

客户端C根据中心二项分布来选取秘密取样

和错误取样

经过计算得到MLWE样本

然后，客户端C计算其口令的哈希值

并将MLWE样本y_c封装为

最后，客户端C将初始化消息

打包后发送给服务器S；其中，pw_C为客户端C的口令，C为客户端C的身份标识，

为维度为d、模数为q的环多项式向量空间，

为维度为d×d、模数为q的环多项式矩阵空间；q为素数；d为正整数；H₁为可扩展输出函数；1) When the client C initiates the key exchange with the server S, the client C first selects a 256-bit random number as the seed ρ, and obtains the public matrix by extending it.

Client C selects secret samples according to the central binomial distribution

and error sampling

MLWE samples are obtained after calculation

Client C then computes the hash of its password

and encapsulate the MLWE sample y_c as

Finally, client C will initialize the message

After packaging, it is sent to the server S; among them, pw_C is the password of the client C, C is the identity of the client C,

is a ring polynomial vector space with dimension d and modulus q,

is a ring polynomial matrix space with dimension d×d and modulus q; q is a prime number; d is a positive integer; H₁ is an extensible output function;2)服务器S对于收到的消息

首先检查消息

的合理性，若

则终止交换过程；否则，服务器S先扩展随机种子ρ为公共矩阵

然后根据中心二项分布生成秘密取样

和错误取样

经过计算得到MLWE样本

然后利用存储的客户端C的口令哈希值

恢复出

最后利用

和秘密样本

计算得到协调多项式

使用调和函数Con(σ_s)得到协商密钥k_σ及辅助协调值v，然后服务器S生成其身份验证信息

和验证客户端身份的信息

并将消息

发送给客户端C以供客户端完成密钥协商并验证其身份；其中，S为服务器S的身份标识，H₂、H₃是验证身份的哈希函数；2) Server S for the received message

Check the message first

reasonableness, if

Then the exchange process is terminated; otherwise, the server S first expands the random seed ρ to a public matrix

Then generate secret samples based on the central binomial distribution

and error sampling

MLWE samples are obtained after calculation

Then use the stored password hash of client C

recover

last use

and secret samples

Calculated to get the coordination polynomial

Use the harmonic function Con(σ_s ) to get the negotiated key k_σ and the auxiliary coordination value v, and then the server S generates its authentication information

and information to verify the identity of the client

and put the message

It is sent to the client C for the client to complete the key negotiation and verify its identity; wherein, S is the identity of the server S, and H₂ and H₃ are the hash functions for verifying the identity;3)客户端C收到服务器S发送的消息

后，首先检查S的MLWE样本

的合理性：若

则客户端C终止交换过程；否则，客户端C首先利用

和自身秘密

生成协调多项式

然后根据协调多项式σ_c和辅助协调值v生成其协商密钥k_σ＝Rec(σ_s,v)；然后通过比较服务器S生成的验证信息k与自己计算得到的

是否相等来验证服务器S的身份；若验证通过，则客户端C计算生成其身份认证信息

以及其会话密钥sk_c，并将k′发送给服务器S；否则，终止交换过程；3) Client C receives the message sent by server S

After, first check the MLWE sample of S

reasonableness: if

Then client C terminates the exchange process; otherwise, client C first utilizes

and its own secrets

Generating Coordination Polynomials

Then generate its negotiated key k_σ =Rec(σ_s ,v) according to the coordination polynomial σ_c and the auxiliary coordination value v; then compare the verification information k generated by the server S with the one calculated by itself

Whether it is equal to verify the identity of the server S; if the verification is passed, the client C calculates and generates its identity authentication information

and its session key sk_c , and send k' to server S; otherwise, terminate the exchange process;4)服务器S通过比较k′与k″的值是否相等完成对客户端C的身份验证，若验证通过，则计算会话密钥sk_s。4) The server S completes the authentication of the client C by comparing whether the values of k' and k" are equal, and if the verification is passed, the session key sk_s is calculated.2.如权利要求1所述的方法，其特征在于，使用模上错误学习问题构建方案。2. The method of claim 1, wherein the scheme is constructed using an error-on-modular learning problem.3.如权利要求1所述的方法，其特征在于，将用户的口令扩展成为高熵的会话密钥。3. The method of claim 1, wherein the user's password is expanded into a high-entropy session key.4.如权利要求1所述的方法，其特征在于，使用OKCN算法作为错误协调机制。4. The method of claim 1, wherein the OKCN algorithm is used as the error coordination mechanism.5.如权利要求1所述的方法，其特征在于，种子ρ为一个256比特的种子；公共矩阵

为包含d×d个多项式的矩阵。5. method as claimed in claim 1 is characterized in that, seed ρ is a seed of 256 bits; Common matrix

is a matrix containing d × d polynomials.6.如权利要求1或5所述的方法，其特征在于，生成公共矩阵

的方法为：对于矩阵中每一个多项式元素a_i,j，利用SHAKE-128扩展种子ρ生成元素大小为16比特的数组，然后采取如下取舍策略：如果数组组成的数字小于q，则将其作为a_i,j的一个系数；否则丢弃该数组。6. The method of claim 1 or 5, wherein a common matrix is generated

The method is: for each polynomial element a_i,j in the matrix, use SHAKE-128 to expand the seed ρ to generate an array with an element size of 16 bits, and then adopt the following round-off strategy: if the number of the array is smaller than q, it is used as a coefficient of a_i,j ; otherwise discard the array.7.如权利要求1所述的方法，其特征在于，每次密钥交换过程中需生成新的公共矩阵

避免后门攻击和all-for-the-price-of-one攻击。7. The method of claim 1, wherein a new public matrix needs to be generated in each key exchange process

Avoid backdoor attacks and all-for-the-price-of-one attacks.8.如权利要求1所述的方法，其特征在于，模数q≡1mod2n，使用NTT算法加速多项式乘法。8. The method of claim 1, wherein the modulus q≡1mod2n is used to accelerate the polynomial multiplication using the NTT algorithm.9.如权利要求1所述的方法，其特征在于，所述协调多项式σ_s、σ_c的系数为256，每个系数需要协商出1个比特的协商密钥；使用每个系数协商1个比特的错误协调机制。9 . The method according to claim 1 , wherein the coefficients of the coordination polynomials σ_s and σ_c are 256, and each coefficient needs to negotiate a 1-bit negotiation key; use each coefficient to negotiate 1 Bit error coordination mechanism.

Images