Provably Secure Three-Party Password-Based Authenticated Key Exchange from RLWE

Abstract

Three-party key exchange, where two clients aim to agree a session key with the help of a trusted server, is prevalent in present-day systems. In this paper, we present a practical and secure three-party password-based authenticated key exchange protocol over ideal lattices. Aside from hash functions our protocol does not rely on external primitives in the construction and the security of our protocol is directly relied on the Ring Learning with Errors (RLWE) assumption. Our protocol attains provable security. A proof-of-concept implementation shows our protocol is indeed practical.

1 Introduction

Key Exchange (KE), which is a fundamental cryptographic primitive, allows two or more parties to securely share a common secret key over insecure networks. KE is one of the most important cryptographic tools and is widely used in building secure communication protocols. Authenticated Key Exchange (AKE), which enables each party to authenticate the other party, can prevent the adversary from impersonating the honest party in the conversation. Password-based Authenticated Key Exchange (PAKE), which allows parties to share a low-entropy password that is easy for human memory, has become an important cryptographic primitive because it is easy to use and does not rely on special hardware to store high-entropy secrets.

The early solution to this problem was to achieve two-party password-based authenticated key exchange (2PAKE), in which both parties identified their communication partners with shared passwords. Many 2PAKE protocols have been proposed [2, 6, 22]. However, in a communication environment where only 2PAKE protocols are available, each party must remember many passwords, for each entity with which he may wish to establish a session key corresponds to a password. In detail, assuming that a communication network has n users, in which any two users exchange a key, there will be $n(n-1)/2$ passwords to be shared, and all these passwords must be stored securely. This is unrealistic when the network is relatively large. To solve this problem, three-party PAKE (3PAKE) was proposed. In 3PAKE, each client shares a password with the trusted server, and then two clients will establish a common session key with the help of the server. This solution is very realistic in practical setup, because it provides each client user with the ability to exchange secure keys with all other client users, and each user only needs to remember one password. The 3PAKE protocol can be applied to various electronic applications, such as in the JobSearch International, trusted third parties can help employers and employees to hire on Jobsearch.

In 1995, Steiner et al. proposed the first 3PAKE protocol [26]. Then many works about 3PAKE protocols have been proposed [1, 7, 11, 16, 27]. For a security 3PAKE protocol, there are two types of attacks it should resist: undetectable on-line password guessing attacks [10] and off-line password guessing attacks [16]. In 1995, Ding and Horster [10] and Sun et al. [27] pointed out that Steiner et al.’s protocol [26] was vulnerable to undetectable on-line password guessing attacks. That is, an adversary can stay un-detected and log into the server during an on-line transaction. In 2000, Lin et al. [16] further pointed out Steiner et al.’s protocols [26] also suffer from off-line password guessing attacks. In this attack, an attacker can guess passwords off-line until getting the correct one. There is another attack: detectable on-line password guessing attacks, which requires the participation of the authentication server. In this attack, the server will detect a failed guess and record it. Since after a few unsuccessful guesses, the server can stop any further attempts, this attack is less harmful. In practice, password-based authenticated key exchanges are required to have a property, forward secrecy, that when the password is compromised, it does not reveal the earlier established session keys and the updating password.

However, the existed 3PAKE are based on the classic hard problems, such as factoring, the RSA problem, or the computational/decisional DH problem. It is well known that those problems are vulnerable to quantum computers [25]. Since the vigorous development of quantum computers, searching other counterparts based on problems which are believed to be resistant to quantum attacks is more and more urgent. Hence the motivation of this paper is that can we propose a proven security 3PAKE that can resist quantum attacks? Note that lattice-based cryptographic have many advantages such as quantum attacks resistance, asymptotic efficiency, conceptual simplicity and worst-case hardness assumption, and it is a perfect choice to build lattice-based 3PAKE.

Our Contributions. In this paper, we propose a 3PAKE protocol based on the Ring Learning with Errors (RLWE), which in turn is as hard as some lattice problems (SIVP) in the worst case on ideal lattices [20]. Our protocol is designed without extra primitives such as public-key encryption, signature or message authentication code, which usually lead to a high cost for certain applications. By having the 3PAKE as a self-contained system, we show that our protocol directly relys on the hardness of RLWE and Pairing with Errors problem (PWE), which can reduce to the RLWE problem, in the random oracle model. Our protocol RLWE-3PAK resists undetectable on-line passwords guessing attacks and off-line passwords guessing attacks, and enjoys forward secrecy and quantum attacks resistance. Furthermore, our protocol enjoys mutual authentication, which means that the users and the server can authenticate one another.

In terms of protocol design, benefitting from the growth of lattice-based key exchange protocols [8, 23], we can utilize the key agreement technique to construct our protocol. We use Peikert’s [23] reconciliation mechanism to achieve the key agreement in our protocol. At the same time, in order to make our protocol resist undetectable passwords guessing attacks and off-line passwords guessing attacks, we also use additional key reconciliation mechanism between server and clients to realize the mutual authentication. Our security model is modified from Bellare et al.’s model [2, 3]. Since the interactions in three-party setting are more complex than that of two-party setting, proving the security of our 3PAKE protocol is a very tricky problem. We use a variant of the Pairing with errors problem [9] to simplify the proof and the proof strategy followed from [21]. Finally, we manage to establish a full proof of security for our protocol and show that our protocol enjoys forward security.

We select concrete choices of parameters and construct a proof-of-concept implementation. The performance results show that our protocol is efficient and practical.

Related Works. In the existed literatures, 3PAKE protocols are based on public/private key cryptography [10, 16, 26], which usually incur additional computation and communication overheads. Asymmetric key cryptography based protocols [11, 15, 17] usually require “the ideal cipher model”, which is a strong assumption, to prove the security of the protocols. There are some other types of protocols [13, 18] which are with no formal security proof.

Lattice-Based AKE or PAKE. Zhang et al. [32] proposed an authenticated RLWE-based key exchange which is similar to HMQV [14]. In 2009, Katz and Vaikuntanathan [12] proposed a CCA-secure lattice-based PAKE, which is proven secure in standard model security. In 2017, Ding et al. [9] proposed RLWE-based PAKE, whose proof is based on random oracle model (ROM), and its implementation is very efficient. Then in 2017, Zhang and Yu [31] proposed a two-round CCA-secure PAKE based on the LWE assumption.

Roadmap. In Sect. 2, we introduce our security model, notations and the Ring Learning with Errors background. Our protocol RLWE-3PAK is in Sect. 3. And in Sect. 4, we give the proof of the protocol’s security. The parameter choices and proof-of-concept implementation of our protocol is presented in Sect. 5. Finally, we conclude and discuss some further works in Sect. 6.

2 Preliminaries

2.1 Security Models

The security model is modified from [2] and [3]. The 3PAKE protocol involves three parties, two clients A and B who wish to establish a shared secret session key and a trusted server S who try to help distribute a key to A and B. Let P be a 3PAKE protocol.

Security Game. Given a security parameter $\kappa$, an algorithmic game initialized is played between ${\mathcal {C}}{\mathcal {H}}$ - a challenger, and a probability polynomial time adversary $\mathcal {A}$. For simulating network traffic for the adversary, ${\mathcal {C}}{\mathcal {H}}$ will essentially run P.

Users and Passwords. There is a fixed set of users, which is partitioned into two non-empty sets of clients and servers. We also assume D is some fixed, non-empty dictionary with size of L. Then before the game starts, a password $pw_{U}$ is drawn uniformly at random from D and assigned to each clients outside of the adversary’s view. And for each server S, we set $pw_{S}:=(f(pw_{U}))_U$, where U runs through all of clients. Usually, f is some efficiently computable one-way function (in our protocol we let f be a hash function).

User Instances. We denote some instance i of a user U as $\varPi _{U}^i$. The adversary $\mathcal {A}$ controls all the communications that exchange between a fixed number of parties by interacting with a set of $\varPi _{U}^i$ oracles. At any point of in time, an client user instance $\varPi _{U}^i$ may accept. When $\varPi _{U}^i$ accepts, it holds a partner-id (PID) $pid_{U}^i$, a session-id (SID) $sid_{U}^i$, and a session key (SK) $sk_{U}^i$. The PID is the identity of the user that the instance believes talking to, and SK is what the instance aims to compute after the protocol completed. The SID is an identifier and is used to uniquely name the ensuing session. Note that the SID and PID are open to the adversary, and the SK certainly is secret for $\mathcal {A}$.

Oracle Queries. The adversary $\mathcal {A}$ has an endless supply of oracles and it models various queries to them with each query models a capability of $\mathcal {A}$. The oracle queries by the adversary $\mathcal {A}$ are described as follows:

• The Send(U, i, M) query allows the adversary to send some message M to oracle $\varPi _{U}^i$ of her choice at will. The $\varPi _{U}^i$ oracle, upon receiving such a query, will compute what the protocol P says, updates its state, and then returns to $\mathcal {A}$ the response message. If $\varPi _{U}^i$ has accepted or terminated, this will be made known to the adversary $\mathcal {A}$. This query is for dealing with controlling the communications by the adversary.

• The Execute(A, i, B, j, S, t) query causes P to be executed to completion between two clients instances $\varPi _{A}^i$, $\varPi _{B}^j$ and a server instance $\varPi _{S}^t$, and hands all the execution’s transcripts to $\mathcal {A}$. This query is for dealing with off-line password guessing attacks.

• The Reveal(U, i) query allows $\mathcal {A}$ to expose session key SK that has been previously accepted. If $\varPi _{U}^i$ has accepted and holds some SK, then $\varPi _{U}^i$, upon receiving such a query, will sends SK back to $\mathcal {A}$. This query is for dealing with known-key security, which means that when the session key is lost, it does not reveal the other session keys.

• The Corrupt(U) query allows $\mathcal {A}$ to corrupt the user U at will. If U is a server, returns $(f(pw_C))_C$ to $\mathcal {A}$, else returns $pw_U$ to $\mathcal {A}$. This query is for dealing with forward secrecy.

• The Test(U, i) is a query that does not correspond to $\mathcal {A}$’s abilities. The oracle chooses a bit $b\in \{0,1\}$ randomly. If $\varPi _{U}^i$ has accepted with some SK and is being asked by such a query, then $\mathcal {A}$ is given the actual session key when $b=1$; $\mathcal {A}$ is given a key chosen uniformly at random when $b=0$. $\mathcal {A}$ is allowed to query this oracle once and only on a fresh $\varPi _{U}^i$ (defined in the following). This query models the semantic security of the session key SK.

Ending the Game. Eventually, the adversary ends the game, and then outputs a single bit $b'$.

And next we define what constitutes the breaking of the 3PAKE protocol. Firstly we introduce the notions of instance partnering and instance freshness with forward secrecy.

Definition 1

(Partnering). Let $\varPi _{A}^i$ and $\varPi _{B}^j$ be two instances. We shall say that $\varPi _{A}^i$ and $\varPi _{B}^j$ are partnered if both instances accept, holding ($sk_A^i,sid_A^i,pid_A^i$) and ($sk_B^j,sid_B^j,pid_B^j$) respectively, and the followings hold:

• $sid_A^i=sid_B^j=sid$ is not null and $sk_A^i=sk_B^j$ and $pid_A^i=B$ and $pid_B^j=A$;

• No instance besides $\varPi _{A}^i$ and $\varPi _{B}^j$ accepts with a SID of sid.

Definition 2

(Freshness). Instance $\varPi _{A}^i$ is fs-fresh or it holds a fresh session key at the end of the execution if none of the following events occur:

• Reveal(A, i) was queried;

• a Reveal(B, j) was queried where $\varPi _{B}^j$ is parted with $\varPi _{A}^i$, if it has one;

• before the Test query, a Corrupt(U) was queried for some user U and a Send(A,i,M) query occurs for some string M.

Password Security. We say the adversary breaks the password security of 3PAKE if he learns the password of a user by either on-line or off-line password guessing attacks.

AKE security. We now define the advantage of the adversary $\mathcal {A}$ against protocol P for the authenticated key exchange (ake). Let $\hbox {Succ}_{P}^{ake}(\mathcal {A})$ be the event that the adversary makes a single Test(A, i) query directed to some terminated fresh instances $\varPi _{A}^i$, and outputs a bit $b'$ eventually, and $b'=b$ where b is the bit selected in the Test(A, i) query. Then $\mathcal {A}$’s advantage is defined as:

$$\begin{aligned} \text {Adv}_{P}^{ake}(\mathcal {A})\overset{\text {def}}{=}2\text {Pr}\Big [\text {Succ}_{P}^{ake}(\mathcal {A})\Big ]-1 \end{aligned}$$

It is easy to verify that

$$\begin{aligned} \text {Pr}(\text {Succ}_{P}^{ake}(\mathcal {A}))=\text {Pr}(\text {Succ}_{P'}^{ake}(\mathcal {A}))+\epsilon \Longleftrightarrow \text {Adv}_{P}^{ake}(\mathcal {A})=\text {Adv}_{P'}^{ake}(\mathcal {A})+2\epsilon . \end{aligned}$$

The protocol 3PAKE is AKE-secured if $\text {Adv}_{P}^{ake}(\mathcal {A})$ is negligible for all probabilistic polynomial time adversaries.

2.2 Notations

Let n be an integer, which is a power of 2. We define the ring of integer polynomials $R:={\mathbb {Z}}[x]/(x^{n}+1)$. For any positive integer q, we set $R_{q}:={\mathbb {Z}}_{q}[x]/(x^{n}+1)$ as the ring of integer polynomials modulo $x^{n}+1$, where every coefficient is reduced modulo q. For a polynomial y in R, identify y with its coefficient vector in ${\mathbb {Z}}$. Let the norm of a polynomial to be the norm of its coefficient vector. Assume $\chi$ is a probability distribution over R, then $x\xleftarrow {\$}\chi$ means the coefficients of x are sampled from $\chi$.

For any positive real $\beta \in {\mathbb {R}}$, we set $\rho _{\beta }(x)=exp(-\pi \frac{||x||^2}{\beta ^2})$ as the Gaussian function, which is scaled by a parameter $\beta$. Let $\rho _{\beta }({\mathbb {Z}}^n)=\sum _{{\mathbf {x}}\in {\mathbb {Z}}^n}\rho _{\beta }({\mathbf {x}})$. Then for a vector ${\mathbf {x}}\in {\mathbb {Z}}^n$, let $D_{{\mathbb {Z}}^n,\beta }({\mathbf {x}})=\frac{\rho _{\beta }({\mathbf {x}})}{\rho _{\beta }({\mathbb {Z}}^n)}$ to indicate the n-dimensional discrete Gaussian distribution. Usually we denote this distribution as $\chi _{\beta }$.

2.3 Ring Learning with Errors

The Learning with Errors (LWE) problem was first introduced by Oded Regev in [24]. He showed that under a quantum reduction, solving LWE problem in the average cases was as hard as solving the worst cases of the certain lattice problems. However since with a large key sizes of $O(n^2)$, LWE based cryptosystems are not efficient for practical applications. In 2010, Lyubashevsky, Peikert, and Regev [20] introduced the version of LWE in the ring setting: the Ring Learning with Errors problem, which could drastically improve the efficiency.

For uniform random elements $a,s\xleftarrow {\$}R_q$ and an error distribution $\chi$, let $A_{s,\chi }$ denote the distribution of the RLWE pair $(a,as+e)$ with the error $e\xleftarrow {\$}\chi$. Then given polynomial number of such samples, the search version of RLWE is to find the secret s, and the decision version of the RLWE problem ($\hbox {DRLWE}_{q,\chi }$) is to distinguish $A_{s,\chi }$ from an uniform distribution pair on $R_{q}\times R_{q}$. RLWE enjoys a worst case hardness guarantee, which we state here.

Theorem 1

([20], Theorem 3.6). Let $R={\mathbb {Z}}[x]/(x^n+1)$ where n is a power of 2, $\alpha =\alpha (n)<\sqrt{logn/n}$, and $q\equiv 1\mod 2n$ which is a ploy(n)-bounded prime such that $\alpha q \ge \omega (\sqrt{logn})$. Then there exists a ploy(n)-time quantum reduction from ${\tilde{O}}(\sqrt{n}/\alpha )$-SIVP (Short Independent Vectors Problem) on ideal lattices in the ring R to solving $\hbox {DRLWE}_{q,\chi }$ with $l-1$ samples, where $\chi =D_{{\mathbb {Z}}^n,\beta }$ is the discrete Gaussian distribution with parameter $\beta =\alpha q \cdot (nl/log(nl))^{1/4}$.

We have the following useful fact.

Lemma 1

([19], Lemma 4.4). For any $k>0$, $Pr _{x\leftarrow \chi _{\beta }}(|x|>k\beta )\le 2e^{-\pi k^2}.$

Note that taking $k=6$ gives tail probability approximating $2^{-162}$.

Reconciliation Mechanism. We now recall the reconciliation mechanism defined in [23]. This technique is one of the foundations of our protocol.

For an integer p (e.g. $p=2$) which divides q, define the modular rounding function $\lfloor \cdot \rceil _p :{\mathbb {Z}}_{q}\rightarrow {\mathbb {Z}}_{p}$ as $\lfloor x \rceil _p :=\lfloor \frac{p}{q}\cdot x\rceil$ and $\lfloor \cdot \rfloor _p :{\mathbb {Z}}_{q}\rightarrow {\mathbb {Z}}_{p}$ as $\lfloor x \rfloor _p :=\lfloor \frac{p}{q}\cdot x\rfloor$. Let the modulus $q\ge 2$ and be an even, define disjoint intervals $I_0:=\{0,1,\ldots ,\lfloor \frac{q}{4}\rceil -1\}$, $I_1:=\{-\lfloor \frac{q}{4}\rceil ,\ldots ,-1\} \bmod {q}$. Note that when $v\in I_0\cup I_1$, $\lfloor v \rceil _2=0$, and when $v\in ( I_0+\frac{q}{2})\cup (I_1+\frac{q}{2})$, $\lfloor v \rceil _2=1$. Define the cross-rounding function $\langle \cdot \rangle _2: {\mathbb {Z}}_q\rightarrow {\mathbb {Z}}_2$ as $\langle v \rangle _2:=\lfloor \frac{4}{q}\cdot v\rfloor \bmod {2}.$ Note that $\langle v \rangle _2=b\in \{0,1\}$ such that $v\in I_b\cup (\frac{q}{2}+I_b);$.

Define the set $E:=[-\frac{q}{8},\frac{q}{8})\cap {\mathbb {Z}}.$ Then suppose v, w are sufficiently close, and given w and $\langle v \rangle _2$, we can recover $\lfloor v \rceil _2$ using the reconciliation function rec: ${\mathbb {Z}}_q\times {\mathbb {Z}}_2\rightarrow {\mathbb {Z}}_2$:

$$\begin{aligned} \text {rec}(w,b)={\left\{ \begin{array}{ll} 0&{} \text {if } w\in I_b+E (\bmod {q}),\\ 1&{} \text {otherwise.}\\ \end{array}\right. } \end{aligned}$$

When q is odd, to avoid the bias produced by the rounding function, Peikert introduced a randomized function dbl(): ${\mathbb {Z}}_{q}\rightarrow {\mathbb {Z}}_{2q}$. For $v\in {\mathbb {Z}}_{q}$, dbl(v)$:=2v -{\bar{e}}\in {\mathbb {Z}}_{2q}$ for some random ${\bar{e}}\in {\mathbb {Z}}$ which is independent of v and uniformly random moduloes two. Usually we denote v with an overline to means that ${\bar{v}}\leftarrow$ dbl(v).

For ease of presentation, we define function HelpRec(X): (1). ${\overline{X}}\leftarrow \text {dbl}(X)$; (2). $W\leftarrow \langle {\overline{X}}\rangle _2$; $K\leftarrow \lfloor {\overline{X}}\rceil _2$; (3). return (K, W).

Note that for $w,v\in {\mathbb {Z}}_q$, we need apply the appropriated rounding function from ${\mathbb {Z}}_{2q}$ to ${\mathbb {Z}}_2$, which means that $\lfloor x \rceil _p=\lfloor \frac{p}{2q}\cdot x\rceil$, $\langle x \rangle _2=\lfloor \frac{4}{2q}\cdot x\rfloor$, and similar with rec function. Obviously, if $(K,W)\leftarrow \text {HelpRec}(X)$ and $Y=X+e$ with $||e||_{\infty }<\frac{q}{8}$, we have rec$(2\cdot Y,W)=K$. These definitions also can be extended to $R_q$ by applying coefficient-wise to the coefficients in ${\mathbb {Z}}_{q}$ of a ring elements. In other words, for a ring element $v=(v_0,\ldots ,v_{n-1})\in R_q$, set $\lfloor v \rceil _2 =(\lfloor v_0 \rceil _2,\ldots ,\lfloor v_{n-1}\rceil _2);$ $\langle v \rangle _2=(\langle v_0\rangle _2, \ldots , \langle v_{n-1} \rangle _2);$ HelpRec$(v)=(\text {HelpRec}(v_0),\ldots ,\text {HelpRec}(v_{n-1}))$. And for a binary-vector $b=(b_0,\ldots ,b_{n-1})\in \{0,1\}^n$, set rec(v, b)=(rec($v_0,b_0$),..., rec($v_{n-1},b_{n-1}$)).

Lemma 2

([23]). For $q\ge 2$ is even, if v is uniformly random chosen from ${\mathbb {Z}}_{q}$, then $\lfloor v \rceil _2$ is uniformly random when given $\langle v \rangle _2$; if $w=v+e\bmod {q}$ for some $v\in {\mathbb {Z}}_q$ and $e\in E$, then rec($w,\langle v \rangle _2$)$=\lfloor v \rceil _2$. For $q>2$ is odd, if v is uniformly random chosen from ${\mathbb {Z}}_q$ and ${\bar{v}}\leftarrow dbl (v)\in {\mathbb {Z}}_{2q}$, then $\lfloor {\bar{v}} \rceil _2$ is uniformly random given $\langle {\bar{v}}\rangle _2$.

The PWE Assumption. To prove the security of our protocol, we introduce the Pairing with Errors (PWE) assumption. This assumption is following the work in [9], and we replace the reconciliation mechanism of them by Peikert’s version. For any $(a,s)\in R_q^2$, we set $\tau (a,s):=\lfloor {\overline{as}}\rceil _2$ and if there is $(c,W)\leftarrow \text {HelpRec}(as)$, then $\tau (a,s)=c=\text {rec}({\overline{as}},W)$. Assume that a PPT adversary $\mathcal {A}$ takes inputs of the form $(a_1,a_2,b,W)$, where $(a_1,a_2,b)\in R_q^3$ and $W\in \{0,1\}^n,$ and outputs a list of values in $\{0,1\}^n$. $\mathcal {A}$’s objective is to obtain the string $\tau (a_2,s)$ in its output, where s is randomly chosen from $R_q$, b is a “small additive perturbation” of $a_1s$, W is $\langle \overline{a_2s}\rangle _2$. Define

$$\begin{aligned} \begin{aligned} \text {Adv}_{R_q}^{\text {PWE}}(\mathcal {A})\overset{\text {def}}{=}Pr\Big [a_1\xleftarrow {\$} R_q;&a_2\xleftarrow {\$} R_q; s,e\xleftarrow {\$} \chi _{\beta };b\leftarrow a_1s+e;\\&W\leftarrow \langle \overline{a_2s}\rangle _2:\tau (a_2,s)\in \mathcal {A}(a_1,a_2,b,W)\Big ]. \end{aligned} \end{aligned}$$

Let $\text {Adv}_{R_q}^{\text {PWE}}(t,N)=max_{\mathcal {A}}\left\{ \text {Adv}_{R_q}^{\text {PWE}}(\mathcal {A})\right\}$, where the maximum is taken over all adversaries times complexity which at most t that output a list containing at most N elements of $\{0,1\}^n$. Then for t and N polynomial in $\kappa$, the PWE assumption states that $\text {Adv}_{R_q}^{\text {PWE}}(t,N)$ is negligible.

To states the hardness of PWE assumption, We define the decision version of PWE problem as follows. If DPWE is hard, so is PWE.

Definition 3

(DPWE). Given $(a_1,a_2,b,W,\sigma )\in R_q \times R_q\times R_q \times \{0,1\}^n\times \{0,1\}^n$ where $W=\langle {\overline{K}}\rangle _2$ for some $K\in R_{q}$, where ${\overline{K}}\leftarrow dbl (K)$ and $\sigma =rec (2\cdot K,W)$. The Decision Pairing with Errors problem (DPWE) is to decide whether $K=a_2s+e_1$, $b=a_1s+e_2$ for some $s,e_1,e_2$ is drawn from $\chi _{\beta }$, or (K, b) is uniformly random in $R_q\times R_q$.

In order to show the reduction of the DPWE problem to the RLWE problem, we would like to introduce a definition to what we called the RLWE-DH problem [9] which can reduce to RLWE problem.

Definition 4

(RLWE-DH). Let $R_q$ and $\chi _{\beta }$ be defined as above. Given an input ring element ($a_1,a_2,b,K$), where (a, X) is uniformly random in $R_q^2$, The DRLWE-DH problem is to tell if K is $a_2s+e_1$ and $b=a_1s+e_2$ for some $s,e_1,e_2\xleftarrow {\$} \chi _{\beta }$ or (K, b) is uniformly random in $R_q\times R_q$.

Theorem 2

([9], Theorem 1). Let $R_q$ and $\chi _{\beta }$ be defined as above, then the RLWE-DH problem is hard to solve if RLWE problem is hard.

Theorem 3

Let $R_q$ and $\chi _{\beta }$ be defined as above. The DPWE problem is hard if the RLWE-DH problem is hard.

Proof

Suppose there exists an algorithm D which can solve the DPWE problem on input $(a_1,a_2,b,W,\sigma )$ where for some $K\in R_{q}$, $W=\langle {\overline{K}}\rangle _2$ and $\sigma =\text {rec}(2\cdot K,W)$ with non-negligible probability $\epsilon$. By using D as a subroutine, we can build a distinguisher $D'$ on input $(a_1',a_2',b',K')$, solve the RLWE-DH problem :

• Compute $W=\langle \overline{K'}\rangle$ and $\sigma =\text {rec}(2\cdot K', W)$.

• Run D using the input $(a_1',a_2',b',W,\sigma )$.

  • If D outputs 1 then $K'$ is $a_2's+e_1$ for some $e_1\xleftarrow {\$} \chi _{\beta }$ and $b'=a_1s+e_2$ for some $s,e_1\xleftarrow {\$} \chi _{\beta }$.

  • Else $(K',b')$ is uniformly random element from $R_q\times R_q$.

Note that if ($a_1',b'$), ($a_2',K'$) is two RLWE pairs, with input $(a_1',a_2',b',W,\sigma )$ defined above, D outputs 1 with probability $\epsilon$, hence RLWE-DH can be solved with probability $\epsilon$ using distinguisher $D'$. This means that RLWE-DH can be solved with non-negligible advantage, which contradicts RLWE-DH’s hardness. $\square$

3 A New Three-Party Password Authenticated Key Exchange

In this section we introduce a new 3PAKE based on RLWE: RLWE-3PAK. The protocol RLWE-3PAK is given in Fig. 1.

3.1 Description of RLWE-3PAK

Let $q=2^{\omega (log n)}+1$ be an odd prime such that $q\equiv 1 \bmod {2n}$. Let $a\in R_q$ be a fixed element chosen uniformly at random and given to all users. Let $\chi _{\beta }$ be a discrete Gaussian distribution with parameter $\beta$. Let $H_1:\{0,1\}^*\mapsto R_q$ be hash function, $H_l:\{0,1\}^*\rightarrow \{0,1\}^\kappa$ for $l\in \{2,3,4\}$ be hash functions which is used for verification of communications, and $H_5:\{0,1\}^*\rightarrow \{0,1\}^\kappa$ be a Key Derivation Function (KDF), where $\kappa$ is the bit-length of the final shared key. We model the hash functions $H_l$ for $l\in \{1,2,3,4,5\}$ as random oracles. We will make use of $\langle \cdot \rangle _2$, $\lfloor \cdot \rceil _2$, HelpRec() and rec() defined in Sect. 2.3.

Fig. 1.

Three-party password authenticated protocol: RLWE-3PAK, where $s_S,e_S,s_f,e_f,s_g,e_g,s_B,e_B,e_B',e_B'',e_A,e_A',e_1,e_2$ is sampled from $\chi _{\beta }$. Shared session key is $sk=H_5(\langle A,B,S,m_A,m_B,p_A,p_B,\sigma \rangle )$.

The function f used to compute client passwords’ verifiers for the server is instantiated as: $f(\cdot )=-H_1(\cdot )$. Our protocol which is illustrated in Fig. 1 consists of the following steps:

• Client B initiation. Client B sends the identity of A, the one who he wants to communicate with, and his own to S as an initial request. (Note that, this step also can be executed by A.)

• Server S first response. Server S receivers B’s message, then S chooses $s_f,e_f,s_g,$ $e_g\xleftarrow {\$}\chi _{\beta }$ to compute $b_A=as_f+e_f$ and $b_B=as_g+e_g$, and computes public elements $m_A=b_A+\gamma '$ and $m_B=b_B+\eta '$ where $\gamma ':=-H_1(pw_1)$, $\eta ':=-H_1(pw_2)$. Then S sends $\langle m_A,m_B\rangle$ to B.

• Client B first response. After receiving S’s message, client B checks if $m_A,m_B\in R_q$. If not, aborts; otherwise retrieves $b_B'=m_B+\eta$ where $\eta =H_1(pw_2)$ and chooses $s_B,e_B,e_B'\xleftarrow {\$}\chi _{\beta }$ to compute $p_B=as_B+e_B$ and $v_1=b_B's_B+e_B'$. Then B uses $v_1$ to compute $(\sigma _B,w_B)\leftarrow \text {HelpRec}(v_1)$, and computes $k_{BS}\leftarrow H_2(\langle A,B,S,b_B',\sigma _B\rangle )$. B sends $\langle m_A,m_B,p_B,k_{BS},w_B\rangle$ to A.

• Client A first response. After receiving B’s message, A checks if $m_A,p_B\in R_q$. If not, aborts; otherwise similarly with B, retrieves $b_A'=m_A+\gamma$ where $\gamma =H_1(pw_1)$ and chooses $s_A,e_A,e_A'\xleftarrow {\$}\chi _{\beta }$ to compute $p_A=as_A+e_A$ and $v_2=b_A's_A+e_A'$. Then A uses $v_2$ to compute $(\sigma _A,w_A)\leftarrow \text {HelpRec}(v_2)$, and computes $k_{AS}\leftarrow H_2(\langle A,B,S,b_A',\sigma _A\rangle )$. Finally A sends $\langle p_A,p_B,k_{AS},k_{BS},w_A,w_B\rangle$ to S.

• Server S second response. After receiving A’s message, S checks if $p_A,p_B\in R_q$. If not, aborts; otherwise computes $\sigma _A'\leftarrow \text {rec}(2p_As_f,w_A)$ and checks if $k_{AS}=H_2(\langle A,B,S,b_A,\sigma _A'\rangle )$. If not, aborts; otherwise computes $\sigma _B'\leftarrow \text {rec}(2p_Bs_g,w_B)$ and checks if $k_{BS}=H_2(\langle A,B,S,b_B,\sigma _A'\rangle )$. If not, aborts; otherwise continues. Then, S samples $s_S,e_1,e_2\xleftarrow {\$}\chi _{\beta }$, and computes $c_B=p_As_S+e_1$ and $c_A=p_Bs_S+e_2$ which will be used to retrieve the final messages by A and B. To give the authentication of S to B and A, S computes $k_{SA}\leftarrow H_2(\langle A,B,S,p_B,\sigma _A'\rangle )$ and $k_{SB}\leftarrow H_2(\langle A,B,S,p_A,\sigma _B'\rangle )$. Finally S sends $\langle p_A,c_A,c_B,k_{SA},k_{SB}\rangle$ to B.

• Client B second response. After receiving S’s message, B checks if $p_A,c_A,c_B\in R_q$. If not, aborts; otherwise checks if $k_{SB}=H_2(\langle A,B,S,p_A,\sigma _B\rangle )$. If not, aborts; otherwise samples $e_B''\xleftarrow {\$}\chi _{\beta }$ and computes $v_B=c_Bs_B+e_B''$, $(\sigma ,w)\leftarrow \text {HelpRec}(v_B)$, $k=H_3(\langle A,B,S,m_A,m_B,p_A,p_B,\sigma \rangle )$, $k''=H_4(\langle A,B,S,m_A,m_B,$ $p_A,p_B,\sigma \rangle )$ and $sk_B=H_5(\langle A,B,S,m_A,m_B,p_A,p_B,\sigma \rangle )$. Finally B sends $\langle c_A,w,k,$ $k_{SA}\rangle$ to A.

• Client A second response. After receiving B’s message, A checks if $c_A\in R_q$. If not, aborts; otherwise checks if $k_{SA}=H_2(\langle A,B,S,p_B,\sigma _A\rangle )$. If not, aborts; otherwise computes $\sigma '\leftarrow \text {rec}(2c_As_A,w)$. Then checks if $k=H_3(\langle A,B,S,m_A,m_B,p_A,$ $p_B,\sigma '\rangle )$. If not, aborts; otherwise computes $k'=H_4(\langle A,B,S,m_A,m_B,p_A,p_B,\sigma '\rangle )$ and $sk_A=H_5(\langle A,B,S,m_A,m_B,p_A,p_B,\sigma '\rangle )$. Finally A sends $k'$ to B.

• Client B finish. After receiving $k'$ from A, B checks if $k'=k''$. If not, aborts; otherwise terminates.

3.2 Design Rationale

In our protocol, the check for ring elements ensures that all ring operations are valid. The participants are split into clients and servers and servers are allowed to store a password file. By having the server store not $pw_1,pw_2$, but $\langle \gamma ',\eta '\rangle$ allows us to improve the efficiency of the server.

Our 3PAKE may seem a bit complicated, but this is because of the need to provide authentication in the exchange sessions. When we remove all authentication functions, we will find that the main body of the protocol is very simple. In the absence of authentication, party A and party B send $p_A$ and $p_B$ to S, respectively. S computes $c_A$ and $c_B$ by using $p_A$, $p_B$ and a random value $s_S$, and sends $c_A$ (resp. $c_B$) to A (resp. B). Finally, A and B can calculate the same secret key by using the reconciliation mechanism with $c_A$, $c_B$ and their own secret keys.

In the 3PAKE model, A and B can not authenticate each other, so they need the help of server S to provide the authentication. In our protocol, $k_{AS}$ ($k_{BS}$) can be viewed as an authentication of A (resp. B) to S. Note that S and A share a password, so only A can calculate the corresponding $b_A$ which is set by S, and only B can calculate $b_B$. Meanwhile, only A (resp. B) can calculate the same key value $\sigma _A$ (resp. $\sigma _B$) with S through the reconciliation mechanism.

Note that the adversary can not guess the password in a limited number of times, so $k_{AS}$ (or $k_{BS}$) can not be computed by adversary in a few tries, which makes our protocol resist undetectable on-line password guessing attacks [10]. Finally in order to resist off-line password guessing attacks [16], session values delivered by the server also need to provide authentication of S to A and B, that is why we add $k_{SA}$ and $k_{SB}$ in server’s outputs. In the security proof, two types of password guessing attacks is discussed in detail. Note that the final Client B finish step may seems redundant, but it is indispensable for the property of forward security [2].

3.3 Correctness

Note that in protocol RLWE-3PAK, if rec($2p_As_f,w_A$)=$\lfloor \overline{v_2}\rceil _2$, the verification for $k_{AS}$ would be correct. By the definition of the reconciliation mechanism and Lemma 2, we have $||v_2-p_As_f||_{\infty }<\frac{q}{8}$ should be satisfied with overwhelming probability. We have

$$\begin{aligned} v_2&=b_As_A+e_A'=(as_f+e_f)s_A+e_A'\\&=as_fs_A+e_fs_A+e_A' \end{aligned}$$

and

$$\begin{aligned} p_As_f&=as_As_f+e_As_f. \end{aligned}$$

Hence we need $||v_2-p_As_f||_{\infty }=||e_fs_A+e_A'-e_As_f||_{\infty }<\frac{q}{8}$. Similarly for the verification of $k_{BS}$, we need $||v_1-p_Bs_g||_{\infty }=||e_gs_B+e_B'-e_Bs_g||_{\infty }<\frac{q}{8}$ with overwhelming probability. And to compute the correct key, it needs rec($2c_As_A,w$)=$\lfloor \overline{v_B}\rceil _2$, which means that $||v_B-c_As_A||_{\infty }<\frac{q}{8}$. We have

$$\begin{aligned}v_B&=c_Bs_B+e_B''=(p_As_S+e_1)s_B+e_B''\\&=as_As_Ss_B+e_As_Ss_B+e_1s_B+e_B'' \end{aligned}$$

and

$$\begin{aligned}c_As_A&=(p_Bs_S+e_2)s_A\\&=as_As_Bs_S+e_Bs_As_S+e_2s_A. \end{aligned}$$

Therefore, it also needs $||v_B-c_As_A||_{\infty }=||e_As_Bs_S+e_1s_B+e_B''-e_Bs_As_S-e_2s_A||_{\infty }< \frac{q}{8}$ with overwhelming probability.

4 Security for RLWE-3PAK

Here we prove that the RLWE-3PAK protocol is secure, which means that an adversary $\mathcal {A}$ who attacks the system cannot determine the SK of fresh instances with greater advantage than that of an detectable on-line dictionary attack.

Theorem 4

Let P:=RLWE-3PAK, described in Fig. 1, using ring $R_q$, and with a password dictionary of size L. Fix an adversary $\mathcal {A}$ that runs in time t, and makes $n_{se},n_{ex},n_{re},n_{co}$ queries of type Send, Execute, Reveal, Corrupt, respectively. Then for $t'=O(t+(n_{ro}+n_{se}+n_{ex})t_{exp})$:

$$\begin{aligned} \begin{aligned} Adv _{P}^{\text {ake-fs}}(\mathcal {A})=C\cdot n_{se}^s+O\Big (n_{se}{} Adv&_{R_q}^{PWE }(t',n_{ro}^2)+Adv _{R_q}^{DRLWE }(t',n_{ro})\\ {}&+\frac{(n_{se}+n_{ex})(n_{ro}+n_{se}+n_{ex})}{q^n}+\frac{n_{se}}{2^{\kappa }}\Big ) \end{aligned} \end{aligned}$$

where $s\in [0.15,0.30]$ and $C\in [0.001,0.1]$ are constant CDF-Zipf regression parameters depending on the password space L [29].

The proof of above theorem will proceed by introducing a series of protocols $P_0,P_1,\ldots ,P_7$ related to P, with $P_0=P$. In $P_7$, the only possible attack for the adversary $\mathcal {A}$ is natural detectable on-line password guessing attacks. Eventually, there are

$$\begin{aligned} \text {Adv}_{P_0}^{ake}\le \text {Adv}_{P_1}^{ake}+\epsilon _1\le \cdots \le \text {Adv}_{P_7}^{ake}+\epsilon _7 \end{aligned}$$

where $\epsilon _1,\ldots ,\epsilon _7$ are negligible values in k. Together with above relations, our result is given by computing the success probability of detectable on-line attack in $P_7$ in the end of the proof. Due to the limitation of the space, we give a informal description of protocols $P_0,P_1,\ldots , P_7$ in Fig. 2, and given the proof sketches of negligible advantage gain from $P_{i-1}$ to $P_i$ in Fig. 3. The full proof of Theorem 4 is given in the full version of this paper in ePrint.

Let correctpw be the event that the adversary make a correct guess of password by detectable on-line passwords attacks. In most existing PAKE studies, passwords are assumed to follow a uniformly random distribution, and Pr(correctpw)$\le \frac{n_{se}}{L}$+$negl(\kappa )$, where L is the size of the password dictionary, $n_{se}$ is the max number of $\mathcal {A}$’s active on-line password guessing attempts before a Corrupt query and negl() is a negligible function. Ding Wang and Ping Wang [29] introduced CDF-Zipf model and in this model Pr(correctpw)$\le C\cdot n_{se}^s$+$negl(\kappa )$ for the Zipf parameters C and s which is depended on the password space L. CDF-Zipf model is more consistent with the real world attacks than traditional formulation. For example, when considering trawling guessing attacks, the actual advantage will be 6.84% when $n_{se}=10^2$, and 12.45% when $n_{se}=10^3$ [28], but the traditional formulation greatly underestimate Advantage to be 0.01% when $n_{se}=10^2$, and 0.10% when $n_{se}=10^3$. When further considering targeted guessing attacks (in which the adversary makes use of the target users personal information), advantage will be about 20% when $n_{se}=10^2$, 25% when $n_{se}=10^3$, and 50% when $n_{se}=10^6$ [30]. So we prefer this model in our analysis.

Fig. 2.

Informal description of protocols $P_0,P_1,\ldots ,P_7$

Fig. 3.

Proof sketches of negligible advantage gain from $P_{i-1}$ to $P_i$

5 Concrete Parameters and Implementation of RLWE-3PAK

In this section, we present our choices of parameters and outline the performance of our RLWE-3PAK.

Here we use the fact of the product of two Gaussian distributed random values that are stated in [32]. Let $x,y\in R$ be two polynomials with degree of n, and the coefficients of x and y are distributed according to discrete Gaussian distribution with parameter $\beta _x,\beta _y$, respectively. Then the individual coefficients of the polynomial xy are approximately normally distributed around zero with parameter $\beta _x \beta _y\sqrt{n}$. Hence for $||v_B-c_As_A||_{\infty }=||e_As_Bs_S+e_1s_B+e_B''-e_Bs_As_S-e_2s_A||_{\infty }< \frac{q}{8}$, by applying Lemma 1 we have that $||v_B-c_As_A||_{\infty }> 6\sqrt{2n^2\beta ^6+2n\beta ^4+\beta ^2}$ with probability approximating $2^{-162}$. Hence we set $6\sqrt{2n^2\beta ^6+2n\beta ^4+\beta ^2}< \frac{q}{8}$, then the two clients will end with the same key with overwhelming probability. And such choices of parameter also make $||v_2-p_As_f||_{\infty }<\frac{q}{8}$ and $||v_1-p_Bs_g||_{\infty }<\frac{q}{8}$ with overwhelming probability be satisfied.

We take $n=1024$, $\beta =8$ and $q=2^{32}-1$. Our implementations are written in C without any parallel computations or multi-thread programming techniques. The program is run on a 3.5 GHz Intel(R) Core(IM) i7-4770K CPU and 4 GB RAM computer running on Ubuntu 16.04.1 64 bit system. The timings for server and clients actions of the authentication protocol are presented in Table 1.

Table 1. Timings of proof-of-concept implementations in ms

Sampling and multiplication operations are the mainly time cost. The sampling technique used in our protocol is the same with [5], which use the Discrete Gaussian to approximate the continuous Gaussian. And to improve performance, we have used multiplication with FFT. Note that by the proof of concept implementation, our protocol can be very efficient.

6 Conclusion

In this paper, we propose a 3PAKE protocol based on RLWE: RLWE-3PAK. We provide a full proof of security of our protocol in the random oracle model. Finally, we construct a proof-of-concept implementation to examine the efficiency of our protocol. The performance results indicate that our protocol is very efficient and practical. Since some literature [4] show that it is delicate to prove quantum resistance with random oracle. It is meaningful to design an efficient 3PAKE protocol without random oracle heuristics in the future.