# Two-Round Password-Based Authenticated Key Exchange from Lattices

Authors: Anqi Yin; Yuanbo Guo; Yuanming Song; Tongzhou Qu; Chen Fang
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

Password-based authenticated key exchange (PAKE) allows participants sharing low-entropy passwords to agree on cryptographically strong session keys over insecure networks. In this paper, we present two PAKE protocols from lattices in the two-party and three-party settings, respectively, which can resist quantum attacks and achieve mutual authentication. The protocols in this paper achieve two rounds of communication by carefully utilizing the splittable properties of the underlying primitive, a CCA (Chosen-Ciphertext Attack)-secure public key encryption (PKE) scheme with associated nonadaptive approximate smooth projection hash (NA-ASPH) system. Compared with other related protocols, the proposed two-round PAKE protocols have relatively less communication and computation overhead. In particular, the two-round 3PAKE is more practical in large-scale communication systems.


---

## Body

## 1. Introduction

Password-based authentication key exchange (PAKE) is theoretically fascinating, since it allows participants sharing short, low-entropy passwords to agree on cryptographically strong session keys over insecure networks [1, 2]. PAKE protocols are very practical as passwords are probably the most common and widely used authentication method [3–6], and password-based authentication can avoid the dependence on public key infrastructure and secure hardware; thereby, it improves the convenience of the system.However, the use of shared short, low-entropy passwords will expose PAKE to greater security threats. This is because it must be ensured that the protocol is immune to off-line dictionary attacks, in which the adversary can exhaust all possible passwords to determine the correct one [7, 8]. Another observation is that an adversary can always succeed by guessing the password as the password dictionary is relatively small (usually polynomial in the security parameter), referred to as an on-line attack. The aim of PAKE is thus to limit the adversary to such an attack only [9].The first successful password-based authenticated key exchange agreement methods were Encrypted Key Exchange methods described by Steven M. Bellovin and Michael Merritt in 1992 [10]. Initial PAKE protocols are generally based on “hybrid” models [11, 12], in which the clients need to store the public key of the server besides sharing a password with the server. The requirement of securely storing long, high-entropy public key is not friendly in multiserver environment. This motivates the study towards password-only protocols [13–16] where clients need to remember only a short password. Most PAKE protocols above provide only informal security arguments. Thus, Bellare et al. [17] and Boyko et al. [18] gave formal models of security of the password-only setting and proved security in the ideal cipher model and random oracle model, respectively. And then, Goldreich and Lindell [19] presented a provably secure password-only key exchange under standard cryptographic assumptions. Their work shows the possibility for password-based authentication under very weak assumptions, but the protocol itself is far from practical.Later, many provably secure PAKE protocols based on various hardness assumptions were proposed. The research is mainly divided into two directions. The former is PAKE in the random oracle/ideal cipher model, which aims to achieve the highest possible levels of performance [20–22]. The latter is dedicated to seeking more efficient PAKE in the standard model [5, 23–25].The first efficient PAKE protocol under standard model was proposed by Katz et al. [7]. They utilized CCA2 (Adaptive Chosen-Ciphertext Attack)-secure encryption system and corresponding smooth projection hash (SPH) function for key exchange to construct their scheme. Then, Gennaro and Lindell [9] abstracted their work and presented a corresponding PAKE framework, referred to as KOY/GL framework without mutual authentication. Based on KOY/GL framework, Jiang and Gong [26] showed a three-round PAKE supporting mutual authentication. Groce and Katz [5] then generalized the protocol by Jiang and Gong and gave a new PAKE framework in the common reference string model (CRS), referred to as JG/GK framework. Subsequently, based on the above two framework, a series of PAKE protocols [27–29] with different security are proposed for different application scenarios.Most above schemes are two-party PAKE (2PAKE), requiring every two participants to share a password, which is not adaptable to large communication systems. In contrast, three-party PAKE (3PAKE) enables each client to share a password with the server for authentication, thereby avoiding the limitation of 2PAKE. Abdalla et al. [30] gave a general structure of the 3PAKE protocol for the first time. Subsequently, cryptographers designed a series of 3PAKE protocols with different efficiency and security [31, 32].The security of most protocols above relies on traditional difficult problems (such as large integer factorization and discrete logarithm problems), so they cannot resist quantum attacks. However, the public-key cryptosystem based on the lattice assumption can resist quantum attacks. In addition, the operation on the lattice is matrix-vector multiplication which can be practically implemented by parallel computing. Therefore, the public-key cryptosystem from lattices will be more secure and efficient.In lattice-based cryptosystem, the research on PAKE is relatively insufficient. In 2009, Katz et al. [33] presented the first lattice-based 2PAKE protocol based on KOY/GL framework. They proposed their protocol by constructing the first lattice-based CCA-secure encryption system and its corresponding approximate smooth projected hash (ASPH) function. Ding et al. [34] then applied the encryption system and ASPH function from Katz et al. [33] to JG/GK framework, and a more efficient protocol is given in the standard model.Ye et al. [35] proposed the first 3PAKE protocol based on the JG/GK framework from lattices, and they proved its security under the standard model. This is a three-round protocol that implements explicit mutual authentication between the client and the server. In 2017, Xu et al. [36] proposed a provably secure 3PAKE protocol based on the R-LWE (ring learning with error) problem according to the idea of DH, but this protocol suffers from low efficiency.Zhang et al. [1] applied a splittable public key encryption system to the KOY/GL framework and proposed a lattice-based PAKE, requiring only two-round communication, so it is more efficient. However, Zhang’s 2PAKE cannot be directly applied to the 3PAKE protocol, because another function is needed to compute the client-side information.In this paper, we present efficient new constructions of 2PAKE and 3PAKE based on the learning with error (LWE) problem based on ideas of [1, 34, 35]. We then prove the security of the proposed protocols in the random oracle model. Significant security (resistance to quantum attacks) and efficiency improvements would also be obtained when basing the protocol on lattice assumption. Compared with the general structure [30], the new protocols reduce the number of communications, thereby improving efficiency. Our protocols also achieve mutual authentication between participants, so they can resist unpredictable on-line attacks. And the proposed two-round 3PAKE is adaptable to large-scale communication systems.


## 2. Preliminaries

### 2.1. Notations

We denote the logarithm with base2 (resp., the natural logarithm) by lb (resp., log). Vectors are expressed in columns and bold lower-case letters (for example, x). A matrix is considered as a collection of column vectors and is represented by bold capital letter (such as X). We denote the concatenation of X and Y as XY. Let x⟵rK denote the random sampling of variable x from the distribution K. For any string x,y∈0,1ℓ, Hamx,y represents the Hamming distance between x and y. Table 1 summarizes the description of other symbols used in this paper.Table 1
Symbol description.
SymbolDescriptionsκSecurity parameterpwPasswordDPassword dictionary∣S∣The size of set SεA real number in0,1/2.ℓℓ=ℓκAn integer related toκskSession keyskpkThe corresponding private key ofpk


### 2.2. Security Model

#### 2.2.1. Participants

Participants include honest clientsA,B,D,⋯∈U, malicious clients A,M,⋯∈E and trusted server C∈S. For simplicity, we assume that the server set S contains only one element C. For each distinct A,B∈Client, assume that A and B share a long-term key called password pwAB. We simply assume that pwABis independently and uniformly chosen at random from the password dictionary D. But our proof of security extends to more general cases. In the following, we refer to honest clients directly as clients, and the malicious clients as adversaries.Each participant can execute multiple protocols with different partners at the same time. We call the execution of a protocol an instance. Denote the instancei of client A and the instance j of server C by ΠAi, and ΠCj, respectively.Each instanceΠAi maintains a local state vector sidAi,pidAi,skAi,accAi,termAi, where sidAi represents the session ID, recording all messages sent and received by ΠAi in order; pidAi (pidAi≠A) represents the partner ID, the participant with which ΠAi believes it is interacting; skAi denotes the session key of ΠAi; accAi and termAi are Boolean variables, indicating whether the ΠAi is accepted or terminated.Before giving a formal definition of adversarial abilities, we first define partnering, correctness, and freshness as follows.Partnering. If (1) sidAi=sidBj≠⊥ and (2) ΠAi=B and ΠBj=A, instances ΠAi and ΠBj are partnered.Correctness. We say that the protocol between partnered instances ΠAi and ΠBj is correct if they are both accepted and establish the same session key, that is, accAi=accBj=1 and skAi=skBj.Freshness. If none of the following cases happens, the instance ΠAi is fresh: (1) adversary A have sent a Reveal query to ΠAi; (2) ΠAi and ΠBj have become partners and adversary A has sent a Reveal query to ΠBj. The definition of Reveal query will be given below.


#### 2.2.2. Adversarial Abilities

It is assumed that the protocol is executed over a generally insecure network. AdversaryA can eavesdrop, intercept, inject, and tamper with messages among different participants. A can also obtain the session key of the accepted instances. The following oracle queries model the adversarial abilities, that is, the adversary’s interaction with various instances.
(i)
ExecuteA,i,B,jQuery. The oracle models off-line attacks for passive adversaries. This oracle executes the protocol between the client instances ΠAi and ΠBj, and it updates the state vectors according to the specific protocol. And return the transcript of this execution to A.(ii)
SendA,i,M. This oracle sends the message M to the client instance ΠAi to update the corresponding state vector appropriately. Finally, it returns the output message of ΠAi to A. This oracle models on-line attacks from active adversaries.(iii)
RevealA,i. This oracle returns the session key of the accepted instance ΠAi to A, thereby modelling the leakage of the session key. This oracle corresponds to an on-line attack from active adversaries.(iv)
TestA,i. The oracle selects a random bit b⟵r0,1. And if b=1, the real session key of ΠAi is returned to A. Otherwise, it returns a uniform string of appropriate length. Note that A can only query this oracle once, and A is only allowed to query a fresh instance. This oracle is used to define security and does not model any adversarial capability in the real world.


#### 2.2.3. The Advantage of the Adversary

The security of the protocol is defined by a security experiment: the adversary is allowed to send a series of queries above, but the Test query can only be sent once; and the experiment ends withA outputting bit b′, a guess of b. Informally, A succeeds if (1) b′=b, that is, A’s guess is correct, representing that the session key is insecure, (2) A makes the instance accepted but there is no corresponding partner, indicating that the protocol cannot achieve mutual authentication. Formally, we use Success to indicate the success of A. The advantage of the adversary in attacking the protocol Π is defined as AdvΠ,A≝2PrSuccess−1.


#### 2.2.4. Secure Protocol

Since the size of the password dictionaryD is usually small, a PPT (Probabilistic Polynomial Time) adversary can always succeed by exhausting D in an on-line attack. Therefore, informally, if on-line attack is the best attack method for all PPT adversaries, the PAKE protocol is secure. Formally, we give the following definition of the secure protocol.Definition 1.
(secure protocol). A protocol is a secure PAKE with mutual authentication if for all password in dictionaryD and for any PPT adversary making at most Qκ on-line attacks, it holds that AdvΠ,Aκ≤Qκ/D+neglκ for some negligible function negl∙.


### 2.3. Splittable Labeled PKE System from Lattices

#### 2.3.1. Splittable Labeled PKE

Let the splittable labeled CCA-secure PKE beSPKE=KeyGen,Enc,Dec. KeyGen is a key generation algorithm outputting the public and secret key pair pk,sk. Enc is an encryption algorithm that returns c=u,v=Encpk,label,pw, whereu=fpk,pw, v=gpk,label,pw, f and g are two different subfunctions that constituteSPKE. Dec is a decryption algorithm defined as pw⟵Declabel,sk,c. For any v′ and label′∈0,1∗, under the random selection of sk and r, the probability that Decsk,label,u,v∉⊥,pw is negligible in κ.The “splittable” attribute is also reflected in the security of the public-key cryptosystem. When proving the CCA security of the splittable cryptosystem, the challenge phase of the CCA game should be modified as follows: (1) the adversaryM first sends two plaintexts pw0,pw1∈D of equal length. (2) The challenger CL randomly chooses b∗⟵r0,1 and r∗⟵r0,1∗. Then, CL computes u∗=fpk,pwb∗,r∗ and returns u∗ to M. (3) Upon receiving u∗, the adversary M submits label⟵0,1∗. (4) CL computes v∗=gpk,label,pwb∗,r∗ and returns v∗ to M.Definition 2.
(CCA security of SPKE).SPKE is a secure CCA-secure public-key encryption scheme if for any PPT adversary, it holds thatAdvSPKE.MIND−CCAκ≤neglκ for some negligible function negl∙.In this paper, we denote the splittable labeled CCA-secure PKE based on LWE problem [1] by Σ=KeyGen,Enc,Dec, and we will use it to construct two-round PAKEs. The definitions of the cryptographic primitives (TrapGen, CRSGen, Prove, Verify, and Solve) on which Σ is based can be found in [1]. TrapGen is a trapdoor generation algorithm for generating public keys and corresponding trapdoors; CRSGen is a common reference string generator, usually implemented by hardware; the Proof/Verify algorithm is similar to the signature/verification algorithm to ensure the integrity of A0,A1,u,v,β; Solve is a trapdoor solving algorithm corresponding to TrapGen.


#### 2.3.2. A Splittable Labeled PKE from Lattices [1]

Supposen1,n2∈ℤ and prime q is polynomial with respect to the security parameter κ. Let n=n1+n2+1, m=Onlogq∈ℤ. α,β∈ℝ are the parameters of the systems. The splittable labeled PKE from lattices Σ=KeyGen,Enc,Dec is defined as follows:KeyGen1κ: given security parameter κ, we have A0,R0⟵TrapGen1n,1m,q, A1,R1⟵TrapGen1n,1m,q, and CRS⟵CRSGen1κ. And return pk,sk=A0,A1,CRS,R0.Encpk,label,pw: given pk=A0,A1,CRS, label⟵0,1∗, and plaintext pw∈D, choose s0,s1⟵rℤqn1,e0,e1⟵rDℤm,αq. Return the ciphertext C=u,v,π, where
(1)u=A0Ts01pw+e0,v=A1Ts11pw+e1and π⟵ProveCRS,A0,A1,u,v,β,s0,s1,pw,label.Decsk,label,C: given sk=R0, label⟵0,1∗, and the ciphertext C=u,v,π, if VerifyCRS,A0,A1,u,v,β,π,label=0, return ⊥. Otherwise, compute
(2)t=s01pw⟵SolveA0,R0,CFinally, returnpw∈ℤqn2.


### 2.4. Nonadaptive Approximate Smooth Projective Hash (NA-ASPH) System

Based on the smooth projected Hash function [37], Katz et al. [33] proposed an Approximate Smooth Projective Hash (ASPH) function that can be used to construct a lattice-based PAKE protocol. In our application, we use a modified definition of ASPH [1] from Katz’s, referred to as nonadaptive approximate smooth projection hash (NA-ASPH) function.Suppose thatΣGen,Enc,Dec is a semantically secure PKE system from lattices. Assume that a valid ciphertext c=u,v can be easily parsed as the output of the function pair f,g. We use KeyGen to generate a key pair pk,sk and we use Cpk to represent the valid ciphertext space corresponding to the public key pk. Define
(3)X=label,c,pw∣label,c∈Cpk,pw∈DL=label,c,pw∣label∈0,1∗,c=Encpk,label,pw,rL¯=label,c,pw∣label∈0,1∗,pw=Decsk,label,c.Based onΣGen,Enc,Dec, we introduce the ϵ-NA-ASPH function defined by the sampling algorithm, which outputs K,ℓ,ℍ=Hk:X⟶0,1ℓ,S,α:K⟶S given the public key pk of Σ (where K is the hash key space and k∈K, α is the key projection function from K to S, and S is the projection key space; the domain and value range of the ϵ-NA-ASPH are X and 0,1ℓ, respectively), such that
(1)
There exist efficient algorithms for sampling a hash keyk⟵rK, computing Hkx=Hku,pw for all x=label,u,v,pw∈X and computing s=αkfor all k∈K(2)
For allk⟵rK, x=label,u,v,pw∈L and randomness r, there are efficient algorithms for computing Hashs,x,r=Hashs,u,pw,r given u=fpk,pw,r and v=gpk,label,pw,r.Theϵ-NA-ASPH has the following properties:
(i)
Correctness. For all x=label,u,v,pw∈L and s=αk, it holds that PrHamHku,pw,Hashs,u,pw,r≥ϵ=neglκ for some negligible function negl∙.(ii)
Smoothness. For any (even unbounded) function h: S⟶X\L¯, k⟵rK, s=αk, x=hs and γ⟵r0,1ℓ, the distributions s,Hkx and s,γ are statistically indistinguishable in the security parameter κNA-ASPH has three modifications compared with ASPH in [33]: (1) the projection function α depends only on the hash key k; (2) Hkx=Hku,pw is determined by the hash key k, the first part of the ciphertext c=u,v and the plaintext pw; (3) for all x=hs∉L¯, the smoothness holds. The first modification here enables the protocol proposed to achieve two rounds of communication, and the latter two are prepared to prove the security of the proposed protocol.


## 2.1. Notations

We denote the logarithm with base2 (resp., the natural logarithm) by lb (resp., log). Vectors are expressed in columns and bold lower-case letters (for example, x). A matrix is considered as a collection of column vectors and is represented by bold capital letter (such as X). We denote the concatenation of X and Y as XY. Let x⟵rK denote the random sampling of variable x from the distribution K. For any string x,y∈0,1ℓ, Hamx,y represents the Hamming distance between x and y. Table 1 summarizes the description of other symbols used in this paper.Table 1
Symbol description.
SymbolDescriptionsκSecurity parameterpwPasswordDPassword dictionary∣S∣The size of set SεA real number in0,1/2.ℓℓ=ℓκAn integer related toκskSession keyskpkThe corresponding private key ofpk


## 2.2. Security Model

### 2.2.1. Participants

Participants include honest clientsA,B,D,⋯∈U, malicious clients A,M,⋯∈E and trusted server C∈S. For simplicity, we assume that the server set S contains only one element C. For each distinct A,B∈Client, assume that A and B share a long-term key called password pwAB. We simply assume that pwABis independently and uniformly chosen at random from the password dictionary D. But our proof of security extends to more general cases. In the following, we refer to honest clients directly as clients, and the malicious clients as adversaries.Each participant can execute multiple protocols with different partners at the same time. We call the execution of a protocol an instance. Denote the instancei of client A and the instance j of server C by ΠAi, and ΠCj, respectively.Each instanceΠAi maintains a local state vector sidAi,pidAi,skAi,accAi,termAi, where sidAi represents the session ID, recording all messages sent and received by ΠAi in order; pidAi (pidAi≠A) represents the partner ID, the participant with which ΠAi believes it is interacting; skAi denotes the session key of ΠAi; accAi and termAi are Boolean variables, indicating whether the ΠAi is accepted or terminated.Before giving a formal definition of adversarial abilities, we first define partnering, correctness, and freshness as follows.Partnering. If (1) sidAi=sidBj≠⊥ and (2) ΠAi=B and ΠBj=A, instances ΠAi and ΠBj are partnered.Correctness. We say that the protocol between partnered instances ΠAi and ΠBj is correct if they are both accepted and establish the same session key, that is, accAi=accBj=1 and skAi=skBj.Freshness. If none of the following cases happens, the instance ΠAi is fresh: (1) adversary A have sent a Reveal query to ΠAi; (2) ΠAi and ΠBj have become partners and adversary A has sent a Reveal query to ΠBj. The definition of Reveal query will be given below.


### 2.2.2. Adversarial Abilities

It is assumed that the protocol is executed over a generally insecure network. AdversaryA can eavesdrop, intercept, inject, and tamper with messages among different participants. A can also obtain the session key of the accepted instances. The following oracle queries model the adversarial abilities, that is, the adversary’s interaction with various instances.
(i)
ExecuteA,i,B,jQuery. The oracle models off-line attacks for passive adversaries. This oracle executes the protocol between the client instances ΠAi and ΠBj, and it updates the state vectors according to the specific protocol. And return the transcript of this execution to A.(ii)
SendA,i,M. This oracle sends the message M to the client instance ΠAi to update the corresponding state vector appropriately. Finally, it returns the output message of ΠAi to A. This oracle models on-line attacks from active adversaries.(iii)
RevealA,i. This oracle returns the session key of the accepted instance ΠAi to A, thereby modelling the leakage of the session key. This oracle corresponds to an on-line attack from active adversaries.(iv)
TestA,i. The oracle selects a random bit b⟵r0,1. And if b=1, the real session key of ΠAi is returned to A. Otherwise, it returns a uniform string of appropriate length. Note that A can only query this oracle once, and A is only allowed to query a fresh instance. This oracle is used to define security and does not model any adversarial capability in the real world.


### 2.2.3. The Advantage of the Adversary

The security of the protocol is defined by a security experiment: the adversary is allowed to send a series of queries above, but the Test query can only be sent once; and the experiment ends withA outputting bit b′, a guess of b. Informally, A succeeds if (1) b′=b, that is, A’s guess is correct, representing that the session key is insecure, (2) A makes the instance accepted but there is no corresponding partner, indicating that the protocol cannot achieve mutual authentication. Formally, we use Success to indicate the success of A. The advantage of the adversary in attacking the protocol Π is defined as AdvΠ,A≝2PrSuccess−1.


### 2.2.4. Secure Protocol

Since the size of the password dictionaryD is usually small, a PPT (Probabilistic Polynomial Time) adversary can always succeed by exhausting D in an on-line attack. Therefore, informally, if on-line attack is the best attack method for all PPT adversaries, the PAKE protocol is secure. Formally, we give the following definition of the secure protocol.Definition 1.
(secure protocol). A protocol is a secure PAKE with mutual authentication if for all password in dictionaryD and for any PPT adversary making at most Qκ on-line attacks, it holds that AdvΠ,Aκ≤Qκ/D+neglκ for some negligible function negl∙.


## 2.2.1. Participants

Participants include honest clientsA,B,D,⋯∈U, malicious clients A,M,⋯∈E and trusted server C∈S. For simplicity, we assume that the server set S contains only one element C. For each distinct A,B∈Client, assume that A and B share a long-term key called password pwAB. We simply assume that pwABis independently and uniformly chosen at random from the password dictionary D. But our proof of security extends to more general cases. In the following, we refer to honest clients directly as clients, and the malicious clients as adversaries.Each participant can execute multiple protocols with different partners at the same time. We call the execution of a protocol an instance. Denote the instancei of client A and the instance j of server C by ΠAi, and ΠCj, respectively.Each instanceΠAi maintains a local state vector sidAi,pidAi,skAi,accAi,termAi, where sidAi represents the session ID, recording all messages sent and received by ΠAi in order; pidAi (pidAi≠A) represents the partner ID, the participant with which ΠAi believes it is interacting; skAi denotes the session key of ΠAi; accAi and termAi are Boolean variables, indicating whether the ΠAi is accepted or terminated.Before giving a formal definition of adversarial abilities, we first define partnering, correctness, and freshness as follows.Partnering. If (1) sidAi=sidBj≠⊥ and (2) ΠAi=B and ΠBj=A, instances ΠAi and ΠBj are partnered.Correctness. We say that the protocol between partnered instances ΠAi and ΠBj is correct if they are both accepted and establish the same session key, that is, accAi=accBj=1 and skAi=skBj.Freshness. If none of the following cases happens, the instance ΠAi is fresh: (1) adversary A have sent a Reveal query to ΠAi; (2) ΠAi and ΠBj have become partners and adversary A has sent a Reveal query to ΠBj. The definition of Reveal query will be given below.


## 2.2.2. Adversarial Abilities

It is assumed that the protocol is executed over a generally insecure network. AdversaryA can eavesdrop, intercept, inject, and tamper with messages among different participants. A can also obtain the session key of the accepted instances. The following oracle queries model the adversarial abilities, that is, the adversary’s interaction with various instances.
(i)
ExecuteA,i,B,jQuery. The oracle models off-line attacks for passive adversaries. This oracle executes the protocol between the client instances ΠAi and ΠBj, and it updates the state vectors according to the specific protocol. And return the transcript of this execution to A.(ii)
SendA,i,M. This oracle sends the message M to the client instance ΠAi to update the corresponding state vector appropriately. Finally, it returns the output message of ΠAi to A. This oracle models on-line attacks from active adversaries.(iii)
RevealA,i. This oracle returns the session key of the accepted instance ΠAi to A, thereby modelling the leakage of the session key. This oracle corresponds to an on-line attack from active adversaries.(iv)
TestA,i. The oracle selects a random bit b⟵r0,1. And if b=1, the real session key of ΠAi is returned to A. Otherwise, it returns a uniform string of appropriate length. Note that A can only query this oracle once, and A is only allowed to query a fresh instance. This oracle is used to define security and does not model any adversarial capability in the real world.


## 2.2.3. The Advantage of the Adversary

The security of the protocol is defined by a security experiment: the adversary is allowed to send a series of queries above, but the Test query can only be sent once; and the experiment ends withA outputting bit b′, a guess of b. Informally, A succeeds if (1) b′=b, that is, A’s guess is correct, representing that the session key is insecure, (2) A makes the instance accepted but there is no corresponding partner, indicating that the protocol cannot achieve mutual authentication. Formally, we use Success to indicate the success of A. The advantage of the adversary in attacking the protocol Π is defined as AdvΠ,A≝2PrSuccess−1.


## 2.2.4. Secure Protocol

Since the size of the password dictionaryD is usually small, a PPT (Probabilistic Polynomial Time) adversary can always succeed by exhausting D in an on-line attack. Therefore, informally, if on-line attack is the best attack method for all PPT adversaries, the PAKE protocol is secure. Formally, we give the following definition of the secure protocol.Definition 1.
(secure protocol). A protocol is a secure PAKE with mutual authentication if for all password in dictionaryD and for any PPT adversary making at most Qκ on-line attacks, it holds that AdvΠ,Aκ≤Qκ/D+neglκ for some negligible function negl∙.


## 2.3. Splittable Labeled PKE System from Lattices

### 2.3.1. Splittable Labeled PKE

Let the splittable labeled CCA-secure PKE beSPKE=KeyGen,Enc,Dec. KeyGen is a key generation algorithm outputting the public and secret key pair pk,sk. Enc is an encryption algorithm that returns c=u,v=Encpk,label,pw, whereu=fpk,pw, v=gpk,label,pw, f and g are two different subfunctions that constituteSPKE. Dec is a decryption algorithm defined as pw⟵Declabel,sk,c. For any v′ and label′∈0,1∗, under the random selection of sk and r, the probability that Decsk,label,u,v∉⊥,pw is negligible in κ.The “splittable” attribute is also reflected in the security of the public-key cryptosystem. When proving the CCA security of the splittable cryptosystem, the challenge phase of the CCA game should be modified as follows: (1) the adversaryM first sends two plaintexts pw0,pw1∈D of equal length. (2) The challenger CL randomly chooses b∗⟵r0,1 and r∗⟵r0,1∗. Then, CL computes u∗=fpk,pwb∗,r∗ and returns u∗ to M. (3) Upon receiving u∗, the adversary M submits label⟵0,1∗. (4) CL computes v∗=gpk,label,pwb∗,r∗ and returns v∗ to M.Definition 2.
(CCA security of SPKE).SPKE is a secure CCA-secure public-key encryption scheme if for any PPT adversary, it holds thatAdvSPKE.MIND−CCAκ≤neglκ for some negligible function negl∙.In this paper, we denote the splittable labeled CCA-secure PKE based on LWE problem [1] by Σ=KeyGen,Enc,Dec, and we will use it to construct two-round PAKEs. The definitions of the cryptographic primitives (TrapGen, CRSGen, Prove, Verify, and Solve) on which Σ is based can be found in [1]. TrapGen is a trapdoor generation algorithm for generating public keys and corresponding trapdoors; CRSGen is a common reference string generator, usually implemented by hardware; the Proof/Verify algorithm is similar to the signature/verification algorithm to ensure the integrity of A0,A1,u,v,β; Solve is a trapdoor solving algorithm corresponding to TrapGen.


### 2.3.2. A Splittable Labeled PKE from Lattices [1]

Supposen1,n2∈ℤ and prime q is polynomial with respect to the security parameter κ. Let n=n1+n2+1, m=Onlogq∈ℤ. α,β∈ℝ are the parameters of the systems. The splittable labeled PKE from lattices Σ=KeyGen,Enc,Dec is defined as follows:KeyGen1κ: given security parameter κ, we have A0,R0⟵TrapGen1n,1m,q, A1,R1⟵TrapGen1n,1m,q, and CRS⟵CRSGen1κ. And return pk,sk=A0,A1,CRS,R0.Encpk,label,pw: given pk=A0,A1,CRS, label⟵0,1∗, and plaintext pw∈D, choose s0,s1⟵rℤqn1,e0,e1⟵rDℤm,αq. Return the ciphertext C=u,v,π, where
(1)u=A0Ts01pw+e0,v=A1Ts11pw+e1and π⟵ProveCRS,A0,A1,u,v,β,s0,s1,pw,label.Decsk,label,C: given sk=R0, label⟵0,1∗, and the ciphertext C=u,v,π, if VerifyCRS,A0,A1,u,v,β,π,label=0, return ⊥. Otherwise, compute
(2)t=s01pw⟵SolveA0,R0,CFinally, returnpw∈ℤqn2.


## 2.3.1. Splittable Labeled PKE

Let the splittable labeled CCA-secure PKE beSPKE=KeyGen,Enc,Dec. KeyGen is a key generation algorithm outputting the public and secret key pair pk,sk. Enc is an encryption algorithm that returns c=u,v=Encpk,label,pw, whereu=fpk,pw, v=gpk,label,pw, f and g are two different subfunctions that constituteSPKE. Dec is a decryption algorithm defined as pw⟵Declabel,sk,c. For any v′ and label′∈0,1∗, under the random selection of sk and r, the probability that Decsk,label,u,v∉⊥,pw is negligible in κ.The “splittable” attribute is also reflected in the security of the public-key cryptosystem. When proving the CCA security of the splittable cryptosystem, the challenge phase of the CCA game should be modified as follows: (1) the adversaryM first sends two plaintexts pw0,pw1∈D of equal length. (2) The challenger CL randomly chooses b∗⟵r0,1 and r∗⟵r0,1∗. Then, CL computes u∗=fpk,pwb∗,r∗ and returns u∗ to M. (3) Upon receiving u∗, the adversary M submits label⟵0,1∗. (4) CL computes v∗=gpk,label,pwb∗,r∗ and returns v∗ to M.Definition 2.
(CCA security of SPKE).SPKE is a secure CCA-secure public-key encryption scheme if for any PPT adversary, it holds thatAdvSPKE.MIND−CCAκ≤neglκ for some negligible function negl∙.In this paper, we denote the splittable labeled CCA-secure PKE based on LWE problem [1] by Σ=KeyGen,Enc,Dec, and we will use it to construct two-round PAKEs. The definitions of the cryptographic primitives (TrapGen, CRSGen, Prove, Verify, and Solve) on which Σ is based can be found in [1]. TrapGen is a trapdoor generation algorithm for generating public keys and corresponding trapdoors; CRSGen is a common reference string generator, usually implemented by hardware; the Proof/Verify algorithm is similar to the signature/verification algorithm to ensure the integrity of A0,A1,u,v,β; Solve is a trapdoor solving algorithm corresponding to TrapGen.


## 2.3.2. A Splittable Labeled PKE from Lattices [1]

Supposen1,n2∈ℤ and prime q is polynomial with respect to the security parameter κ. Let n=n1+n2+1, m=Onlogq∈ℤ. α,β∈ℝ are the parameters of the systems. The splittable labeled PKE from lattices Σ=KeyGen,Enc,Dec is defined as follows:KeyGen1κ: given security parameter κ, we have A0,R0⟵TrapGen1n,1m,q, A1,R1⟵TrapGen1n,1m,q, and CRS⟵CRSGen1κ. And return pk,sk=A0,A1,CRS,R0.Encpk,label,pw: given pk=A0,A1,CRS, label⟵0,1∗, and plaintext pw∈D, choose s0,s1⟵rℤqn1,e0,e1⟵rDℤm,αq. Return the ciphertext C=u,v,π, where
(1)u=A0Ts01pw+e0,v=A1Ts11pw+e1and π⟵ProveCRS,A0,A1,u,v,β,s0,s1,pw,label.Decsk,label,C: given sk=R0, label⟵0,1∗, and the ciphertext C=u,v,π, if VerifyCRS,A0,A1,u,v,β,π,label=0, return ⊥. Otherwise, compute
(2)t=s01pw⟵SolveA0,R0,CFinally, returnpw∈ℤqn2.


## 2.4. Nonadaptive Approximate Smooth Projective Hash (NA-ASPH) System

Based on the smooth projected Hash function [37], Katz et al. [33] proposed an Approximate Smooth Projective Hash (ASPH) function that can be used to construct a lattice-based PAKE protocol. In our application, we use a modified definition of ASPH [1] from Katz’s, referred to as nonadaptive approximate smooth projection hash (NA-ASPH) function.Suppose thatΣGen,Enc,Dec is a semantically secure PKE system from lattices. Assume that a valid ciphertext c=u,v can be easily parsed as the output of the function pair f,g. We use KeyGen to generate a key pair pk,sk and we use Cpk to represent the valid ciphertext space corresponding to the public key pk. Define
(3)X=label,c,pw∣label,c∈Cpk,pw∈DL=label,c,pw∣label∈0,1∗,c=Encpk,label,pw,rL¯=label,c,pw∣label∈0,1∗,pw=Decsk,label,c.Based onΣGen,Enc,Dec, we introduce the ϵ-NA-ASPH function defined by the sampling algorithm, which outputs K,ℓ,ℍ=Hk:X⟶0,1ℓ,S,α:K⟶S given the public key pk of Σ (where K is the hash key space and k∈K, α is the key projection function from K to S, and S is the projection key space; the domain and value range of the ϵ-NA-ASPH are X and 0,1ℓ, respectively), such that
(1)
There exist efficient algorithms for sampling a hash keyk⟵rK, computing Hkx=Hku,pw for all x=label,u,v,pw∈X and computing s=αkfor all k∈K(2)
For allk⟵rK, x=label,u,v,pw∈L and randomness r, there are efficient algorithms for computing Hashs,x,r=Hashs,u,pw,r given u=fpk,pw,r and v=gpk,label,pw,r.Theϵ-NA-ASPH has the following properties:
(i)
Correctness. For all x=label,u,v,pw∈L and s=αk, it holds that PrHamHku,pw,Hashs,u,pw,r≥ϵ=neglκ for some negligible function negl∙.(ii)
Smoothness. For any (even unbounded) function h: S⟶X\L¯, k⟵rK, s=αk, x=hs and γ⟵r0,1ℓ, the distributions s,Hkx and s,γ are statistically indistinguishable in the security parameter κNA-ASPH has three modifications compared with ASPH in [33]: (1) the projection function α depends only on the hash key k; (2) Hkx=Hku,pw is determined by the hash key k, the first part of the ciphertext c=u,v and the plaintext pw; (3) for all x=hs∉L¯, the smoothness holds. The first modification here enables the protocol proposed to achieve two rounds of communication, and the latter two are prepared to prove the security of the proposed protocol.


## 3. A Two-Round 2PAKE Protocol

We now describe the proposed two-round 2PAKE, which is based on the protocol by Groce and Katz [9] and the splittable PKE scheme by Zhang and Yu [1].


### 3.1. Primitives

The primitives we use are the following: (1) a splittable labeled PKE schemeΣGen,Enc,Dec with an associatedϵ-NA-ASPH K,ℓ,ℍ=Hk:X⟶0,1ℓ,S,α:K⟶S, where the scheme Σ can be divided into function pair f,g; (2) error-correcting code ECC:0,1κ⟶0,1ℓ and the corresponding decoding algorithm ECC−1:0,1ℓ⟶0,1n. ECC can correct 2ϵ-fraction of errors. We assume that if ρ is sampled uniformly from 0,1ℓ, μ=ECC−1ρ is uniformly distributed in 0,1nprovided that μ≠⊥.


### 3.2. Initialization

The proposed protocol requires the public keypk of the schemeΣ, also known as the common reference string (CRS). We want to emphasize that during the execution of the entire protocol, no participant needs to know the private key corresponding to the public key.


### 3.3. Protocol Execution

A high-level depiction of the two-round 2PAKE protocol is given in Table2. We assume that the execution of the protocol is between client A and server C. Client A and server C share a password pwA∈D. When client A wants to initialize an authentication with the server C, A chooses a random tape r1⟵r0,1∗ for encryption and a hash key k1⟵rK for the NA-ASPH. Then, client A computes the projection key s1=αk1, sets label1=ACs1. And A computes c1=u1,v1=Σpk,label1,pwA,r1, where u1=fpk,pwA,r1 and v1=gpk,label1,pwA,r1. Finally, client A sends the message As1c1=u1,v1 to server C.Table 2
An honest execution of the two-round 2PAKE protocol.
Two-round 2PAKEClient AServer Cr1⟵r0,1∗k1⟵rKs1=αk1label1=ACs1u1=fpk,pwA,r1v1=gpk,label1,pwA,r1As1c1=u1,v1⟶k2⟵rK,k2∗⟵rKs2=αk2,s2∗=αk2∗rjτjskj⟵Hk2∗u1,pwAu2=fpk,pwA,rjtk=Hashs1,u2,pwA,rj⊕Hk2u1,pwAΔ=tk⊕ECCHk2∗u1,pwAlabel2=CAs1s2s2∗Δc1v2=gpk,label2,pwA,rjs2s2∗Δc2=u2,v2⟵tk′=Hk1u2,pwA⊕Hashs2,u1,pwA,r1H′=ECC−1tk′⊕ΔIfHamH′,Hashs2∗,u1,pwA,r1≤2ε/ℓriτiski⟵H′skAC=skiskCA=skjAfter receivingAs1c1 from client A, server C checks whether c1 is a valid ciphertext with respect to pk and label1=ACs1. If not, C rejects and the protocol aborts. Otherwise, C chooses hash keys k2⟵rK and k2∗⟵rK, and it computes projection keys s2=αk2, s2∗=αk2∗, rjrjskj⟵Hk2∗u1,pwA, u2=fpk,pwA,rj, tk=Hashs1,u2,pwA,rj⊕Hk2u1,pwA, and Δ=tk⊕ECCHk2∗u1,pwA. Server C then sets label2=CAs1s2s2∗Δc1and computes v2=gpk,label2,pwA,rj. Finally, server C sends to client A the message s2s2∗Δc2=u2,v2 and outputs skC=skj.Upon receivings2s2∗Δc2 from server C, client A checks whether c2 is a valid ciphertext with respect to pk andlabel2=CAs1s2s2∗Δc1. If not, client A rejects and the protocol aborts. Otherwise, client A computes tk′=Hk1u2,pwA⊕Hashs2,u1,pwA,r1, H′=ECC−1tk′⊕Δ. Then it checks whether the Hamming distance between H′ and Hashs2∗,u1,pwA,r1 is less than 2ε/ℓ. If not, client A rejects and the protocol aborts. Otherwise, client A sets riτiski⟵H′ and outputs skA=ski.


### 3.4. Correctness

After honestly executing the protocol, participants can obtain different session keys with negligible probability. First, according to the smoothness of NA-ASPH, we can conclude that bothHk1u2,pwA⊕Hashs2,u1,pwA,r1 and Hashs1,u2,pwA,rj⊕Hk2u1,pwA have at most ϵ-fraction of nonzeros. Therefore, tk⊕tk′ has at most 2ϵ-fraction of nonzeros. Then, we can obtain that H′=ECC−1tk′⊕Δ=ECC−1tk′oplus;tk⊕ECCHk2∗u1,pwA=Hk2∗u1,pwA as we assume that ECC can correct 2ϵ-fraction of errors. Second, we verify the validity of Hk2∗u1,pwA by checking whether the Hamming distance between H′ and Hashs2∗,u1,pwA,r1 is less than 2ε/ℓ. If it is the case, it holds that ski=skj. This completes the correctness argument.


### 3.5. Security

We now show that the above two-round 2PAKE is secure through the proof of the following theorem.Theorem 1.
IfΣGen,Enc,Dec is a splittable CCA-secure PKE scheme associated with an ϵ-NA-ASPH K,ℓ,ℍ=Hk:X⟶0,1ℓ,S,α:K⟶S and ECC:0,1κ⟶0,1ℓ is an error-correcting code which can correct 2ϵ-fraction of errors, then the protocol in Table 2 is a secure PAKE protocol.Proof.
SupposeA is a PPT attacker targeting this protocol. We estimate the advantage of adversary A through a series of experiments T0,T1,T2,⋯, where T0 represents the experiment in the real protocol. By analyzing the difference of adversary’s advantage between two adjacent experiments and defining the adversary’s advantage in the final experiment, we can finally get the adversary’s advantage in experiment T0, that is, the adversary’s advantage when attacking the real protocol. In experiment Ti, the event Successi indicates that adversary A succeeds, and the adversary’s advantage is defined as AdvA,iκ=2PrSuccessi−1.ExperimentT0. This experiment corresponds to the security experiment of the real protocol. Attackers can send all queries according to the regulations of the secure model, and the instance being queried will respond according to the actual protocol specifications.ExperimentT1. We change the simulation method of Execute query. The only difference from the experiment T0 is that the calculation method of tk′ is changed to tk′=Hk1u2,pwA⊕Hk2u1,pwA.Lemma 1.
IfK,ℓ,ℍ=Hk:X⟶0,1ℓ,S,α:K⟶S is an ϵ-NA-ASPH, and ECC:0,1κ⟶0,1ℓ is an error-correcting code which can correct 2ϵ-fraction of errors, then∣AdvA,1κ−AdvA,0κ∣≤neglκ.Proof.
Since the simulator knowsk1 and k2, it is easy to know that Lemma 1 holds according to the approximate correctness of NA-ASPH and the correctness of ECC.ExperimentT2. Compared with experiment T1, we modify the response to the Execute query as shown below. The ciphertext c1 is replaced by the encryption of the illegal password pwA′∉D, and tk′calculated by the client A is forced to be equal to the tk calculated by the server C, and other calculations remain unchanged.Lemma 2.
IfΣGen,Enc,Dec is a CCA-secure PKE scheme, then∣AdvA,2κ−AdvA,1κ∣≤neglκ.Proof.
We use standard hybrid argument to analyze the impact of replacingpwA with pwA′ on the adversary’s advantage. We set the number of queries to qexe and define a series of intermediate experiments. The first η queries in the experiment are same as those in T2, the remaining qexe−η queries are same as those in T1. The Send query conforms to the security model. It can be seen that experiments T10 and F1qexe are completely consistent with the experiments T1 and T2, respectively. If the lemma is not true, that is, the difference of A’s advantage between experiments T1 and T2 is not negligible, there must be some η such that the difference of A’s advantage between T1η−1 and T1η cannot be ignored. Then, we can construct an attacker M for the security of the encryption systemΣ so that it can successfully attack Σ with nonnegligible probability.We now construct an adversaryM who attacks the CCA-secure PKE scheme Σ in the following way: given the public key pk, the adversary M simulates the entire experiment for A according to the experiment T1η, including selecting random passwords for the participants and selecting the random bit b for A in the Test query. When answering the Execute query, M sends pwA,pwA′ as its challenge plaintext pair to M’s own challenger. After receiving the challenge ciphertext c1′,M replaces c1 with c1′ in the Execute query. Finally, M checks whether A guesses the random bit in the Test query. If A succeeds, M outputs 1; otherwise, M outputs 0.LetEventΣpwAM denote that M obtains the challenge ciphertext of the real password pwA and outputs 1 at the end of the experiment. Let EventΣpwA′M indicate that Mobtains the challenge ciphertext of the invalid password pwA′ and outputs 1 at the end of the experiment. For the ηth query, that is, M gets the challenge ciphertext of the real password pwA, the environment provided by M for the protocol attacker A is the same as experiment T1η−1. Therefore, in experiment T1η−1, the probability that M outputs 1 is exactly the same as A’s success probability (PrSuccessT1η−1), i.e., PrEventΣpwAM=1=PrSuccessT1η−1. Similarly, when M gets the challenge ciphertext of the invalid password pwA′, the probability that M outputs 1 is the probability that A succeeds (PrSuccessT1η) in attacking the protocol in experiment T1η, namely PrEventΣpwA′M=1=PrSuccessT1η. Let AdvΣ,MIND−CCAκ be M’s advantage in attacking the encryption system Σ, then
(4)AdvT1ηκ−AdvT1η−1κ=2PrSuccessT1η−PrSuccessT1η−1=2PrEventΣpwA′M=1−PrEventΣpwAM=1=2AdvΣ,MIND−CCAκ.According to the CCA security of encryption systemΣ, the lemma holds. We emphasize that only the CPA security of Σ is actually used here.ExperimentT3. We change the response to the Execute query: (1) change the calculation method of tk to tk=Hk1u2,pwA⊕Hk2u1,pwA. (2) Replace the ciphertext c2 with the encryption of an illegal password pwA′∉D.Lemma 3.
IfΣGen,Enc,Dec is a splittable CCA-secure PKE scheme associated with and ϵ-NA-ASPH, and ECC:0,1κ⟶0,1ℓ is an error-correcting code which can correct 2ϵ-fraction of errors, then∣AdvA,3κ−AdvA,2κ∣≤neglκ.Proof.
This lemma is shown through a series of experiments similar toT1, T2, and T3. In addition, this experiment utilizes the modified CCA security experiment shown in Section 2.3 instead of the standard CCA security experiment.ExperimentT4. We continue to modify the response to the Execute query as follows. We set rjτjskj to a random string of the appropriate length and the riτiski calculated by client A to be equal to the rjτjskj calculated by server C.Lemma 4.
IfK,ℓ,ℍ=Hk:X⟶0,1ℓ,S,α:K⟶S is an ε-NA-ASPH, then ∣AdvA,4κ−AdvA,3κ∣≤neglκ.Proof.
This comes from the smoothness of NA-ASPH, because when responding to an Execute query inT3, the hash function Hk is always applied to pwA′∉Dn, so even if s is given, the output is statistically close to uniform. In addition, in T3 and T4 the string riτiski used by the client is equal to the string rjτjskj computed by the server.Note that the Execute query inT4 will generate a random session key and random transcripts, which have nothing to do with the actual password of any participant. In the following experiment, we begin to modify the responses to the Send queries. Let Send0A,i,C represent the “start” message, which enables the client instance ΠAi to initiate authentication with the server S. Note that when calculating the number of communication rounds, we ignore the “start” message like other related research. Let Send1C,j,msg1=s1c1=u1,v1 represent the first message of the protocol sent to the server instance Πcj. Let Send2A,i,msg2=s2s2∗Δc2=u1,v1 denote the second message of the protocol sent to the client instance ΠAi. We also record the secret key skpk, corresponding to the public key in the generated CRS.Now, we make some explanations for msg1 and msg2. The output ofsend0 oracle or the input of send1 oracle are msg1. Similarly, msg2 may be the output of send1 oracle or the output of send2 oracle. If msg1/msg2 is output by a previous send0/send1 oracle, then we call msg1/msg2 oracle-generated.ExperimentT5. In experiment T5, we change the response to send1 queries. If msg1 is oracle-generated, the experiment is the same as T4. Otherwise, we set label1=ACs1. We check the validity of c1 according to label1 and pk.
(i)
Ifc1 is invalid, the experiment just aborts as the real protocol(ii)
Else, we can getpwAad by decrypting c1, because we have skpk. If pwAad=pwA, we just declare that adversary A succeeds, and the experiment is terminated. If pwAad≠pwA, we set tk and Hk2∗u1,pwA computed by the server as random tapes of the appropriate lengthLemma 5.
IfK,ℓ,ℍ=Hk:X⟶0,1ℓ,S,α:K⟶S is an ϵ-NA-ASPH, then AdvA,4κ≤AdvA,5κ+neglκ.Proof.
In the actual protocol, server C simply refuses, and the protocol terminates whenc1 is invalid. Therefore, if msg1 is oracle-generated, or msg1 is not oracle-generated and c1 is invalid, then experiment T5 is consistent with experiment T4. Now, we only need to consider the case where msg1 is not oracle-generated and c1 is valid.
(i)
IfpwAad=pwA, adversary A succeeds. Note that this only improves the adversary’s advantage(ii)
IfpwAad≠pwA, tk and Hk2∗u1,pwA computed by the server are both set to random tapes. From the view of adversary A, there is no difference between these changes. First, as c1,pwAad∉L¯, in the view of A, both tk=Hashs1,u2,pwA,rj⊕Hk2u1,pwAand Δ=tk⊕ECCHk2∗u1,pwAad are statistically indistinguishable from random uniform distribution. This can be derived directly from the smoothness of NA-ASPH. Similarly, from the view of A, rjτjskj=Hk2∗u1,pwAad is also statistically indistinguishable from random uniform distribution. Therefore, pwAad≠pwA only introduces a negligible difference in experiment T5.Finally, we obtain thatAdvA,4κ≤AdvA,5κ+neglκ.ExperimentT6. In experiment T6, let msg1 be the output from a previous Send0 query A,i,C (note that such a query must exist). Send2 query is handled as follows: If msg2 is oracle-generated by a previous Send1 query, the experiment is similar to T5 except for (1) computing tk′ as tk′=Hk1u2,pwA⊕Hk2u1,pwA and (2) setting riτiski=rjτjskj. Otherwise, we set label2=CAs1s2s2∗Δc1. We check the validity of c2 according to label2 and pk.
(i)
Ifc2 is invalid, the experiment just aborts as the real protocol(ii)
Else, we can obtainpwAad similar to T5. If pwAad=pwA, we declare that A succeeds and the experiment terminates. Otherwise, if ΠAi is accepted, let riτiski to be a random tape of appropriate lengthLemma 6.
IfK,ℓ,ℍ=Hk:X⟶0,1ℓ,S,α:K⟶S is an ϵ-NA-ASPH, and ECC:0,1κ⟶0,1ℓ is an error-correcting code which can correct 2ϵ-fraction of errors, then AdvA,5κ≤AdvA,6κ+neglκ.Proof.
We prove different situations separately. First, if both msg1 and msg2 are oracle-generated, the simulator will know the hash keysk1 and k2. According to the smoothness of the NA-ASPH, the changes in computing tk′ andriτiski are just conceptual (in this case, it holds that riτiski=rjτjskj in both T5 and T6). Second, if msg2 is not oracle-generated, the simulator sets label2=CAs1s2s2∗Δc1 and then uses label2 and pk to check whether c2 is valid. If not, T5 and T6 are the same as the real protocol. Otherwise, the simulator uses skpk to decrypt c2 and obtains pwAad.
(i)
IfpwAad=pwA, adversary A succeeds. Note that this just improves the adversary advantage(ii)
IfpwAad≠pwA, according to section 2.4, label2,c2,pwAad does not belong to L¯. Then, by the smoothness of NA-ASPH, Hk1u2,pwA and thus tk′=Hk1u2,pwA⊕Hk2u1,pwA are both statistically close to uniform over 0,1ℓ. Furthermore, we have riτiskiriτiski⟵H′=ECC−1tk′⊕Δ is statistically close to uniform over 0,1κ. Therefore, the modifications of pwAad≠pwA bring a negligible statistical difference. Note that the output of ECC−1tk′⊕Δ may be ⊥. In this case, client A rejectsExperimentT7. Compared with experiment T6, we modify the response to a Send0 query. The only difference is that we use pwA′∉D to compute c1.Lemma 7.
IfΣGen,Enc,Dec is a CCA-secure PKE scheme, then ∣AdvA,7κ−AdvA,6κ∣≤neglκ.Proof.
We analyze the impact of replacingpwA with pwA′∉D on the adversary’s advantage similar to T2. But for the sake of simplicity, we consider that A only executes a single Send0 query. The correctness still holds according to standard hybrid argument. If the lemma is not true, that is, the difference of A’s advantage between experiments T6 and T7 is not negligible, then an attacker M can be constructed for the security experiment of the encryption systemΣ, which can successfully attack Σ with nonnegligible probability.We now construct an adversaryM who attacks the CCA-secure PKE scheme Σ in the following way: given the public keypk, the adversary M simulates the entire experiment for A according to experiment T7, including selecting random passwords for the participants and selecting the random bit b for A in the Test query. When answering the Send0 query, M will send pwA,pwA′ as its challenge plaintext pair to M’s own challenger. After receiving the challenge ciphertext c1′, M replaces c1 with c1′ in the Send0 query. Finally, M checks whether A guesses the random bit in the Test query. If A succeeds, M outputs 1; otherwise, M outputs 0.LetEventΣpwAM denote that M gets the challenge ciphertext of the real password pwA and outputs 1 at the end of the experiment. Let EventΣpwA′M represent that M gets the challenge ciphertext of the invalid password pwA′ and outputs 1 at the end of the experiment. If M gets the challenge ciphertext of the real password pwA, the environment provided by M for the protocol adversary A is the same as experiment T6. Therefore, the probability that M outputs 1 is exactly the same as A’s success probability (PrSuccessT6) in experiment T6, i.e., PrEventΣpwAM=1=PrSuccessT6. Similarly, PrEventΣpwA′M=1=PrSuccessT7. Let AdvΣ,MIND−CCAκ be M’s advantage in attacking the encryption system Σ, then
(4)AdvT1ηκ−AdvT1η−1κ=2PrSuccessT1η−PrSuccessT1η−1=2PrEventΣpwA′M=1−PrEventΣpwAM=1=2AdvΣ,MIND−CCAκ.According to the CCA security of the encryption systemΣ, the lemma holds.ExperimentT8. Experiment T8 is similar to T7 except that if msg1 is oracle-generated: (1) tk computed by the server is set to be Hk1u2,pwA⊕Hk2u1,pwA; (2) a random string rjτjskj of appropriate length is set for ΠCj.Lemma 8.
IfΣGen,Enc,Dec is a splittable CCA-secure PKE scheme associated with an ϵ-NA-ASPH K,ℓ,ℍ=Hk:X⟶0,1ℓ,S,α:K⟶S, and ECC:0,1κ⟶0,1ℓ is an error-correcting code which can correct 2ϵ-fraction of errors, then ∣AdvA,8κ−AdvA,7κ∣≤neglκ.Proof.
First, if msg1 is oracle-generated, the simulator has hash keysk1 and k2; thus, it can compute tk=Hk1u2,pwA⊕Hk2u1,pwA.Secondly, since the ciphertext c1 is the encryption of pwA′∉D, Hk2u1,pwA and tk are statistically close to uniform. Similarly, rjτjskj (rjτjskj⟵Hk2∗u1,pwA) is also statistically close to uniform. Thus, we have that the modifications here introduce only a statistically negligible difference. Therefore, AdvA,8κ−AdvA,7κ≤neglκ.ExperimentT9. For the final experiment, we again modify the response to the Send1 queries. If msg1 is oracle-generated, the ciphertext c2 is now computed as the encryption of pwA′∉D.Lemma 9.
IfΣGen,Enc,Dec is a splittable CCA-secure PKE scheme, then AdvA,9κ−AdvA,8κ≤neglκ.Proof.
We analyze the impact of replacingpwA with pwA′∉D on the adversary’s advantage. We consider that A only executes a single Send1 query similar to T7. Now, we show that if any PPT adversary A can distinguish these two experiments, then we can construct an attacker M breaking the CCA security experiment (in Section 2.3) of the CCA encryption systemΣ with a nonnegligible probability.We now construct an adversaryM interacting with A in T8 to attack the CCA-secure PKE scheme Σ in the following way: given the public keypk, the adversary M simulates the entire experiment, including selecting random passwords for the participants and selecting the random bit b for A in the Test query. When answering the Send1 query, M will send pwA,pwA′ as its challenge plaintext pair to M’s own challenger. After receiving the challenge ciphertext c1′, M replaces c1 with c1′ in the Send1 query. When M needs to decrypt some valid ciphertext c2′, it will send label2′,c2′ to its own challenger to obtain the corresponding pwA′. Finally, M checks whether A guesses the random bit correctly in the Test query. If A succeeds, M outputs 1; otherwise, M outputs 0.LetEventΣpwAM/EventΣpwA′M denote that M gets the challenge ciphertext of the password pwA/pwA′ and outputs 1. If M gets the challenge ciphertext of pwA/pwA′, the environment provided by M for the protocol adversary A is the same as experiment T8/T9. Therefore, we have PrEventΣpwAM=1=PrSuccessT8 and PrEventΣpwA′M=1=PrSuccessT9. Let AdvΣ,MIND−CCAκ be M’s advantage in attacking the encryption system Σ, then
(6)AdvT9κ−AdvT8κ=2PrSuccessT9−PrSuccessT8=2PrEventΣpwA′M=1−PrEventΣpwAM=1=2AdvΣ,MIND−CCAκ.According to the CCA security of encryption systemΣ, the lemma holds.So far, we have completed the modification of Send query. We now analyze the adversary’s advantage in the final experimentT9. If adversary A cannot guess the correct password, A can only rely on guessing the random bit b in the Test query to succeed. Note that all session keys are replaced with random tapes, so the probability of A guessing b is only 1/2. At the same time, as described in experiments T5 and T6, the adversary A can succeed by guessing the password, and the probability of each correct guess is at most 1/D, so the ultimate advantage of adversary A is at most qsend/D. Combining the conclusions of Lemma 1 to Lemma 9, we can see that AdvT0n≤qsend/D+neglκ, that is, the conclusion of Theorem 1 is established.


## 3.1. Primitives

The primitives we use are the following: (1) a splittable labeled PKE schemeΣGen,Enc,Dec with an associatedϵ-NA-ASPH K,ℓ,ℍ=Hk:X⟶0,1ℓ,S,α:K⟶S, where the scheme Σ can be divided into function pair f,g; (2) error-correcting code ECC:0,1κ⟶0,1ℓ and the corresponding decoding algorithm ECC−1:0,1ℓ⟶0,1n. ECC can correct 2ϵ-fraction of errors. We assume that if ρ is sampled uniformly from 0,1ℓ, μ=ECC−1ρ is uniformly distributed in 0,1nprovided that μ≠⊥.


## 3.2. Initialization

The proposed protocol requires the public keypk of the schemeΣ, also known as the common reference string (CRS). We want to emphasize that during the execution of the entire protocol, no participant needs to know the private key corresponding to the public key.


## 3.3. Protocol Execution

A high-level depiction of the two-round 2PAKE protocol is given in Table2. We assume that the execution of the protocol is between client A and server C. Client A and server C share a password pwA∈D. When client A wants to initialize an authentication with the server C, A chooses a random tape r1⟵r0,1∗ for encryption and a hash key k1⟵rK for the NA-ASPH. Then, client A computes the projection key s1=αk1, sets label1=ACs1. And A computes c1=u1,v1=Σpk,label1,pwA,r1, where u1=fpk,pwA,r1 and v1=gpk,label1,pwA,r1. Finally, client A sends the message As1c1=u1,v1 to server C.Table 2
An honest execution of the two-round 2PAKE protocol.
Two-round 2PAKEClient AServer Cr1⟵r0,1∗k1⟵rKs1=αk1label1=ACs1u1=fpk,pwA,r1v1=gpk,label1,pwA,r1As1c1=u1,v1⟶k2⟵rK,k2∗⟵rKs2=αk2,s2∗=αk2∗rjτjskj⟵Hk2∗u1,pwAu2=fpk,pwA,rjtk=Hashs1,u2,pwA,rj⊕Hk2u1,pwAΔ=tk⊕ECCHk2∗u1,pwAlabel2=CAs1s2s2∗Δc1v2=gpk,label2,pwA,rjs2s2∗Δc2=u2,v2⟵tk′=Hk1u2,pwA⊕Hashs2,u1,pwA,r1H′=ECC−1tk′⊕ΔIfHamH′,Hashs2∗,u1,pwA,r1≤2ε/ℓriτiski⟵H′skAC=skiskCA=skjAfter receivingAs1c1 from client A, server C checks whether c1 is a valid ciphertext with respect to pk and label1=ACs1. If not, C rejects and the protocol aborts. Otherwise, C chooses hash keys k2⟵rK and k2∗⟵rK, and it computes projection keys s2=αk2, s2∗=αk2∗, rjrjskj⟵Hk2∗u1,pwA, u2=fpk,pwA,rj, tk=Hashs1,u2,pwA,rj⊕Hk2u1,pwA, and Δ=tk⊕ECCHk2∗u1,pwA. Server C then sets label2=CAs1s2s2∗Δc1and computes v2=gpk,label2,pwA,rj. Finally, server C sends to client A the message s2s2∗Δc2=u2,v2 and outputs skC=skj.Upon receivings2s2∗Δc2 from server C, client A checks whether c2 is a valid ciphertext with respect to pk andlabel2=CAs1s2s2∗Δc1. If not, client A rejects and the protocol aborts. Otherwise, client A computes tk′=Hk1u2,pwA⊕Hashs2,u1,pwA,r1, H′=ECC−1tk′⊕Δ. Then it checks whether the Hamming distance between H′ and Hashs2∗,u1,pwA,r1 is less than 2ε/ℓ. If not, client A rejects and the protocol aborts. Otherwise, client A sets riτiski⟵H′ and outputs skA=ski.


## 3.4. Correctness

After honestly executing the protocol, participants can obtain different session keys with negligible probability. First, according to the smoothness of NA-ASPH, we can conclude that bothHk1u2,pwA⊕Hashs2,u1,pwA,r1 and Hashs1,u2,pwA,rj⊕Hk2u1,pwA have at most ϵ-fraction of nonzeros. Therefore, tk⊕tk′ has at most 2ϵ-fraction of nonzeros. Then, we can obtain that H′=ECC−1tk′⊕Δ=ECC−1tk′oplus;tk⊕ECCHk2∗u1,pwA=Hk2∗u1,pwA as we assume that ECC can correct 2ϵ-fraction of errors. Second, we verify the validity of Hk2∗u1,pwA by checking whether the Hamming distance between H′ and Hashs2∗,u1,pwA,r1 is less than 2ε/ℓ. If it is the case, it holds that ski=skj. This completes the correctness argument.


## 3.5. Security

We now show that the above two-round 2PAKE is secure through the proof of the following theorem.Theorem 1.
IfΣGen,Enc,Dec is a splittable CCA-secure PKE scheme associated with an ϵ-NA-ASPH K,ℓ,ℍ=Hk:X⟶0,1ℓ,S,α:K⟶S and ECC:0,1κ⟶0,1ℓ is an error-correcting code which can correct 2ϵ-fraction of errors, then the protocol in Table 2 is a secure PAKE protocol.Proof.
SupposeA is a PPT attacker targeting this protocol. We estimate the advantage of adversary A through a series of experiments T0,T1,T2,⋯, where T0 represents the experiment in the real protocol. By analyzing the difference of adversary’s advantage between two adjacent experiments and defining the adversary’s advantage in the final experiment, we can finally get the adversary’s advantage in experiment T0, that is, the adversary’s advantage when attacking the real protocol. In experiment Ti, the event Successi indicates that adversary A succeeds, and the adversary’s advantage is defined as AdvA,iκ=2PrSuccessi−1.ExperimentT0. This experiment corresponds to the security experiment of the real protocol. Attackers can send all queries according to the regulations of the secure model, and the instance being queried will respond according to the actual protocol specifications.ExperimentT1. We change the simulation method of Execute query. The only difference from the experiment T0 is that the calculation method of tk′ is changed to tk′=Hk1u2,pwA⊕Hk2u1,pwA.Lemma 1.
IfK,ℓ,ℍ=Hk:X⟶0,1ℓ,S,α:K⟶S is an ϵ-NA-ASPH, and ECC:0,1κ⟶0,1ℓ is an error-correcting code which can correct 2ϵ-fraction of errors, then∣AdvA,1κ−AdvA,0κ∣≤neglκ.Proof.
Since the simulator knowsk1 and k2, it is easy to know that Lemma 1 holds according to the approximate correctness of NA-ASPH and the correctness of ECC.ExperimentT2. Compared with experiment T1, we modify the response to the Execute query as shown below. The ciphertext c1 is replaced by the encryption of the illegal password pwA′∉D, and tk′calculated by the client A is forced to be equal to the tk calculated by the server C, and other calculations remain unchanged.Lemma 2.
IfΣGen,Enc,Dec is a CCA-secure PKE scheme, then∣AdvA,2κ−AdvA,1κ∣≤neglκ.Proof.
We use standard hybrid argument to analyze the impact of replacingpwA with pwA′ on the adversary’s advantage. We set the number of queries to qexe and define a series of intermediate experiments. The first η queries in the experiment are same as those in T2, the remaining qexe−η queries are same as those in T1. The Send query conforms to the security model. It can be seen that experiments T10 and F1qexe are completely consistent with the experiments T1 and T2, respectively. If the lemma is not true, that is, the difference of A’s advantage between experiments T1 and T2 is not negligible, there must be some η such that the difference of A’s advantage between T1η−1 and T1η cannot be ignored. Then, we can construct an attacker M for the security of the encryption systemΣ so that it can successfully attack Σ with nonnegligible probability.We now construct an adversaryM who attacks the CCA-secure PKE scheme Σ in the following way: given the public key pk, the adversary M simulates the entire experiment for A according to the experiment T1η, including selecting random passwords for the participants and selecting the random bit b for A in the Test query. When answering the Execute query, M sends pwA,pwA′ as its challenge plaintext pair to M’s own challenger. After receiving the challenge ciphertext c1′,M replaces c1 with c1′ in the Execute query. Finally, M checks whether A guesses the random bit in the Test query. If A succeeds, M outputs 1; otherwise, M outputs 0.LetEventΣpwAM denote that M obtains the challenge ciphertext of the real password pwA and outputs 1 at the end of the experiment. Let EventΣpwA′M indicate that Mobtains the challenge ciphertext of the invalid password pwA′ and outputs 1 at the end of the experiment. For the ηth query, that is, M gets the challenge ciphertext of the real password pwA, the environment provided by M for the protocol attacker A is the same as experiment T1η−1. Therefore, in experiment T1η−1, the probability that M outputs 1 is exactly the same as A’s success probability (PrSuccessT1η−1), i.e., PrEventΣpwAM=1=PrSuccessT1η−1. Similarly, when M gets the challenge ciphertext of the invalid password pwA′, the probability that M outputs 1 is the probability that A succeeds (PrSuccessT1η) in attacking the protocol in experiment T1η, namely PrEventΣpwA′M=1=PrSuccessT1η. Let AdvΣ,MIND−CCAκ be M’s advantage in attacking the encryption system Σ, then
(4)AdvT1ηκ−AdvT1η−1κ=2PrSuccessT1η−PrSuccessT1η−1=2PrEventΣpwA′M=1−PrEventΣpwAM=1=2AdvΣ,MIND−CCAκ.According to the CCA security of encryption systemΣ, the lemma holds. We emphasize that only the CPA security of Σ is actually used here.ExperimentT3. We change the response to the Execute query: (1) change the calculation method of tk to tk=Hk1u2,pwA⊕Hk2u1,pwA. (2) Replace the ciphertext c2 with the encryption of an illegal password pwA′∉D.Lemma 3.
IfΣGen,Enc,Dec is a splittable CCA-secure PKE scheme associated with and ϵ-NA-ASPH, and ECC:0,1κ⟶0,1ℓ is an error-correcting code which can correct 2ϵ-fraction of errors, then∣AdvA,3κ−AdvA,2κ∣≤neglκ.Proof.
This lemma is shown through a series of experiments similar toT1, T2, and T3. In addition, this experiment utilizes the modified CCA security experiment shown in Section 2.3 instead of the standard CCA security experiment.ExperimentT4. We continue to modify the response to the Execute query as follows. We set rjτjskj to a random string of the appropriate length and the riτiski calculated by client A to be equal to the rjτjskj calculated by server C.Lemma 4.
IfK,ℓ,ℍ=Hk:X⟶0,1ℓ,S,α:K⟶S is an ε-NA-ASPH, then ∣AdvA,4κ−AdvA,3κ∣≤neglκ.Proof.
This comes from the smoothness of NA-ASPH, because when responding to an Execute query inT3, the hash function Hk is always applied to pwA′∉Dn, so even if s is given, the output is statistically close to uniform. In addition, in T3 and T4 the string riτiski used by the client is equal to the string rjτjskj computed by the server.Note that the Execute query inT4 will generate a random session key and random transcripts, which have nothing to do with the actual password of any participant. In the following experiment, we begin to modify the responses to the Send queries. Let Send0A,i,C represent the “start” message, which enables the client instance ΠAi to initiate authentication with the server S. Note that when calculating the number of communication rounds, we ignore the “start” message like other related research. Let Send1C,j,msg1=s1c1=u1,v1 represent the first message of the protocol sent to the server instance Πcj. Let Send2A,i,msg2=s2s2∗Δc2=u1,v1 denote the second message of the protocol sent to the client instance ΠAi. We also record the secret key skpk, corresponding to the public key in the generated CRS.Now, we make some explanations for msg1 and msg2. The output ofsend0 oracle or the input of send1 oracle are msg1. Similarly, msg2 may be the output of send1 oracle or the output of send2 oracle. If msg1/msg2 is output by a previous send0/send1 oracle, then we call msg1/msg2 oracle-generated.ExperimentT5. In experiment T5, we change the response to send1 queries. If msg1 is oracle-generated, the experiment is the same as T4. Otherwise, we set label1=ACs1. We check the validity of c1 according to label1 and pk.
(i)
Ifc1 is invalid, the experiment just aborts as the real protocol(ii)
Else, we can getpwAad by decrypting c1, because we have skpk. If pwAad=pwA, we just declare that adversary A succeeds, and the experiment is terminated. If pwAad≠pwA, we set tk and Hk2∗u1,pwA computed by the server as random tapes of the appropriate lengthLemma 5.
IfK,ℓ,ℍ=Hk:X⟶0,1ℓ,S,α:K⟶S is an ϵ-NA-ASPH, then AdvA,4κ≤AdvA,5κ+neglκ.Proof.
In the actual protocol, server C simply refuses, and the protocol terminates whenc1 is invalid. Therefore, if msg1 is oracle-generated, or msg1 is not oracle-generated and c1 is invalid, then experiment T5 is consistent with experiment T4. Now, we only need to consider the case where msg1 is not oracle-generated and c1 is valid.
(i)
IfpwAad=pwA, adversary A succeeds. Note that this only improves the adversary’s advantage(ii)
IfpwAad≠pwA, tk and Hk2∗u1,pwA computed by the server are both set to random tapes. From the view of adversary A, there is no difference between these changes. First, as c1,pwAad∉L¯, in the view of A, both tk=Hashs1,u2,pwA,rj⊕Hk2u1,pwAand Δ=tk⊕ECCHk2∗u1,pwAad are statistically indistinguishable from random uniform distribution. This can be derived directly from the smoothness of NA-ASPH. Similarly, from the view of A, rjτjskj=Hk2∗u1,pwAad is also statistically indistinguishable from random uniform distribution. Therefore, pwAad≠pwA only introduces a negligible difference in experiment T5.Finally, we obtain thatAdvA,4κ≤AdvA,5κ+neglκ.ExperimentT6. In experiment T6, let msg1 be the output from a previous Send0 query A,i,C (note that such a query must exist). Send2 query is handled as follows: If msg2 is oracle-generated by a previous Send1 query, the experiment is similar to T5 except for (1) computing tk′ as tk′=Hk1u2,pwA⊕Hk2u1,pwA and (2) setting riτiski=rjτjskj. Otherwise, we set label2=CAs1s2s2∗Δc1. We check the validity of c2 according to label2 and pk.
(i)
Ifc2 is invalid, the experiment just aborts as the real protocol(ii)
Else, we can obtainpwAad similar to T5. If pwAad=pwA, we declare that A succeeds and the experiment terminates. Otherwise, if ΠAi is accepted, let riτiski to be a random tape of appropriate lengthLemma 6.
IfK,ℓ,ℍ=Hk:X⟶0,1ℓ,S,α:K⟶S is an ϵ-NA-ASPH, and ECC:0,1κ⟶0,1ℓ is an error-correcting code which can correct 2ϵ-fraction of errors, then AdvA,5κ≤AdvA,6κ+neglκ.Proof.
We prove different situations separately. First, if both msg1 and msg2 are oracle-generated, the simulator will know the hash keysk1 and k2. According to the smoothness of the NA-ASPH, the changes in computing tk′ andriτiski are just conceptual (in this case, it holds that riτiski=rjτjskj in both T5 and T6). Second, if msg2 is not oracle-generated, the simulator sets label2=CAs1s2s2∗Δc1 and then uses label2 and pk to check whether c2 is valid. If not, T5 and T6 are the same as the real protocol. Otherwise, the simulator uses skpk to decrypt c2 and obtains pwAad.
(i)
IfpwAad=pwA, adversary A succeeds. Note that this just improves the adversary advantage(ii)
IfpwAad≠pwA, according to section 2.4, label2,c2,pwAad does not belong to L¯. Then, by the smoothness of NA-ASPH, Hk1u2,pwA and thus tk′=Hk1u2,pwA⊕Hk2u1,pwA are both statistically close to uniform over 0,1ℓ. Furthermore, we have riτiskiriτiski⟵H′=ECC−1tk′⊕Δ is statistically close to uniform over 0,1κ. Therefore, the modifications of pwAad≠pwA bring a negligible statistical difference. Note that the output of ECC−1tk′⊕Δ may be ⊥. In this case, client A rejectsExperimentT7. Compared with experiment T6, we modify the response to a Send0 query. The only difference is that we use pwA′∉D to compute c1.Lemma 7.
IfΣGen,Enc,Dec is a CCA-secure PKE scheme, then ∣AdvA,7κ−AdvA,6κ∣≤neglκ.Proof.
We analyze the impact of replacingpwA with pwA′∉D on the adversary’s advantage similar to T2. But for the sake of simplicity, we consider that A only executes a single Send0 query. The correctness still holds according to standard hybrid argument. If the lemma is not true, that is, the difference of A’s advantage between experiments T6 and T7 is not negligible, then an attacker M can be constructed for the security experiment of the encryption systemΣ, which can successfully attack Σ with nonnegligible probability.We now construct an adversaryM who attacks the CCA-secure PKE scheme Σ in the following way: given the public keypk, the adversary M simulates the entire experiment for A according to experiment T7, including selecting random passwords for the participants and selecting the random bit b for A in the Test query. When answering the Send0 query, M will send pwA,pwA′ as its challenge plaintext pair to M’s own challenger. After receiving the challenge ciphertext c1′, M replaces c1 with c1′ in the Send0 query. Finally, M checks whether A guesses the random bit in the Test query. If A succeeds, M outputs 1; otherwise, M outputs 0.LetEventΣpwAM denote that M gets the challenge ciphertext of the real password pwA and outputs 1 at the end of the experiment. Let EventΣpwA′M represent that M gets the challenge ciphertext of the invalid password pwA′ and outputs 1 at the end of the experiment. If M gets the challenge ciphertext of the real password pwA, the environment provided by M for the protocol adversary A is the same as experiment T6. Therefore, the probability that M outputs 1 is exactly the same as A’s success probability (PrSuccessT6) in experiment T6, i.e., PrEventΣpwAM=1=PrSuccessT6. Similarly, PrEventΣpwA′M=1=PrSuccessT7. Let AdvΣ,MIND−CCAκ be M’s advantage in attacking the encryption system Σ, then
(4)AdvT1ηκ−AdvT1η−1κ=2PrSuccessT1η−PrSuccessT1η−1=2PrEventΣpwA′M=1−PrEventΣpwAM=1=2AdvΣ,MIND−CCAκ.According to the CCA security of the encryption systemΣ, the lemma holds.ExperimentT8. Experiment T8 is similar to T7 except that if msg1 is oracle-generated: (1) tk computed by the server is set to be Hk1u2,pwA⊕Hk2u1,pwA; (2) a random string rjτjskj of appropriate length is set for ΠCj.Lemma 8.
IfΣGen,Enc,Dec is a splittable CCA-secure PKE scheme associated with an ϵ-NA-ASPH K,ℓ,ℍ=Hk:X⟶0,1ℓ,S,α:K⟶S, and ECC:0,1κ⟶0,1ℓ is an error-correcting code which can correct 2ϵ-fraction of errors, then ∣AdvA,8κ−AdvA,7κ∣≤neglκ.Proof.
First, if msg1 is oracle-generated, the simulator has hash keysk1 and k2; thus, it can compute tk=Hk1u2,pwA⊕Hk2u1,pwA.Secondly, since the ciphertext c1 is the encryption of pwA′∉D, Hk2u1,pwA and tk are statistically close to uniform. Similarly, rjτjskj (rjτjskj⟵Hk2∗u1,pwA) is also statistically close to uniform. Thus, we have that the modifications here introduce only a statistically negligible difference. Therefore, AdvA,8κ−AdvA,7κ≤neglκ.ExperimentT9. For the final experiment, we again modify the response to the Send1 queries. If msg1 is oracle-generated, the ciphertext c2 is now computed as the encryption of pwA′∉D.Lemma 9.
IfΣGen,Enc,Dec is a splittable CCA-secure PKE scheme, then AdvA,9κ−AdvA,8κ≤neglκ.Proof.
We analyze the impact of replacingpwA with pwA′∉D on the adversary’s advantage. We consider that A only executes a single Send1 query similar to T7. Now, we show that if any PPT adversary A can distinguish these two experiments, then we can construct an attacker M breaking the CCA security experiment (in Section 2.3) of the CCA encryption systemΣ with a nonnegligible probability.We now construct an adversaryM interacting with A in T8 to attack the CCA-secure PKE scheme Σ in the following way: given the public keypk, the adversary M simulates the entire experiment, including selecting random passwords for the participants and selecting the random bit b for A in the Test query. When answering the Send1 query, M will send pwA,pwA′ as its challenge plaintext pair to M’s own challenger. After receiving the challenge ciphertext c1′, M replaces c1 with c1′ in the Send1 query. When M needs to decrypt some valid ciphertext c2′, it will send label2′,c2′ to its own challenger to obtain the corresponding pwA′. Finally, M checks whether A guesses the random bit correctly in the Test query. If A succeeds, M outputs 1; otherwise, M outputs 0.LetEventΣpwAM/EventΣpwA′M denote that M gets the challenge ciphertext of the password pwA/pwA′ and outputs 1. If M gets the challenge ciphertext of pwA/pwA′, the environment provided by M for the protocol adversary A is the same as experiment T8/T9. Therefore, we have PrEventΣpwAM=1=PrSuccessT8 and PrEventΣpwA′M=1=PrSuccessT9. Let AdvΣ,MIND−CCAκ be M’s advantage in attacking the encryption system Σ, then
(6)AdvT9κ−AdvT8κ=2PrSuccessT9−PrSuccessT8=2PrEventΣpwA′M=1−PrEventΣpwAM=1=2AdvΣ,MIND−CCAκ.According to the CCA security of encryption systemΣ, the lemma holds.So far, we have completed the modification of Send query. We now analyze the adversary’s advantage in the final experimentT9. If adversary A cannot guess the correct password, A can only rely on guessing the random bit b in the Test query to succeed. Note that all session keys are replaced with random tapes, so the probability of A guessing b is only 1/2. At the same time, as described in experiments T5 and T6, the adversary A can succeed by guessing the password, and the probability of each correct guess is at most 1/D, so the ultimate advantage of adversary A is at most qsend/D. Combining the conclusions of Lemma 1 to Lemma 9, we can see that AdvT0n≤qsend/D+neglκ, that is, the conclusion of Theorem 1 is established.


## 4. A Two-Round 3PAKE Protocol

In this section, we propose a two-round 3PAKE protocol based on the two-round 2PAKE protocol in Section3. Client A and server C share the password pwA, and client B and server C share the password pwB. The primitives and the initialization process here are the same as the two-round 2PAKE protocol above. The clients and server implement the honest 3PAKE protocol on lattice, as shown in Table 3.Table 3
An honest execution of two-round 3PAKE protocol.
Two-round 3PAKE protocolClient AServerClient Br1A⟵r0,1∗k1A⟵rKs1A=αk1Alabel1A=ABSs1Au1A=fpk,pwA,r1Av1A=gpk,label1A,pwA,r1Ar1B⟵r0,1∗k1B⟵rKs1B=αk1Blabel1B=BASs1Bu1B=fpk,pwB,r1Bv1B=gpk,label1B,pwB,r1BABSs1Ac1A=u1A,v1A⟶BASs1Bc1B=u1B,v1B⟵k2A⟵rK,k2A∗⟵rKs2A=αk2A,s2A∗=αk2A∗rjArjAskjA⟵Hk2A∗u1A,pwAmA=τjA⊕skjBu2A=fpk,pwA,rjAtkA=Hashs1A,u2A,pwA,rjA⊕Hk2Au1A,pwAΔA=tkA⊕ECCHk2A∗u1A,pwAlabel2A=ABCs1As2As2A∗ΔAc1Av2A=gpk,label2A,pwA,rjAk2B⟵rK,k2B∗⟵rKs2B=αk2B,s2B∗=αk2B∗rjBτjBskjB⟵Hk2B∗u1B,pwBmB=τjB⊕skjAu2B=fpk,pwB,rjBtkB=Hashs1B,u2B,pwB,rjB⊕Hk2Bu1B,pwBΔB=tkB⊕ECCHk2B∗u1B,pwBlabel2B=BACs1Bs2Bs2B∗ΔBc1Bv2B=gpk,label2B,pwB,rjBs2As2A∗ΔAc2A=u2A,v2AmA⟵s2Bs2B∗ΔBc2B=u2B,v2BmB⟶tkA′=Hk1Au2A,pwA⊕Hashs2A,u1A,pwA,r1AHA′=ECC−1tkA′⊕ΔAIfHamHA′,Hashs2A∗,u1A,pwA,r1A≤2ε/ℓriAriAskiA⟵HA′skAB=mA⊕τiA⊕skiAtkB′=Hk1Bu2B,pwB⊕Hashs2B,u1B,pwB,r1BHB′=ECC−1tkB′⊕ΔBIfHamHB′,Hashs2B∗,u1B,pwB,r1B≤2ε/ℓriBτiBskiB⟵HB′skBA=mB⊕τiB⊕skiB


### 4.1. Protocol Execution

Clients A and B, respectively, choose random tapesr1A⟵r0,1∗ and r1B⟵r0,1∗ for encryption hash keys k1A,k1B⟵rK. Then, A/B computes the projection key s1A=αk1A/s1B=αk1B and sets label1A=ABSs1A/label1BBASs1B. A/B continues to compute c1A=u1A,v1A=Σpk,label1A,pwA,r1A/c1B=u1B,v1B=Σpk,label1B,pwB,r1B. Finally, client A/B sends to server C a message ABSs1Ac1A=u1A,v1A/BASs1BcB1=uB1,v1B.After receivingABSs1Ac1A and BASs1BcB1 from clients A and B, the server C checks whether c1A and c1B are valid ciphertexts with respect to pk, label1A and label1B. If not, C refuses and the protocol is terminated. Otherwise, C chooses hash keys k2A,k2B⟵rK and k2A∗,k2B∗⟵rK. It computes s2A=αk2A, s2B=αk2B, s2A∗=αk2A∗, s2B∗=αk2B∗, rjAτjAskjA⟵Hk2A∗u1A,pwA, mA=τjA⊕skjB, mB=τjB⊕skjA, rjBτjBskjB⟵Hk2B∗u1B,pwB, u2A=fpk,pwA,rjA, u2B=fpk,pwB,rjB, tkA=Hashs1A,u2A,pwArjA⊕Hk2Au1A,pwA, tkB=Hashs1B,u2B,pwB,rjB⊕Hk2Bu1B,pwB, ΔA=tkA⊕ECCHk2A∗u1A,pwA, and ΔB=tkB⊕ECCHk2B∗u1B,pwB. Then, C sets label2A=ABCs1As2As2A∗ΔA‖c1A and label2B=BACs1Bs2Bs2B∗ΔB‖c1B and computes v2A=gpk,label2A,pwA,rjA, v2B=gpk,label2B,pwB,rjB. Finally, C sends to A/B the message s2As2A∗ΔAc2A=u2A,v2AmA/s2Bs2B∗ΔBc2B=u2B,v2BmB and outputs skAB=skjA⊕skjB.Received from server Cs2As2A∗ΔAc2A=u2A,v2AmA/s2Bs2B∗ΔBc2B=u2B,v2BmB, client A/B checks whether c2A/c2B is a valid ciphertext with respect to pk andlabel2A/label2B. If not, A/B rejects and the protocol aborts. Otherwise, A/B computes tkA′=Hk1Au2A,pwA⊕Hashs2A,u1A,pwA,r1A/tkB′=Hk1Bu2B,pwB⊕Hashs2B,u1B,pwB,r1B, HA′=ECC−1tkA′⊕ΔA/HB′=ECC−1tkB′⊕ΔB. Client A/B then checks whether the Hamming distance between HA′/HB′ and Hashs2A∗,u1A,pwA,r1A/Hashs2B∗,u1B,pwB,r1B is less than 2ε/ℓ. If not, Client A/B rejects and the protocol aborts. Otherwise, A/B sets riAτiAskiA⟵HA′/riBτiBskiB⟵HB′ and outputs skAB=mA⊕τiA⊕skiA/skBA=mB⊕τiB⊕skiB.


### 4.2. Correctness

After the protocol is executed honestly, the probability of a mismatch between the session keys obtained by the two clients A and B is negligible. From the approximate correctness of the NA-ASPH, the probability that the Hamming distance betweentkAtkB calculated by client A (B) and tkA′tkB′ calculated by the clients is greater than εn∙n can be neglected. Then, from the definition of error correction code ECC, client A (B) and server C can obtain the same riAτiAskiA(rjBτjBskjB), so A and B can get the same session key,
(7)skAB=mA⊕τiA⊕skiA=τjA⊕skjB⊕τiA⊕skiA=skjB⊕skiA=τjB⊕skjA⊕τiB⊕skiB=mB⊕τiB⊕skiB=skAB.


### 4.3. Security

Since the protocol here is symmetrical with respect to the clients, the proof usually can only take one client as an example. The security proof of the protocol follows Section3 closely. We outline the main ideas. First, based on the CCA security of the underlying primitive Σ, the adversary cannot obtain any useful information about the real password through Execute query. In the Execute query, if the simulator replaces the valid password with an illegal one, guaranteed by the smoothness of NA-ASPH, the adversary cannot distinguish the corresponding two experiments computationally. Second, if the adversary simply replays the messages between participants, the proof is the same as the Execute query. Third, if the adversary modifies the output message of some instances (that is, it modifies (label, c)), the simulator can obtain the corresponding plaintext pwA/Bad through the decryption oracle provided by CCA security. If pwA/Bad=pwA/B holds, the corresponding attack is successful, which will increase the adversary’s advantage. Using the CCA security of Σ, pwA/B is uniformly sampled from the password dictionary D, so PrpwA/Bad=pwA/B≤1/D. Assuming that the adversary can perform at most Q(κ) on-line attacks, then the adversary’s advantage is at most Qκ/D. And if pwA/Bad≠pwA/B holds, then from the adversary’s view, the session key obtained is indistinguishable from the uniform distribution (according to the smoothness of NA-ASPH).


## 4.1. Protocol Execution

Clients A and B, respectively, choose random tapesr1A⟵r0,1∗ and r1B⟵r0,1∗ for encryption hash keys k1A,k1B⟵rK. Then, A/B computes the projection key s1A=αk1A/s1B=αk1B and sets label1A=ABSs1A/label1BBASs1B. A/B continues to compute c1A=u1A,v1A=Σpk,label1A,pwA,r1A/c1B=u1B,v1B=Σpk,label1B,pwB,r1B. Finally, client A/B sends to server C a message ABSs1Ac1A=u1A,v1A/BASs1BcB1=uB1,v1B.After receivingABSs1Ac1A and BASs1BcB1 from clients A and B, the server C checks whether c1A and c1B are valid ciphertexts with respect to pk, label1A and label1B. If not, C refuses and the protocol is terminated. Otherwise, C chooses hash keys k2A,k2B⟵rK and k2A∗,k2B∗⟵rK. It computes s2A=αk2A, s2B=αk2B, s2A∗=αk2A∗, s2B∗=αk2B∗, rjAτjAskjA⟵Hk2A∗u1A,pwA, mA=τjA⊕skjB, mB=τjB⊕skjA, rjBτjBskjB⟵Hk2B∗u1B,pwB, u2A=fpk,pwA,rjA, u2B=fpk,pwB,rjB, tkA=Hashs1A,u2A,pwArjA⊕Hk2Au1A,pwA, tkB=Hashs1B,u2B,pwB,rjB⊕Hk2Bu1B,pwB, ΔA=tkA⊕ECCHk2A∗u1A,pwA, and ΔB=tkB⊕ECCHk2B∗u1B,pwB. Then, C sets label2A=ABCs1As2As2A∗ΔA‖c1A and label2B=BACs1Bs2Bs2B∗ΔB‖c1B and computes v2A=gpk,label2A,pwA,rjA, v2B=gpk,label2B,pwB,rjB. Finally, C sends to A/B the message s2As2A∗ΔAc2A=u2A,v2AmA/s2Bs2B∗ΔBc2B=u2B,v2BmB and outputs skAB=skjA⊕skjB.Received from server Cs2As2A∗ΔAc2A=u2A,v2AmA/s2Bs2B∗ΔBc2B=u2B,v2BmB, client A/B checks whether c2A/c2B is a valid ciphertext with respect to pk andlabel2A/label2B. If not, A/B rejects and the protocol aborts. Otherwise, A/B computes tkA′=Hk1Au2A,pwA⊕Hashs2A,u1A,pwA,r1A/tkB′=Hk1Bu2B,pwB⊕Hashs2B,u1B,pwB,r1B, HA′=ECC−1tkA′⊕ΔA/HB′=ECC−1tkB′⊕ΔB. Client A/B then checks whether the Hamming distance between HA′/HB′ and Hashs2A∗,u1A,pwA,r1A/Hashs2B∗,u1B,pwB,r1B is less than 2ε/ℓ. If not, Client A/B rejects and the protocol aborts. Otherwise, A/B sets riAτiAskiA⟵HA′/riBτiBskiB⟵HB′ and outputs skAB=mA⊕τiA⊕skiA/skBA=mB⊕τiB⊕skiB.


## 4.2. Correctness

After the protocol is executed honestly, the probability of a mismatch between the session keys obtained by the two clients A and B is negligible. From the approximate correctness of the NA-ASPH, the probability that the Hamming distance betweentkAtkB calculated by client A (B) and tkA′tkB′ calculated by the clients is greater than εn∙n can be neglected. Then, from the definition of error correction code ECC, client A (B) and server C can obtain the same riAτiAskiA(rjBτjBskjB), so A and B can get the same session key,
(7)skAB=mA⊕τiA⊕skiA=τjA⊕skjB⊕τiA⊕skiA=skjB⊕skiA=τjB⊕skjA⊕τiB⊕skiB=mB⊕τiB⊕skiB=skAB.


## 4.3. Security

Since the protocol here is symmetrical with respect to the clients, the proof usually can only take one client as an example. The security proof of the protocol follows Section3 closely. We outline the main ideas. First, based on the CCA security of the underlying primitive Σ, the adversary cannot obtain any useful information about the real password through Execute query. In the Execute query, if the simulator replaces the valid password with an illegal one, guaranteed by the smoothness of NA-ASPH, the adversary cannot distinguish the corresponding two experiments computationally. Second, if the adversary simply replays the messages between participants, the proof is the same as the Execute query. Third, if the adversary modifies the output message of some instances (that is, it modifies (label, c)), the simulator can obtain the corresponding plaintext pwA/Bad through the decryption oracle provided by CCA security. If pwA/Bad=pwA/B holds, the corresponding attack is successful, which will increase the adversary’s advantage. Using the CCA security of Σ, pwA/B is uniformly sampled from the password dictionary D, so PrpwA/Bad=pwA/B≤1/D. Assuming that the adversary can perform at most Q(κ) on-line attacks, then the adversary’s advantage is at most Qκ/D. And if pwA/Bad≠pwA/B holds, then from the adversary’s view, the session key obtained is indistinguishable from the uniform distribution (according to the smoothness of NA-ASPH).


## 5. Protocol Performance Analysis

In this section, we will compare the performance of the two proposed protocols with other related protocols in terms of safety and efficiency. The comparison results are shown in Table4, where Type represents the protocol type, M-Auth indicates whether the protocol can provide mutual authentication, Round denotes the number of communication rounds required by the protocol, Anti-Qu represents whether the protocol can resist quantum attacks, C-method indicates the operation method of the protocol, C-cost represents the communication cost of the protocol, V-mul denotes vector multiplication, Exp indicates exponentiation, and n=n1+n2.Table 4
Performance comparisons of PAKE protocols.
ProtocolTypeM-AuthAnti-QuRoundC-methodC-costZ-2PAKE [1]2-party√√2V-mul(2m+2n1)lbq+nK-2PAKE [33]2-party╳√3V-mul(mn+2n)lbq+3nD-2PAKE [34]2-party√√3V-mul(mn/2+m/2+3n)lbq+2n2PAKE2-party√√2V-mul(2m+3n1)lbq+nA-3PAKE [30]3-party╳╳4Exp—Y-3PAKE [35]3-party√√3V-mul2[(mn+n)lbq+3n]X-3PAKE [36]3-party√√3V-mul7nlbq+9n+53PAKE3-party√√2V-mul2[(2m+3n1)lbq+2n]In terms of security, we mainly compare with other protocols in (1) whether it can resist quantum attacks; (2) whether it can achieve mutual authentication. In terms of efficiency, we mainly compare from the following three aspects: (1) the selection of cryptographic primitives, (2) the calculation method, and (3) the communication overhead. Note that the calculation method adopted is used to roughly measure the computational cost of the corresponding protocol. Moreover, the computational cost of modular exponential operations is much greater than linear operations on matrices and vectors.Compared with the K-PAKE [33] and D-PAKE [34], the advantage of the 2PAKE is that mutual authentication and key exchange can be achieved within two rounds of transmission. And the size of the ciphertext of K-PAKE and D-PAKE are O (n) larger than 2PAKE. The size of the projection key of K-PAKE and D-PAKE is determined by the ciphertext and the hash key, larger than that of 2PAKE.Compared with the typical three-party PAKE, A-3PAKE [30], the 3PAKE in this paper is lattice-based and can resist quantum attacks. The proposed 3PAKE can achieve mutual authentication within two rounds of transmission. In addition, A-3PAKE uses exponential operation, while the 3PAKE protocol uses vector multiplication, which has higher computational efficiency.Compared with Y-3PAKE [35] and X-3PAKE [36] protocols, 3PAKE only requires 2 rounds of transmission. The communication cost of Y-3PAKE protocol mainly depends on the size of the ciphertext, the projection key, and the message authentication code. The size of the ciphertext is O (n) larger than 3PAKE. The size of the projection key of Y-3PAKE is determined by the ciphertext and the hash key, larger than that of 3PAKE. In addition, the Y-PAKE protocol needs to calculate and send a message authentication code for mutual authentication, while 3PAKE performs mutual authentication by verifying the validity of the ciphertext. The amount of messages that needs to be transmitted in X-PAKE is large, resulting in increased communication overhead. Therefore, the communication overhead of the Y-3PAKE and X-PAKE protocols is greater than 3PAKE in this paper.Z-PAKE [1] is also a two-round protocol, but it is designed for two parties. Compared with the Z-PAKE protocol, 2PAKE adds a projection key to the communication overhead. However, if the three-party PAKE based on Z-PAKE is implemented in a traditional way, at least 4 rounds of communication, that is, 8 message transmissions, are required. But the 3PAKE in this paper only needs 2 rounds of communication, namely 4 message transmissions.The protocols in this paper have advantages of efficiency and security over traditional protocols based on finite fields, since lattice operations (vector multiplication) are more efficient than exponentiation and lattice problems remain hard for quantum attacks and subexponential-time adversaries. Both protocols in this article can achieve mutual authentication; thus, they can resist imperceptible on-line dictionary attacks. Besides, they are both two-round protocols with less number of transmissions. And the underlying primitive is an improved lattice-based CCA-secure PKE, which can reduce encryption parameters and further reduce computational overhead. In particular, compared with other three-party protocols, the two-round 3PAKE protocol proposed has smaller communication and computation overhead, so it is adaptable to large-scale communication systems.


## 6. Conclusions

This paper proposes two password-based authenticated key exchange protocols based on the LWE problem from lattices, which can resist quantum attacks and have high efficiency. In the random oracle model, this paper gives a strict security proof of the proposed protocols. In addition, the proposed PAKE protocols can achieve mutual authentication in two rounds of transmission. And the 3PAKE protocol is practical for large-scale communication systems. Compared with the existing related protocols, the protocols in this paper have higher security and lower communication and computing overhead. In our protocols, the client’s password is stored on a single server, so the proposed protocols are not resistant to hacker attacks. In the future, we will study the multiserver PAKE protocol that can resist hacker attacks.



---

*Source: 8893628-2020-12-14.xml*