# Post-Quantum Secure Password-Authenticated Key Exchange Based on Ouroboros

Authors: Hao Wang; Yu Li; Li-Ping Wang
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Password-authenticated key exchange (PAKE) protocols play an important role in cryptography. Most of PAKEs are based on the Diffie–Hellman key exchange protocols or RSA encryption schemes, but their security is threatened by quantum computers. In this study, we propose the first code-based PAKE protocol based on Ouroboros, which is a code-based key exchange protocol. Our scheme enjoys high efficiency and provides mutual explicit authentication, with a security reduction to decoding random quasi-cyclic codes in the random oracle model.


---

## Body

## 1. Introduction

Authenticated key exchange (AKE) allows two communicating entities to establish a common and high-entropy secret session key over an insecure communication network. In general, users need to store some prepared long-time secret keys with high entropy in devices such as smart cards and ID cards. However, the access to hardware devices makes AKE more inconvenient and complex.To solve this shortcoming, password-authenticated key exchange (PAKE) was proposed since PAKEs only require human-memorable passwords with low entropy, such as six to eight characters. Nowadays, more and more people tend to use handheld devices, and so PAKEs have a wide range of practical applications. Nevertheless, it is difficult to design a secure key exchange protocol based on passwords, because the low entropy of a password makes it vulnerable to dictionary attacks if an adversary can get some password-dependent data. Generally speaking, there are two types of dictionary attacks. The first one is an online dictionary attack. In this attack, an adversary actively participates the execution of a protocol. For example, an adversary runs a protocol with a guessed password and observes whether the protocol succeeds. However, this type of attack is easy to avoid by just allowing an adversary to test at most a constant number of passwords per online interaction. What we need to consider is the another dictionary attack, i.e., offline dictionary attack. In this attack, an adversary can observe the execution of a protocol or interacts with the participants of the protocol. Next, the adversary tests the correctness of a guessed password offline. To avoid this attack, session keys and protocol messages must look computationally independent from passwords to the adversary.The first PAKE protocol was proposed by Bellovin and Merritt in [1], which is called the encrypted key exchange (EKE) protocol, but they did not give a formal security proof in the protocol. Since then, a number of PAKE protocols were proposed [2–7]. However, these protocols still have no formal security proof. Until 2000, the formal security models began with the works of Bellare et al. [8] and Boyko et al. [9]. Canetti et al. introduced the universally composable notion to PAKE security model in 2005 [10].With the security model, plenty of protocols have been designed and analyzed. On the one hand, most of PAKEs are designed using the Diffie–Hellman (DH) key exchange protocols [9, 11–15], in which the PAK [9] and PPK [15] protocols are two efficient and simple constructions of PAKEs based on the DH key exchange protocol. The PAK protocol is three-pass protocol and provides explicit authentication, and the PPK protocol is two-pass protocol and provides implicit authentication. On the other hand, some PAKEs were designed using RSA encryption schemes [16–19]. In particular, Mackenzie et al. proposed the first RSA-based PAKE protocol with a formal security proof in 2000, which is called SNAPI [17]. In 2004, Zhang showed that SNAPI protocol was not practical and proposed two efficient RSA-based PAKEs [19].Since the well-known Shor algorithm was proposed [20], the security of the DH key exchange protocols and RSA encryption schemes encounters great challenges. Fortunately, lattice-based cryptosystems and code-based cryptosystems are supposed to effectively resist attack on the quantum computers. Based on AKE protocols [21–26], several simple and efficient lattice-based PAKE protocols have been designed [27, 28]. The protocols in [27] can be regarded as a parallel extension of the PAK and PPK. In the code-based cryptosystem, there are no DH-type key exchange protocols. Nevertheless, Deneuville et al. proposed a secure and efficient code-based key exchange protocol, which is called Ouroboros [29]. The Ouroboros scheme gathers the best properties of the MDPC-McEliece [30] and the HQC [31] and has a simple decoding algorithm. The security of the Ouroboros is reduced to decoding random quasi-cyclic codes in the random oracle model. As far as we know, there is no code-based provably secure PAKE scheme.In this study, we propose the first code-based PAKE protocol based on Ouroboros with formal security proof. The protocol is constructed by using a weight-restricted hash function and enjoys several desired features, including high efficiency, mutual explicit authentication, and quantum resistance, with a security reduction in our scheme to decoding random quasi-cyclic codes in the random oracle model.The rest of this study is organized as follows. Section2 introduces notations used throughout the study and gives needed preliminary definitions and propositions. In Section 3, we review the security model. In Section 4, we provide a detailed description of our PAKE protocol. Section 5 gives the formal security analysis of our PAKE protocol. Section 6 provides the efficiency evaluation of our scheme. Finally, Section 7 concludes the study.


## 2. Preliminaries

In this section, we introduce notations and needed preliminary definitions and propositions throughout the study.


### 2.1. Notations

In this study, the ring of integers is denoted byℤ, and a finite field is denoted by Fq with q elements, where q is a prime number. Additionally, we denote the Hamming weight of a vector by ω·, i.e., the number of its nonzero coordinates. V denotes a vector space of dimension n over F2 for some positive n∈ℤ. Elements of V can be considered as row vectors or polynomials in ℛ=F2X/Xn−1 and represented by lower-case bold letters. The product of two elements x,y∈V is defined similarly as in ℛ, i.e., x⋅y=c∈V with(1)cm=∑i+j≡mmodnxiyj,form∈0,1,…,n−1.For any finite setT, x←$T denotes x is a uniformly random element sampled from T. For an event E, E¯ denotes the complementary event of E.In particular, we also use the symbolSwnF2 as follows:(2)SwnF2=x∈F2n:ωx=w.


### 2.2. Coding Theory

We now focus on relevant basic definitions and properties relating to coding theory.Definition 1.
(Linear Code). A linearn,kq code C with length n and dimension k over Fq is a subspace of Fqn.Definition 2.
(Generator Matrix). A generator matrix for a linearn,kq code C is a matrix G∈Fqk×n whose rows form a basis for C, i.e.,(3)C=μG,forμ∈Fqk.Definition 3.
(Parity Check Matrix). A parity check matrixH∈Fqn−k×n for a linear code C is a generator matrix for the dual code C⊥, i.e.,(4)C⊥=x∈Fqn:Hx⊺=0.Definition 4.
(Quasi-Cyclic Codes [30]). Given positive integers s, n, and k, a /sn,k linear code C is quasi-cyclic (QC) of order s if for any c=c1,c2,…,cs∈C it holds that Xc1,Xc2,…,Xcs∈C.Definition 5.
(Systematic Quasi-Cyclic Codes of Rate 1/s[30]). A systematic quasi-cyclic sn,n code of order s is a quasi-cyclic code with a parity check matrix of the form(5)H=In0⋯0A10In⋯0A2⋮⋮⋱⋮⋮00⋯InAs−1,where A1,…,As−1 are n×n circulant matrices.
Next, we define the syndrome decoding (SD) problem overF2 in the Hamming metric.Definition 6.
(SD Distribution). Given positive integersn,k,w, the SD n,k,w distribution chooses H←$F2n−k×n and x←$SwnF2 and outputs H,σx=Hx⊺.Definition 7.
(Search SD Problem). GivenH,y⊺∈F2n−k×n×F2n−k from the SD distribution, the search SD problem decides whether there exists x∈SwnF2, such that Hx⊺=y⊺.Definition 8.
(Decisional SD Problem) On inputH,y⊺∈F2n−k×n×F2n−k, the decisional SD problem DSD n,k,w needs to decide with nonnegligible advantage whether H,y⊺ came from the SD distribution or the uniform distribution over F2n−k×n×F2n−k.
The search SD problem in the Hamming metric has been proved NP complete over binary field in the worst case [32], and the decisional SD problem has been proved to be polynomially equivalent to its search version [33].
Then, we describe relevant definitions of quasi-cyclic codes.Definition 9.
(s-QCSD Distribution). Given positive integers n,k,w,s, the s-QCSD n,k,w,s distribution chooses H←$F2sn−k×sn and x=x1,…,xs, where xi←$SwinF2, and outputs H,σx=Hx⊺.Definition 10.
(Searchs-QCSD Problem). Given positive integers n,k,w,s, a random systematic parity check matrix H∈F2sn−k×sn of a quasi-cyclic code, and y←$F2sn−k, the search s-QCSD problem decides whether there exists x=x1,…,xs, where xi←$SwinF2, such that Hx⊺=y⊺.Definition 11.
(Decisionals-QCSD Problem). Given positive integers n,k,w,s, a random parity check matrix H∈F2sn−k×sn of a systematic quasi-cyclic code C and y←F2\sn, the decisional s-QCSD (s-DQCSD) problem asks to decide with nonnegligible advantage whether H,y⊺ came from the s-QCSD distribution or the uniform distribution over F2sn−k×sn×F2sn−k.


#### 2.2.1. The s-QCSD Problem Assumption [29]

The searchs-QCSD problem is hard on average. Let A be a probabilistic polynomial time adversary. The input of A is a random parity check matrix H∈F2sn−k×sn and a vector y∈F2sn. The probability AdvAs−QCSD of outputting vector x=x1,…,xs with Hx⊺=y⊺ and ωxi=wi by A is negligible, where(6)AdvAs−QCSD=PrH⟵$F2sn−k×sn;y⟵$F2sn;Hx⊺=y⊺;x=x1,…,xs;xi∈SwinF2:x∈AH,y,wi.LetAdvs−QCSDOt=maxAAdvAs−QCSD, where the maximum is over all adversaries of time complexity at most t.


### 2.3. Weight-Restricted Hash Function

Our PAKE protocol uses a weight-restricted hash function proposed in the RaCoSS scheme[34]. We denote this weight-restricted hash function by ℋ≀. Although the RaCoSS scheme has been broken, ℋ≀ is still secure under proper parameters[35]. Before giving the description of weight-restricted hash function, let us first introduce the definition of collision-resistant hash function.Definition 12.
A hash functionℋ is called collision-resistant hash function if the probability that any adversary ℬ finds two distinct values that satisfies the following condition is negligible:(7)PrM,M′←ℬ:M≠M′∧ℋM=ℋM′≤neglλ,where neglλ is a negligible function.Lemma 1.
(see [36]). Given a collision-resistant hash function ℋ:0,1∗⟶0,1n1, and an encode algorithm Enc·, which encode any n1 bit message into n2 bit message with Hamming weight w, the function Encℋ·:0,1∗⟶0,1n2 is still a collision-resistant hash function.We put the weight-restricted hash functionℋ≀ in Algorithm 1. Simply speaking, ℋ≀ uses a byte string message m, two integers w and n as input. Then, SHA3-512 is used to calculate the position of 1. The output is a n-bit string with Hamming weight w. According to Lemma 1, ℋ≀ is a collision-resistant hash function.Algorithm 1: Weight-restricted hash function.
Input: Message byte string m, integer w, integer n.Output: A n-bit string with Hamming weight w.(1)
ℓ←⌈log2n⌉(2)
I←∅(3)
S←m,0x00m,0x01m,0x02‖m,…,0xFF‖m(4)
fors∈Sdo(5)
x← SHA3-512 s(6)
x1,x2,…,x⌊521/ℓ⌋←ℓ−bitsx(7)
fori=1 to ⌊512/ℓ⌋do(8)
yi← int xi(9)
ifyi<nthen(10)
I←I∪yi(11)
end if(12)
ifI=wthen(13)
Break(14)
end if(15)
end for(16)
end for(17)
ifI<wthen(18)
Outputs⊥(19)
else(20)
Outputs an-bit string where Ii-th bit is 1 (Ii∈I,0≤i≤w−1) and other bits are 0.(21)
end if


### 2.4. Ouroboros Scheme

We now recall the Ouroboros scheme from [29], which is the basic of our PAKE protocol. The Ouroboros scheme uses a function fw proposed in [37]. Simply speaking, giving the positions of the “1” is enough to obtain random vectors with fixed weight w. For more details about this function, we refer the readers to [37]. Besides, the Ouroboros scheme uses a hash function ℋ˜:0,1∗⟶SwnF2. The decoding algorithm CE decoder is presented in Algorithm 2. In short, it puts x, y, ec=xr2−yr1+e, threshold value t, the weight w of r1 and r2, and the weight we of e as input. The output of this algorithm is r1,r2 if it succeeds.Algorithm 2: CE Decoder x,y,ec,t,w,we.
Input:x, y, ec=xr2−yr1+e, threshold value t, the weight w of r1 and r2 and the weight we of e.Output:r1,r2 if the algorithm succeeds, ⊥ otherwise.(1)
u,v←0,0∈F2n2, H←rot−y⊺,rotx⊺∈F2n×2n, syn←ec(2)
while [ωu≠w or ωv≠w] and ωsyn>wedo(3)
sum←syn×H(4)
temp←0∈F22n(5)
fori∈0,2n−1do(6)
if sum i≥tthen(7)
temp [i]  = temp i⊕1(8)
end if(9)
end for(10)
u,v=u,v⊕temp(11)
syn=syn−H×temp(12)
end while(13)
ifωec−H×u,v⊺>wethen(14)
Outputs⊥(15)
else(16)
Outputsu,v(17)
end ifThe Ouroboros scheme is presented as follows:(a)
Alice generates h←$F2n and x,y←$SwnF2. Then, she computes s=x+hy. Finally, she sends h,s to Bob.(b)
Bob generates r1,r2←$SwnF2 and computes er=fwℋ˜r1,r2. Next, he randomly generates ε←$SwεnF2. Then, he computes s1=r1+hr2 and s2=sr2+er+ε. Finally, he sends s1,s2 to Alice and saves the vector ε as the shared secret.(c)
Alice computes ec=s2−ys1=xr2−yr1+er+ε when receiving s1 and s2. Then, she uses the decoding algorithm CE decoder x,y,ec,t,w,w+wε to get r1 and r2. Finally, she computes the shared secret ε=ec−xr2+yr1−fwℋ˜r1,r2.Theorem 1 (see [29]).
The Ouroboros protocol satisfies indistinguishability under chosen plaintext attack (IND-CPA) under the 2-DQCSD and 3-DQCSD assumptions.


## 2.1. Notations

In this study, the ring of integers is denoted byℤ, and a finite field is denoted by Fq with q elements, where q is a prime number. Additionally, we denote the Hamming weight of a vector by ω·, i.e., the number of its nonzero coordinates. V denotes a vector space of dimension n over F2 for some positive n∈ℤ. Elements of V can be considered as row vectors or polynomials in ℛ=F2X/Xn−1 and represented by lower-case bold letters. The product of two elements x,y∈V is defined similarly as in ℛ, i.e., x⋅y=c∈V with(1)cm=∑i+j≡mmodnxiyj,form∈0,1,…,n−1.For any finite setT, x←$T denotes x is a uniformly random element sampled from T. For an event E, E¯ denotes the complementary event of E.In particular, we also use the symbolSwnF2 as follows:(2)SwnF2=x∈F2n:ωx=w.


## 2.2. Coding Theory

We now focus on relevant basic definitions and properties relating to coding theory.Definition 1.
(Linear Code). A linearn,kq code C with length n and dimension k over Fq is a subspace of Fqn.Definition 2.
(Generator Matrix). A generator matrix for a linearn,kq code C is a matrix G∈Fqk×n whose rows form a basis for C, i.e.,(3)C=μG,forμ∈Fqk.Definition 3.
(Parity Check Matrix). A parity check matrixH∈Fqn−k×n for a linear code C is a generator matrix for the dual code C⊥, i.e.,(4)C⊥=x∈Fqn:Hx⊺=0.Definition 4.
(Quasi-Cyclic Codes [30]). Given positive integers s, n, and k, a /sn,k linear code C is quasi-cyclic (QC) of order s if for any c=c1,c2,…,cs∈C it holds that Xc1,Xc2,…,Xcs∈C.Definition 5.
(Systematic Quasi-Cyclic Codes of Rate 1/s[30]). A systematic quasi-cyclic sn,n code of order s is a quasi-cyclic code with a parity check matrix of the form(5)H=In0⋯0A10In⋯0A2⋮⋮⋱⋮⋮00⋯InAs−1,where A1,…,As−1 are n×n circulant matrices.
Next, we define the syndrome decoding (SD) problem overF2 in the Hamming metric.Definition 6.
(SD Distribution). Given positive integersn,k,w, the SD n,k,w distribution chooses H←$F2n−k×n and x←$SwnF2 and outputs H,σx=Hx⊺.Definition 7.
(Search SD Problem). GivenH,y⊺∈F2n−k×n×F2n−k from the SD distribution, the search SD problem decides whether there exists x∈SwnF2, such that Hx⊺=y⊺.Definition 8.
(Decisional SD Problem) On inputH,y⊺∈F2n−k×n×F2n−k, the decisional SD problem DSD n,k,w needs to decide with nonnegligible advantage whether H,y⊺ came from the SD distribution or the uniform distribution over F2n−k×n×F2n−k.
The search SD problem in the Hamming metric has been proved NP complete over binary field in the worst case [32], and the decisional SD problem has been proved to be polynomially equivalent to its search version [33].
Then, we describe relevant definitions of quasi-cyclic codes.Definition 9.
(s-QCSD Distribution). Given positive integers n,k,w,s, the s-QCSD n,k,w,s distribution chooses H←$F2sn−k×sn and x=x1,…,xs, where xi←$SwinF2, and outputs H,σx=Hx⊺.Definition 10.
(Searchs-QCSD Problem). Given positive integers n,k,w,s, a random systematic parity check matrix H∈F2sn−k×sn of a quasi-cyclic code, and y←$F2sn−k, the search s-QCSD problem decides whether there exists x=x1,…,xs, where xi←$SwinF2, such that Hx⊺=y⊺.Definition 11.
(Decisionals-QCSD Problem). Given positive integers n,k,w,s, a random parity check matrix H∈F2sn−k×sn of a systematic quasi-cyclic code C and y←F2\sn, the decisional s-QCSD (s-DQCSD) problem asks to decide with nonnegligible advantage whether H,y⊺ came from the s-QCSD distribution or the uniform distribution over F2sn−k×sn×F2sn−k.


### 2.2.1. The s-QCSD Problem Assumption [29]

The searchs-QCSD problem is hard on average. Let A be a probabilistic polynomial time adversary. The input of A is a random parity check matrix H∈F2sn−k×sn and a vector y∈F2sn. The probability AdvAs−QCSD of outputting vector x=x1,…,xs with Hx⊺=y⊺ and ωxi=wi by A is negligible, where(6)AdvAs−QCSD=PrH⟵$F2sn−k×sn;y⟵$F2sn;Hx⊺=y⊺;x=x1,…,xs;xi∈SwinF2:x∈AH,y,wi.LetAdvs−QCSDOt=maxAAdvAs−QCSD, where the maximum is over all adversaries of time complexity at most t.


## 2.2.1. The s-QCSD Problem Assumption [29]

The searchs-QCSD problem is hard on average. Let A be a probabilistic polynomial time adversary. The input of A is a random parity check matrix H∈F2sn−k×sn and a vector y∈F2sn. The probability AdvAs−QCSD of outputting vector x=x1,…,xs with Hx⊺=y⊺ and ωxi=wi by A is negligible, where(6)AdvAs−QCSD=PrH⟵$F2sn−k×sn;y⟵$F2sn;Hx⊺=y⊺;x=x1,…,xs;xi∈SwinF2:x∈AH,y,wi.LetAdvs−QCSDOt=maxAAdvAs−QCSD, where the maximum is over all adversaries of time complexity at most t.


## 2.3. Weight-Restricted Hash Function

Our PAKE protocol uses a weight-restricted hash function proposed in the RaCoSS scheme[34]. We denote this weight-restricted hash function by ℋ≀. Although the RaCoSS scheme has been broken, ℋ≀ is still secure under proper parameters[35]. Before giving the description of weight-restricted hash function, let us first introduce the definition of collision-resistant hash function.Definition 12.
A hash functionℋ is called collision-resistant hash function if the probability that any adversary ℬ finds two distinct values that satisfies the following condition is negligible:(7)PrM,M′←ℬ:M≠M′∧ℋM=ℋM′≤neglλ,where neglλ is a negligible function.Lemma 1.
(see [36]). Given a collision-resistant hash function ℋ:0,1∗⟶0,1n1, and an encode algorithm Enc·, which encode any n1 bit message into n2 bit message with Hamming weight w, the function Encℋ·:0,1∗⟶0,1n2 is still a collision-resistant hash function.We put the weight-restricted hash functionℋ≀ in Algorithm 1. Simply speaking, ℋ≀ uses a byte string message m, two integers w and n as input. Then, SHA3-512 is used to calculate the position of 1. The output is a n-bit string with Hamming weight w. According to Lemma 1, ℋ≀ is a collision-resistant hash function.Algorithm 1: Weight-restricted hash function.
Input: Message byte string m, integer w, integer n.Output: A n-bit string with Hamming weight w.(1)
ℓ←⌈log2n⌉(2)
I←∅(3)
S←m,0x00m,0x01m,0x02‖m,…,0xFF‖m(4)
fors∈Sdo(5)
x← SHA3-512 s(6)
x1,x2,…,x⌊521/ℓ⌋←ℓ−bitsx(7)
fori=1 to ⌊512/ℓ⌋do(8)
yi← int xi(9)
ifyi<nthen(10)
I←I∪yi(11)
end if(12)
ifI=wthen(13)
Break(14)
end if(15)
end for(16)
end for(17)
ifI<wthen(18)
Outputs⊥(19)
else(20)
Outputs an-bit string where Ii-th bit is 1 (Ii∈I,0≤i≤w−1) and other bits are 0.(21)
end if


## 2.4. Ouroboros Scheme

We now recall the Ouroboros scheme from [29], which is the basic of our PAKE protocol. The Ouroboros scheme uses a function fw proposed in [37]. Simply speaking, giving the positions of the “1” is enough to obtain random vectors with fixed weight w. For more details about this function, we refer the readers to [37]. Besides, the Ouroboros scheme uses a hash function ℋ˜:0,1∗⟶SwnF2. The decoding algorithm CE decoder is presented in Algorithm 2. In short, it puts x, y, ec=xr2−yr1+e, threshold value t, the weight w of r1 and r2, and the weight we of e as input. The output of this algorithm is r1,r2 if it succeeds.Algorithm 2: CE Decoder x,y,ec,t,w,we.
Input:x, y, ec=xr2−yr1+e, threshold value t, the weight w of r1 and r2 and the weight we of e.Output:r1,r2 if the algorithm succeeds, ⊥ otherwise.(1)
u,v←0,0∈F2n2, H←rot−y⊺,rotx⊺∈F2n×2n, syn←ec(2)
while [ωu≠w or ωv≠w] and ωsyn>wedo(3)
sum←syn×H(4)
temp←0∈F22n(5)
fori∈0,2n−1do(6)
if sum i≥tthen(7)
temp [i]  = temp i⊕1(8)
end if(9)
end for(10)
u,v=u,v⊕temp(11)
syn=syn−H×temp(12)
end while(13)
ifωec−H×u,v⊺>wethen(14)
Outputs⊥(15)
else(16)
Outputsu,v(17)
end ifThe Ouroboros scheme is presented as follows:(a)
Alice generates h←$F2n and x,y←$SwnF2. Then, she computes s=x+hy. Finally, she sends h,s to Bob.(b)
Bob generates r1,r2←$SwnF2 and computes er=fwℋ˜r1,r2. Next, he randomly generates ε←$SwεnF2. Then, he computes s1=r1+hr2 and s2=sr2+er+ε. Finally, he sends s1,s2 to Alice and saves the vector ε as the shared secret.(c)
Alice computes ec=s2−ys1=xr2−yr1+er+ε when receiving s1 and s2. Then, she uses the decoding algorithm CE decoder x,y,ec,t,w,w+wε to get r1 and r2. Finally, she computes the shared secret ε=ec−xr2+yr1−fwℋ˜r1,r2.Theorem 1 (see [29]).
The Ouroboros protocol satisfies indistinguishability under chosen plaintext attack (IND-CPA) under the 2-DQCSD and 3-DQCSD assumptions.


## 3. Security Model

This section reviews the formal security model from [8]. Consider the form of a PAKE protocol with two users. Users are expected to establish and use the same keys over the network that is fully controlled by a probabilistic and polynomial time adversary A. The adversary A can initialize protocol communications between user instances, deliver messages to unintended recipients, and observe their reaction according to the protocol. The adversary can reveal the session keys established by user instances and enumerate all the passwords in the password space D in the offline attack. In the following, we perform the formal description of the security model.


### 3.1. Security Game

Let P be a PAKE protocol andU be the fixed set of users. A two-party protocol in PAKE model is considered, and the users in U are partitioned to two non-empty entities, called Alice and Bob (A and B for short). Before the game starts, for each entity, a password π is chosen uniformly at random from password space D. A set of efficiently computable cryptographic functions is specified, i.e., hash functions, and the public cryptographic parameters are generated.


### 3.2. User Instances

During the model, there are an unlimited number of instances running the protocol simultaneously for each user. Thei instance of user A is denoted as ΠAi. An instance ΠAi accepts at any time, and the same rule applies to user B. When an instance accepts, it possesses a partner id pid, a session id sid, and a session key sk. The pid is the identity of the user instance that the current instance believes it is talking to. The sid is a string, which uniquely identifies this session. In general, the sid is composed of the concatenation of all messages sent and received by the instance ΠAi (or ΠBj). The sk is the final target to be calculated.


### 3.3. Queries

The queries that adversaryA may make during the game are as follows [8]:(i)
SendA,i,M: the message M is send to instance ΠAi. The instance computes what the protocol specifies and outputs the result to the adversary. We assume whether the instance accepts or not is visible to the adversary.(ii)
ExecuteA,i,B,j: an honest execution between two instances ΠAi and ΠBj is carried out, where A≠B and ΠAi and ΠBj were not used before. Finally, the transcript of this execution is given to the adversary.(iii)
RevealA,i: the session key skAi of ΠAi is returned to the adversary.(iv)
TestA,i: this query is valid if and only if the instance is fresh, as defined below. In this case, ΠAi generates a random bit b. If b=1, the real session key skAi is sent to the adversary; otherwise, a random session key chosen uniformly from the sk space is sent. This query is allowed only once during the game.(v)
OracleM: this gives the adversary oracle access to a function h, which is selected at random from some probability space.Now, we give some definitions for the formal security model.Definition 13.
(Partnering). LetΠAi and ΠBj be a pair of instances. ΠAi and ΠBj are partnered if both have accepted and have the same unique session id sid and the same session key sk.Definition 14.
(Freshness).ΠAi is fresh if (i) it has accepted, and (ii) an adversary A has not queried RevealA,i or RevealB,j, where ΠBj is ΠAi’s partner, if it has.Definition 15.
(Correctness). IfΠAi and ΠBj are partnered and both are accepted, then they conclude with the same session key sk.Definition 16.
LetSuccP be the event that adversary A asks a single test query on a fresh instance and outputs a bit b′ with b′=b at the end of the game. The advantage of the adversary A is defined as follows:(8)AdvPA=2PrSuccP−1.
The following is definition of secure PAKE protocol, which is the same as in [38].Definition 17.
A protocol P is called a secure PAKE protocol if for every polynomial time adversaryA that makes at most nsense≤D queries of Send type to different instances, the following inequality holds, AdvPA≤nse/D+ε, where D means the size of the password space and ε is a negligible function of security parameters.


## 3.1. Security Game

Let P be a PAKE protocol andU be the fixed set of users. A two-party protocol in PAKE model is considered, and the users in U are partitioned to two non-empty entities, called Alice and Bob (A and B for short). Before the game starts, for each entity, a password π is chosen uniformly at random from password space D. A set of efficiently computable cryptographic functions is specified, i.e., hash functions, and the public cryptographic parameters are generated.


## 3.2. User Instances

During the model, there are an unlimited number of instances running the protocol simultaneously for each user. Thei instance of user A is denoted as ΠAi. An instance ΠAi accepts at any time, and the same rule applies to user B. When an instance accepts, it possesses a partner id pid, a session id sid, and a session key sk. The pid is the identity of the user instance that the current instance believes it is talking to. The sid is a string, which uniquely identifies this session. In general, the sid is composed of the concatenation of all messages sent and received by the instance ΠAi (or ΠBj). The sk is the final target to be calculated.


## 3.3. Queries

The queries that adversaryA may make during the game are as follows [8]:(i)
SendA,i,M: the message M is send to instance ΠAi. The instance computes what the protocol specifies and outputs the result to the adversary. We assume whether the instance accepts or not is visible to the adversary.(ii)
ExecuteA,i,B,j: an honest execution between two instances ΠAi and ΠBj is carried out, where A≠B and ΠAi and ΠBj were not used before. Finally, the transcript of this execution is given to the adversary.(iii)
RevealA,i: the session key skAi of ΠAi is returned to the adversary.(iv)
TestA,i: this query is valid if and only if the instance is fresh, as defined below. In this case, ΠAi generates a random bit b. If b=1, the real session key skAi is sent to the adversary; otherwise, a random session key chosen uniformly from the sk space is sent. This query is allowed only once during the game.(v)
OracleM: this gives the adversary oracle access to a function h, which is selected at random from some probability space.Now, we give some definitions for the formal security model.Definition 13.
(Partnering). LetΠAi and ΠBj be a pair of instances. ΠAi and ΠBj are partnered if both have accepted and have the same unique session id sid and the same session key sk.Definition 14.
(Freshness).ΠAi is fresh if (i) it has accepted, and (ii) an adversary A has not queried RevealA,i or RevealB,j, where ΠBj is ΠAi’s partner, if it has.Definition 15.
(Correctness). IfΠAi and ΠBj are partnered and both are accepted, then they conclude with the same session key sk.Definition 16.
LetSuccP be the event that adversary A asks a single test query on a fresh instance and outputs a bit b′ with b′=b at the end of the game. The advantage of the adversary A is defined as follows:(8)AdvPA=2PrSuccP−1.
The following is definition of secure PAKE protocol, which is the same as in [38].Definition 17.
A protocol P is called a secure PAKE protocol if for every polynomial time adversaryA that makes at most nsense≤D queries of Send type to different instances, the following inequality holds, AdvPA≤nse/D+ε, where D means the size of the password space and ε is a negligible function of security parameters.


## 4. Our PAKE Protocol

In this section, we present an efficient Ouroboros-based PAKE protocol called OPAKE. Our protocol is described in a generic fashion in Figure1. We use a weight-restricted hash function ℋ≀:0,1∗⟶0,1n as mentioned earlier. Hash functions are defined as follows:ℋ˜:0,1∗⟶SwnF2, ℋ1,ℋ2,ℋ3:0,1∗⟶0,1k, where k is a security parameter. Assume that ℋ˜,ℋ1,ℋ2,ℋ3, and ℋ≀ are independent random functions. Let D be the password space, and π∈D be the password that Alice and Bob share. Then, our protocol is shown as follows.Figure 1
OPAKE.


### 4.1. OPAKE

(a)
Alice generates R←$0,1k and chooses h←$F2n and x,y←$SwnF2. Next, she computes α=ℋ≀π,R,A,B,h. Then, she computes s=α+x+hy. Finally, she sends A,h,s,R to Bob.(b)
Bob tests whether s,h∈F2n. If not, then he rejects the protocol. Otherwise, he generates r1,r2←$SwnF2 and computes er=fwℋ˜r1,r2. Next, he randomly generates ε←$SwεnF2. Then, he computes α=ℋ≀π,R,A,B,h. Finally, he computes s1=r1+hr2 and s2=s−αr2+er+ε and sends B,s1,s2 to Alice.(c)
Alice computes ec=s2−ys1=xr2−yr1+er+ε when receiving s1 and s2. Then, she uses the decoding algorithm CE decoder x,y,ec,t,w,w+wε to get r1 and r2. Then, she computes ρ=ec−xr2+yr1−fwℋ˜r1,r2. Finally, she computes μ=ℋ1ρ,R,A,B,h and sends A,μ to Bob.(d)
Bob tests whether μ is equal to ℋ1ε,R,A,B,h. If not, then he rejects. Otherwise, he accepts and computes η=ℋ2ε,R,A,B,h and a session key sk=ℋ3ε,R,A,B,h. Finally, he sends B,η to Alice.(e)
Alice tests whether η is equal to ℋ2ρ,R,A,B,h. If not, then she rejects. Otherwise, she accepts and computes a session key sk=ℋ3ρ,R,A,B,h.


### 4.2. Correctness

To show the correctness of our protocol, it is sufficient to show that the material derived from Alice and Bob is the same,i.e., ε=ρ. Firstly, honest Alice sends reasonable A,h,s,R to Bob, and honest Bob uses the correct password π to compute α. Then, Bob chooses the secret material ε and encrypts it into the ciphertext s1,s2. Next, Alice decrypts s1,s2 and gets the same material according to the Ouroboros scheme. Hence, the correctness of our PAKE protocol is verified when the two participants execute the protocol honestly.


## 4.1. OPAKE

(a)
Alice generates R←$0,1k and chooses h←$F2n and x,y←$SwnF2. Next, she computes α=ℋ≀π,R,A,B,h. Then, she computes s=α+x+hy. Finally, she sends A,h,s,R to Bob.(b)
Bob tests whether s,h∈F2n. If not, then he rejects the protocol. Otherwise, he generates r1,r2←$SwnF2 and computes er=fwℋ˜r1,r2. Next, he randomly generates ε←$SwεnF2. Then, he computes α=ℋ≀π,R,A,B,h. Finally, he computes s1=r1+hr2 and s2=s−αr2+er+ε and sends B,s1,s2 to Alice.(c)
Alice computes ec=s2−ys1=xr2−yr1+er+ε when receiving s1 and s2. Then, she uses the decoding algorithm CE decoder x,y,ec,t,w,w+wε to get r1 and r2. Then, she computes ρ=ec−xr2+yr1−fwℋ˜r1,r2. Finally, she computes μ=ℋ1ρ,R,A,B,h and sends A,μ to Bob.(d)
Bob tests whether μ is equal to ℋ1ε,R,A,B,h. If not, then he rejects. Otherwise, he accepts and computes η=ℋ2ε,R,A,B,h and a session key sk=ℋ3ε,R,A,B,h. Finally, he sends B,η to Alice.(e)
Alice tests whether η is equal to ℋ2ρ,R,A,B,h. If not, then she rejects. Otherwise, she accepts and computes a session key sk=ℋ3ρ,R,A,B,h.


## 4.2. Correctness

To show the correctness of our protocol, it is sufficient to show that the material derived from Alice and Bob is the same,i.e., ε=ρ. Firstly, honest Alice sends reasonable A,h,s,R to Bob, and honest Bob uses the correct password π to compute α. Then, Bob chooses the secret material ε and encrypts it into the ciphertext s1,s2. Next, Alice decrypts s1,s2 and gets the same material according to the Ouroboros scheme. Hence, the correctness of our PAKE protocol is verified when the two participants execute the protocol honestly.


## 5. Formal Security Analysis of OPAKE

This section gives the formal security of OPAKE under the security model defined in Section3. We prove that an adversary A attacking the protocol OPAKE is unable to determine the sk of a fresh instance with advantage greater than that of an online dictionary attack.Theorem 2.
LetA be an adversary, which runs in time t, and the adversary’s advantage in attacking the protocol is bounded by(9)AdvOPAKEA≤nseD+Onexe+nseAdv2−QCSDOt+Adv3−QCSDOt+nexe+nsenro2k+nse2k,where D denotes the size of the password space, nexe denotes the number of the queries of type Exexcute oracle, nro denotes the number of the queries of the random oracle, and nse denotes the number of queries of type Send oracle.To prove this theorem, we present a sequence of hybrid experiments byP0,P1,P2,P3, and P4 and denote the advantage of A when attacking in the experiment Pi by AdvA,Pi.Protocol P0: in this protocol, the adversary A makes a number of oracle queries in Section 3, i.e., Send,Execute,Reveal, and Test. Besides, the adversary A has access to five independent random oracles ℋ˜,ℋ1,ℋ2,ℋ3, and ℋ≀. Each random oracle is simulated by a list of input-output pairs. When receiving a new query input x, the oracle checks whether x was queried before. If there exists xi=x, then the oracle returns the output in the list. Otherwise, the oracle generates a random number and returns it. Then, the oracle adds the new pair to the list.Protocol P1: this protocol is identical to P0 except that if the oracle Execute A,i,B,j is called between two instances ΠAi and ΠBj, then the session keys skAi and skBj are set equal to a random number selected from 0,1k. Now, we prove that change in the Execute oracle affects the advantage of A in a negligible value.Claim 1.
For any polynomial time adversaryA, we have(10)AdvA,P1−AdvA,P0≤nexeAdv2−QCSDOt+nexeAdv3−QCSDOt+nexenro2k,where nexedenotes the number of the queries of typeExexcuteoracle,nrodenotes the number of the queries of random oracle, andtdenotes the running time ofA.Proof of Claim1:.
First, we show that the probability of same random numbers generated in two different Execute oracle queries is very small. In this situation,A can distinguish P0 and P1 by making the Reveal query simplify. According to the birthday paradox, it is easy to show that the probability of this situation occurring is bounded by Onexe2/2n.
Now, we fix an oracle ExecuteA,i,B,j and assume that the random numbers h,s,R) and ε in this oracle call are not used in previous Execute query. Without the knowledge of ε, the output of ℋ3 is indistinguishable from a random number uniformly selected from 0,1k. Thus, the adversary A can distinguish P0 and P1 if and only if A can recover the information of ε. We denote the probability that A recovers the information of ε by pε. We give two games G1 and G2 to bound pε.GameG1: the adversary carries an honest execution between instances ΠAi and ΠBj:(1)
ΠAi generates R←$0,1k and chooses h←$F2n and x,y←$SwnF2. Next, ΠAi queries the random oracle ℋ≀ on (π,R,A,B,h). The reply of ℋ≀ is denoted by α. Then, ΠAi computes s=α+x+hy. Finally, ΠAi sends A,h,s,R to ΠBj.(2)
ΠBj generates r1,r2←$SwnF2, queries the random oracle ℋ˜ on (r1,r2), and computes er=fwℋ˜r1,r2. Next, ΠBj randomly generates ε←$SwεnF2. Then, ΠBj queries the random oracle ℋ≀ on π,R,A,B,h. The reply of ℋ≀ is denoted by α. Finally, ΠBj computes s1=r1+hr2 and s2=s−αr2+er+ε and sends B,s1,s2 to ΠAi.(3)
ΠAi computes ec=s2−ys1 when receiving s1 and s2. Next, ΠAi uses the decoding algorithm CE decoder x,y,ec,t,w,w+wε to get r1,r2. Then, ΠAi computes ρ=ec−xr2+yr1−fwℋ˜r1,r2. Finally, ΠAi queries the random oracle ℋ1 on ρ,R,A,B,h (denoted by μ) and sends A,μ to ΠBj.(4)
After receivingμ from ΠAi, ΠBj queries the random oracle ℋ2 on ε,R,A,B,h (denoted by η). Finally, ΠBj accepts and sends B,η to ΠAi.(5)
After receivingη from ΠBj, ΠAi accepts. This game ends and adversary A outputs its guess of ε.GameG2: this game is similar to game G1 except that instances ΠAi and ΠBj do not query random oracles ℋ1 and ℋ2:(1)
ΠAi generates R←$0,1k and chooses h←$F2n and x,y←$SwnF2. Next, ΠAi queries the random oracle ℋ≀ on (π,R,A,B,h). The reply of ℋ≀ is denoted by α. Then, ΠAi computes s=α+x+hy. Finally, ΠAi sends A,h,s,R to ΠBj.(2)
ΠBj generates r1,r2←$SwnF2, queries the random oracle ℋ˜ on (r1,r2), and computes er=fwℋ˜r1,r2. Next, ΠBj randomly generates ε←$SwεnF2. Then, ΠBj queries the random oracle ℋ≀ on π,R,A,B,h. The reply of ℋ≀ is denoted by α. Finally, ΠBj computes s1=r1+hr2 and s2=s−αr2+er+ε and sends B,s1,s2 to ΠAi.(3)
After receivings1 and s2 from ΠBj, ΠAi sends a random number μ←$0,1k to ΠBj.(4)
After receivingμ from ΠAi, ΠBj sends a random number η←$0,1k to ΠAi and accepts.(5)
After receivingη from ΠBj, ΠAi accepts. This game ends, and adversary A outputs his guess of ε.
We denote the probability thatA guesses the correct ε in game Gi by pεGi,i∈1,2. Let E be the event that A guesses the correct ε on oracle ℋ1 or ℋ2 with ε,R,A,B,h. Then,(11)pε=pεG1=pεG1|EPrE+pεG1|E¯PrE¯≤PrE+pεG1|E¯.
Obviously, the probability thatA guesses the correct ε is as follows:(12)PrE=nroCnwε,where nro means the number of queries to random oracle ℋ1 and ℋ2. By assuming Cnwε≥2k, we have PrE≤nro/2k.
It is easy to see thatμ and η are indistinguishable from the random numbers in 0,1k when ε,R,A,B,h is not queried in random oracle ℋ1 and ℋ2. So, pεG1|E¯=pεG2. In the following, we show that pεG2≤Adv2−QCSDOt+Adv3−QCSDOt. Given a reasonable h,s, finding the correct information α such that s=α+x+hy is a 2-QCSD problem. Besides, given h,s and x←$SwnF2, we construct an algorithm W to solve 3-QCSD problem by running A on a simulation of the game G2. Algorithm W runs A exactly as G2 except for the change that πBj computes the encryption of message x in step (2). If A returns the correct x, then our algorithm W can solve the 3-QCSD problem. Hence,(13)pεG1|E¯≤Adv2−QCSDOt+Adv3−QCSDOt.
Moreover,(14)pϵ≤nro2k+Adv2−QCSDOt+Adv3−QCSDOt.
SupposeA makes nexe queries of Execute at all. We have(15)AdvA,P1−AdvA,P0≤nexeAdv2−QCSDOt+nexeAdv3−QCSDOt+nexenro2k.
Thus, the claim is desired.
Protocol P2: this protocol is identical to P1 except that when πBj receives the message A,h,s,R generated from πAi, and if πAi and πBj both accept, they are given same random session key sk←$0,1k. If only πBj accepts, a session key sk←$0,1k is for πBj, while no session key is for πAi.Claim 2.
For any polynomial time adversaryA, we get(16)AdvA,P2−AdvA,P1≤nseAdv2−QCSDOt+Adv3−QCSDOt,where nse denotes the number of queries of the type Send and t denotes the running time of A.Proof of Claim2:.
when instanceπBj receives the message A,h,s,R generated from πAi, the message B,s1,s2 is sent by πBj and got by the adversary A. Since the message h,s,R was generated by πAi, A has no information about the secret private key x,y according to the 2-QCSD problem. The advantage of solving the message ε from s1 and s2 by the adversary A is bounded by AdvC3−QCSDOt. In conclusion, suppose that the adversary A makes nse oracle queries of Send oracle, adversary’s advantage of distinguishing between P1 and P2 is bounded by nseAdv2−QCSDOt+nseAdv3−QCSDOt. Therefore, the claim is desired.
Protocol P3: in this protocol, we assume that instance πAi receives a message B,s1,s2 generated from instance πBj, while πBj receives a message A,h,s,R from πAi. In this situation, both πAi and πBj accept and are given a same random session key sk←$0,1k if their session key were not replaced with a random key in protocol P2.Claim 3.
For any polynomial time adversaryA making nse queries of Send oracle to different instances, we obtain(17)AdvA,P3=AdvA,P2.Proof of Claim3:.
It is clear thatP2 and P3 are perfectly indistinguishable for polynomial time adversary A.
Protocol P4: in this protocol, we assume that instance πAi receives a message B,s1,s2 generated from adversary A, or πBj receives a message A,h,s,R generated from adversary A. In this situation, if πAi or πBj accepts the protocol instance, then the protocol halts and adversary A succeeds automatically.Claim 4.
For any polynomial time adversaryA making nse queries of Send oracle to different instances, we have(18)AdvA,P3≤AdvA,P4.Proof of Claim4:.
It is clear that the modification inP4 improves the probability of winning the protocol for the adversary A.Claim 5.
For any polynomial time adversaryA making nse queries of Send oracle, we get(19)AdvA,P4=2PrSuccP4−1≤2nseD+2nse2k+2nseAdv2−QCSDOt+2nseAdv3−QCSDOt+2nsenro2k.Proof of Claim5:.
we consider two cases.Case 1.
Assume that instanceπAi receives a message B,s1,s2 generated from adversary A. After receiving the message, instance πAi computes ρ from the message. Then, πAi gets μ from the query of the random oracle ℋ1 on ρ,R,A,B,h. Next, πAi returns μ to the adversary. In this situation, A has to generate a η, which is equal to the output from random oracle ℋ2 on ρ,R,A,B,h. One possibility is that A guesses the correct η with probability 1/2k since A has no knowledge of ρ. Another possibility is that A recovers the message of ρ with probability pρ. Obviously, pρ is restricted by two factors. The first factor is that adversary A guesses the correct password π and gets the right number η from the query of the random oracle ℋ2. The probability of this case is 1/D. The second factor is that adversary A has to generate the correct form h,s containing α and recover the message ε from s1,s2. As analyzed before, the probability in this situation is bounded by nro/2k+AdvC2−QCSDOt+AdvC3−QCSDOt. We use nse1 to denote the number of this kind of queries. Thus, the success probability of A in this case is bounded by(20)PrSuccCaseI≤nse11D+nro2k+Adv2−QCSDOt+Adv3−QCSDOt+12k.Case 2.
Assume that instanceπBj receives a message A,h,s,R generated from adversary A. After receiving the message, instance πBj generates r1,r2←$SwnF2, queries the random oracle ℋ˜ on (r1,r2), and computes er=fwℋ˜r1,r2. Next, ΠBj randomly generates ε←$SwεnF2. Then, ΠBj queries the random oracle ℋ≀ on π,R,A,B,h. The reply of ℋ≀ is denoted by α. Finally, ΠBj computes s1=r1+hr2 and s2=s−αr2+er+ε and returns B,s1,s2 to A. In this situation, A has to generate a μ, which is equal to the output from random oracle ℋ1 on ε,R,A,B,h. Similar to the previous case, one possibility is that A guesses the correct η with probability 1/2k since A has no knowledge of ε. Another possibility is that A guesses the correct password π. We use nse2 to denote the number of this kind of queries. Thus, the success probability of A in this case is bounded by(21)PrSuccCaseII≤nse21D+12k.
Hence, we get(22)PrSuccP4≤nse11D+nro2k+Adv2−QCSDOt+Adv3−QCSDOt+12k+nse21D+12k≤nseD+nse2k+nseAdv2−QCSDOt+nseAdv3−QCSDOt+nsenro2k.
Therefore, we have(23)AdvA,P4=2PrSuccP4−1≤2nseD+2nse2k+2nseAdv2−QCSDOt+2nseAdv3−QCSDOt+2nsenro2k.
By combining all the claims, we have the advantage for the adversaryA in the real attack, i.e.,(24)AdvOPAKEA≤nseD+Onexe+nseAdv2−QCSDOt+Adv3−QCSDOt+nexe+nsenro2k+nse2k.
Hence, Theorem2 is desired.


## 6. Performance Analysis

In this section, we provide the efficiency evaluation of our scheme. The security parameters we used are adopted from the Ouroboros scheme[29]. The scheme implementation is written in C++. The program has been performed on a computer running Linux. The computer has an Intel Core i7-8750H CPU@2.20 GHz and 4 GB of memory. For each parameter set, the performance of our proposed protocol is shown in Table 1. The results show that the efficiency of our scheme is considerable.Table 1
Time consumption of different security levels of OPAKE.
InstancenwwεtkSecurityTime (ms)OPAKE-805851474730512806.41OPAKE-128136917575455121287.53OPAKE-25640013147147855122569.14


## 7. Conclusion

In this study, we propose a new password-authenticated key exchange based on Ouroboros key exchange scheme with formal security proof. Our PAKE scheme enjoys several desired properties, including (1) our scheme has considerable efficiency; (2) our scheme provides mutual explicit authentication; and (3) our scheme is resistant to quantum attacks and an attacker who gets the session key cannot use it to perform an offline dictionary attack. The security of our scheme is reduced to decoding random quasi-cyclic codes in the random oracle model.



---

*Source: 9257443-2022-07-14.xml*