# Improved Verifier-Based Three-Party Password-Authenticated Key Exchange Protocol from Ideal Lattices

Authors: Yongli Tang; Ying Li; Zongqu Zhao; Jing Zhang; Lina Ren; Yuanhong Li
Journal: Security and Communication Networks
 (2021)

---

## Abstract

With the advent of large-scale social networks, two communication users need to generate session keys with the help of a remote server to communicate securely. In the existing three-party authenticated key exchange (3PAKE) protocols, users’ passwords need to be stored on the server; it cannot resist the server disclosure attack. To solve this security problem, we propose a more efficient 3PAKE protocol based on the verification element by adopting a public-key cryptosystem and approximate smooth projection hash (ASPH) function on an ideal lattice. Using the structure of separating authentication from the server, the user can negotiate the session key only after two rounds of communication. The analysis results show that it can improve the efficiency of computation and communication and resist the server disclosure attack, quantum algorithm attack, and replay attack; moreover, it has session key privacy to the server. This protocol can meet the performance requirement of the current communication network.


---

## Body

## 1. Introduction

In 1976, Diffie and Hellman [1] first proposed a key exchange (KE) protocol to generate a session key between two users, to realize the secure transmission of information in the channel, but they did not consider the identity authentication of two users. Then, authenticated key exchange (AKE) protocol is proposed based on the KE protocol. AKE protocol ensures that it can still correctly generate the session key among two users in the case of an active attack by the adversary.AKE protocol can be classified into identity-based AKE protocol, public-key infrastructure (PKI) based AKE protocol, and password-based AKE (PAKE) protocol. PAKE protocol dislodges the public-key infrastructure in the network and takes the low entropy password as the input so that the participants can negotiate a high entropy session key after mutual authentication on the insecure channel. The PAKE protocol has attracted extensive attention because the password is short, practical, and easy to remember.With the emergence of large-scale user mutual communication, the implementation of the two-party authenticated key exchange (2PAKE) protocol increases the burden of user password management [2–5], and the 3PAKE protocol allows users to negotiate a session key with other users when they share a password with the server. In the 3PAKE protocol, if the user’s password is stored on the server in plaintext, it is called symmetric 3PAKE protocol. Once the server is attacked and the password file is leaked, the attacker can forge a legitimate user to access after obtaining the user’s password [6–10]. Rising is a company focusing on the research and development of anti-virus products and network security products. Its threat intelligence system is based on threat detection technology of big data analysis and can trace the trajectory of threat behavior by using threat intelligence, and it once captures an overseas virus transmission server. The virus transmission server scans the server in the network by using a weak password. Once the server is found, it will implant a virus to obtain the password file on the server. When the virus transmission server is captured, it has stored the IP address and account’s weak password of more than 2000 MSSQL servers and more than 600 phpMyAdmin servers.Against this type of server file disclosure attack, Kwon et al. [11] constructed the first 3PAKE protocol based on verification element in 2007. The user sends the transformed value of the password to the server as a verification element. Now, even if the verification element on the server is leaked, the adversary cannot speculate the user’s plaintext password. When the adversary carries out an offline dictionary attack to obtain the user’s password, the server can notify the user that the verification element has been leaked and allow the user to reexecute the registration phase and generate a new verification element [12]. This approach effectively solves the disadvantages of the symmetric 3PAKE protocol.In 2016, Yang et al. [13] proposed the first 3PAKE protocol based on a verification element under the standard model. However, through analysis, it is found that the user calculates the message sent to the server according to the password in the process of key agreement. Now, the attacker can use the message authentication code (MAC) value in the information to execute the offline dictionary attack on the user’s password. In 2020, Zhang et al. [14] used the smooth projection hash function based on Yang’s protocol and improved it by using the DDH difficulty hypothesis, so that after four rounds of communication between participants, it can negotiate a session key of both sides.With the advent of the quantum computer, the traditional number theory problems cannot effectively resist the solution of the quantum algorithm, and the difficult problems on the lattice make the complexity of the worst-case consistent with the average case. Therefore, as a lattice cryptosystem that can mitigate the quantum attack, it has attracted extensive attention. In 2012, Ding et al. [15] first constructed the KE protocol on the lattice. Ye et al. [16] first constructed the 3PAKE protocol on the lattice in 2013. With continuous research, in 2018, Yu et al. [17] constructed a new 3PAKE protocol by using the approximate smooth projection hash function on the lattice. They used the separable public-key encryption system, and a session key can be negotiated in only two rounds of communication, reducing the communication overhead. In the same year, Choi et al. [18] designed a new 3PAKE protocol; they introduced implicit server authentication based on Ding et al. so that it can still safely complete key negotiation under incomplete trusted servers. To improve the computational efficiency, Liu et al. [19] proposed a 3PAKE protocol based on RLWE. Their protocol only depends on the hardness of the RLWE problem; it has no additional primitive in the protocol designed and can resist undetectable online password attacks and offline password attacks. They struck a balance between efficiency and security. However, these symmetric 3PAKE protocols cannot resist server disclosure attack [20, 21]. In 2019, Zhang et al. [22] proposed a 3PAKE protocol based on the verification element under the standard model. To enhance the security of the protocol, it uses anonymous authentication for server and user authentication, which increases the computation cost. In 2021, Shu et al. [23] adopted the Peikert [24] error reconciliation mechanism and proposed a 3PAKE protocol based on the verification element on the ideal lattice; it reduces the space complexity, but it needs six rounds of communication to negotiate a session key and increases the communication overhead.It can see that the existing 3PAKE protocols cannot solve the server disclosure attack and reduce the communication overhead, and the authentication cannot be separated from the server. Therefore, we construct a 3PAKE protocol based on the verification element using the approximate smooth projection hash function [25] on the ideal lattice. Specifically speaking, the main contributions are as follows:(i)
Reducing space complexity: We use the public-key encryption system on the ideal lattice to reduce the size of the key and ciphertext. Because the ciphertext will be transmitted on the channel, shortening the ciphertext size can effectively improve the communication overhead efficiency.(ii)
It can simplify the protocol flow and effectively reduce the communication overhead. The proposed 3PAKE protocol adopts an asymmetric structure to separate the authentication from the server. Using the approximate smooth projection hash function on the ideal lattice, each user can only transmit information with the server once to generate the session key. However, in the existing 2PAKE and 3PAKE, it needs at least four messages sent by the user and the server to generate a session key.(iii)
Lower computational overhead: Most of the calculations are carried out on the polynomial ring in our protocol, so we can use the Fast Fourier Transform (FFT) algorithm to decrease the number of operations. In addition, the operation in the protocol can be parallelized by using the particularity of polynomialfx=xn+1 and module q≡1mod2n. Finally, our protocol can obtain the optimal implementation in the domain Zq, to significantly improve the operating rate.(iv)
Greater security: Not only does the proposed protocol depend on the server to distribute the session key, but also the user’s temporary private key determines part of the session key. Thus, the session key is private to the server, and it has forward security.The organization of this paper is as follows: we introduce the ideal lattice, RLWE problem and discrete Gaussian function, and other knowledge and give the specific structure of the public-key encryption algorithm and the approximate smooth hash function on the ideal lattice in Section2. Then, in Section 3, we introduce the security model of the proposed protocol. The complete structure and security proof of the protocol are given in Sections 4 and 5, respectively. Finally, in Section 6, we compare the security with the protocols in [2, 14, 17, 23], and the experimental results of the protocol under different initial parameters are given to show the computation and communication overhead of each stage of the protocol.


## 2. Preliminaries

### 2.1. Lattices

Definition 1.
LetB=b1,b2,⋅⋅⋅,bm∈Rn×m be a set of linearly independent vectors in Rn, and n and m are positive integers. The lattice generated by B is defined as ℒB=∑i=1mxibi:xi∈Zm, and B is the basis of ℒB. n and m are the dimension and rank of the lattice, respectively.Definition 2 (circular lattice).
Note that the once cyclic displacement of the vectora=a0,a1,⋯,an−1T is written as rota=an−1,a0,a1,⋯,,an−1T. For lattice ℒ, if ∀a∈ℒ, rota∈ℒ, then the lattice ℒ is called a cyclic lattice, record as Rota=a,rota,⋯,rotn−1a, and expressed as(1)Rota=a0an−1⋅⋅⋅a1a1a0⋅⋅⋅a2⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅an−1an−2⋅⋅⋅a0.Definition 3 (ideal lattice).
In 2006, Lyubashevsky et al. [26] extended the cyclic lattice and first proposed the ideal lattice. A lattice, having a special ring structure, is called an ideal lattice. q is a prime number and satisfies n=2kk>1, q≡1mod2n, fx=xn+1∈Zx, and fx is irreducible on the set of all rational numbers. R=Zx/fx is a ring of the integer polynomial fx; then, the elements in R are usually represented by integer polynomials of less degree n. If vector a∈R, the cyclic lattice ℒRota generated by a is an ideal of ring Zx/xn−1. Rq=Zqx/fx is an integer polynomial ring of modules fx and q, in which the elements can be represented by a polynomial of degree n−1 and the coefficients are expressed as 0,1,⋅⋅⋅,q−1. The ideal lattice lows down the space complexity by using a vector to represent an n dimensional lattice.Definition 4 (RLWE problem).
LetRq=R/qR be a quotient ring with a positive integer q as the module. We suppose n,m≥1, q≥2, an error distribution χβ which is a Gaussian distribution over Rq, where β is the noise parameter, satisfying β∈0,1 and nlogn≤βq≤q/4. For s∈Rq, it will output a,a⋅s+emodq∈Rq×Rq through sampling a⟵Rq and noise e⟵χβ.Definition 5 (decisionRLWEn,m,q,χβ problem).
Givenm independent uniformly distributed samples from Rq×Rq, there is no arbitrary probabilistic polynomial time (PPT) algorithm to distinguish whether the sample is chosen from RLWE distribution or uniform and random Rq×Rq.Definition 6 (searchRLWEn,m,q,χβ problem).
Randomly generate polynomiala∈Rq,s∈Rq, and e⟵χβ; they satisfy bi=ais+ei. Now, given multiple groups ai,bi, it is needed to find s.Theorem 1 (see [25]).
We supposen=2kk>1, q≡1mod2n, β∈0,1; they satisfy βq≥wlogn. Then, the O˜n/β-approximate SVP (shortest vector problem) can be reduced to R−DLEWn,m,q,χβ problem and R−SLEWn,m,q,χβ problem through quantum.


### 2.2. Discrete Gaussian Distribution

For anyσ>0, ρσ,cx=exp−πx−c2/σ2 is a Gaussian distribution function taking c∈R as the center and σ as the standard deviation. For any σ>0, with taking c∈Rm as the center and σ as the parameter, the discrete Gaussian distribution over lattice ℒ is defined as Dℒ,σ,cy=ρσ,cy/ρσ,cℒ, where y∈ℒ,ρσ,cℒ=∑x∈ℒρσ,cx. Note that c can be ignored not writing when c is 0.Theorem 2.
Gaussian distribution has the following characters: given the standard deviationσ and positive integer m, the following formulas hold:(2)Prx⟵Dσm:x>2σm<2−m,Prx⟵Dσ1:x>ωσlogm=2−wlogm.


### 2.3. Public-Key Cryptosystem Based on Ideal Lattice

Letn and m be positive integers; the security parameter is n; and q is an odd prime and satisfies q≥n2.5, q≡1mod2n, m≥6logq. A public-key cryptosystem, whose difficulty is based on the RLWE problem, is mainly composed of three algorithms.(i)
pk,sk⟵KeyGen1n1/2: this is a key generation algorithm, which inputs a security parameter n and outputs the public-private key pair pk,sk of the system(ii)
c1,c2⟵Encpk,msg: this is called an encapsulation algorithm. It takes as input a public key pk and a plaintext msg and outputs c=c1,c2(iii)
msg⟵Decsk,c1,c2: this is the decapsulation algorithm corresponding to the encapsulation algorithm; it takes as input the private key sk and ciphertext c1,c2 and outputs the corresponding plaintext m or “⊥”


### 2.4. Approximate Smooth Projection Hash Function

The smooth projective hash function is an important component in lattice-based cryptography. It was first proposed by Cramer and Shoup [27]. Later, to construct a PAKE protocol against quantum attack, Katz et al. [28] improved it and extended it to the construction of the PAKE protocol for efficient communication. In this paper, we adopt the approximate smooth projection hash (ASPH) function [25] based on an ideal lattice and further modify it according to the requirements of our protocol.We assumePKε=KeyGen,Enc,Dec, and it is a semantically secure public-key encryption system composed of functions on the lattice. Cpk represents the effective ciphertext space generated by public key pk encryption, and P is the plaintext space. We define X and language L∈X as follows:(3)X=c,m∣c∈Cpk;m∈P,L¯m=c,m∈X∣c=Encpkm,r,r∈0,1∗,L¯=∪m∈PL¯m,Lm=c,m∈X∣m=Decskc,L=∪m∈PLm.For any wordc∈L, the hash value of c∈L can be expressed in two ways: using the hash key hk and c or using the projection key hp and the evidence w corresponding to c∈L. The function ε−ASPH of a public-key encryption system corresponding to the public key pk on the lattice is composed of four algorithms, which can be expressed as ε−ASPH=HashKG,ProjKG,Hash,ProjH.(i)
HashKG1n: Given the security parameter n, the hash key generation algorithm outputs the hash key hk. Note H=Hhkhk∈HK represents the hash function cluster and HK is the hash key space.(ii)
ProjKGhk,pk: The projection key generation algorithm takes a hash key hk and a public key pk; it outputs the corresponding projection key hp∈HP, where HP is the projection key space.(iii)
Hashhk,L,c: When it inputs the hash key hk, language L¯ , and any word c∈L¯, the hash function outputs the hash value h.(iv)
ProjHhp,w: This is a projection hash function. Let the projection key hp and evidence w of word c∈L¯ be the input, and it outputs the projection hash value h′.εn correctness: for ∀c∉L¯ and corresponding evidence w, let εn∈0,1;Hama,b represents the hamming distance between a and b; and then PrHamHashhk,L,c,ProjHhp,w≥εn⋅n≤negln holds.Smoothness: for∀c∉L¯,hp=ProjKGhk,L,c,p⟵0,1r, the distributions of hp,Hashhk,L,c and hp,p are indistinguishable in the statistical distance. When n is the security parameter, εSASPHn is defined as a negligible upper bound of the statistical distance of the two distributions.


### 2.5. Specific Internal Structure

Combined with the content introduced in Section2.3, we construct a public-key encryption scheme on the ideal lattice and instantiate the approximate smooth projection hash function in the proposed protocol. The specific structure is as follows.


#### 2.5.1. Public-Key Encryption Scheme Based on RLWE Problem

(i)
pk,sk⟵KeyGen1n: Input a security parameter n ; then, it selects B0⟵Rrand runs the trapdoor function to get B1,T1⟵ideal−trapGen and B2,T2⟵ideal−trapGen, where B0,B1,B2∈Rqm, T1,T2∈Rm×m. It finally outputs a public/private key pair pk,sk of the system;(ii)
c1,c2⟵Encpk,msg: Let pk=B0,B1,B2 and a plaintext m∈Zqn be input; then, it selects r⟵Rr,e1,e2⟵Rr, the coefficients of e1 and e2 obey distribution χβ. It outputs c=c1,c2, where c1=B1⋅wa+e1modq,c2=B0⋅wa+B2⋅m+e2modq.(iii)
msg⟵Decsk,c1,c2: The private key sk and ciphertext c1,c2 are input; this decapsulation algorithm outputs the corresponding plaintext m or “⊥”.


#### 2.5.2. Approximate Smooth Projective Hash Function on Ideal Lattice

(1) Hash key: The hash key space is HK=Rqmn used in this protocol to ensure the approximate correctness of ε−ASPH function, and the coefficients of polynomial ejj≤n must obey Gaussian distribution χβ for any e1,e2,⋯,en∈HK.(2) Projection key: The projection key is generated by the hash key. For any e1,e2,⋯,en∈HK, the corresponding projection key is u1,u2,⋯,un=αe1,e2,⋯,en∈HP, and HP∈Zqnn is the projection key space. The specific calculation process is as follows:(4)uj=MapM−vejT⋅B^0j≤n.MapM−vej is the result of connecting the coefficients of polynomial ej∈Rqm, and it finally outputs a one-dimensional column vector composed of coefficients ej. After performing this type of operations on all ej∈e1,e2,⋯,en, the result of transpose operation will be point multiplied by B^0. B0⟵Rr is a public parameter and B^0 is generated by the following calculations:(5)B0=b01b02⋅⋅⋅b0m,B^0=rotb01Trotb02T⋅⋅⋅rotb0mT∈Zmn×n.(3) Hash functionℋ=Hhkhk∈HK: the hash key hk=e1,e2,⋅⋅⋅,en∈HK and x=c,m are used as input, and then perform the following calculations:zj=MapM−vejT⋅MapM−vc2−B2⋅m∈Zq, where m∈Zqn.Outputs:(6)bj′=0,ifzj′<q−121,ifzj′>q−12.(4) Projection functionProjHhphp∈HP: let the projection key hp=u1,u2,⋯,un and the evidence w of x∈L¯ be input, and run the following calculations:(7)zj′=ujw∈Zq.Outputs:(8)bj′=0,ifzj′<q−121,ifzj′>q−12.Theorem 3 (see [18]).
If the parametersm,n,q,β,ω satisfy q⋅wlogmn<r<ε/8⋅mn2β, then the above structure ℋ=Hhkhk∈HK is a ε−ASPH function.


#### 2.5.3. MAC Based on Key Hash Function

Message authentication mechanism can verify the identity of information source and integrity of data. Our protocol uses the MAC technology to authenticate information. The MAC based on the key hash function takes as input a key and a message and outputs an information summary by using the hash algorithm. By verifying the correctness of the information summary, the receiver can realize the identity authentication of the information source and the integrity authentication of the message.Using the correctness of approximate smooth projection hash function, the hash function value and projection function value between the user and the server can be input as a key; then, an information summary is generated by SHA-256. The specific structure is as follows:(9)Ρ=mackey,x=a⋅key+e+hxq−1/2modq.After receiving the MAC value, the receiver uses the keykey∗ to generate a new information summary:(10)Ρ∗=mackey∗,x=a⋅key∗+e∗+hxq−1/2modq.VerifyΡ∗−Ρ≤χβ; if it holds, it proves that the information is indeed sent by the claimant, is complete, and has not been modified.


## 2.1. Lattices

Definition 1.
LetB=b1,b2,⋅⋅⋅,bm∈Rn×m be a set of linearly independent vectors in Rn, and n and m are positive integers. The lattice generated by B is defined as ℒB=∑i=1mxibi:xi∈Zm, and B is the basis of ℒB. n and m are the dimension and rank of the lattice, respectively.Definition 2 (circular lattice).
Note that the once cyclic displacement of the vectora=a0,a1,⋯,an−1T is written as rota=an−1,a0,a1,⋯,,an−1T. For lattice ℒ, if ∀a∈ℒ, rota∈ℒ, then the lattice ℒ is called a cyclic lattice, record as Rota=a,rota,⋯,rotn−1a, and expressed as(1)Rota=a0an−1⋅⋅⋅a1a1a0⋅⋅⋅a2⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅an−1an−2⋅⋅⋅a0.Definition 3 (ideal lattice).
In 2006, Lyubashevsky et al. [26] extended the cyclic lattice and first proposed the ideal lattice. A lattice, having a special ring structure, is called an ideal lattice. q is a prime number and satisfies n=2kk>1, q≡1mod2n, fx=xn+1∈Zx, and fx is irreducible on the set of all rational numbers. R=Zx/fx is a ring of the integer polynomial fx; then, the elements in R are usually represented by integer polynomials of less degree n. If vector a∈R, the cyclic lattice ℒRota generated by a is an ideal of ring Zx/xn−1. Rq=Zqx/fx is an integer polynomial ring of modules fx and q, in which the elements can be represented by a polynomial of degree n−1 and the coefficients are expressed as 0,1,⋅⋅⋅,q−1. The ideal lattice lows down the space complexity by using a vector to represent an n dimensional lattice.Definition 4 (RLWE problem).
LetRq=R/qR be a quotient ring with a positive integer q as the module. We suppose n,m≥1, q≥2, an error distribution χβ which is a Gaussian distribution over Rq, where β is the noise parameter, satisfying β∈0,1 and nlogn≤βq≤q/4. For s∈Rq, it will output a,a⋅s+emodq∈Rq×Rq through sampling a⟵Rq and noise e⟵χβ.Definition 5 (decisionRLWEn,m,q,χβ problem).
Givenm independent uniformly distributed samples from Rq×Rq, there is no arbitrary probabilistic polynomial time (PPT) algorithm to distinguish whether the sample is chosen from RLWE distribution or uniform and random Rq×Rq.Definition 6 (searchRLWEn,m,q,χβ problem).
Randomly generate polynomiala∈Rq,s∈Rq, and e⟵χβ; they satisfy bi=ais+ei. Now, given multiple groups ai,bi, it is needed to find s.Theorem 1 (see [25]).
We supposen=2kk>1, q≡1mod2n, β∈0,1; they satisfy βq≥wlogn. Then, the O˜n/β-approximate SVP (shortest vector problem) can be reduced to R−DLEWn,m,q,χβ problem and R−SLEWn,m,q,χβ problem through quantum.


## 2.2. Discrete Gaussian Distribution

For anyσ>0, ρσ,cx=exp−πx−c2/σ2 is a Gaussian distribution function taking c∈R as the center and σ as the standard deviation. For any σ>0, with taking c∈Rm as the center and σ as the parameter, the discrete Gaussian distribution over lattice ℒ is defined as Dℒ,σ,cy=ρσ,cy/ρσ,cℒ, where y∈ℒ,ρσ,cℒ=∑x∈ℒρσ,cx. Note that c can be ignored not writing when c is 0.Theorem 2.
Gaussian distribution has the following characters: given the standard deviationσ and positive integer m, the following formulas hold:(2)Prx⟵Dσm:x>2σm<2−m,Prx⟵Dσ1:x>ωσlogm=2−wlogm.


## 2.3. Public-Key Cryptosystem Based on Ideal Lattice

Letn and m be positive integers; the security parameter is n; and q is an odd prime and satisfies q≥n2.5, q≡1mod2n, m≥6logq. A public-key cryptosystem, whose difficulty is based on the RLWE problem, is mainly composed of three algorithms.(i)
pk,sk⟵KeyGen1n1/2: this is a key generation algorithm, which inputs a security parameter n and outputs the public-private key pair pk,sk of the system(ii)
c1,c2⟵Encpk,msg: this is called an encapsulation algorithm. It takes as input a public key pk and a plaintext msg and outputs c=c1,c2(iii)
msg⟵Decsk,c1,c2: this is the decapsulation algorithm corresponding to the encapsulation algorithm; it takes as input the private key sk and ciphertext c1,c2 and outputs the corresponding plaintext m or “⊥”


## 2.4. Approximate Smooth Projection Hash Function

The smooth projective hash function is an important component in lattice-based cryptography. It was first proposed by Cramer and Shoup [27]. Later, to construct a PAKE protocol against quantum attack, Katz et al. [28] improved it and extended it to the construction of the PAKE protocol for efficient communication. In this paper, we adopt the approximate smooth projection hash (ASPH) function [25] based on an ideal lattice and further modify it according to the requirements of our protocol.We assumePKε=KeyGen,Enc,Dec, and it is a semantically secure public-key encryption system composed of functions on the lattice. Cpk represents the effective ciphertext space generated by public key pk encryption, and P is the plaintext space. We define X and language L∈X as follows:(3)X=c,m∣c∈Cpk;m∈P,L¯m=c,m∈X∣c=Encpkm,r,r∈0,1∗,L¯=∪m∈PL¯m,Lm=c,m∈X∣m=Decskc,L=∪m∈PLm.For any wordc∈L, the hash value of c∈L can be expressed in two ways: using the hash key hk and c or using the projection key hp and the evidence w corresponding to c∈L. The function ε−ASPH of a public-key encryption system corresponding to the public key pk on the lattice is composed of four algorithms, which can be expressed as ε−ASPH=HashKG,ProjKG,Hash,ProjH.(i)
HashKG1n: Given the security parameter n, the hash key generation algorithm outputs the hash key hk. Note H=Hhkhk∈HK represents the hash function cluster and HK is the hash key space.(ii)
ProjKGhk,pk: The projection key generation algorithm takes a hash key hk and a public key pk; it outputs the corresponding projection key hp∈HP, where HP is the projection key space.(iii)
Hashhk,L,c: When it inputs the hash key hk, language L¯ , and any word c∈L¯, the hash function outputs the hash value h.(iv)
ProjHhp,w: This is a projection hash function. Let the projection key hp and evidence w of word c∈L¯ be the input, and it outputs the projection hash value h′.εn correctness: for ∀c∉L¯ and corresponding evidence w, let εn∈0,1;Hama,b represents the hamming distance between a and b; and then PrHamHashhk,L,c,ProjHhp,w≥εn⋅n≤negln holds.Smoothness: for∀c∉L¯,hp=ProjKGhk,L,c,p⟵0,1r, the distributions of hp,Hashhk,L,c and hp,p are indistinguishable in the statistical distance. When n is the security parameter, εSASPHn is defined as a negligible upper bound of the statistical distance of the two distributions.


## 2.5. Specific Internal Structure

Combined with the content introduced in Section2.3, we construct a public-key encryption scheme on the ideal lattice and instantiate the approximate smooth projection hash function in the proposed protocol. The specific structure is as follows.


### 2.5.1. Public-Key Encryption Scheme Based on RLWE Problem

(i)
pk,sk⟵KeyGen1n: Input a security parameter n ; then, it selects B0⟵Rrand runs the trapdoor function to get B1,T1⟵ideal−trapGen and B2,T2⟵ideal−trapGen, where B0,B1,B2∈Rqm, T1,T2∈Rm×m. It finally outputs a public/private key pair pk,sk of the system;(ii)
c1,c2⟵Encpk,msg: Let pk=B0,B1,B2 and a plaintext m∈Zqn be input; then, it selects r⟵Rr,e1,e2⟵Rr, the coefficients of e1 and e2 obey distribution χβ. It outputs c=c1,c2, where c1=B1⋅wa+e1modq,c2=B0⋅wa+B2⋅m+e2modq.(iii)
msg⟵Decsk,c1,c2: The private key sk and ciphertext c1,c2 are input; this decapsulation algorithm outputs the corresponding plaintext m or “⊥”.


### 2.5.2. Approximate Smooth Projective Hash Function on Ideal Lattice

(1) Hash key: The hash key space is HK=Rqmn used in this protocol to ensure the approximate correctness of ε−ASPH function, and the coefficients of polynomial ejj≤n must obey Gaussian distribution χβ for any e1,e2,⋯,en∈HK.(2) Projection key: The projection key is generated by the hash key. For any e1,e2,⋯,en∈HK, the corresponding projection key is u1,u2,⋯,un=αe1,e2,⋯,en∈HP, and HP∈Zqnn is the projection key space. The specific calculation process is as follows:(4)uj=MapM−vejT⋅B^0j≤n.MapM−vej is the result of connecting the coefficients of polynomial ej∈Rqm, and it finally outputs a one-dimensional column vector composed of coefficients ej. After performing this type of operations on all ej∈e1,e2,⋯,en, the result of transpose operation will be point multiplied by B^0. B0⟵Rr is a public parameter and B^0 is generated by the following calculations:(5)B0=b01b02⋅⋅⋅b0m,B^0=rotb01Trotb02T⋅⋅⋅rotb0mT∈Zmn×n.(3) Hash functionℋ=Hhkhk∈HK: the hash key hk=e1,e2,⋅⋅⋅,en∈HK and x=c,m are used as input, and then perform the following calculations:zj=MapM−vejT⋅MapM−vc2−B2⋅m∈Zq, where m∈Zqn.Outputs:(6)bj′=0,ifzj′<q−121,ifzj′>q−12.(4) Projection functionProjHhphp∈HP: let the projection key hp=u1,u2,⋯,un and the evidence w of x∈L¯ be input, and run the following calculations:(7)zj′=ujw∈Zq.Outputs:(8)bj′=0,ifzj′<q−121,ifzj′>q−12.Theorem 3 (see [18]).
If the parametersm,n,q,β,ω satisfy q⋅wlogmn<r<ε/8⋅mn2β, then the above structure ℋ=Hhkhk∈HK is a ε−ASPH function.


### 2.5.3. MAC Based on Key Hash Function

Message authentication mechanism can verify the identity of information source and integrity of data. Our protocol uses the MAC technology to authenticate information. The MAC based on the key hash function takes as input a key and a message and outputs an information summary by using the hash algorithm. By verifying the correctness of the information summary, the receiver can realize the identity authentication of the information source and the integrity authentication of the message.Using the correctness of approximate smooth projection hash function, the hash function value and projection function value between the user and the server can be input as a key; then, an information summary is generated by SHA-256. The specific structure is as follows:(9)Ρ=mackey,x=a⋅key+e+hxq−1/2modq.After receiving the MAC value, the receiver uses the keykey∗ to generate a new information summary:(10)Ρ∗=mackey∗,x=a⋅key∗+e∗+hxq−1/2modq.VerifyΡ∗−Ρ≤χβ; if it holds, it proves that the information is indeed sent by the claimant, is complete, and has not been modified.


## 2.5.1. Public-Key Encryption Scheme Based on RLWE Problem

(i)
pk,sk⟵KeyGen1n: Input a security parameter n ; then, it selects B0⟵Rrand runs the trapdoor function to get B1,T1⟵ideal−trapGen and B2,T2⟵ideal−trapGen, where B0,B1,B2∈Rqm, T1,T2∈Rm×m. It finally outputs a public/private key pair pk,sk of the system;(ii)
c1,c2⟵Encpk,msg: Let pk=B0,B1,B2 and a plaintext m∈Zqn be input; then, it selects r⟵Rr,e1,e2⟵Rr, the coefficients of e1 and e2 obey distribution χβ. It outputs c=c1,c2, where c1=B1⋅wa+e1modq,c2=B0⋅wa+B2⋅m+e2modq.(iii)
msg⟵Decsk,c1,c2: The private key sk and ciphertext c1,c2 are input; this decapsulation algorithm outputs the corresponding plaintext m or “⊥”.


## 2.5.2. Approximate Smooth Projective Hash Function on Ideal Lattice

(1) Hash key: The hash key space is HK=Rqmn used in this protocol to ensure the approximate correctness of ε−ASPH function, and the coefficients of polynomial ejj≤n must obey Gaussian distribution χβ for any e1,e2,⋯,en∈HK.(2) Projection key: The projection key is generated by the hash key. For any e1,e2,⋯,en∈HK, the corresponding projection key is u1,u2,⋯,un=αe1,e2,⋯,en∈HP, and HP∈Zqnn is the projection key space. The specific calculation process is as follows:(4)uj=MapM−vejT⋅B^0j≤n.MapM−vej is the result of connecting the coefficients of polynomial ej∈Rqm, and it finally outputs a one-dimensional column vector composed of coefficients ej. After performing this type of operations on all ej∈e1,e2,⋯,en, the result of transpose operation will be point multiplied by B^0. B0⟵Rr is a public parameter and B^0 is generated by the following calculations:(5)B0=b01b02⋅⋅⋅b0m,B^0=rotb01Trotb02T⋅⋅⋅rotb0mT∈Zmn×n.(3) Hash functionℋ=Hhkhk∈HK: the hash key hk=e1,e2,⋅⋅⋅,en∈HK and x=c,m are used as input, and then perform the following calculations:zj=MapM−vejT⋅MapM−vc2−B2⋅m∈Zq, where m∈Zqn.Outputs:(6)bj′=0,ifzj′<q−121,ifzj′>q−12.(4) Projection functionProjHhphp∈HP: let the projection key hp=u1,u2,⋯,un and the evidence w of x∈L¯ be input, and run the following calculations:(7)zj′=ujw∈Zq.Outputs:(8)bj′=0,ifzj′<q−121,ifzj′>q−12.Theorem 3 (see [18]).
If the parametersm,n,q,β,ω satisfy q⋅wlogmn<r<ε/8⋅mn2β, then the above structure ℋ=Hhkhk∈HK is a ε−ASPH function.


## 2.5.3. MAC Based on Key Hash Function

Message authentication mechanism can verify the identity of information source and integrity of data. Our protocol uses the MAC technology to authenticate information. The MAC based on the key hash function takes as input a key and a message and outputs an information summary by using the hash algorithm. By verifying the correctness of the information summary, the receiver can realize the identity authentication of the information source and the integrity authentication of the message.Using the correctness of approximate smooth projection hash function, the hash function value and projection function value between the user and the server can be input as a key; then, an information summary is generated by SHA-256. The specific structure is as follows:(9)Ρ=mackey,x=a⋅key+e+hxq−1/2modq.After receiving the MAC value, the receiver uses the keykey∗ to generate a new information summary:(10)Ρ∗=mackey∗,x=a⋅key∗+e∗+hxq−1/2modq.VerifyΡ∗−Ρ≤χβ; if it holds, it proves that the information is indeed sent by the claimant, is complete, and has not been modified.


## 3. Security Model

### 3.1. Parties of the Protocol

3PAKE protocol participants include users and servers.U represents a user collection, C∈U is an honest user, and V∈U is a malicious user. S represents a server collection; we usually assume that the server collection has only one element, that is, S=S.


### 3.2. Long-Term Key

The long-term key in the protocol is the user’s password; we assume the length of the nonempty dictionaryD is l, and the password pwU of each user U∈U is randomly selected from D. The server S has a password list pwS=<pwSU>U∈U of all users, where pwSU=saltU,VU is composed of the user’s salt value saltU and the verification element VU produced by the password pwU and salt value saltU.


### 3.3. Security Model of 3PAKE Protocol

In the 3PAKE protocol, each participant can execute multiple sessions at the same time. LetUi represent the i−th instance of user U and let Sj represent the j−th instance of the server S. Here, an instance represents a session. We suppose there is a PPT algorithm adversary A which knows all the malicious user’s password set pwA=<pwε>ε∈V and also can control the communication channel among all users. Adversary can obtain the specific abilities by sending the following queries.(i)
ExecuteU1a,Sj,U2b: This query gives A the ability to wiretap channels. After activating instances U1a,Sj, and U2b, A will get all the information transmitted between the user and the server.(ii)
SendUu,msg: This query simulates A’s active attack on the user instance. The adversary A selects the message msg and sends it to the user instance Uu. Finally, A obtains the reply of Uu to the message msg.(iii)
SendSj,msg: This query helps A to actively attack the server instance. The adversary A selects the message msg and sends it to the server instance Sj. Finally, the adversary A obtains the reply of the instance Sj to the message msg.(iv)
RevealUa: This query simulates session key is lost or leaked. After the adversary A executes this query, A can obtain all session keys skUa of the instance Ua.(v)
CorruptU: The execution of this query simulates the adversary ’s corruption attack on user U. After A executes this query, it will obtain the user’s password pwU.(vi)
CorruptS: Adversary A sends this query to launch a corruption attack on the server S. After A executes this query, it will obtain the password list pwS=<pwSU>U∈U=<saltU,VU>U∈U of the server S.(vii)
TestUa: When this query is executed, it is valid only when the user instance Ua is fresh. We throw a random coin b∈0,1. If b=1, it will return the real session key SKab to the adversary A; otherwise, it will return a random bit string with the same length as the session key to the adversary A.


### 3.4. Accepted State

ssidi represents the session serial number of the user instance Ui and pidUi represents the intended communicator of Ui. If an instance executes successfully and generates the corresponding session key, we say it has been accepted.


### 3.5. Matching Session

If (1) the instancesU1a and U2b all have been accepted; (2) U1a and U2b have the same session serial number ssid; and (3) U1a and U2b are mutually intended communicators, the instances U1a and U2b are a matching session.


### 3.6. Fresh session

If the instanceUi has been accepted and the adversary A has not asked a Reveal query to Ui, as well as the adversary A has not asked a Corrupt query to the user U and server S before instance Ui is accepted, then Ui is fresh.


### 3.7. Definition of Security

During executing a 3PAKE protocol, any PPT adversaryA can ask Execute, Send, Reveal, and Corrupt queries in any order for many times. Note that Test query can only be asked once. At the end of the game, the adversary A outputs his guess b′ about b. If b′=b holds, it means that adversary A has broken the protocol. Let D be the space of user password and let P represent the protocol which A attacks. The advantage of A breaking the 3PAKE protocol is AdvP,DakeA=2prSuccP,DakeA−1, where SuccP,DakeA represents the success probability of breaking the protocol.


## 3.1. Parties of the Protocol

3PAKE protocol participants include users and servers.U represents a user collection, C∈U is an honest user, and V∈U is a malicious user. S represents a server collection; we usually assume that the server collection has only one element, that is, S=S.


## 3.2. Long-Term Key

The long-term key in the protocol is the user’s password; we assume the length of the nonempty dictionaryD is l, and the password pwU of each user U∈U is randomly selected from D. The server S has a password list pwS=<pwSU>U∈U of all users, where pwSU=saltU,VU is composed of the user’s salt value saltU and the verification element VU produced by the password pwU and salt value saltU.


## 3.3. Security Model of 3PAKE Protocol

In the 3PAKE protocol, each participant can execute multiple sessions at the same time. LetUi represent the i−th instance of user U and let Sj represent the j−th instance of the server S. Here, an instance represents a session. We suppose there is a PPT algorithm adversary A which knows all the malicious user’s password set pwA=<pwε>ε∈V and also can control the communication channel among all users. Adversary can obtain the specific abilities by sending the following queries.(i)
ExecuteU1a,Sj,U2b: This query gives A the ability to wiretap channels. After activating instances U1a,Sj, and U2b, A will get all the information transmitted between the user and the server.(ii)
SendUu,msg: This query simulates A’s active attack on the user instance. The adversary A selects the message msg and sends it to the user instance Uu. Finally, A obtains the reply of Uu to the message msg.(iii)
SendSj,msg: This query helps A to actively attack the server instance. The adversary A selects the message msg and sends it to the server instance Sj. Finally, the adversary A obtains the reply of the instance Sj to the message msg.(iv)
RevealUa: This query simulates session key is lost or leaked. After the adversary A executes this query, A can obtain all session keys skUa of the instance Ua.(v)
CorruptU: The execution of this query simulates the adversary ’s corruption attack on user U. After A executes this query, it will obtain the user’s password pwU.(vi)
CorruptS: Adversary A sends this query to launch a corruption attack on the server S. After A executes this query, it will obtain the password list pwS=<pwSU>U∈U=<saltU,VU>U∈U of the server S.(vii)
TestUa: When this query is executed, it is valid only when the user instance Ua is fresh. We throw a random coin b∈0,1. If b=1, it will return the real session key SKab to the adversary A; otherwise, it will return a random bit string with the same length as the session key to the adversary A.


## 3.4. Accepted State

ssidi represents the session serial number of the user instance Ui and pidUi represents the intended communicator of Ui. If an instance executes successfully and generates the corresponding session key, we say it has been accepted.


## 3.5. Matching Session

If (1) the instancesU1a and U2b all have been accepted; (2) U1a and U2b have the same session serial number ssid; and (3) U1a and U2b are mutually intended communicators, the instances U1a and U2b are a matching session.


## 3.6. Fresh session

If the instanceUi has been accepted and the adversary A has not asked a Reveal query to Ui, as well as the adversary A has not asked a Corrupt query to the user U and server S before instance Ui is accepted, then Ui is fresh.


## 3.7. Definition of Security

During executing a 3PAKE protocol, any PPT adversaryA can ask Execute, Send, Reveal, and Corrupt queries in any order for many times. Note that Test query can only be asked once. At the end of the game, the adversary A outputs his guess b′ about b. If b′=b holds, it means that adversary A has broken the protocol. Let D be the space of user password and let P represent the protocol which A attacks. The advantage of A breaking the 3PAKE protocol is AdvP,DakeA=2prSuccP,DakeA−1, where SuccP,DakeA represents the success probability of breaking the protocol.


## 4. Construction of Our Protocol

When users make a key agreement with the help of the server, they need to register with the server first, let the server store the verification element corresponding to the user password, and ensure that the server cannot recover the plaintext password through the verification element.


### 4.1. System Initialization Phase

Running key generation algorithmpk,sk⟵KeyGen1n: it takes as input a secure parameter n, then selects B0⟵Rr, and runs trapdoor generation algorithm to get B1,T1⟵ideal−trapGen and B2,T2⟵ideal−trapGen. It finally outputs pk=B0,B1,B2 as a public key and sk=T1,T2 as a secret key. Note that keep private key sk=T1,T2 secret, and Param=B0,B1,B2 public.


### 4.2. User Registration

When users join the system for the first time, they need to register. The specific operations are as follows:(i)
UserUi chooses identification IDi and password pwi, selects a salt value salti randomly, and uses SHA−256 to generate seeds of two pseudo-random number generators (PRNG): one is seed1=SHA−256salti||SHA−256IDi||pwi and the other is seed2=SHA−256seed1.(ii)
Input the seeds of the pseudorandom number generator, then selectsi,ei from the discrete Gaussian distribution χβ, note that si and ei are polynomials whose coefficients obey χβ, choose a⟵Rr, calculate the verification element vi=a⋅si+ei∈Rq corresponding to the user Ui, and let a be public and the other secret.(iii)
UserUi sends a,IDi,vi to the server S through the secure channel. If a,IDi,vi is not in the database list Q, a,IDi,vi will be automatically added to Q. Otherwise, it will send a new registration message to the user. After the user Ui successfully executes the registration phase, seed1,seed2,si,ei,vi needs to be deleted from the local memory and pwi,salti is stored locally.


### 4.3. Mutual Authentication and Key Agreement Phase

This stage is shown in Figure1; the user Ua negotiates a session key SKab with the user Ub. When user Ui has a session, Ui will automatically generate a session IDssidi, and ssidi exists in increasing form. At the same time, after each session is successfully executed, the server will record the user session serial number in the local database list to effectively prevent message replay.(iii)
The serverS first looks up the verification element corresponding to Ua in the local list. If it cannot be found, exit. Otherwise, S checks the Ua’s session serial number ssida. If ssida does not meet the requirements, exit. Finally, ma and ha are recovered according to the local information, and the Ua’s identity authentication is realized by verifying the effectiveness of the ciphertext Ca1,Ca2, the integrity verification of the message xa is realized by verifying the effectiveness of φa. If they are all valid, the server S selects δsa⟵0,1r, δsb⟵0,1r, e4,e5⟵Rr, wb⟵Rr randomly, and e4 and e5 are polynomials whose coefficients obey discrete distribution χβ. The hash key hkb=HashKG1n of user Ub is randomly selected, and S calculates the projection key hpb=ProjKGpk,hkb, projection function value hb=ProjHhpb,wb and mb=IDb||IDa||S||hkb||ssidb||vb||1⋅⋅⋅ and gets ciphertext Cb1=B1⋅wb+e4modq and Cb2=B0⋅wb+B2⋅mb+e5modq for massage mb. Next, S uses random values δsa and δsb to calculate ca=Fδsb1⊕Fδsa3, cb=Fδsa1⊕Fδb3, Δa=ha⊕ECCδsa, Δb=hb⊕ECCδsb. Finally, the projection function value hb is used to regenerate the verifiable MAC value φa′=MAChb,IDaIDbS‖xa for xa and S sends <ca,Δa,ha,IDa,IDb,S,cb,Δb,hks,Cs=Cs1,Cs2,xa,φa′> to user Ub.(iii)
After receiving the message sent byS, user Ub can recover verification element vb′=a⋅sb+eb, message mb′=IDbIDaShkbssidbvb′1⋯, and hash function value hb′=Hashpk,hkb,Cb1,mb′ by using pwb and saltb stored locally. Using the correctness of the approximate smooth projection hash function, the user can verify whether φa′ is correct by hb′. After passing verification, Ub selects e6,e7⟵Rr and skb′⟵Rr randomly and uniformly, the coefficients of e6 and e7 obey Gaussian distribution χβ, and skb′ is regarded as the temporary private key. Then, Ub calculates xb=a⋅skb′+2e6, kb=x⋅skb′+2e7, σb=gkb, and ρb=Extrkb,σb. According to the hash function value hb′, the decoding algorithm ECC−1 of the error correction code and Δb, Ubcan calculate δsb=ECC−1hb′⊕Δb and generate the session key SKba=cb⊕Fδsb1⊕Fδsb3⊕σb⊕ρb, with the user Ua, and the verifiable MAC value φb=MACha,IDaIDbS‖xb is generated by using ha. Finally, ca,Δa,xb,IDa,IDb,S,σb,φb,ssidb are sent to user Ua.(iv)
Ua first checks Ub’s session serial number ssidb after receiving the message. If it does not meet the requirements, exit. Otherwise, Ua calculates the corresponding projection key hpa=ProjKGpk,hka according to the hash key hka selected which is stored locally; then, the projection function value ha′=ProjHhpa,wa is calculated according to the projection key hpa and the evidence wa that can prove the ciphertext. Using the correctness of the approximate smooth projection hash function, the user can verify whether φb is correct by ha′. If it passes the verification, Ua will select e8⟵Rr randomly. And according to the projection function ha′, the decoding algorithm ECC−1 of the error correction code, and Δa, Ua calculates δsa=ECC−1ha′⊕Δa, ka=y⋅ska′+2e8, and ρa=Extrka,σb. Finally, Ua generates the session key SKab=ca⊕Fδsa1⊕Fδsa3⊕σb⊕ρa with the user Ub.Figure 1
RLWE-3VAKE mutual authentication and key agreement phase.


### 4.4. Correctness

When usersUa, Ub and server S run the protocol honestly and if a valid session key SKab=SKba can be generated with overwhelming probability, it is said that a 3PAKE protocol based on verification element is correct.Taking userUa as an example, Ua encrypts the verification element corresponding to his password to obtain an effective ciphertext Ca1,Ca2, the server S uses the ciphertext and hash key sent by the user to calculate the hash function value, and the user uses the projection key to obtain a projection function value. According to the approximate correctness of the function ε−ASPH, the probability that the hamming distance of ha is ε greater than ha′ is negligible. The error correction code defined in this paper can correct error 2ε. Finally, users Ua and Ub can obtain δsa and δsb which is same as the server, respectively. Meanwhile, user Ua can use(11)ρa=Extrka,σb=ka+σbq−12modqmod2=kb+2ε+σbq−12modqmod2=kb+σbq−12modqmod2+2εmod2=kb+σbq−12modqmod2=Extrkb,σb=ρb,to calculateρa.


## 4.1. System Initialization Phase

Running key generation algorithmpk,sk⟵KeyGen1n: it takes as input a secure parameter n, then selects B0⟵Rr, and runs trapdoor generation algorithm to get B1,T1⟵ideal−trapGen and B2,T2⟵ideal−trapGen. It finally outputs pk=B0,B1,B2 as a public key and sk=T1,T2 as a secret key. Note that keep private key sk=T1,T2 secret, and Param=B0,B1,B2 public.


## 4.2. User Registration

When users join the system for the first time, they need to register. The specific operations are as follows:(i)
UserUi chooses identification IDi and password pwi, selects a salt value salti randomly, and uses SHA−256 to generate seeds of two pseudo-random number generators (PRNG): one is seed1=SHA−256salti||SHA−256IDi||pwi and the other is seed2=SHA−256seed1.(ii)
Input the seeds of the pseudorandom number generator, then selectsi,ei from the discrete Gaussian distribution χβ, note that si and ei are polynomials whose coefficients obey χβ, choose a⟵Rr, calculate the verification element vi=a⋅si+ei∈Rq corresponding to the user Ui, and let a be public and the other secret.(iii)
UserUi sends a,IDi,vi to the server S through the secure channel. If a,IDi,vi is not in the database list Q, a,IDi,vi will be automatically added to Q. Otherwise, it will send a new registration message to the user. After the user Ui successfully executes the registration phase, seed1,seed2,si,ei,vi needs to be deleted from the local memory and pwi,salti is stored locally.


## 4.3. Mutual Authentication and Key Agreement Phase

This stage is shown in Figure1; the user Ua negotiates a session key SKab with the user Ub. When user Ui has a session, Ui will automatically generate a session IDssidi, and ssidi exists in increasing form. At the same time, after each session is successfully executed, the server will record the user session serial number in the local database list to effectively prevent message replay.(iii)
The serverS first looks up the verification element corresponding to Ua in the local list. If it cannot be found, exit. Otherwise, S checks the Ua’s session serial number ssida. If ssida does not meet the requirements, exit. Finally, ma and ha are recovered according to the local information, and the Ua’s identity authentication is realized by verifying the effectiveness of the ciphertext Ca1,Ca2, the integrity verification of the message xa is realized by verifying the effectiveness of φa. If they are all valid, the server S selects δsa⟵0,1r, δsb⟵0,1r, e4,e5⟵Rr, wb⟵Rr randomly, and e4 and e5 are polynomials whose coefficients obey discrete distribution χβ. The hash key hkb=HashKG1n of user Ub is randomly selected, and S calculates the projection key hpb=ProjKGpk,hkb, projection function value hb=ProjHhpb,wb and mb=IDb||IDa||S||hkb||ssidb||vb||1⋅⋅⋅ and gets ciphertext Cb1=B1⋅wb+e4modq and Cb2=B0⋅wb+B2⋅mb+e5modq for massage mb. Next, S uses random values δsa and δsb to calculate ca=Fδsb1⊕Fδsa3, cb=Fδsa1⊕Fδb3, Δa=ha⊕ECCδsa, Δb=hb⊕ECCδsb. Finally, the projection function value hb is used to regenerate the verifiable MAC value φa′=MAChb,IDaIDbS‖xa for xa and S sends <ca,Δa,ha,IDa,IDb,S,cb,Δb,hks,Cs=Cs1,Cs2,xa,φa′> to user Ub.(iii)
After receiving the message sent byS, user Ub can recover verification element vb′=a⋅sb+eb, message mb′=IDbIDaShkbssidbvb′1⋯, and hash function value hb′=Hashpk,hkb,Cb1,mb′ by using pwb and saltb stored locally. Using the correctness of the approximate smooth projection hash function, the user can verify whether φa′ is correct by hb′. After passing verification, Ub selects e6,e7⟵Rr and skb′⟵Rr randomly and uniformly, the coefficients of e6 and e7 obey Gaussian distribution χβ, and skb′ is regarded as the temporary private key. Then, Ub calculates xb=a⋅skb′+2e6, kb=x⋅skb′+2e7, σb=gkb, and ρb=Extrkb,σb. According to the hash function value hb′, the decoding algorithm ECC−1 of the error correction code and Δb, Ubcan calculate δsb=ECC−1hb′⊕Δb and generate the session key SKba=cb⊕Fδsb1⊕Fδsb3⊕σb⊕ρb, with the user Ua, and the verifiable MAC value φb=MACha,IDaIDbS‖xb is generated by using ha. Finally, ca,Δa,xb,IDa,IDb,S,σb,φb,ssidb are sent to user Ua.(iv)
Ua first checks Ub’s session serial number ssidb after receiving the message. If it does not meet the requirements, exit. Otherwise, Ua calculates the corresponding projection key hpa=ProjKGpk,hka according to the hash key hka selected which is stored locally; then, the projection function value ha′=ProjHhpa,wa is calculated according to the projection key hpa and the evidence wa that can prove the ciphertext. Using the correctness of the approximate smooth projection hash function, the user can verify whether φb is correct by ha′. If it passes the verification, Ua will select e8⟵Rr randomly. And according to the projection function ha′, the decoding algorithm ECC−1 of the error correction code, and Δa, Ua calculates δsa=ECC−1ha′⊕Δa, ka=y⋅ska′+2e8, and ρa=Extrka,σb. Finally, Ua generates the session key SKab=ca⊕Fδsa1⊕Fδsa3⊕σb⊕ρa with the user Ub.Figure 1
RLWE-3VAKE mutual authentication and key agreement phase.


## 4.4. Correctness

When usersUa, Ub and server S run the protocol honestly and if a valid session key SKab=SKba can be generated with overwhelming probability, it is said that a 3PAKE protocol based on verification element is correct.Taking userUa as an example, Ua encrypts the verification element corresponding to his password to obtain an effective ciphertext Ca1,Ca2, the server S uses the ciphertext and hash key sent by the user to calculate the hash function value, and the user uses the projection key to obtain a projection function value. According to the approximate correctness of the function ε−ASPH, the probability that the hamming distance of ha is ε greater than ha′ is negligible. The error correction code defined in this paper can correct error 2ε. Finally, users Ua and Ub can obtain δsa and δsb which is same as the server, respectively. Meanwhile, user Ua can use(11)ρa=Extrka,σb=ka+σbq−12modqmod2=kb+2ε+σbq−12modqmod2=kb+σbq−12modqmod2+2εmod2=kb+σbq−12modqmod2=Extrkb,σb=ρb,to calculateρa.


## 5. Security Analysis

A 3PAKE protocol based on the verification element can be widely used on the premise of ensuring its correctness and security. This section proves the security of the protocol under the security model given in Section3. With that, we prove the forward security of the protocol and the privacy of the session key to the server.


### 5.1. Security Proof

Theorem 4.
If the public-key encryption systemPKE=keyGen,Enc,Dec based on the ideal lattice is CCA secure ε−ASPH function cluster corresponding to the public key system PKE=keyGen,Enc,Dec.ECC:0,1n⟶0,1k is the coding algorithm of error correction code. It can correct the 2ε error partthrough the decoding algorithm ECC−1:0,1k⟶0,1n corresponding to the coding algorithm ECC. F=Fδ:δ∈0,1kk∈ℕ is a pseudo-random function cluster; and then, this protocol is secure.Proof.
Assuming that any PPT attacker can makeqexe,qsend,qre,qco for Execute, Send, Reveal and Corrupt inquiries at most, the total running time is t at most. The advantage of the attacker is simulated by constructing a series of games named G0,G1,⋅⋅⋅,G8. In this series of games, A’s advantage of breaking the protocol gradually increases. Finally, as long as the advantage of the attacker’s success in the game G8 is negligible, A cannot break the protocol. The advantage of A breaking the protocol is defined as AdvP,DakeA=2prSuccP,DakeA−1.GameG0. This game corresponds to the real attack in the security model. For all kinds of queries sent by the attacker A, A may get honest answers. At this time, the advantage of the attacker A is AdvP,DakeA=Adv0A.GameG1. In this game, we modify the simulation model of Execute inquiry and replace the answer generated by the user using ProjH with the corresponding Hash calculation in each Execute inquiry, such as hU′'=Hashpk,hku,Cu2,mu′, u∈A,B.Proof.
Due to the approximate correctness ofε−ASPHand the coding algorithm E:0,1n⟶0,1k of the error correction code, A has the same advantages in the game G1; it can be denoted by Adv1A=Adv0A.GameG2. During the simulated Execute query, for any user u∈A,B, the only difference between game G2 and game G1 is that the ciphertext Cu in the message sent by the user for the first time is replaced with the ciphertext of encrypting the virtual verification element VT0 (i.e., the verification element that does not belong to the password space D). Finally, we can see that the advantage difference of A between game G2 and game G1 can be ignored. We recorded it as Adv2A−Adv1A<2qexe⋅AdvPKEaket+Oqsend+qexe.Proof.
Taking the public keypk as a public parameter, ℬ is the attacker of the public-key encryption system so that ℬ can answer the queries of attackerA. ℬ sends vu′,VT0 to their challenger as the challenge plaintext and replaces the ciphertext Cu with the received challenge ciphertext Cu′ in the Execute query. Then, A makes their guess b′ about the random bit b in the Test query. If b′=b, the guess is successful, and ℬ outputs 1. Otherwise, ℬ outputs 0. According to the CCA security of the public-key cryptosystem on the ideal lattice, the attacker ℬ cannot distinguish two ciphertexts with negligible advantage. Therefore, the ciphertext in the qexeExecute query sent by the attacker can be replaced with the encrypted ciphertext of the virtual verification element VT0. Considering that the attacker A only needs additional calculation time during Execute and Send query in the whole process of simulating the protocol and does not need additional calculation time during other queries because it only needs to return the corresponding state, it only needs t+Oqsend+qexe at most calculation time in the whole process.GameG3. In this game, hu=Hashpk,hku,Cu2,mu′ and u∈A,B in the Execute query will be replaced by a randomly selected bit string of equal length. Let εASPHn be a negligible upper bound of the statistical distance between the outputs of inputting nonverbal element and the uniform random distribution. Here, Adv3A−Adv2A<2qexe⋅εSAPHn.Proof.
It is known that the ciphertexts are replaced by the encryption results of the virtual verification element in gameG2, so the input of the approximate smooth projection hash function is a nonverbal element. According to the smoothness of the function, the statistical distance between the outputs of the inputting nonverbal element and the uniform random distribution can be ignored.GameG4. In the Execute query, sku′,xu will be replaced by a randomly selected bit string of equal length, where u∈A,B. Here, Adv4A=Adv3A.Proof.
It is known that the ciphertext in gameG2 has been replaced by the encryption of the virtual verification element, and hu will be replaced by a random bit string with an equal length in the game G3. Now, xu,φu is random. According to the decision RLWEn,m,q,χβ problem, the advantages of game G4 and game G3 are the same.GameG5. Game G5 modifies the pseudorandom function in Execute query, and the others remain unchanged, the same as game G4. δsa and δsb are still randomly selected, but the values of Fδsa1, Fδa3, Fδb1, and Fδsb1 are replaced with independent and random numbers. Adv5A=Adv4A holds at this time because the pseudorandom function Fδsu is hidden for the user.Proof.
The user and the server have the sameΔa, and according to the correctness of the decoding algorithm E−1:0,1k⟶0,1n of the error correction code, the user will get the same δsa as the server.
The above is to modify theExecute query. It can be known from the content of game G1 to game G5 that all messages are replaced with random values independent of the user’s password, and the attacker cannot obtain any information related to the user’s password in the Oracle query so that the communication parties can finally negotiate a completely random session key.
Next, we modify theSend query, SendSj,msg1 means sending message msg1 to the server instance Sj, and SendUu,msg2 indicates sending message msg2 to the user instance Uu. Only when the server instance Sj receives a correct and valid message msg1, it can return the corresponding valid message msg2 to the attacker. Note that Send0Uu,Sj represents that the user instance Uu and the server instance Sj are activated and start to execute the protocol. In addition, the simulator ℳ should record the private key sk corresponding to the public key pk in the key generation phase.GameG6. For SendS,<IDu′,IDu,S,hku′,Cu1',Cu2',ssidu′> query received from the server, where u∈A,B, if there is no corresponding verification element vu′ in the local password list IDu′ of the server, the emulator ℳ rejects the message, or if ssidu′ is smaller than the value of the previous session serial number saved by the server, the message is rejected. Finally, ℳ checks whether the ciphertext Cu1',Cu2' is valid. If not, ℳ continues to reject the message. Otherwise, the emulator ℳ decrypts the ciphertext Cu1',Cu2' with the corresponding private key sk and gets the user’s verification element. If vu∗=vu′, it is considered that the attacker has broken the protocol and ends the game simulation. The modification of the above game obviously increases the probability of an attacker’s success, so Adv5A≤Adv6A+2qsend⋅εSAPHn holds.Proof.
IfCu1',Cu2' is a valid ciphertext, the simulator ℳ can successfully decrypt to obtain vu∗. If vu∗=vu′, this situation significantly increases the success advantage of the attacker A. When vu∗≠vu′, ciphertext Cu1',Cu2'∈X\L¯ is obvious. According to the smoothness of ε−ASPH, vu∗≠vu′ does not increase the advantage of the attacker A. It is found that Adv5A≤Adv6A+2qsend⋅εSAPHn holds by applying the proof of the game G3.GameG7. We modify the query received by the user in this game. Let the message msg1=<IDu′,IDu,S,hku′,Cu1',Cu2',ssidu′> be a valid output of SendUu,Δu,hu> for the previous SendUu,<Δu,hu> query. If Δu,hu is a replay of an honest simulated SendS,<IDu′,IDu,S,hku′,Cu1',Cu2',ssidu′> query, hu′ will no longer be generated for the user according to the protocol, but force the user to have the same δsu as the server. Because it is hidden from the attacker, the above modifications will not increase the attacker’s advantage, and Adv7A=Adv6A holds.GameG8. The model of the response to the activation message Send0Uu,Sj is further modified. If the user is activated, the ciphertext is replaced with the encryption of the virtual verification element VT0. Now, Adv7A−Adv8A<2qsend⋅AdvPKE′aket+Oqsend+qexe.Proof.
The same as the proof of gameG2 because the public-key encryption system is CPA secure, the advantage difference of attacker A between this game and game G7 can be ignored.
According to the constructed gameG8, the attacker A can successfully break the protocol only if they meet the following conditions:(i)
The attacker forges a legal user to communicate, and the ciphertext is generated by encrypting the verification elementvU corresponding to the user password in the message sent to the server.(ii)
The attacker pretends to be the server and sends a valid messageΔa,ha to the user.(iii)
In theTest query, the attacker’s guess b′ of random bit b satisfies b′=b.
It can be seen from the analysis that the first and second conditions can be satisfied only whenA can obtain the password of the legal user from the session. However, through the game constructed above, it can be found that the attacker can no longer obtain any information related to the password during the session, even if the user verification element on the server has leaked, the attacker can only guess the user’s password by a dictionary attack. Let the user password space D in the proposed protocol obey the Zipf principle; C and ϖ are the parameters of Zipf. Note that ℱ represents that the first two conditions are true; then Prℱ≤C⋅qsendϖ. At the end of game G8, the session key negotiated by the user has been replaced with a completely random value. Here, the probability of a successful guess by the attacker in the Test query is 1/2 at most. Therefore, Adv8A≤C⋅qsendϖ.
To sum up, the advantages of the attacker in the gameG0 is Adv0A≤C⋅qsendϖ+2qsend+qexe⋅AdvPKE′aket+Oqsend+qexe+εSAPHn. Meanwhile, Adv1A=Adv0A; it can see that the attacker’s advantage is only a negligible difference from the dictionary attack advantage. Therefore, the proposed 3PAKE protocol based on the verification element is secure.


### 5.2. Forward Security

Theorem 5.
When the search RLWE difficult assumption is true, if the attacker still cannot use the known private key to interact with the participants to obtain the correct session key after obtaining the long-term private key of each participant in the protocol, the protocol has forward security.Proof.
In this protocol, the session key among users needs to be generated with the help of the server. The complete session key includes two parts: one is determined by the server and the other is determined by users. When the attacker has the long-term private key of the server, they can authenticate with the user and server by forging ciphertext and signature. Now, they can obtain part of the session key calculated by the server. The session key determined by the user is also related to the temporary key selected by the user for this communication. The temporary keysku′ is not transmitted on the channel, and the attacker can only obtain xu=a⋅sku′+2e transmitted on the channel. On the premise that the attacker knows a,xu, the attacker needs to solve the search RLWE problem to obtain the temporary private key sku′.


### 5.3. Privacy of Session Key

Theorem 6.
When the search RLWE difficulty assumption holds, the session key negotiated by the user using our protocol is private to the server. In other words, it is inoperable when the honest server wants to recover the user’s session key because of curiosity.Proof.
Firstly, we construct an adversaryARLWE against the search RLWE problem and let adversary Aprivacy destroy session key privacy. It is assumed that adversary Aprivacy can have qexe, qsend times Execute and Send queries when launching the session key attack, and the total running time is t at most. In the process of an attack, a random coin b∈0,1 is thrown by ARLWE to obtain a triplet xb,Cb,φb. When b=0, the triplet is the real RLWE generated by the running protocol. When b=1, the triplet is random. Right now, adversary ARLWE simulates protocol stipulates, honestly runs, and answers the Execute and Send query of adversary Aprivacy, but when responding to the query, ARLWE replaces the relevant contents x,C,φ with xb,Cb,φb in the real protocol.
Finally,Aprivacy outputs the guess b′ according to the response. If b′=b, ARLWE outputs 1, the triplet xb,Cb,φb is a real RLWE, and the probability of ARLWE guessing successfully can be denoted by PrARLWEwins=Prb′=b|b=1. If b′≠b, ARLWE outputs 0, the triplet xb,Cb,φb is random, and the probability of ARLWE guessing successfully can be expressed as below.
PrARLWEwins=Prb′≠b|b=0. Therefore, the probability ARLWE solving the search RLWE problem can be calculated as(12)PrARLWEwins=12Prb′=b∣b=1+Prb′≠b∣b=0=1212+12AP,DprivacyAprivacy+1−12=12+14AP,DprivacyAprivacy.


## 5.1. Security Proof

Theorem 4.
If the public-key encryption systemPKE=keyGen,Enc,Dec based on the ideal lattice is CCA secure ε−ASPH function cluster corresponding to the public key system PKE=keyGen,Enc,Dec.ECC:0,1n⟶0,1k is the coding algorithm of error correction code. It can correct the 2ε error partthrough the decoding algorithm ECC−1:0,1k⟶0,1n corresponding to the coding algorithm ECC. F=Fδ:δ∈0,1kk∈ℕ is a pseudo-random function cluster; and then, this protocol is secure.Proof.
Assuming that any PPT attacker can makeqexe,qsend,qre,qco for Execute, Send, Reveal and Corrupt inquiries at most, the total running time is t at most. The advantage of the attacker is simulated by constructing a series of games named G0,G1,⋅⋅⋅,G8. In this series of games, A’s advantage of breaking the protocol gradually increases. Finally, as long as the advantage of the attacker’s success in the game G8 is negligible, A cannot break the protocol. The advantage of A breaking the protocol is defined as AdvP,DakeA=2prSuccP,DakeA−1.GameG0. This game corresponds to the real attack in the security model. For all kinds of queries sent by the attacker A, A may get honest answers. At this time, the advantage of the attacker A is AdvP,DakeA=Adv0A.GameG1. In this game, we modify the simulation model of Execute inquiry and replace the answer generated by the user using ProjH with the corresponding Hash calculation in each Execute inquiry, such as hU′'=Hashpk,hku,Cu2,mu′, u∈A,B.Proof.
Due to the approximate correctness ofε−ASPHand the coding algorithm E:0,1n⟶0,1k of the error correction code, A has the same advantages in the game G1; it can be denoted by Adv1A=Adv0A.GameG2. During the simulated Execute query, for any user u∈A,B, the only difference between game G2 and game G1 is that the ciphertext Cu in the message sent by the user for the first time is replaced with the ciphertext of encrypting the virtual verification element VT0 (i.e., the verification element that does not belong to the password space D). Finally, we can see that the advantage difference of A between game G2 and game G1 can be ignored. We recorded it as Adv2A−Adv1A<2qexe⋅AdvPKEaket+Oqsend+qexe.Proof.
Taking the public keypk as a public parameter, ℬ is the attacker of the public-key encryption system so that ℬ can answer the queries of attackerA. ℬ sends vu′,VT0 to their challenger as the challenge plaintext and replaces the ciphertext Cu with the received challenge ciphertext Cu′ in the Execute query. Then, A makes their guess b′ about the random bit b in the Test query. If b′=b, the guess is successful, and ℬ outputs 1. Otherwise, ℬ outputs 0. According to the CCA security of the public-key cryptosystem on the ideal lattice, the attacker ℬ cannot distinguish two ciphertexts with negligible advantage. Therefore, the ciphertext in the qexeExecute query sent by the attacker can be replaced with the encrypted ciphertext of the virtual verification element VT0. Considering that the attacker A only needs additional calculation time during Execute and Send query in the whole process of simulating the protocol and does not need additional calculation time during other queries because it only needs to return the corresponding state, it only needs t+Oqsend+qexe at most calculation time in the whole process.GameG3. In this game, hu=Hashpk,hku,Cu2,mu′ and u∈A,B in the Execute query will be replaced by a randomly selected bit string of equal length. Let εASPHn be a negligible upper bound of the statistical distance between the outputs of inputting nonverbal element and the uniform random distribution. Here, Adv3A−Adv2A<2qexe⋅εSAPHn.Proof.
It is known that the ciphertexts are replaced by the encryption results of the virtual verification element in gameG2, so the input of the approximate smooth projection hash function is a nonverbal element. According to the smoothness of the function, the statistical distance between the outputs of the inputting nonverbal element and the uniform random distribution can be ignored.GameG4. In the Execute query, sku′,xu will be replaced by a randomly selected bit string of equal length, where u∈A,B. Here, Adv4A=Adv3A.Proof.
It is known that the ciphertext in gameG2 has been replaced by the encryption of the virtual verification element, and hu will be replaced by a random bit string with an equal length in the game G3. Now, xu,φu is random. According to the decision RLWEn,m,q,χβ problem, the advantages of game G4 and game G3 are the same.GameG5. Game G5 modifies the pseudorandom function in Execute query, and the others remain unchanged, the same as game G4. δsa and δsb are still randomly selected, but the values of Fδsa1, Fδa3, Fδb1, and Fδsb1 are replaced with independent and random numbers. Adv5A=Adv4A holds at this time because the pseudorandom function Fδsu is hidden for the user.Proof.
The user and the server have the sameΔa, and according to the correctness of the decoding algorithm E−1:0,1k⟶0,1n of the error correction code, the user will get the same δsa as the server.
The above is to modify theExecute query. It can be known from the content of game G1 to game G5 that all messages are replaced with random values independent of the user’s password, and the attacker cannot obtain any information related to the user’s password in the Oracle query so that the communication parties can finally negotiate a completely random session key.
Next, we modify theSend query, SendSj,msg1 means sending message msg1 to the server instance Sj, and SendUu,msg2 indicates sending message msg2 to the user instance Uu. Only when the server instance Sj receives a correct and valid message msg1, it can return the corresponding valid message msg2 to the attacker. Note that Send0Uu,Sj represents that the user instance Uu and the server instance Sj are activated and start to execute the protocol. In addition, the simulator ℳ should record the private key sk corresponding to the public key pk in the key generation phase.GameG6. For SendS,<IDu′,IDu,S,hku′,Cu1',Cu2',ssidu′> query received from the server, where u∈A,B, if there is no corresponding verification element vu′ in the local password list IDu′ of the server, the emulator ℳ rejects the message, or if ssidu′ is smaller than the value of the previous session serial number saved by the server, the message is rejected. Finally, ℳ checks whether the ciphertext Cu1',Cu2' is valid. If not, ℳ continues to reject the message. Otherwise, the emulator ℳ decrypts the ciphertext Cu1',Cu2' with the corresponding private key sk and gets the user’s verification element. If vu∗=vu′, it is considered that the attacker has broken the protocol and ends the game simulation. The modification of the above game obviously increases the probability of an attacker’s success, so Adv5A≤Adv6A+2qsend⋅εSAPHn holds.Proof.
IfCu1',Cu2' is a valid ciphertext, the simulator ℳ can successfully decrypt to obtain vu∗. If vu∗=vu′, this situation significantly increases the success advantage of the attacker A. When vu∗≠vu′, ciphertext Cu1',Cu2'∈X\L¯ is obvious. According to the smoothness of ε−ASPH, vu∗≠vu′ does not increase the advantage of the attacker A. It is found that Adv5A≤Adv6A+2qsend⋅εSAPHn holds by applying the proof of the game G3.GameG7. We modify the query received by the user in this game. Let the message msg1=<IDu′,IDu,S,hku′,Cu1',Cu2',ssidu′> be a valid output of SendUu,Δu,hu> for the previous SendUu,<Δu,hu> query. If Δu,hu is a replay of an honest simulated SendS,<IDu′,IDu,S,hku′,Cu1',Cu2',ssidu′> query, hu′ will no longer be generated for the user according to the protocol, but force the user to have the same δsu as the server. Because it is hidden from the attacker, the above modifications will not increase the attacker’s advantage, and Adv7A=Adv6A holds.GameG8. The model of the response to the activation message Send0Uu,Sj is further modified. If the user is activated, the ciphertext is replaced with the encryption of the virtual verification element VT0. Now, Adv7A−Adv8A<2qsend⋅AdvPKE′aket+Oqsend+qexe.Proof.
The same as the proof of gameG2 because the public-key encryption system is CPA secure, the advantage difference of attacker A between this game and game G7 can be ignored.
According to the constructed gameG8, the attacker A can successfully break the protocol only if they meet the following conditions:(i)
The attacker forges a legal user to communicate, and the ciphertext is generated by encrypting the verification elementvU corresponding to the user password in the message sent to the server.(ii)
The attacker pretends to be the server and sends a valid messageΔa,ha to the user.(iii)
In theTest query, the attacker’s guess b′ of random bit b satisfies b′=b.
It can be seen from the analysis that the first and second conditions can be satisfied only whenA can obtain the password of the legal user from the session. However, through the game constructed above, it can be found that the attacker can no longer obtain any information related to the password during the session, even if the user verification element on the server has leaked, the attacker can only guess the user’s password by a dictionary attack. Let the user password space D in the proposed protocol obey the Zipf principle; C and ϖ are the parameters of Zipf. Note that ℱ represents that the first two conditions are true; then Prℱ≤C⋅qsendϖ. At the end of game G8, the session key negotiated by the user has been replaced with a completely random value. Here, the probability of a successful guess by the attacker in the Test query is 1/2 at most. Therefore, Adv8A≤C⋅qsendϖ.
To sum up, the advantages of the attacker in the gameG0 is Adv0A≤C⋅qsendϖ+2qsend+qexe⋅AdvPKE′aket+Oqsend+qexe+εSAPHn. Meanwhile, Adv1A=Adv0A; it can see that the attacker’s advantage is only a negligible difference from the dictionary attack advantage. Therefore, the proposed 3PAKE protocol based on the verification element is secure.


## 5.2. Forward Security

Theorem 5.
When the search RLWE difficult assumption is true, if the attacker still cannot use the known private key to interact with the participants to obtain the correct session key after obtaining the long-term private key of each participant in the protocol, the protocol has forward security.Proof.
In this protocol, the session key among users needs to be generated with the help of the server. The complete session key includes two parts: one is determined by the server and the other is determined by users. When the attacker has the long-term private key of the server, they can authenticate with the user and server by forging ciphertext and signature. Now, they can obtain part of the session key calculated by the server. The session key determined by the user is also related to the temporary key selected by the user for this communication. The temporary keysku′ is not transmitted on the channel, and the attacker can only obtain xu=a⋅sku′+2e transmitted on the channel. On the premise that the attacker knows a,xu, the attacker needs to solve the search RLWE problem to obtain the temporary private key sku′.


## 5.3. Privacy of Session Key

Theorem 6.
When the search RLWE difficulty assumption holds, the session key negotiated by the user using our protocol is private to the server. In other words, it is inoperable when the honest server wants to recover the user’s session key because of curiosity.Proof.
Firstly, we construct an adversaryARLWE against the search RLWE problem and let adversary Aprivacy destroy session key privacy. It is assumed that adversary Aprivacy can have qexe, qsend times Execute and Send queries when launching the session key attack, and the total running time is t at most. In the process of an attack, a random coin b∈0,1 is thrown by ARLWE to obtain a triplet xb,Cb,φb. When b=0, the triplet is the real RLWE generated by the running protocol. When b=1, the triplet is random. Right now, adversary ARLWE simulates protocol stipulates, honestly runs, and answers the Execute and Send query of adversary Aprivacy, but when responding to the query, ARLWE replaces the relevant contents x,C,φ with xb,Cb,φb in the real protocol.
Finally,Aprivacy outputs the guess b′ according to the response. If b′=b, ARLWE outputs 1, the triplet xb,Cb,φb is a real RLWE, and the probability of ARLWE guessing successfully can be denoted by PrARLWEwins=Prb′=b|b=1. If b′≠b, ARLWE outputs 0, the triplet xb,Cb,φb is random, and the probability of ARLWE guessing successfully can be expressed as below.
PrARLWEwins=Prb′≠b|b=0. Therefore, the probability ARLWE solving the search RLWE problem can be calculated as(12)PrARLWEwins=12Prb′=b∣b=1+Prb′≠b∣b=0=1212+12AP,DprivacyAprivacy+1−12=12+14AP,DprivacyAprivacy.


## 6. Performance Analysis

This section analyzes the security and efficiency of the protocol. Table1 lists the security comparison results of our protocol with references [2, 14, 17, 23]. A/B/S in Table 1 represents the number of messages to be sent by user A, user B, and server S, respectively. Table 2 shows the analysis results of the calculation overheads and communication overheads of our protocol.Table 1
Security comparison.
SchemeTypeDifficulty problemVerification elementReplay attackPrivacy of session keyA/B/SLiu et al. [2]2-partyChebyshev chaotic mapNoYesNull2/1/-Zhang et al. [14]3-partyDDH assumptionYesNoYes2/2/4Yu et al. [17]3-partyLWENoYesNo1/1/2Shu et al. [23]3-partyRLWEYesYesYes3/4/2Ours3-partyRLWEYesYesYes1/1/1Table 2
Computation and communication cost of the proposed protocol.
Stagen = 32n = 64n = 128n = 256n = 512First computation cost of user A1.96 ms3.97 ms9.61 ms22.82 ms78.91 msServer’s computation cost20.52 ms63.10 ms353.49 ms3373.06 ms45802.87 msUser B’s computation cost0.38 ms0.63 ms1.07 ms3.39 ms4.62 msSecond computation cost of user A0.31 ms0.47 ms0.77 ms1.49 ms3.20 msTotal communication cost7 KB13 KB24 KB48 KB79 KB


### 6.1. Security Comparison

By analyzing the protocol of Guo and Zhang [29], Liu and Xue [2] found that the adversary in [29] can obtain the trust of the server by replaying the messages of other legitimate users. If an adversary uses this loophole to launch a DoS attack, it will consume the resources of the server and cause legitimate users to be unable to access the service. To solve this problem, Liu and Xue’s protocol introduces a timestamp and reduces a lot of unnecessary communication overheads; they reduce the six rounds of communication in the existing protocol to three and effectively solve the server spoofing attack and offline dictionary attack. However, their protocol is a 2PAKE protocol. With the emergence of large-scale end-to-end communication, users will communicate with each other frequently. 2PAKE protocol makes users need to store a large number of passwords for key agreement. Note that the 2PAKE protocol does not need a server to negotiate, so it is impossible to discuss whether the session key is private.The protocol of Yu et al. [17] introduces the session sequence number to resist the replay attack. The number of communication rounds is reduced to two rounds by using the separable cryptosystem and the smooth hash projection function. Since the password is stored in plaintext on the server, it cannot resist the server disclosure attack. In addition, the honest and curious server can recover the session key between users, and their protocol cannot resist the server’s internal attack.The protocols in [14, 23] are a 3PAKE protocol based on a verification element, effectively resisting the server disclosure attack. The protocol of Zhang et al. is based on the DDH assumption and cannot be against the quantum algorithm attack [14]. Although the session key can be negotiated only by four rounds of communication, it cannot resist the replay attack and cannot meet the security requirements in practical applications. Shu et al. [23] provided quantum level security, introduced the session sequence number to resist replay attack, and realized the privacy of the session key to the server, but they increased the communication overheads. It needs seven rounds of communication and sends nine massages to make a session key agreement.Based on protecting the user password, our protocol can also resist replay attacks. The proposed protocol is constructed according to the RLWE problem that improves security and reduces the storage space of the key. We use FFT to accelerate the operation speed, effectively lower down the time complexity, and introduce a message authentication mechanism to solve the problem of session key disclosure caused by the dishonesty of the server. In general, this protocol effectively resists the server disclosure attack and has stronger security.


### 6.2. Efficiency Analysis

Our protocol adopts an asymmetric model. User A initiating the establishment of the session key needs to perform two calculations: the first calculation is used to generate the information related to the session request, and the session key negotiated with user B is generated in the second calculation. We analyze the efficiency of the proposed protocol on Windows 10 system, 11th Gen. Intel (R) core (TM) i5-1135g7 @ 2.40 GHz processor and 16.0 GB running memory, and the computational complexity of each stage is the average value of running 10000 calculations. Table 2 lists the specific computation overhead of each communication stage and the total communication overhead of the protocol.Set the parametersn=2k, k≥2, q=n3−1, m=6logq; now our protocol is safe, where kand m are integer. It can be seen from Table 2 that with the increase of n, the computation overhead of each stage also increases. Note that the computation overhead of user A for the first round of communication and server, relatively speaking, is large. User A needs to generate ciphertext, message authentication code, and other information during the first round of communication; these operations are relatively complex. The server needs to verify the validity of the ciphertext and message authentication code, regenerate the message authentication code of user A, and generate a valid ciphertext for user B. When verifying the validity of ciphertext, the server needs to recover the corresponding plaintext message using the Exhaustive Method. In the experiment, we assume that plaintext can be decrypted and recovered in the worst case; that is to say, the server needs to run q times to decrypt successfully, and the value of q will increase rapidly with the increase of n. Therefore, the growth rate of computation overhead at this stage is high. And the computation overhead of the server will be optimized in the real operation process.Whenn=128 (n=256 or n=512), the total communication overhead is 29 KB (56 KB or 95 KB). It can be seen that the computation and communication overhead of each stage is low when n=128, n=256, or n=512; it can resist quantum algorithm attacks, and achieve the required security level, so the proposed protocol can be effectively applied to the large-scale communication networks.


## 6.1. Security Comparison

By analyzing the protocol of Guo and Zhang [29], Liu and Xue [2] found that the adversary in [29] can obtain the trust of the server by replaying the messages of other legitimate users. If an adversary uses this loophole to launch a DoS attack, it will consume the resources of the server and cause legitimate users to be unable to access the service. To solve this problem, Liu and Xue’s protocol introduces a timestamp and reduces a lot of unnecessary communication overheads; they reduce the six rounds of communication in the existing protocol to three and effectively solve the server spoofing attack and offline dictionary attack. However, their protocol is a 2PAKE protocol. With the emergence of large-scale end-to-end communication, users will communicate with each other frequently. 2PAKE protocol makes users need to store a large number of passwords for key agreement. Note that the 2PAKE protocol does not need a server to negotiate, so it is impossible to discuss whether the session key is private.The protocol of Yu et al. [17] introduces the session sequence number to resist the replay attack. The number of communication rounds is reduced to two rounds by using the separable cryptosystem and the smooth hash projection function. Since the password is stored in plaintext on the server, it cannot resist the server disclosure attack. In addition, the honest and curious server can recover the session key between users, and their protocol cannot resist the server’s internal attack.The protocols in [14, 23] are a 3PAKE protocol based on a verification element, effectively resisting the server disclosure attack. The protocol of Zhang et al. is based on the DDH assumption and cannot be against the quantum algorithm attack [14]. Although the session key can be negotiated only by four rounds of communication, it cannot resist the replay attack and cannot meet the security requirements in practical applications. Shu et al. [23] provided quantum level security, introduced the session sequence number to resist replay attack, and realized the privacy of the session key to the server, but they increased the communication overheads. It needs seven rounds of communication and sends nine massages to make a session key agreement.Based on protecting the user password, our protocol can also resist replay attacks. The proposed protocol is constructed according to the RLWE problem that improves security and reduces the storage space of the key. We use FFT to accelerate the operation speed, effectively lower down the time complexity, and introduce a message authentication mechanism to solve the problem of session key disclosure caused by the dishonesty of the server. In general, this protocol effectively resists the server disclosure attack and has stronger security.


## 6.2. Efficiency Analysis

Our protocol adopts an asymmetric model. User A initiating the establishment of the session key needs to perform two calculations: the first calculation is used to generate the information related to the session request, and the session key negotiated with user B is generated in the second calculation. We analyze the efficiency of the proposed protocol on Windows 10 system, 11th Gen. Intel (R) core (TM) i5-1135g7 @ 2.40 GHz processor and 16.0 GB running memory, and the computational complexity of each stage is the average value of running 10000 calculations. Table 2 lists the specific computation overhead of each communication stage and the total communication overhead of the protocol.Set the parametersn=2k, k≥2, q=n3−1, m=6logq; now our protocol is safe, where kand m are integer. It can be seen from Table 2 that with the increase of n, the computation overhead of each stage also increases. Note that the computation overhead of user A for the first round of communication and server, relatively speaking, is large. User A needs to generate ciphertext, message authentication code, and other information during the first round of communication; these operations are relatively complex. The server needs to verify the validity of the ciphertext and message authentication code, regenerate the message authentication code of user A, and generate a valid ciphertext for user B. When verifying the validity of ciphertext, the server needs to recover the corresponding plaintext message using the Exhaustive Method. In the experiment, we assume that plaintext can be decrypted and recovered in the worst case; that is to say, the server needs to run q times to decrypt successfully, and the value of q will increase rapidly with the increase of n. Therefore, the growth rate of computation overhead at this stage is high. And the computation overhead of the server will be optimized in the real operation process.Whenn=128 (n=256 or n=512), the total communication overhead is 29 KB (56 KB or 95 KB). It can be seen that the computation and communication overhead of each stage is low when n=128, n=256, or n=512; it can resist quantum algorithm attacks, and achieve the required security level, so the proposed protocol can be effectively applied to the large-scale communication networks.


## 7. Conclusion

Using approximate smooth projection hash function technology and message authentication mechanism on the ideal lattice, we construct a more efficient 3PAKE protocol based on the verification element. Compared with the existing verification element-based 3PAKE protocol, our protocol reduces space complexity and improves computation and communication efficiency. It only needs two rounds of communication to correctly negotiate a session key. Furthermore, it can be against server password disclosure attack, server internal attack, and replay attack; we give the semantic security proof of the new protocol. In short, the proposed protocol has high security and low overhead, which can meet the communication requirements of large-scale low bandwidth networks.



---

*Source: 6952869-2021-11-29.xml*