# Module-LWE-Based Key Exchange Protocol Using Error Reconciliation Mechanism

Authors: Wenjuan Jia; Guanhao Xue; Baocang Wang; Yupu Hu
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Lattice-based key exchange protocols have attracted tremendous attention for its post-quantum security. In this work, we construct a Module-LWE-based key exchange protocol using Peikert’s error reconciliation mechanism. Compared with Kyber.KE, our key exchange protocol reduces the total communication cost by 96-byte, i.e., 3.2%∼6.1%, under the different parameter sets, and without reducing the post-quantum security levels. Moreover, our key exchange protocol slightly reduces the probability of session key agreement failure and the time consumed by modular multiplication of numbers and ring elements by approximately 30%. Thus, the key exchange protocol in this paper is more suitable for the lightweight communication systems.


---

## Body

## 1. Introduction

Key exchange protocol, which enables secure communications over an untrusted network by deriving and distributing shared keys between two or more parties, is one of the most fundamental cryptographic primitives and is widely applied in modern Internet protocols such as TLS [1] and SSL [2]. However, Shor [3] discovered an efficient quantum solving algorithm for the integer factorization and discrete logarithm problems in 1994, which would render number-theoretic cryptosystems insecure if large-scale quantum computers become available. With the rapid developments of quantum technology and quantum computer, we are getting closer to the quantum crisis of current public key cryptosystems. Therefore, it is urgent to propose post-quantum cryptographic schemes, such as public key encryptions (PKE), signatures, and key exchanges, that can resist quantum computer attacks. Lattice-based cryptography is one of the main directions in this field and has become the most promising post-quantum cryptography (PQC) candidate for standardization.Lattice-based key exchange protocols are generally constructed using thelearning with errors (LWE) problem and its variants. In 2005, Regev [4, 5] introduced the LWE problem and showed that solving the LWE problem with a Gaussian error distribution is at least as hard as quantumly solving the approximates shortest vector problem (GapSVP) and shortest independent vector problem (SIVP) on lattices in the worst case. Later, Peikert [6] gave a classical reduction from the approximate GapSVP (and its variants) to the search version of LWE, but with somewhat worse parameters.Although LWE provides provably secure cryptosystems, most LWE-based schemes are inefficient which motivates the research around more efficient LWE variants. These variants improve the asymptotic and practical efficiency by considering the ring of integers of a number field [7, 8], a ring of polynomials [9], or a module over a number field [10, 11]. Lyubashevsky et al. [7] introduced the ring learning with errors (Ring-LWE) problem and proved its hardness is related to the hardness of the lattice problems based on ideal lattices. Later, the module learning with errors (Module-LWE) problem was introduced by Langlois and Stele [11] in 2015, and Module-LWE comes with the hardness guarantees given by lattice problems based on module lattices. Since the algebraic structures of module lattices are more complicated than ideal lattices, Module-LWE might be able to provide a better level of security than Ring-LWE, while still providing performance advantages over LWE. In this paper, we focus on the key exchange protocols based on Module-LWE, as Module-LWE provides a nice security-efficiency trade-off by bridging LWE and Ring-LWE.Lattice-based key exchange protocols generally include two types of protocols constructed using error reconciliation mechanism or key encapsulation mechanism (KEM). Most LWE-based (and its variants) key exchange protocols are constructed using error reconciliation mechanism, such as Ding’s key exchange [12], BCNS [13], NewHope [14], Frodo [15], etc. Ding et al. [12] proposed an LWE-based Diffie-Hellman-like key exchange protocol and gave its security proof in 2012. Later, for Peikert’s tweaked version [16] of Ding’s key exchange protocol [12], Bos et al. [13] presented a concrete instantiation whose security is based on Ring-LWE problem and gave an implementation integrated into OpenSSL, with the affirmed goal of providing post-quantum security for TLS. Unfortunately, the performance of BCNS seems quite disappointing. In 2015, Alkim et al. [14] improved and generalized Peikert’s error reconciliation mechanism [16] using an analog error-correction approach and presented an unauthenticated key exchange protocol that solved the performance and security issues in BCNS [13]. Subsequently, Bos et al. [15] proposed the Frodo protocol based on similar ideas to the LWE-based protocol in [12], but as in the Ring-LWE-based key exchange protocols BCNS [13] and NewHope [14], Bos et al. incorporated and extended Peikert’s error reconciliation mechanism [16] and further modified the protocol to save bandwidth.Key exchange protocols constructed using KEM include NewHope-simple [17] and Kyber.KE [18], etc. Most of the exiting lattice-based key exchange protocols are constructed using KEM for its simplicity and modularity, although it will cause more communication cost. Alkim et al. [17] introduced NewHope-simple in 2016, which is a variant of the NewHope [14]. The main advantage of NewHope-simple over NewHope is simplicity; in particular, NewHope-simple avoids the error reconciliation mechanism. In 2018, Bos et al. [18] presented Kyber.KE that was constructed using a IND-CCA-secure KEM, and the security of Kyber.KE is based on the hardness of Module-LWE in the classical and quantum random oracle models. Recently, Xue et al. [19] presented an authentication key exchange (AKE) protocol following a generic construction with a KEM and a signature scheme in 2021. Compared with the Kyber.AKE [18], Xue’s AKE protocol reduced the communication overhead under the same post-quantum security levels.In this work, we propose a key exchange protocol constructed using error reconciliation mechanism, its security based on the hardness of Module-LWE problem. Compared with Kyber.KE, our key exchange protocol reduces the total communication cost by 96 bytes, i.e., 3.2%∼6.1%, under the same post-quantum security levels and different parameter sets, and the time consumed by modular multiplication of ring elements and numbers by approximately 30%. Secondly, the number of the most time-consuming operations (such as discrete binomial sampling and modular multiplication of ring elements) is reduced in our key exchange protocol since the reencryption is not used. Thus, our key exchange protocol is more suitable for lightweight communication protocol, such as Internet of Vehicles environment and smart home terminals. Thirdly, our protocol slightly reduces the probability of the agreement failure for the compression algorithm used is less than that in Kyber.KE. Moreover, the key exchange protocol proposed in this paper is relatively symmetric: the process of the protocol is symmetric, and the computational as well as communication costs of two parties are nearly the same. Finally, our key exchange protocol inherits the parameter sets of Kyber.KE, which lead to the same post-quantum security strength, and the computational efficiency is almost the same as Kyber.KE according to the performance analysis.Section2 gives the necessary preliminaries and definitions. Then, Section 3 describes our key exchange protocol, analyzes the correctness and security, and gives parameter sets and its performance. Finally, Section 4 makes a conclusion of our work.


## 2. Preliminaries

Denote the security parameter byλ, and the negligible function by neglλ∈λ−ω1. Let q be a prime, n be a power of two, positive integer k be the rank of Module-LWE, and q≡1mod2n. We write ℤ for the set of integers, ℚ for the set of rational numbers, and ℝ for the set of reals. Let ℤq:=ℤ/qℤ, R:=ℤx/xn+1, and Rq=R/qR:=ℤqx/xn+1. We use bold lowercase letters a for column vectors, bold uppercase letters A for matrices, and ⋅T for the transpose of vectors/matrices. Denote probability distributions by calligraphic letters S, and discrete set by uppercase letters S. We write x←S to denote sampling x from the distribution S, and x←S to denote that x is chosen uniformly at random from a set S. For an even (resp., odd) positive integer p, we define x^=xmod±p to be unique element x^ in the range −p/2<x^≤p/2 (resp., −p−1/2<x^≤p−1/2 such that x^=xmodp, and x^=xmod+p to be unique element x^ in the range 0≤x^<p such that x^=xmodp. Assume that Sample⋅ is an extendable output function, that is, a function on bit strings in which the output can be extended to any desired length. Let y∼S=Samplex (resp., y∼S=Samplex); i.e., if function Sample⋅ takes x as input, then its output is y according to distribution S (resp., uniformly over a set S).


### 2.1. Module-LWE Problem and Compression Algorithm

The Module-LWE problem was first defined by Brakerski et al. [10] and studied in detail by Langlois and Stehlé [11]. Let K be a number field of degree n, and R be the ring of integers of K. Let Kℝ:=K⊗ℚℝ, TR:=Kℝ/R, and TqR:=Kℝ/qR. We refer the reader to [20] and [11, 21–24] for the thorough introduction to algebraic number theory. Let χ be a distribution on Kℝ.The search Module-LWE problemMLWEq,k,m,n,χ is to find s∈Rqk given A,b:=As+e, where A←Rqm×k, s←Rqk, and e←χm, whereas the decision variant of the Module-LWE problem dMLWEq,k,m,n,χ asks to distinguish the distribution A,b:=As+e from uniform distribution A,u, where A←Rqm×k, s←Rqk, e←χm, and u←TqRm.It can be shown that thenormal form of the above problems where the secret distribution is a discretized version of the error distribution is no easier than the case where the secret is chosen uniformly at random. When the error distribution χ is a Gaussian distribution of parameter η>0 or a centered binomial distribution of parameter η>0, we write MLWEq,k,m,n,ηdMLWEq,k,m,n,η. We denote Advq,k,m,n,χMLWEA by the advantage of the adversary A in solving the search Module-LWE problem, and Advq,k,m,n,χdMLWED by the advantage of the distinguisher D in distinguishing between the two distributions of the decision Module-LWE problem. More precisely, the Module-LWE problem is defined as follows.Definition 1.
Letq≥2 be a modulus, m=polyλ be the number of samples, k>0 be the rank of Module-LWE, and n=polyλ be the degree of modular polynomial. Let χ be a distribution on Kℝ.
We say that the search problemMLWEq,k,m,n,χ is hard, if it holds for every PPT adversary A that(1)Advq,k,m,n,χMLWEA=PrA1λ,A,b:=As+e=s≤neglλ,where A←Rqm×k, s←Rqk, and e←χm.
We say that the decision problemdMLWEq,k,m,n,χ is hard, if it holds for every PPT distinguisher D that(2)Advq,k,m,n,χdMLWED=PrD1λ,A,b:=As+e=1−PrD1λ,A,u=1≤neglλ,where A←Rqm×k, s←Rqk, e←χm, and u←TqRm.Let integerη>0; the central binomial distributionβη is defined as follows: randomly choosing samples xi,yii=1η from 0,1η, and output ∑i=1ηxi−yi. For v∈R, v←βη means that each of its coefficients is sampling from βη independently. Next, we review the compression algorithm in [18].Definition 2.
Let0<d<logq be an integer and q>0 be a modulus. The compression algorithm consists of two functions: Compressq⋅,d and Decompressq⋅,d. These two functions are defined as follows:(3)Compressqx,d:=2dq⋅xmod+2dforx∈ℤq,Decompressqx,d:=q2d⋅xforx∈ℤ2d.IfCompressq⋅,d or Decompressq⋅,d is used with vector v∈Rqk, then the function is applied to each coefficient individually.


### 2.2. Error Reconciliation Mechanism

When constructing key exchange protocol using LWE problem and its variants, a serious matter is that there usually are errors in the protocol, which leads to similar values instead of the same values. These errors are significant to the post-quantum security and should be handled since the key exchange protocol requires communication parties get common session key. Theerror reconciliation mechanism, first introduced by Ding et al. [12], is the key technique to deal with errors. It mainly include Ding’s error reconciliation mechanism [12], Peikert’s error reconciliation mechanism (and its multibit variant) [16], and D˜4 lattice decoding [14] so far. Peikert’s error reconciliation mechanism is widely used because of its simplicity and efficiency, such as BCNS [13] and Frodo [15], and the detailed process of reconciliation mechanism and its correctness is described in [16]. Next, we recall Peikert’s reconciliation mechanism.Definingx:=x+1/2∈ℤ for x∈ℝ, for an integer p that divides q (typically p=2), the modular rounding function⋅q,p:ℤq⟶ℤp is defined by xq,p:=x⋅p/qmodp. Defining I0:=0,1,…,q/4−1, I1:=−q/4,…,−2,−1modq, and E=−q/8,q/8∩ℤ. The cross-rounding function⋅q,2:ℤq⟶ℤ2 is defined by xq,2:=4/q⋅xmod2, and the reconciliation functionRec⋅,⋅:ℤq×ℤ2⟶ℤ2 is defined by Recy,σ:=0 if y∈Iσ+Emodq; otherwise Recy,σ:=1, where σ∈ℤ2.Both modular rounding and cross-rounding functions are extended to polynomialsf∈Rq coefficientwise. Lemma 1 shows that the modular rounding xq,2 of a uniform random element x∈ℤq is uniform random in ℤ2 given cross-rounding xq,2 of x; i.e., xq,2 hides xq,2. Lemma 2 shows that one can recover xq,2 from an element y∈ℤq close to an element x∈ℤq, given only y and the cross-rounding xq,2.Lemma 1 (see [16], Claim 3.1).
For evenq, if x∈ℤq is uniformly random, then xq,2 is uniformly random given xq,2.Lemma 2 (see [16], Claim 3.2).
For evenq, if y=x+emodq for some x∈ℤq and e∈E, then Recy,xq,2=xq,2.When modulusq is odd, it is necessary to work in ℤ2q rather than ℤq to avoid bias in the derived bits. Since we use odd q in this paper, we need to introduce the randomized doubling function from [16]. The randomized doubling function dbl⋅:ℤq⟶ℤ2q is defined by dblx:=2x−e¯, where e¯ is sampled from −1,0,1 with probabilities Pre¯=−1=Pre¯=1=1/4 and Pre¯=0=1/2. The randomized doubling function is extended to polynomials f∈Rq by applying it to each of f ’s coefficients.Lemma3 shows that, for a uniform random element x∈ℤq, the modular rounding dblx2q,2 of dblx∈ℤ2q is uniform random in ℤ2 given cross-rounding dblx2q,2; i.e., dblx2q,2 hides dblx2q,2. Moreover, if y,x∈ℤq are close, then so are 2y,x^:=dblx∈ℤ2q; i.e., if y=x+emodq for some e∈E, then we have 2y=x¯+2e+e¯mod2q. Thus, one can recover x¯2q,2 of a random element x∈ℤq from an element y∈ℤq close to x and the cross-rounding x¯2q,2, as described by Lemma 4.Lemma 3 (see [16], Claim 3.3).
For oddq, if x∈ℤq is uniformly random and x¯:=dblx∈ℤ2q, then x¯2q,2 is uniformly random given x¯2q,2.Lemma 4 (see [16], Section 3.2).
For oddq, let x¯:=dblx∈ℤ2q; if y=x+emodq for some x∈ℤq and e∈E, then Rec2y,x¯2q,2=x¯2q,2.


## 2.1. Module-LWE Problem and Compression Algorithm

The Module-LWE problem was first defined by Brakerski et al. [10] and studied in detail by Langlois and Stehlé [11]. Let K be a number field of degree n, and R be the ring of integers of K. Let Kℝ:=K⊗ℚℝ, TR:=Kℝ/R, and TqR:=Kℝ/qR. We refer the reader to [20] and [11, 21–24] for the thorough introduction to algebraic number theory. Let χ be a distribution on Kℝ.The search Module-LWE problemMLWEq,k,m,n,χ is to find s∈Rqk given A,b:=As+e, where A←Rqm×k, s←Rqk, and e←χm, whereas the decision variant of the Module-LWE problem dMLWEq,k,m,n,χ asks to distinguish the distribution A,b:=As+e from uniform distribution A,u, where A←Rqm×k, s←Rqk, e←χm, and u←TqRm.It can be shown that thenormal form of the above problems where the secret distribution is a discretized version of the error distribution is no easier than the case where the secret is chosen uniformly at random. When the error distribution χ is a Gaussian distribution of parameter η>0 or a centered binomial distribution of parameter η>0, we write MLWEq,k,m,n,ηdMLWEq,k,m,n,η. We denote Advq,k,m,n,χMLWEA by the advantage of the adversary A in solving the search Module-LWE problem, and Advq,k,m,n,χdMLWED by the advantage of the distinguisher D in distinguishing between the two distributions of the decision Module-LWE problem. More precisely, the Module-LWE problem is defined as follows.Definition 1.
Letq≥2 be a modulus, m=polyλ be the number of samples, k>0 be the rank of Module-LWE, and n=polyλ be the degree of modular polynomial. Let χ be a distribution on Kℝ.
We say that the search problemMLWEq,k,m,n,χ is hard, if it holds for every PPT adversary A that(1)Advq,k,m,n,χMLWEA=PrA1λ,A,b:=As+e=s≤neglλ,where A←Rqm×k, s←Rqk, and e←χm.
We say that the decision problemdMLWEq,k,m,n,χ is hard, if it holds for every PPT distinguisher D that(2)Advq,k,m,n,χdMLWED=PrD1λ,A,b:=As+e=1−PrD1λ,A,u=1≤neglλ,where A←Rqm×k, s←Rqk, e←χm, and u←TqRm.Let integerη>0; the central binomial distributionβη is defined as follows: randomly choosing samples xi,yii=1η from 0,1η, and output ∑i=1ηxi−yi. For v∈R, v←βη means that each of its coefficients is sampling from βη independently. Next, we review the compression algorithm in [18].Definition 2.
Let0<d<logq be an integer and q>0 be a modulus. The compression algorithm consists of two functions: Compressq⋅,d and Decompressq⋅,d. These two functions are defined as follows:(3)Compressqx,d:=2dq⋅xmod+2dforx∈ℤq,Decompressqx,d:=q2d⋅xforx∈ℤ2d.IfCompressq⋅,d or Decompressq⋅,d is used with vector v∈Rqk, then the function is applied to each coefficient individually.


## 2.2. Error Reconciliation Mechanism

When constructing key exchange protocol using LWE problem and its variants, a serious matter is that there usually are errors in the protocol, which leads to similar values instead of the same values. These errors are significant to the post-quantum security and should be handled since the key exchange protocol requires communication parties get common session key. Theerror reconciliation mechanism, first introduced by Ding et al. [12], is the key technique to deal with errors. It mainly include Ding’s error reconciliation mechanism [12], Peikert’s error reconciliation mechanism (and its multibit variant) [16], and D˜4 lattice decoding [14] so far. Peikert’s error reconciliation mechanism is widely used because of its simplicity and efficiency, such as BCNS [13] and Frodo [15], and the detailed process of reconciliation mechanism and its correctness is described in [16]. Next, we recall Peikert’s reconciliation mechanism.Definingx:=x+1/2∈ℤ for x∈ℝ, for an integer p that divides q (typically p=2), the modular rounding function⋅q,p:ℤq⟶ℤp is defined by xq,p:=x⋅p/qmodp. Defining I0:=0,1,…,q/4−1, I1:=−q/4,…,−2,−1modq, and E=−q/8,q/8∩ℤ. The cross-rounding function⋅q,2:ℤq⟶ℤ2 is defined by xq,2:=4/q⋅xmod2, and the reconciliation functionRec⋅,⋅:ℤq×ℤ2⟶ℤ2 is defined by Recy,σ:=0 if y∈Iσ+Emodq; otherwise Recy,σ:=1, where σ∈ℤ2.Both modular rounding and cross-rounding functions are extended to polynomialsf∈Rq coefficientwise. Lemma 1 shows that the modular rounding xq,2 of a uniform random element x∈ℤq is uniform random in ℤ2 given cross-rounding xq,2 of x; i.e., xq,2 hides xq,2. Lemma 2 shows that one can recover xq,2 from an element y∈ℤq close to an element x∈ℤq, given only y and the cross-rounding xq,2.Lemma 1 (see [16], Claim 3.1).
For evenq, if x∈ℤq is uniformly random, then xq,2 is uniformly random given xq,2.Lemma 2 (see [16], Claim 3.2).
For evenq, if y=x+emodq for some x∈ℤq and e∈E, then Recy,xq,2=xq,2.When modulusq is odd, it is necessary to work in ℤ2q rather than ℤq to avoid bias in the derived bits. Since we use odd q in this paper, we need to introduce the randomized doubling function from [16]. The randomized doubling function dbl⋅:ℤq⟶ℤ2q is defined by dblx:=2x−e¯, where e¯ is sampled from −1,0,1 with probabilities Pre¯=−1=Pre¯=1=1/4 and Pre¯=0=1/2. The randomized doubling function is extended to polynomials f∈Rq by applying it to each of f ’s coefficients.Lemma3 shows that, for a uniform random element x∈ℤq, the modular rounding dblx2q,2 of dblx∈ℤ2q is uniform random in ℤ2 given cross-rounding dblx2q,2; i.e., dblx2q,2 hides dblx2q,2. Moreover, if y,x∈ℤq are close, then so are 2y,x^:=dblx∈ℤ2q; i.e., if y=x+emodq for some e∈E, then we have 2y=x¯+2e+e¯mod2q. Thus, one can recover x¯2q,2 of a random element x∈ℤq from an element y∈ℤq close to x and the cross-rounding x¯2q,2, as described by Lemma 4.Lemma 3 (see [16], Claim 3.3).
For oddq, if x∈ℤq is uniformly random and x¯:=dblx∈ℤ2q, then x¯2q,2 is uniformly random given x¯2q,2.Lemma 4 (see [16], Section 3.2).
For oddq, let x¯:=dblx∈ℤ2q; if y=x+emodq for some x∈ℤq and e∈E, then Rec2y,x¯2q,2=x¯2q,2.


## 3. Key Exchange Protocol

In this section, we propose a Module-LWE-based unauthenticated key exchange protocol using Peikert’s error reconciliation mechanism, which is a variant of Kyber.KE [18]. We first describe the concrete process of the key exchange protocol and then prove its correctness and security. Finally, we give the parameter sets and analyze the performance of our key exchange protocol, including communication cost and computation overhead.


### 3.1. Key Exchange Protocol Using Peikert’s Error Reconciliation Mechanism

We present a Module-LWE-based key exchange protocol using Peikert’s error reconciliation mechanism, instead of using IND-CCA-secure KEM as in Krber.KE [18]. In particular, Alice (initiator) sends b,ρ to Bob (responder) in both our key exchange protocol and Kyber.KE, where b is the output of the compression function. However, Bob sends u,c to Alice in the second round of our key exchange protocol, where u is the output of the compression function and c is the output of the cross-rounding function. But Bob sends u,v,d to Alice in the second round of Kyber.KE, where both u and v are the output of the compression function and d is a 256-bit random bit string. The specific description of the protocol is shown in Figure 1.Figure 1
Key exchange protocol using Peikert’s error reconciliation mechanism.Compared with Kyber.KE [18], our key exchange protocol has the following differences.


#### 3.1.1. Our Key Exchange Protocol Is Relatively Symmetric and Reduces the Communication Cost in the Second Round

The Kyber.KE is asymmetric: Alice generates key pair and sends public key to the Bob, then Bob encrypts random session key with public key and sends the ciphertext back to Alice, and finally Alice decrypts the received ciphertext to get the session key. It is known from [18] that the communication costs in the first and second rounds of Kyber.KE are not equal. However, the communication costs of both rounds are equal in our key exchange protocol, and we reduce the communication cost in the second round. See Section 3.4 for detailed analysis.


#### 3.1.2. Our Key Exchange Protocol Slightly Reduces the Probability of Session Key Agreement Failure

The Kyber.KE always compresses public key and ciphertext using compression algorithm; this is done not only to save communication traffic but also to ensure correctness. Generally, the least significant bits are discarded and the other bits are retained using the compression function. Thus, the probability of the session key agreement failure can be effectively reduced without using the compression algorithm or reducing the number of times of the compression algorithm is used. In Kyber.KE, the compression algorithm will add an extra error term on sent messages, which means the encoded messages are not uniformly at random and then may leak some information. However, the ideal situation (no compression algorithm is used) and the real situation are indistinguishable under certain parameter sets according to the analysis of [18]. Compared with Kyber.KE, our key exchange protocol reduces the number of the compression functions used by 4 times and the decompression functions used by 2 times; thus it can slightly reduce the probability of session key agreement failure of the key exchange protocol. If the compression algorithm is not used, it will not affect the correctness of the protocol but increase the additional communication traffic. Therefore, we still use the compression algorithm and prove that it has no effect on the correctness and security of the protocol in Sections 3.2 and 3.3.


### 3.2. Correctness

This section gives the correctness proof of our Module-LWE-based key exchange protocol. According to Section2.2, when q is odd, there will be an additional randomized doubling function dbl⋅ in Peikert’s error reconciliation mechanism, and it maps x∈ℤq to x¯:=dblx∈ℤ2q.Assume that the tiny error betweenb∈Rqk and b′ after using compression algorithm is cb; i.e.,(4)b′=DecompressqCompressqb,dt,dt=As+e+cb.Similarly, suppose thatu′=DecompressqCompressqu,du,du=ATs′+e1+cu for u∈Rqk.Thus the difference betweenv′ and v¯ is(5)v¯−v′=2⋅b′Ts′+e2−e¯−2⋅sTu′=2⋅eTs′+cbTs′+e2−sTe1−sTcu−e¯.Peikert’s error reconciliation mechanism shows that the error tolerance range isq/2 when q is odd. Therefore, the output of reconciliation function is Recv′,c=v¯2q,2 if the difference between v′ and v¯ satisfies v¯−v′≤q/2. Then the inequation above turns to(6)2⋅eTs′+cbTs′+e2−sTe1−sTcu−e¯≤q2,i.e.,(7)eTs′+cbTs′+e2−sTe1−sTcu≤q4.Compared with the correctness proof in Kyber.KE, inequation (1) is almost the same. Thus, we have that the probability that inequation (1) holds is no less than 1−2−128 by choosing appropriate parameter sets, which means that the probability of session key agreement failure is less than 2−128.Note that there is a slight difference between inequation (1) and the inequation in Kyber.KE [18], because v is not compressed in our key exchange protocol; i.e., the error term cv of v is missed in inequation (1). Even though the norm of cv is relatively small, it increases the probability of session key agreement failure in Kyber.KE under the same parameter sets. In other words, the probability of session key agreement failure in our key exchange protocol is smaller than that in Kyber.KE.


### 3.3. Security Proof

This section gives the security proof of our key exchange protocol by designing a sequence of games. The Module-LWE-based key exchange protocol described in Figure1 is constructed using Peikert’s error reconciliation mechanism; its security relies on the hardness of Module-LWE problem. One can prove that the generated session key is undistinguishable from equal-length random bit string.Theorem 1.
Letq be an odd prime, n,k be public parameters, and η be the parameter of binomial distribution. Then the key exchange protocol described in Figure 1 is secure, provided that the decision Module-LWE problem dMLWEq,k,k+1,n,η is hard. More precisely, if D is an distinguisher for dMLWEq,k,k+1,n,η, then(8)Advq,k,k,n,ηKEA≤2⋅Advq,k,k+1,n,ηdMLWED,where A is an adversary for the key exchange protocol described in Figure 1.Proof. Letb∗ be the bit guessed by adversary, and A an adversary for the key exchange protocol described in Figure 1. Consider the following sequence of games. Game 0. This is the original game, where the messages are honestly generated according to the description in Figure 1. Our goal is to bound Advq,k,k,n,ηKEA∗=|Prb=b∗inGame0−1/2|. Note that, in Game 0, the Module-LWE samples are A,b0:=As+e, AT,u0:=ATs′+e1, and b′T,v:=b′Ts′+e2.Game 1. In this game, assume that b0 is chosen uniformly at random from Rqk; i.e., A,b0 is chosen uniformly at random from Rqk×k×Rqk instead of a Module-LWE sample. In Game 1, the Module-LWE samples are AT,u0:=ATs′+e1 and b′T,v:=b′Ts′+e2. By the assumption that the decision Module-LWE problem dMLWEq,k,k+1,n,η is hard, we know that Game 0 and Game 1 are computationally indistinguishable. In other words, there exists a Module-LWE distinguisher D with the same running times as that of A, such that |Prb=b∗inGame0−Prb=b∗inGame1|≤Advq,k,k,n,ηdMLWED≤Advq,k,k+1,n,ηdMLWED.Game 2. In this game, assume that u0,v is chosen uniformly at random from Rqk×Rq; i.e., both AT,u0 and b′T,v are chosen uniformly at random from Rqk×k×Rqk and Rqk×Rq, respectively. By the assumption that the decision Module-LWE problem dMLWEq,k,k+1,n,η is hard, we know that Game 1 and Game 2 are computationally indistinguishable. In other words, there exists a Module-LWE distinguisher D with the same running times as that of A, such that |Prb=b∗in Game1−Prb=b∗in Game2|≤Advq,k,k+1,n,ηdMLWED.In Game 2, sincev∈Rq is uniformly random and v¯:=dblv, according to Lemma 3 in Section 2.2, we know that real session key k:=v¯2q,2 is uniformly random in 0,1n given c:=v¯2q,2. Therefore, Prb=b∗inGame2=1/2.Collecting the probabilities yields the required bound.


### 3.4. Parameter Sets and Performance

In this section, we give the parameter sets of the protocol described in Figure1 and analysis of their performance. Based on the analysis of Section 3.1, the parameter sets of Kyber.KE can perfectly satisfy the correctness of our key exchange protocol. The parameter sets of the protocol described in Figure 1 and their performance are listed in Table 1, where “Alice ⟶ Bob” (resp. “Bob ⟶ Alice”) denotes the communication cost in the first (resp., second) round.Table 1
Parameter sets and performance of our key exchange protocol.
Parameter setsnkqηdt,dupq secAlice⟶Bob (bytes)Bob⟶Alice (bytes)Light256276815(11, 11)102736736Default256376814(11, 11)16110881088Paranoid256476813(11, 11)21814401440It is known that Alice sendsb,ρ to Bob in both the key exchange protocol described in Figure 1 and Kyber.KE [18]. However, Bob sends u,c to Alice in the second round of the key exchange protocol described in Figure 1 and sends u,v,d in Kyber.KE. We take the parameter set “Default” as an example to calculate the reduced communication cost in the key exchange protocol described in Figure 1. Both in our key exchange protocol and in Kyber.KE, u is a vector of three polynomials with 256 11-bit coefficients. In Kyber.KE, v is a polynomial with 256 3-bit coefficients and d is a 256-bit random string; i.e., 32×3+32=128 bytes are required to store v and d. But in our key exchange protocol, each coefficient of v¯=dblv∈R2q is in ℤ2q; then the cross-rounding function takes v¯ as input and outputs a 256-bit (32-byte) string c. According to the analysis above, our key exchange protocol reduces the total communication cost by 96-byte, i.e., 4.2%. Note that no matter which parameter sets we choose, the total communication cost reduced is invariant. Therefore, compared with Kyber.KE, our key exchange protocol reduces the total communication cost by 3.2%∼6.1% for different parameter sets.In terms of computational efficient, the number of the most time-consuming operations, such as discrete binomial sampling and modular multiplication of ring elements, used in our key exchange protocol is less than that in Kyber.KE, since our key exchange protocol does not use the reencryption. In relatively time-consuming operations, we mainly talk about the modular multiplication of ring elements and numbers. Note that the randomized doubling function, cross-rounding function, modular rounding function, and compression algorithm are all modular multiplications of ring elements and numbers. Moreover, the time consumed by these operations is the same for vectors of the same dimension. In particular, Kyber.KE includes 6 compression functions and 4 decompress functions, whereas our key exchange protocol includes 2 compression functions, 2 decompress functions, 1 randomized doubling function, 1 cross-rounding function, and 1 modular rounding function. Therefore, compared with Kyber.KE, our key exchange protocol reduces the time consumed by modular multiplication of numbers and ring elements by approximately 30%, and the only difference between two protocols is that some operations are transferred from the initiator to the responder.From the aspect of security, both our key exchange protocol and Kyber.KE are based on Module-LWE problem, and the scale of the problem is equal. Thus the security strength of our key exchange protocol is the same as that of Kyber.KE.Table1 shows that the communication costs of both rounds are equal, which means our key exchange protocol is a Diffie-Hellman-like symmetric key exchange protocol. Since symmetric key exchange protocols can ensure that the computation and communication costs of the two parties are roughly the same instead of occupying the computing resources of one party, it is more suitable to be deployed among users of the same level, such as the Internet of Vehicles (IOV) environment.


## 3.1. Key Exchange Protocol Using Peikert’s Error Reconciliation Mechanism

We present a Module-LWE-based key exchange protocol using Peikert’s error reconciliation mechanism, instead of using IND-CCA-secure KEM as in Krber.KE [18]. In particular, Alice (initiator) sends b,ρ to Bob (responder) in both our key exchange protocol and Kyber.KE, where b is the output of the compression function. However, Bob sends u,c to Alice in the second round of our key exchange protocol, where u is the output of the compression function and c is the output of the cross-rounding function. But Bob sends u,v,d to Alice in the second round of Kyber.KE, where both u and v are the output of the compression function and d is a 256-bit random bit string. The specific description of the protocol is shown in Figure 1.Figure 1
Key exchange protocol using Peikert’s error reconciliation mechanism.Compared with Kyber.KE [18], our key exchange protocol has the following differences.


### 3.1.1. Our Key Exchange Protocol Is Relatively Symmetric and Reduces the Communication Cost in the Second Round

The Kyber.KE is asymmetric: Alice generates key pair and sends public key to the Bob, then Bob encrypts random session key with public key and sends the ciphertext back to Alice, and finally Alice decrypts the received ciphertext to get the session key. It is known from [18] that the communication costs in the first and second rounds of Kyber.KE are not equal. However, the communication costs of both rounds are equal in our key exchange protocol, and we reduce the communication cost in the second round. See Section 3.4 for detailed analysis.


### 3.1.2. Our Key Exchange Protocol Slightly Reduces the Probability of Session Key Agreement Failure

The Kyber.KE always compresses public key and ciphertext using compression algorithm; this is done not only to save communication traffic but also to ensure correctness. Generally, the least significant bits are discarded and the other bits are retained using the compression function. Thus, the probability of the session key agreement failure can be effectively reduced without using the compression algorithm or reducing the number of times of the compression algorithm is used. In Kyber.KE, the compression algorithm will add an extra error term on sent messages, which means the encoded messages are not uniformly at random and then may leak some information. However, the ideal situation (no compression algorithm is used) and the real situation are indistinguishable under certain parameter sets according to the analysis of [18]. Compared with Kyber.KE, our key exchange protocol reduces the number of the compression functions used by 4 times and the decompression functions used by 2 times; thus it can slightly reduce the probability of session key agreement failure of the key exchange protocol. If the compression algorithm is not used, it will not affect the correctness of the protocol but increase the additional communication traffic. Therefore, we still use the compression algorithm and prove that it has no effect on the correctness and security of the protocol in Sections 3.2 and 3.3.


## 3.1.1. Our Key Exchange Protocol Is Relatively Symmetric and Reduces the Communication Cost in the Second Round

The Kyber.KE is asymmetric: Alice generates key pair and sends public key to the Bob, then Bob encrypts random session key with public key and sends the ciphertext back to Alice, and finally Alice decrypts the received ciphertext to get the session key. It is known from [18] that the communication costs in the first and second rounds of Kyber.KE are not equal. However, the communication costs of both rounds are equal in our key exchange protocol, and we reduce the communication cost in the second round. See Section 3.4 for detailed analysis.


## 3.1.2. Our Key Exchange Protocol Slightly Reduces the Probability of Session Key Agreement Failure

The Kyber.KE always compresses public key and ciphertext using compression algorithm; this is done not only to save communication traffic but also to ensure correctness. Generally, the least significant bits are discarded and the other bits are retained using the compression function. Thus, the probability of the session key agreement failure can be effectively reduced without using the compression algorithm or reducing the number of times of the compression algorithm is used. In Kyber.KE, the compression algorithm will add an extra error term on sent messages, which means the encoded messages are not uniformly at random and then may leak some information. However, the ideal situation (no compression algorithm is used) and the real situation are indistinguishable under certain parameter sets according to the analysis of [18]. Compared with Kyber.KE, our key exchange protocol reduces the number of the compression functions used by 4 times and the decompression functions used by 2 times; thus it can slightly reduce the probability of session key agreement failure of the key exchange protocol. If the compression algorithm is not used, it will not affect the correctness of the protocol but increase the additional communication traffic. Therefore, we still use the compression algorithm and prove that it has no effect on the correctness and security of the protocol in Sections 3.2 and 3.3.


## 3.2. Correctness

This section gives the correctness proof of our Module-LWE-based key exchange protocol. According to Section2.2, when q is odd, there will be an additional randomized doubling function dbl⋅ in Peikert’s error reconciliation mechanism, and it maps x∈ℤq to x¯:=dblx∈ℤ2q.Assume that the tiny error betweenb∈Rqk and b′ after using compression algorithm is cb; i.e.,(4)b′=DecompressqCompressqb,dt,dt=As+e+cb.Similarly, suppose thatu′=DecompressqCompressqu,du,du=ATs′+e1+cu for u∈Rqk.Thus the difference betweenv′ and v¯ is(5)v¯−v′=2⋅b′Ts′+e2−e¯−2⋅sTu′=2⋅eTs′+cbTs′+e2−sTe1−sTcu−e¯.Peikert’s error reconciliation mechanism shows that the error tolerance range isq/2 when q is odd. Therefore, the output of reconciliation function is Recv′,c=v¯2q,2 if the difference between v′ and v¯ satisfies v¯−v′≤q/2. Then the inequation above turns to(6)2⋅eTs′+cbTs′+e2−sTe1−sTcu−e¯≤q2,i.e.,(7)eTs′+cbTs′+e2−sTe1−sTcu≤q4.Compared with the correctness proof in Kyber.KE, inequation (1) is almost the same. Thus, we have that the probability that inequation (1) holds is no less than 1−2−128 by choosing appropriate parameter sets, which means that the probability of session key agreement failure is less than 2−128.Note that there is a slight difference between inequation (1) and the inequation in Kyber.KE [18], because v is not compressed in our key exchange protocol; i.e., the error term cv of v is missed in inequation (1). Even though the norm of cv is relatively small, it increases the probability of session key agreement failure in Kyber.KE under the same parameter sets. In other words, the probability of session key agreement failure in our key exchange protocol is smaller than that in Kyber.KE.


## 3.3. Security Proof

This section gives the security proof of our key exchange protocol by designing a sequence of games. The Module-LWE-based key exchange protocol described in Figure1 is constructed using Peikert’s error reconciliation mechanism; its security relies on the hardness of Module-LWE problem. One can prove that the generated session key is undistinguishable from equal-length random bit string.Theorem 1.
Letq be an odd prime, n,k be public parameters, and η be the parameter of binomial distribution. Then the key exchange protocol described in Figure 1 is secure, provided that the decision Module-LWE problem dMLWEq,k,k+1,n,η is hard. More precisely, if D is an distinguisher for dMLWEq,k,k+1,n,η, then(8)Advq,k,k,n,ηKEA≤2⋅Advq,k,k+1,n,ηdMLWED,where A is an adversary for the key exchange protocol described in Figure 1.Proof. Letb∗ be the bit guessed by adversary, and A an adversary for the key exchange protocol described in Figure 1. Consider the following sequence of games. Game 0. This is the original game, where the messages are honestly generated according to the description in Figure 1. Our goal is to bound Advq,k,k,n,ηKEA∗=|Prb=b∗inGame0−1/2|. Note that, in Game 0, the Module-LWE samples are A,b0:=As+e, AT,u0:=ATs′+e1, and b′T,v:=b′Ts′+e2.Game 1. In this game, assume that b0 is chosen uniformly at random from Rqk; i.e., A,b0 is chosen uniformly at random from Rqk×k×Rqk instead of a Module-LWE sample. In Game 1, the Module-LWE samples are AT,u0:=ATs′+e1 and b′T,v:=b′Ts′+e2. By the assumption that the decision Module-LWE problem dMLWEq,k,k+1,n,η is hard, we know that Game 0 and Game 1 are computationally indistinguishable. In other words, there exists a Module-LWE distinguisher D with the same running times as that of A, such that |Prb=b∗inGame0−Prb=b∗inGame1|≤Advq,k,k,n,ηdMLWED≤Advq,k,k+1,n,ηdMLWED.Game 2. In this game, assume that u0,v is chosen uniformly at random from Rqk×Rq; i.e., both AT,u0 and b′T,v are chosen uniformly at random from Rqk×k×Rqk and Rqk×Rq, respectively. By the assumption that the decision Module-LWE problem dMLWEq,k,k+1,n,η is hard, we know that Game 1 and Game 2 are computationally indistinguishable. In other words, there exists a Module-LWE distinguisher D with the same running times as that of A, such that |Prb=b∗in Game1−Prb=b∗in Game2|≤Advq,k,k+1,n,ηdMLWED.In Game 2, sincev∈Rq is uniformly random and v¯:=dblv, according to Lemma 3 in Section 2.2, we know that real session key k:=v¯2q,2 is uniformly random in 0,1n given c:=v¯2q,2. Therefore, Prb=b∗inGame2=1/2.Collecting the probabilities yields the required bound.


## 3.4. Parameter Sets and Performance

In this section, we give the parameter sets of the protocol described in Figure1 and analysis of their performance. Based on the analysis of Section 3.1, the parameter sets of Kyber.KE can perfectly satisfy the correctness of our key exchange protocol. The parameter sets of the protocol described in Figure 1 and their performance are listed in Table 1, where “Alice ⟶ Bob” (resp. “Bob ⟶ Alice”) denotes the communication cost in the first (resp., second) round.Table 1
Parameter sets and performance of our key exchange protocol.
Parameter setsnkqηdt,dupq secAlice⟶Bob (bytes)Bob⟶Alice (bytes)Light256276815(11, 11)102736736Default256376814(11, 11)16110881088Paranoid256476813(11, 11)21814401440It is known that Alice sendsb,ρ to Bob in both the key exchange protocol described in Figure 1 and Kyber.KE [18]. However, Bob sends u,c to Alice in the second round of the key exchange protocol described in Figure 1 and sends u,v,d in Kyber.KE. We take the parameter set “Default” as an example to calculate the reduced communication cost in the key exchange protocol described in Figure 1. Both in our key exchange protocol and in Kyber.KE, u is a vector of three polynomials with 256 11-bit coefficients. In Kyber.KE, v is a polynomial with 256 3-bit coefficients and d is a 256-bit random string; i.e., 32×3+32=128 bytes are required to store v and d. But in our key exchange protocol, each coefficient of v¯=dblv∈R2q is in ℤ2q; then the cross-rounding function takes v¯ as input and outputs a 256-bit (32-byte) string c. According to the analysis above, our key exchange protocol reduces the total communication cost by 96-byte, i.e., 4.2%. Note that no matter which parameter sets we choose, the total communication cost reduced is invariant. Therefore, compared with Kyber.KE, our key exchange protocol reduces the total communication cost by 3.2%∼6.1% for different parameter sets.In terms of computational efficient, the number of the most time-consuming operations, such as discrete binomial sampling and modular multiplication of ring elements, used in our key exchange protocol is less than that in Kyber.KE, since our key exchange protocol does not use the reencryption. In relatively time-consuming operations, we mainly talk about the modular multiplication of ring elements and numbers. Note that the randomized doubling function, cross-rounding function, modular rounding function, and compression algorithm are all modular multiplications of ring elements and numbers. Moreover, the time consumed by these operations is the same for vectors of the same dimension. In particular, Kyber.KE includes 6 compression functions and 4 decompress functions, whereas our key exchange protocol includes 2 compression functions, 2 decompress functions, 1 randomized doubling function, 1 cross-rounding function, and 1 modular rounding function. Therefore, compared with Kyber.KE, our key exchange protocol reduces the time consumed by modular multiplication of numbers and ring elements by approximately 30%, and the only difference between two protocols is that some operations are transferred from the initiator to the responder.From the aspect of security, both our key exchange protocol and Kyber.KE are based on Module-LWE problem, and the scale of the problem is equal. Thus the security strength of our key exchange protocol is the same as that of Kyber.KE.Table1 shows that the communication costs of both rounds are equal, which means our key exchange protocol is a Diffie-Hellman-like symmetric key exchange protocol. Since symmetric key exchange protocols can ensure that the computation and communication costs of the two parties are roughly the same instead of occupying the computing resources of one party, it is more suitable to be deployed among users of the same level, such as the Internet of Vehicles (IOV) environment.


## 4. Conclusion

In this paper, we propose a Module-LWE-based key exchange protocol using Peikert’s error reconciliation mechanism. Compared with Kyber.KE, our key exchange protocol reduces the total communication cost by 96 bytes, i.e., 3.2%∼6.1%, under the same post-quantum security levels and different parameter sets. Furthermore, our key exchange protocol slightly reduces the probability of session key agreement failure due to the reduction in the use of compression algorithms, has the less number of the most time-consuming operations (such as discrete binomial sampling and modular multiplication of ring elements) since the reencryption is not used, and reduces the time consumed by modular multiplication of numbers and ring elements by approximately 30%. Unlike the protocol using the KEM, our key exchange protocol is a Diffie-Hellman-like symmetric protocol, which means the computation and communication costs of the two parties are roughly the same. With the advantages and properties above, our key exchange protocol is more suitable for the lightweight communication protocol, such as deployed in the IOV environment and smart home terminals.



---

*Source: 8299232-2022-02-01.xml*