Password-Authenticated Key Exchange from Group Actions

Abstract

We present two provably secure password-authenticated key exchange (PAKE) protocols based on a commutative group action. To date the most important instantiation of isogeny-based group actions is given by CSIDH. To model the properties more accurately, we extend the framework of cryptographic group actions (Alamati et al., ASIACRYPT 2020) by the ability of computing the quadratic twist of an elliptic curve. This property is always present in the CSIDH setting and turns out to be crucial in the security analysis of our PAKE protocols.

Despite the resemblance, the translation of Diffie-Hellman based PAKE protocols to group actions either does not work with known techniques or is insecure (“How not to create an isogeny-based PAKE”, Azarderakhsh et al., ACNS 2020). We overcome the difficulties mentioned in previous work by using a “bit-by-bit” approach, where each password bit is considered separately.

Our first protocol $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ can be executed in a single round. Both parties need to send two set elements for each password bit in order to prevent offline dictionary attacks. The second protocol $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$ requires only one set element per password bit, but one party has to send a commitment on its message first. We also discuss different optimizations that can be used to reduce the computational cost. We provide comprehensive security proofs for our base protocols and deduce security for the optimized versions.

1 Introduction

Password-authenticated key exchange (PAKE) enables two parties to securely establish a joint session key assuming that they only share a low-entropy secret known as the password. This reflects that passwords are often represented in short human-readable formats and are chosen from a small set of possible values, often referred to as dictionary.

Since the introduction of PAKE by Bellovin and Merritt [8], many PAKE protocols have been proposed, including SPEKE [20], SPAKE2 [4], J-PAKE [19] and CPace [18]. In particular over the last few years, the design and construction of PAKE protocols has attracted increasing attention, as the Crypto Forum Research Group (CFRG) which is part of the Internet Research Task Force (IETF) started a selection process to decide which PAKE protocols should be used in IETF protocols. Recently, CPace was selected as the recommended protocol for symmetric PAKE, where both parties share the same password.

Different models have been used to formally prove security of PAKE protocols, like indistinguishability-based models or the universal composability framework. In general, a PAKE protocol should resist offline and online dictionary attacks. On the one hand an adversary should not be able to perform an exhaustive search of the password offline. On the other hand, an active adversary should only be able to try a small number of passwords in one protocol execution. Furthermore, forward security ensures that session keys are still secure, even if the password is leaked at a later point in time. The same should hold if session keys are disclosed, which should not affect security of other session keys.

CSIDH and Group Actions. The PAKE protocols mentioned above are mostly based on a Diffie-Hellman key exchange in a prime order group. A promising post-quantum replacement is isogeny-based key exchange. The different isogeny-based protocols can be divided into two groups. On the one hand there are constructions based on commutative group actions on a set of elliptic curves. The first proposals by Couveignes [12], and Stolbunov and Rostovtsev [27] suggested to use the action of the class group $\mathop {cl}(\mathcal {O})$ on the set of $\mathbb {F}_q$-isomorphism classes of ordinary elliptic curves with endomorphism ring $\mathcal {O}$. In 2018, Castryck et al. showed that this idea can also be adapted to the class group action on the set of $\mathbb {F}_p$-isomorphism classes of supersingular elliptic curves [11]. The resulting scheme is called CSIDH and constitutes the first practical key exchange scheme based on class group actions.

In [12], Couveignes introduces hard homogeneous spaces - an abstract framework for group actions that models isogeny-based assumptions. This framework has been further refined by Alamati et al. in [5]. Using the abstract setting of cryptographic group actions the authors develop several new cryptographic primitives that can be instantiated with CSIDH. On the other hand there is the Supersingular Isogeny Diffie-Hellman (SIDH) protocol suggested by Jao and De Feo in 2011 [21]. Here, the set of $\mathbb {F}_{p^2}$-isomorphism classes of supersingular elliptic curves is considered. The endomorphism ring of a supersingular elliptic curve over $\mathbb {F}_{p^2}$ is non-commutative, hence protocols based on SIDH do not fall into the group action framework.

We now recall the framework of (restricted) effective group actions introduced in [5]. Throughout, $\mathcal {G}$ denotes a finite commutative group and $\mathcal {X}$ a set. We assume that $\mathcal {G}$ acts regularly on $\mathcal {X}$ via the operator $\star : \mathcal {G}\times \mathcal {X}\rightarrow \mathcal {X}$. Regularity guarantees that for any $x,y \in \mathcal {X}$ there exists precisely one group element $g \in \mathcal {G}$ satisfying $y = g \star x$. Broadly speaking, we are interested in group actions, where evaluation is easy, but the “discrete logarithm problem” is hard. Expressed differently:

• Given $x \in \mathcal {X}$ and $g \in \mathcal {G}$, one can efficiently compute the set element $y = g \star x$.

• Given $x,y \in \mathcal {X}$, it is hard to find the element $g \in \mathcal {G}$ satisfying $y = g\star x$.

These properties facilitate the definition of a Diffie-Hellman key exchange. Let x be some fixed set element. Alice chooses a secret $g_A \in \mathcal {G}$ and publishes $y_A = g_A \star x$. Similarly Bob chooses $g_B \in \mathcal {G}$ and publishes $y_B = g_B \star x$. They can both compute the shared secret $y_{AB} = g_A \star y_B = g_B \star y_A$. The group action computational Diffie-Hellman problem $(\textsf{GA}\text {-}\textsf{CDH})$ then states that given $y_A$ and $y_B$, it is hard to compute $y_{AB}$. We refer to Sect. 3 for more precise definitions.

Contributions and Technical Details. Our main contributions are the two PAKE protocols $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ and $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$ based on commutative group actions. These are the first two provably secure PAKE protocols that are directly constructed from isogenies.

Group Actions with Twists. To date the most important instantiation of isogeny-based group actions is given by CSIDH. To model this situation more accurately, we suggest an enhancement of the framework which includes the ability of computing the quadratic twist of an elliptic curve efficiently. This property is inherent to CSIDH (cf. [11]) and it turns out to be crucial in the security analysis of our PAKE protocols. On the one hand, twisting allows us to construct an offline dictionary attack against our first natural PAKE attempt $\mathsf {GA\text {-}PAKE}_\ell$. Notably, this first protocol is secure for group actions where twisting is not possible efficiently. On the other hand, twists play an important role in various security reductions applied to prove the security of our new protocols $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ and $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$. Interestingly, this is also the case when twists are not part of any of the two problems involved in the reduction.

First attempt: $\mathsf {GA\text {-}PAKE}_\ell$. Our two secure PAKE protocols are modifications of $\mathsf {GA\text {-}PAKE}_\ell$. In order to illustrate the main idea behind the protocols, we describe $\mathsf {GA\text {-}PAKE}_\ell$ in more detail here. The protocol (Fig. 1) can be seen as an adaption of the simple password exponential key exchange protocol $\textsf{SPEKE}$ [20] to the group action setting. In $\textsf{SPEKE}$ the password is used to hash to a generator of the group. Then the user and the server establish a session key following the Diffie-Hellman key exchange. Directly translating this protocol to the group action setting requires to hash the password to a random set element $x \in \mathcal {X}$. For isogeny-based group actions, this is still an open problem, hence (at the moment) a straight-forward translation of $\textsf{SPEKE}$ is not possible (see also [6, §4.1]). In $\mathsf {GA\text {-}PAKE}_\ell$ we map the password to an $\ell$-tuple of elements in $\mathcal {X}$ instead of hashing to one element. More precisely, two elements $\textsf{crs}=(x_0,x_1) \in \mathcal {X}^2$ are fixed by a trusted party and a password $\textsf{pw}= (b_1, \dots ,b_\ell ) \in \{0,1\}^\ell$ is mapped to the tuple $(x_{b_1}, \cdots , x_{b_\ell }) \in \mathcal {X}^\ell$. Then a Diffie-Hellman key exchange is performed with basis $x_{b_i}$ for each $i \in [\ell ]$. This means the user generates $\ell$ random group elements $u_1,\dots ,u_\ell$ and computes the elements $x^\textsf{U}_1 = u_1 \star x_{b_1}, \dots , x^\textsf{U}_\ell = u_\ell \star x_{b_\ell }$ which it sends to the server. Similarly, the server generates $\ell$ random group elements $s_1,\dots , s_\ell$ and computes $x^\textsf{S}_1 = s_1 \star x_{b_1}, \dots , x^\textsf{S}_\ell = s_\ell \star x_{b_\ell }$ which it sends to the user. Note that the messages may be sent simultaneously in one round. Then both parties compute $z_i = u_i \star x^\textsf{S}_i = s_i \star x^\textsf{U}_i$ for each $i \in [\ell ]$. Finally the session key K is computed as $K = \textsf{H}(\textsf{U},\textsf{S},x^\textsf{U}_1,...,x^\textsf{U}_\ell ,x^\textsf{S}_1,...,x^\textsf{S}_\ell ,\textsf{pw},z_1,...,z_\ell )$, where $\textsf{H}:\{0,1\}^*\rightarrow \mathcal {K}$ is a hash function into the key space $\mathcal {K}$.

Fig. 1.

First Attempt: Protocol $\mathsf {GA\text {-}PAKE}_\ell$.

In Sect. 5, we present an offline dictionary attack against $\mathsf {GA\text {-}PAKE}_\ell$ for group actions with twists. This attack is not captured by the abstract group action framework defined in [5] which underlines the necessity of our suggested enhancement of the framework. Roughly speaking, the attack uses the fact that an attacker can choose its message in dependence on the other party’s message. Using twists, it can then achieve that certain terms in the key derivation cancel out and the session key no longer depends on the other party’s input.

Secure PAKE: $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ and $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$. The protocol $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ is a modified version of $\mathsf {GA\text {-}PAKE}_\ell$. Here security is achieved by doubling the message length in the first round of the protocol and tripling it in the key derivation. Intuitively the additional parts of the message can be viewed as an additional challenge for the key derivation that inhibits an attacker from choosing its message depending on the other party’s message. The security of the protocol relies on a new computational assumption, $\textsf{SqInv}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$, in which the adversary needs to compute the square and the inverse of its input at the same time (cf. Definition 7, Theorem 1).

The protocol $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$ is a modification of $\mathsf {GA\text {-}PAKE}_\ell$ as well. In order to achieve security against offline dictionary attacks, the protocol requires that the server sends a commitment before receiving the first message from the user. This prevents that any party chooses its message depending on the other party’s message. We reduce the security of the protocol to the hardness of standard security assumptions in the isogeny-based setting (Theorem 2). An overview of our results is provided in Fig. 2.

Fig. 2.

Overview of our security implications between assumptions (round boxes) and schemes (square boxes). Note that there exists an attack against protocol $\mathsf {GA\text {-}PAKE}_\ell$ using twists which makes it insecure for CSIDH. Our two main protocols $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ and $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$ are proven secure under protocol-specific assumptions, but we also give reductions to simpler assumptions making use of the twisting property. Solid arrows denote tight reductions, dashed arrows non-tight reductions.

Optimizations. Both $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ and $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$ require to compute multiple group action evaluations. In the last section, we discuss two optimizations that can be used to reduce the number of evaluations and show that these do not affect the security of the protocols. The first makes a tradeoff between the size of the public parameters (the common reference string $\textsf{crs}$) and the number of elements that have to be sent as well as the group actions that have to be performed. The second optimization relies on the possibility to compute twists efficiently, which is yet another advantage of adding this property to the framework and which allows to decrease the size of the public parameters by a factor of 2. We denote the final optimizations by $\textsf{Com}\text {-}\textsf{GA}\text {-}\textsf{PAKE}^\textsf{t}_{\ell ,N}$ and $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}^\textsf{t}_{\ell ,N}$, where N is a parameter for the $\textsf{crs}$ size. If N equals 1, we omit it. An overview and example of the parameter choice is provided in Table 1.

Difficulties in Constructing PAKE from Isogenies. Terada and Yoneyama [30] proposed isogeny-based PAKE based on the EKE approach. The basic idea is that the parties perform an SIDH or CSIDH key exchange where the messages are encrypted with the password. However, as shown in [6], these protocols are not only vulnerable to offline dictionary attacks, but a modified version is even vulnerable to man-in-the-middle attacks. The main reason for the insecurity is that the elliptic curves used in the key exchange and encrypted with the password are distinguishable from random bitstrings. An exhaustive search over all passwords just requires to check if the decrypted message is a valid curve.

Another proposal based on SIDH was made by Taraskin et al. [29]. In this protocol the password is used to obfuscate the auxiliary points that are exchanged during an SIDH key exchange. While their obfuscation method prevents a certain type of offline dictionary attack, the authors were not able to provide a security proof for their protocol. The same is true for a symmetric variant of the protocol proposed by Soukharev and Hess [28]. Until now these are the only PAKE protocol based on isogenies which are not broken.

As noted in [6], other popular Diffie-Hellman constructions may also not be directly translated into the isogeny setting. The main reason is that hashing into the set of supersingular elliptic curves is still an open problem. This approach is for example used in SPEKE. (However, we show how to non-trivially translate the idea.) Also the approach of J-PAKE seems difficult as in this scheme different public keys are combined to obtain certain “mixed” public keys. In isogeny-based protocols, the public keys are elliptic curves and there is no natural ring structure on the set of elliptic curves that would allow to combine two elliptic curves.

Table 1. Overview of our two optimized protocols $\textsf{Com}\text {-}\textsf{GA}\text {-}\textsf{PAKE}^\textsf{t}_{\ell ,N}$ and $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}^\textsf{t}_{\ell ,N}$ and comparison to the only other CSIDH-based constructions. All protocols use a bit-wise approach, i.e., passwords are treated as bitstrings of length $\ell$. Sample values for $\ell =128$ are marked in gray. “Elements” refers to the number of set elements (+ strings or symmetric ciphertexts) that each party has to send. “Evaluations” refers to the number of group action evaluations that each party has to perform. “Rew.” indicates that rewinding is used to reduce to the assumption indicated in the table and $\textsf{GA}\text {-}\textsf{DDH}$ refers to the group action decisional Diffie-Hellman problem.

In the following, we elaborate known generic constructions of PAKE from hash proof systems (HPS) and oblivious transfer (OT). We explain that the only known isogeny-based HPS is not suitable for generic constructions. On the other hand, the isogeny-based OT protocols from the literature are suited for generic constructions. However, we show that the resulting PAKE protocols are less efficient than our new proposals.

Using the framework of cryptographic group actions, Alamati et al. construct a universal hash proof system [5, §4.1]. In general, it is known how to build CCA-secure encryption [13] and also PAKE from hash proof systems [17]. However, the details here are less clear. The hashing key consists of multiple elements linear in the size of the universality parameter. The reason being that we can only make use of one group operation provided by the group action. This also needs to be considered when constructing an encryption scheme. In order to construct PAKE, the framework by Gennaro and Lindell and follow-up works require a hash proof system for the language of ciphertexts of a public-key encryption scheme, which seems to be hard to construct given only the operation of the group action. The HPS in [5] is only based on a DDH-like assumption.

It is well known that PAKE can also be generically constructed from OT [10]. One construction uses a UC-secure OT protocol and the other one a statistically receiver-private OT protocol. In both, the password is interpreted as a bit string and for each bit, the user and server run the oblivious transfer protocol for randomly chosen messages which will be used to derive the session key. In the following, we apply the construction to two existing OT protocols.

• Alamati et al. propose a two-message statistically sender-private OT, however we can construct a similar receiver-private OT protocol based on their dual-mode public-key encryption scheme and the transformation given in [25]. The resulting OT protocol already uses a “bit-by-bit” approach, hence the resulting PAKE will have communication and computation complexity quadratic in the parameter $\ell$.

• Recently, Lai et al. proposed a new very efficient CSIDH-based OT protocol using twists and the random oracle model [24]. However, in order to achieve active security the protocol needs four rounds.¹ Additionally applying the generic PAKE compiler results in a protocol with complexity linear in $\ell$.

The efficiency of the generic constructions is compared to our new protocols in Table 1. While the computational cost of our protocols $\textsf{Com}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_{\ell ,N}$ and $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_{\ell ,N}$ is also linear in $\ell$, the cost is considerably lower for concrete instantiations. Moreover, our scheme $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_{\ell ,N}$ is the only one-round protocol, where both parties send simultaneous flows.

Open Problems and Future Work. Until now, protocols based on CSIDH or group actions that use search problems together with the random oracle model do not consider quantum access to the ROM [16, 22,23,24, 31]. Since PAKE proofs are already complex, we also did not prove security in the QROM. Although no reprogramming of the random oracle is necessary, the main difficulty in the QROM is to simulate the real session keys using the decision oracle. We leave this as future work. We believe that we can easily allow quantum access to the additional random oracle that is used in $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$ to commit on the message. In this case, the output is transferred classically in the first message flow such that extraction is possible using recently developed techniques [15].

As [24], we use rewinding to reduce the interactive assumption underlying $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$ to a standard assumption. An interesting open question is whether current techniques enabling quantum rewinding are applicable here.

Outline. Section 3 sets the framework for our paper. We introduce (restricted) effective group actions with twists and define the computational assumptions underlying the security of our protocols. In Sect. 4, we give some background on the security model that is used in the subsequent sections. In Sect. 5 we present our first attempt for a PAKE protocol, $\mathsf {GA\text {-}PAKE}_\ell$, and explain its security gap. Section 6 contains a thorough analysis of our new secure protocol $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$. In Sect. 7 we present the protocol $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$ and sketch the security proof. Finally, we discuss possible optimizations of the protocols in Sect. 8.

2 Preliminaries

For integers m, n where $m<n$, [m, n] denotes the set $\{m,m+1,...,n\}$. For $m=1$, we simply write [n]. For a set S, denotes that s is sampled uniformly and independently at random from S. $y \leftarrow \mathcal {A}(x_1,x_2,...)$ denotes that on input $x_1,x_2,...$ the probabilistic algorithm $\mathcal {A}$ returns y. $\mathcal {A}^\textsc {O}$ denotes that algorithm $\mathcal {A}$ has access to oracle $\textsc {O}$. An adversary is a probabilistic algorithm. We will use code-based games, where $\Pr [{\textsf{G}_{}} \Rightarrow 1]$ denotes the probability that the final output of game ${\textsf{G}_{}}$ is 1.

3 (Restricted) Effective Group Actions (with Twists)

In this section we recall the definition of (restricted) effective group actions from [5], which provides an abstract framework to build cryptographic primitives relying on isogeny-based assumptions such as CSIDH. Moreover, we suggest an enhancement of this framework, by introducing (restricted) effective group actions with twists. This addition is essential for the security analysis of our new PAKE protocols.

Definition 1

(Group Action). Let $(\mathcal {G},\cdot )$ be a group with identity element $\mathop {id}\in \mathcal {G}$, and $\mathcal {X}$ a set. A map

$$ \star : \mathcal {G}\times \mathcal {X}\rightarrow \mathcal {X}$$

is a group action if it satisfies the following properties:

• 1. Identity: $\mathop {id}\star x = x$ for all $x \in \mathcal {X}$.

• 2. Compatibility: $(g\cdot h) \star x = g \star (h \star x)$ for all $g,h \in \mathcal {G}$ and $x \in \mathcal {X}$.

Remark 1

Throughout this paper, we only consider group actions, where $\mathcal {G}$ is commutative. Moreover we assume that the group action is regular. This means that for any $x,y \in \mathcal {X}$ there exists precisely one $g \in \mathcal {G}$ satisfying $y = g \star x$.

Definition 2

(Effective Group Action). Let $(\mathcal {G},\mathcal {X},\star )$ be a group action satisfying the following properties:

• 1. The group $\mathcal {G}$ is finite and there exist efficient (PPT) algorithms for membership and equality testing, (random) sampling, group operation and inversion.

• 2. The set $\mathcal {X}$ is finite and there exist efficient algorithms for membership testing and to compute a unique representation.

• 3. There exists a distinguished element $\tilde{x}\in \mathcal {X}$ with known representation.

• 4. There exists an efficient algorithm to evaluate the group action, i.e. to compute $g \star x$ given g and x.

Then we call $\tilde{x}\in \mathcal {X}$ the origin and $(\mathcal {G},\mathcal {X},\star ,\tilde{x})$ an effective group action $(\textsf{EGA})$.

In practice, the requirements from the definition of $\textsf{EGA}$ are often too strong. Therefore we will consider the weaker notion of restricted effective group actions.

Definition 3

(Restricted Effective Group Action). Let $(\mathcal {G},\mathcal {X},\star )$ be a group action and let ${\textbf {g}}=(g_1,...,g_n)$ be a generating set for $\mathcal {G}$. Assume that the following properties are satisfied:

• 1. The group $\mathcal {G}$ is finite and $n = \mathop {poly}(\log (\# \mathcal {G}))$.

• 2. The set $\mathcal {X}$ is finite and there exist efficient algorithms for membership testing and to compute a unique representation.

• 3. There exists a distinguished element $\tilde{x}\in \mathcal {X}$ with known representation.

• 4. There exists an efficient algorithm that given $g_i\in {\textbf {g}}$ and $x\in \mathcal {X}$, outputs $g_i \star x$ and $g_i^{-1} \star x$.

Then we call $(\mathcal {G},\mathcal {X},\star ,\tilde{x})$ a restricted effective group action $(\textsf{REGA})$.

3.1 Isogeny-Based $\textsf{REGA}$s

An important instantiation of $\textsf{REGA}$s is provided by isogeny-based group actions. We will focus on the $\textsf{CSIDH}$ setting and present a refined definition of $\textsf{REGA}$s tailored to this situation.

Let p be a large prime of the form $p = 4 \cdot \ell _1 \cdots \ell _n -1$, where the $\ell _i$ are small distinct odd primes. Fix the elliptic curve $E_0:y^2 = x^3+x$ over $\mathbb {F}_p$. The curve $E_0$ is supersingular and its $\mathbb {F}_p$-rational endomorphism ring is $\mathcal {O}= \mathbb {Z}[\pi ]$, where $\pi$ is the Frobenius endomorphism. Let be the set of elliptic curves defined over $\mathbb {F}_p$, with endomorphism ring $\mathcal {O}$. The ideal class group $\mathop {cl}(\mathcal {O})$ acts on the set , i.e., there is a map

satisfying the properties from Definition 1 [11, Theorem 7]. Moreover the analysis in [11] readily shows that is indeed a $\textsf{REGA}$.

Elliptic curves in admit equations of the form $E_A: y^2=x^3+Ax^2+x$, which allows to represent them by their Montgomery coefficient $A \in \mathbb {F}_p$. An intrinsic property of the CSIDH group action which is not covered by Definition 3, is the following. For any curve , its quadratic twist is easily computed as $(E_A)^t = E_{-A}$ and satisfies the property $(E_A)^t = [\mathfrak {a}]^{-1} \star E_0$.

Definition 4

((Restricted) Effective Group Action with Twists). We say that a $(\textsf{R})\textsf{EGA}$ $(\mathcal {G},\mathcal {X}, \star , \tilde{x})$ is a (Restricted) Effective Group Action with Twists $(\mathsf {(R)EGAT})$ if there exists an efficient algorithm that given $x = g \star \tilde{x}\in \mathcal {X}$ computes $x^t = g^{-1} \star \tilde{x}$.

As noted in [11, §10], this property contrasts with the classical group-based setting. It has already been used for the design of new cryptographic primitives based on CSIDH such as the signature scheme CSIFiSh [9] and the OT protocol in [24]. Moreover, it is important to consider twists in the security analysis of schemes based on group actions. In Sect. 5 we use twists to construct an attack on the protocol $\mathsf {GA\text {-}PAKE}_\ell$ showing that it cannot be securely instantiated with the CSIDH group action. On the other hand, we prove that $\mathsf {GA\text {-}PAKE}_\ell$ is secure when instantiated with a group action without efficient twisting. The proof for that is given in the full version [1, Appendix C].

3.2 Computational Assumptions

For cryptographic applications, we are interested in (restricted) effective group actions that are equipped with the following hardness properties:

• Given $(x, y) \in \mathcal {X}^2$, it is hard to find $g \in \mathcal {G}$ such that $y = g \star x$.

• Given $(x,y_0,y_1) \in \mathcal {X}^3$, it is hard to find $z = (g_0 \cdot g_1) \star x$, where $g_0,g_1 \in \mathcal {G}$ are such that $y_0 = g_0 \star x$ and $y_1 = g_1 \star x$.

In [5] such group actions are called cryptographic group actions, and in [12] they are called hard homogeneous spaces.

The two hardness assumptions are the natural generalizations of the discrete logarithm assumption and the Diffie-Hellman assumption in the traditional group based setting. In analogy to this setting, we introduce the notation

$$ \textsf{GA}\text {-}\textsf{CDH}_x(y_0,y_1)= g_0 \star y_1, \quad \text { where } g_0 \in \mathcal {G}\text { such that } y_0 = g_0 \star x $$

and define the decision oracle

$$ \textsc {GA}\text {-}\textsc {DDH}_x(y_0,y_1,z) ={\left\{ \begin{array}{ll} 1 &{} \text {if } \textsf{GA}\text {-}\textsf{CDH}_x(y_0,y_1) = z,\\ 0 &{} \text {otherwise}. \end{array}\right. } $$

For both, $\textsf{GA}\text {-}\textsf{CDH}$ and $\textsc {GA}\text {-}\textsc {DDH}$, we omit the index x if $x = \tilde{x}$, i. e., we set $\textsf{GA}\text {-}\textsf{CDH}_{\tilde{x}}(y_0,y_1) = \textsf{GA}\text {-}\textsf{CDH}(y_0,y_1)$ and equivalently for $\textsc {GA}\text {-}\textsc {DDH}_{\tilde{x}}(y_0,y_1,z)$.

We now introduce three computational problems $\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$, $\textsf{GA}\text {-}\textsf{Gap}\textsf{CDH}$, $\textsf{SqInv}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ (Definitions 5 to 7). The security of our $\textsf{PAKE}$ protocols relies on the hardness of these problems.

The first two problems are variants of the standard Diffie-Hellman problem, where an adversary is either given access to some fixed-basis decision oracles (indicated by the prefix strong) or to a general decision oracle (indicated by the prefix gap). Note that these problems were already defined and used in previous work [16, 22, 23, 31]. Since the problem from Definition 7 has not been studied in any previous work, we provide evidence for its hardness in Remark 3.

Definition 5

(Group Action Strong Computational Diffie-Hellman Problem ($\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$)). On input $(g\star \tilde{x},h\star \tilde{x}) \in \mathcal {X}^2$, the $\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ problem requires to compute the set element $(g\cdot h)\star \tilde{x}$. To an effective group action $\textsf{XXX}\in \{\textsf{EGA},\textsf{REGA},\textsf{EGAT},\textsf{REGAT}\}$, we associate the advantage function of an adversary $\mathcal {A}$ as

$$\begin{aligned} \textsf{Adv}^{\textsf{GA}\text {-}\textsf{St}\textsf{CDH}}_\textsf{XXX}(\mathcal {A}) := \Pr [\mathcal {A}^{\textsc {GA}\text {-}\textsc {DDH}(g\star \tilde{x},\cdot ,\cdot )}(g\star \tilde{x},h\star \tilde{x})\Rightarrow (g\cdot h)\star \tilde{x}], \end{aligned}$$

where and $\mathcal {A}$ has access to decision oracle $\textsc {GA}\text {-}\textsc {DDH}(g\star \tilde{x},\cdot ,\cdot )$.

Definition 6

(Group Action Gap Computational Diffie-Hellman Problem ($\textsf{GA}\text {-}\textsf{Gap}\textsf{CDH}$)). On input $(g\star \tilde{x},h\star \tilde{x}) \in \mathcal {X}^2$, the $\textsf{GA}\text {-}\textsf{Gap}\textsf{CDH}$ problem requires to compute the set element $(g\cdot h)\star \tilde{x}$. To an effective group action $\textsf{XXX}\in \{\textsf{EGA},\textsf{REGA},\textsf{EGAT},\textsf{REGAT}\}$, we associate the advantage function of an adversary $\mathcal {A}$ as

$$\begin{aligned} \textsf{Adv}^{\textsf{GA}\text {-}\textsf{Gap}\textsf{CDH}}_\textsf{XXX}(\mathcal {A}) := \Pr [\mathcal {A}^{\textsc {GA}\text {-}\textsc {DDH}_{*}}(g\star \tilde{x},h\star \tilde{x})\Rightarrow (g\cdot h)\star \tilde{x}], \end{aligned}$$

where and $\mathcal {A}$ has access to a general decision oracle $\textsc {GA}\text {-}\textsc {DDH}_{*}$.

Remark 2

A group action where the group action computational Diffie-Hellman problem (without any decision oracle) is hard, is the same as a weak unpredictable group action as defined by Alamati et al. [5]. Further details are given in the full version [1, Appendix A]. Also note that the ability to compute the twist of a set element does not help in solving these problems. Hence, all results based on these problems remain true for $\mathsf {(R)EGAT}$.

Definition 7

(Square-Inverse $\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ ($\textsf{SqInv}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$)). On input $x = g \star \tilde{x}$, the $\textsf{SqInv}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ problem requires to find a tuple $(y, y_0,y_1) \in \mathcal {X}^3$ such that $y_0 = g^{2} \star y$ and $y_1 = g^{-1} \star y$. For a group action $\textsf{XXX}\in \{\textsf{EGA},\textsf{REGA},\textsf{EGAT},\textsf{REGAT}\}$, we define the advantage function of $\mathcal {A}$ as

where $\textsc {O}=\{ \textsc {GA}\text {-}\textsc {DDH}_{x^t}(x,\cdot ,\cdot ), \textsc {GA}\text {-}\textsc {DDH}(x,\cdot ,\cdot ) \}$.

Remark 3

Intuitively $\textsf{SqInv}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ is hard if we assume that the adversary can only use the group and twist operation. To go into more detail, $\mathcal {A}$ can choose y only based on known elements, that is either based on $\tilde{x}$, its input x or $x^t$.

If $\mathcal {A}$ chooses $y=\alpha \star \tilde{x}$ for some $\alpha \in \mathcal {G}$, then it can easily compute $y_1=\alpha \star x^t$, but not $y_0=\alpha g^2 \star \tilde{x}$. If $\mathcal {A}$ chooses $y=\alpha \star x$, then computing $y_1=\alpha \star \tilde{x}$ is trivial, but computing $y_0 = \alpha g^3 \star \tilde{x}$ is hard. If $\mathcal {A}$ chooses $y=\alpha \star x^t$, then computing $y_0=\alpha \star x$ is trivial, but computing $y_1=\alpha g^{-2} \star \tilde{x}$ is hard.

4 Password Authenticated Key Exchange

Password-authenticated key exchange (PAKE) allows two parties, typically referred to as the user and the server, to establish a shared session key with the help of a short secret, known as a password, which can be drawn from a small set of possible values. To prove security of a PAKE protocol, we use the indistinguishability-based model by Bellare, Pointcheval and Rogaway [7] and its extension to multiple test queries by Abdalla, Fouque and Pointcheval [2].

The name spaces for users $\mathcal {U}$ and servers $\mathcal {S}$ are assumed to be disjoint. Each pair of user and server $(\textsf{U},\textsf{S})\in \mathcal {U}\times \mathcal {S}$ holds a shared password $\textsf{pw}_{\textsf{U}\textsf{S}}$. A party $\textsf{P}$ denotes either a user or server. Each party $\textsf{P}$ has multiple instances $\pi _\textsf{P}^i$ and each instance has its own state. We denote the session key space by $\mathcal {K}$. Passwords are bit strings of length $\ell$ and we define the password space as $\mathcal{P}\mathcal{W}\subsetneq \{0,1\}^\ell$.

Instance State. The state of an instance $\pi _\textsf{P}^i$ is a tuple $(\textsf{e},\textsf{tr},K,\text {acc})$ where

• $\textsf{e}$ stores the (secret) ephemeral values chosen by the party in that instance.

• $\textsf{tr}$ stores the trace of that instance, i.e., the user and server name involved in the protocol execution and the messages sent and received by that instance.

• $K$ is the accepted session key.

• $\text {acc}$ is a Boolean flag that indicates whether the instance has accepted the session key. As long as the instance did not receive the last message, $\text {acc}=\bot$.

To access individual components of the state, we write $\pi _\textsf{P}^t{.}\{\textsf{e},\textsf{tr},K,\text {acc}\}$.

Partnering. Partnering is defined via matching conversations. In particular, a user instance $\pi _\textsf{U}^{t_0}$ and a server instance $\pi _\textsf{S}^{t_1}$ are partnered iff

$$\pi _\textsf{U}^{t_0}{.}\text {acc}=\pi _\textsf{S}^{t_1}{.}\text {acc}={\textbf {true}}~~~ {\textbf {and }}~~ \pi _\textsf{U}^{t_0}{.}\textsf{tr}=\pi _\textsf{S}^{t_1}{.}\textsf{tr}.$$

Two user instances are never partnered, neither are two server instances. We define a partner predicate $\textsf{Partner}(\pi _{\textsf{P}_0}^{t_0},\pi _{\textsf{P}_1}^{t_1})$ which outputs 1 if the two instances $\pi _{\textsf{P}_0}^{t_0}$ and $\pi _{\textsf{P}_1}^{t_1}$ are partnered and 0 otherwise.

Security Experiment. The security experiment is played between a challenger and an adversary $\mathcal {A}$. The challenger draws a random challenge bit $\beta$ and creates the public parameters. Then it outputs the public parameters to $\mathcal {A}$. Now $\mathcal {A}$ has access to the following oracles:

• $\textsc {Execute}(\textsf{U},t_0,\textsf{S},t_1)$: one complete protocol execution between user instance $\pi _\textsf{U}^{t_0}$ and server instance $\pi _\textsf{S}^{t_1}$. This query models security against passive adversaries.

• $\textsc {SendInit}$, $\textsc {SendResp}$, $\textsc {SendTermInit}$, $\textsc {SendTermResp}$: send oracles to model security against active adversaries. $\textsc {SendTermResp}$ is only available for three-message protocols.

• $\textsc {Corrupt}(\textsf{U},\textsf{S})$: outputs the shared password $\textsf{pw}_{\textsf{U}\textsf{S}}$ of $\textsf{U}$ and $\textsf{S}$.

• $\textsc {Reveal}(\textsf{P},t)$: outputs the session key of instance $\pi _\textsf{P}^t$.

• $\textsc {Test}(\textsf{P},t)$: challenge query. Depending on the challenge bit $\beta$, the experiment outputs either the session key of instance $\pi _\textsf{P}^t$ or a uniformly random key. By $\pi _\textsf{P}^t{.}\text {test}={\textbf {true}}$, we mark an instance as tested.

We denote the experiment by $\textsf{Exp}_{\textsf{PAKE}}$. The pseudocode is given in $\textsf{G}_0$ in Fig. 5, instantiated with our first PAKE protocol.

Freshness. During the game, we register if a query is allowed to prevent trivial wins. Therefore, we define a freshness predicate $\textsf{Fresh}(\textsf{P},i)$. An instance $\pi _\textsf{P}^t$ is fresh iff

• 1. $\pi _\textsf{P}^t$ accepted.

• 2. $\pi _\textsf{P}^t$ was not queried to $\textsc {Test}$ or $\textsc {Reveal}$ before.

• 3. At least one of the following conditions holds:

  • 3.1 $\pi _\textsf{P}^t$ accepted during a query to $\textsc {Execute}$.

  • 3.2 There exists more than one partner instance.

  • 3.3 A unique fresh partner instance exists.

  • 3.4 No partner exists and $\textsc {Corrupt}$ was not queried.

Definition 8

(Security of PAKE). We define the security experiment, partnering and freshness conditions as above. The advantage of an adversary $\mathcal {A}$ against a password authenticated key exchange protocol $\textsf{PAKE}$ in $\textsf{Exp}_{\textsf{PAKE}}$ is defined as

$$\begin{aligned} \textsf{Adv}_{\textsf{PAKE}}(\mathcal {A})&{:}{=}\, \left| \Pr [\textsf{Exp}_{\textsf{PAKE}}\Rightarrow 1] - \frac{1}{2}\right| . \end{aligned}$$

A PAKE is considered secure if the best the adversary can do is to perform an online dictionary attack. More concretely, this means that the advantage of the adversary should be negligibly close to $q_s/ |\mathcal{P}\mathcal{W}|$ when passwords are drawn uniformly and independently from $\mathcal{P}\mathcal{W}$, where $q_s$ is the number of send queries made by the adversary.

Note that this definition captures weak forward secrecy. In the full version of our paper, we give an extended security definition capturing also perfect forward secrecy, as well as proofs for our protocols [1, Appendix F].

5 First Attempt: Protocol $\mathsf {GA\text {-}PAKE}_\ell$

The $\mathsf {GA\text {-}PAKE}_\ell$ protocol was already introduced in the introduction (Sect. 1). We refer to Fig. 1 for a description of the protocol. In contrast to the two PAKE protocols from Sects. 6 and 7, $\mathsf {GA\text {-}PAKE}_\ell$ is not secure for $\textsf{EGAT}$s, i.e., if it is possible to compute twists of set elements efficiently. In particular it should not be instantiated with the $\textsf{CSIDH}$-group action. However, it is instructive to examine its security and it serves as a good motivation for the design of the two secure PAKE protocols $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ and $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$.

In this section we present an offline dictionary attack against $\mathsf {GA\text {-}PAKE}_\ell$ for $\mathsf {(R)EGAT}$. However, if twisting is hard, then we can prove security of $\mathsf {GA\text {-}PAKE}_\ell$ based on a hardness assumption that is similar to the simultaneous Diffie-Hellman problem which was introduced to prove the security of TBPEKE and CPace [3, 26]. The proof for $\mathsf {GA\text {-}PAKE}_\ell$ is given in the full version [1, Appendix C].

Proposition 1

For $\textsf{EGAT}$s, the protocol $\mathsf {GA\text {-}PAKE}_\ell$ is vulnerable to offline dictionary attacks.

Proof

We construct an adversary $\mathcal {A}$ that takes the role of the server. The attack is summarized in Fig. 3. After receiving $x^\textsf{U}$, the adversary computes

$$x^\textsf{S}_i=\tilde{s_i}\star (x^\textsf{U}_i)^t=\tilde{s_i}\star (u_i\star x_{b_i})^t=(\tilde{s_i}\cdot u_i^{-1})\star x_{b_i}^t=(\tilde{s_i}\cdot u_i^{-1}\cdot g_{b_i}^{-1}) \star \tilde{x}$$

for each $i \in [\ell ]$ and sends $x^\textsf{S}_1, \dots , x^\textsf{S}_{\ell }$ to the user. Then the user computes $z_i=u_i\star x^\textsf{S}_i=(\tilde{s_i}\cdot g_{b_i}^{-1}) \star \tilde{x}=\tilde{s_i}\star x_{b_i}^t$. For each $i \in [\ell ]$, the adversary $\mathcal {A}$ can now compute $z_i$ for both possibilities $b_i=0$ and $b_i=1$. This allows him to compute K for all possible passwords $\textsf{pw}\in \mathcal{P}\mathcal{W}\subsetneq \{0,1\}^\ell$ (being offline).    $\square$

Fig. 3.

Attack against $\mathsf {GA\text {-}PAKE}_\ell$ using twists.

This offline attack can easily be used to win the security experiment with high probability. $\mathcal {A}$ only needs to issue two send queries. It chooses any user $\textsf{U}$, initiates a session and computes its message $x^\textsf{S}_1,...,x^\textsf{S}_\ell$ as described in Fig. 3. It reveals the corresponding session key and starts its offline attack by brute forcing all $\textsf{pw}\in \mathcal{P}\mathcal{W}$ until it finds a match for a candidate $\textsf{pw}^*$. Now $\mathcal {A}$ issues its second send query. This time it computes the message following the protocol using $\textsf{pw}^*$ and derives a key $K^*$. It issues a test query and gets $K_\beta$. If $K^*=K_\beta$, then it outputs 0, otherwise it outputs 1. In case there is more than one password candidate, i.e., two inputs to $\textsf{H}$ lead to the same $K^*$, then $\mathcal {A}$ can issue another send and reveal query to rule out false positives. In the end, it can still happen that $\beta =1$ and $K^*=K$, but this event only occurs with probability $1/|\mathcal {K}|$.

Corollary 1

For any adversary $\mathcal {A}$ against $\mathsf {GA\text {-}PAKE}_\ell$ instantiated with an $\textsf{EGAT}$, we have $\Pr [\textsf{Exp}_{\mathsf {GA\text {-}PAKE}_\ell }\Rightarrow 1]=1-\frac{1}{|\mathcal {K}|}$.

6 $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$: One-Round PAKE from Group Actions

In the previous section we showed that $\mathsf {GA\text {-}PAKE}_\ell$ is insecure when instantiated with an $\textsf{EGAT}$. Here, we present the modification $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$, which impedes the offline dictionary attack presented in that section. Broadly speaking, the idea is to double the message size of both parties in the first flow. In the second flow it is then necessary to compute certain “cross products” which is only possible if the previous message has been honestly generated. The letter $\textsf{X}$ in $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ stands for cross product.

By means of these modifications, the protocol $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ is provably secure for $\textsf{EGAT}$s. We show that its security can be reduced to the hardness of the computational problems $\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ and $\textsf{SqInv}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ (Theorem 1).

The setup for $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ is the same as for $\mathsf {GA\text {-}PAKE}_\ell$. The $\textsf{crs}=(x_{0},x_{1})$ comprises two elements of the set $\mathcal {X}$, and the shared password is a bit string $(b_1,\dots , b_{\ell })$ of length $\ell$. In the first flow of the protocol the user generates $2\cdot \ell$ random group elements, $u_1, \dots , u_{\ell }$ and $\hat{u}_1, \dots , \hat{u}_{\ell }$. Using these elements it computes the set elements $x^\textsf{U}_i = u_i \star x_{b_i}$ and $\hat{x}^\textsf{U}_i = \hat{u}_i \star x_{b_i}$ for each $i \in [\ell ]$ and sends these to the server. Simultaneously, the server generates the random group elements $s_1, \dots , s_{\ell }$ and $\hat{s}_1, \dots , \hat{s}_{\ell }$, which it uses to compute the set elements $x^\textsf{S}_i = s_i \star x_{b_i}$ and $\hat{x}^\textsf{S}_i = \hat{s}_i \star x_{b_i}$ for each $i \in [\ell ]$ and sends these to the user. Upon receiving the set elements from the other party, both the server and the user compute

$$ z_{i,1} = u_i \star x^\textsf{S}_i = s_i \star x^\textsf{U}_i, \quad z_{i,2} = \hat{u}_i \star x^\textsf{S}_i = s_i \star \hat{x}^\textsf{U}_i, \quad z_{i,3} = u_i \star \hat{x}^\textsf{S}_i = \hat{s}_i \star x^\textsf{U}_i, $$

for each $i \in [\ell ]$. Finally, these elements are used to compute the session key K. The protocol is sketched in Fig. 4.

Fig. 4.

PAKE protocol $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ from group actions.

We now prove the security of $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ for $\textsf{EGAT}$s.

Theorem 1

(Security of $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$). For any adversary $\mathcal {A}$ against $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ that issues at most $q_e$ execute queries and $q_s$ send queries and where $\textsf{H}$ is modeled as a random oracle, there exist an adversary $\mathcal {B}_1$ against $\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ and an adversary $\mathcal {B}_2$ against $\textsf{SqInv}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ such that

$$\textsf{Adv}_{\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell }(\mathcal {A})\le \textsf{Adv}^{\textsf{GA}\text {-}\textsf{St}\textsf{CDH}}_{\textsf{EGAT}}(\mathcal {B}_1) + \textsf{Adv}^{\textsf{SqInv}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}}_{\textsf{EGAT}}(\mathcal {B}_2) + \frac{q_s}{|\mathcal{P}\mathcal{W}|} + \frac{(q_s+ q_e)^2}{|\mathcal {G}|^{2\ell }}.$$

Before proving Theorem 1, we will introduce a new computational assumption which is tailored to the protocol.

Definition 9

(Double Simultaneous $\textsf{GA}\text {-}\textsf{StCDH}$ $(\textsf{D}\textsf{Sim}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH})$). On input $(x_0,x_1,w_0,w_1) = (g_0 \star \tilde{x}, g_1 \star \tilde{x}, h_0 \star \tilde{x}, h_1 \star \tilde{x}) \in \mathcal {X}^4$, the $\textsf{D}\textsf{Sim}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ problem requires to find a tuple $(y, y_0,y_1, y_2,y_3) \in \mathcal {X}^5$ such that

$$ (y_0,y_1,y_2,y_3) = (g_0^{-1}\cdot h_0 \star y,\, g_0^{-1}\cdot h_1 \star y,\, g_1^{-1} \cdot h_0 \star y,\, g_1^{-1} \cdot h_1 \star y). $$

For a group action $\textsf{XXX}\in \{\textsf{EGA},\textsf{REGA},\textsf{EGAT},\textsf{REGAT}\}$, we define the advantage function of an adversary $\mathcal {A}$ as

where $\textsc {O}=\{\textsc {GA}\text {-}\textsc {DDH}_{x_j}(w_i,\cdot ,\cdot )\}_{i,j \in \{0,1\}}$.

Remark 4

Note that $\textsf{D}\textsf{Sim}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ may be viewed as the doubled version of the $\textsf{Sim}\text {-}\textsf{GA}\text {-}\textsf{StCDH}$ problem defined in the full version of the paper [1, Definition 12]. The latter is an assumption underlying the security of $\mathsf {GA\text {-}PAKE}_\ell$ and (in the notation of the above problem) it only requires to find the tuple $(y,y_0,y_2)$. For a group action with twists, this admits the trivial solution $(y,y_0,y_2) = (w_0^t,x_0^t,x_1^t)$. Such a trivial solution is inhibited by requiring to find $y_1$ and $y_3$ as well.

The $\textsf{D}\textsf{Sim}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ problem is implied by $\textsf{SqInv}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$, more precisely

$$\begin{aligned} \textsf{Adv}_{\textsf{EGAT}}^{\textsf{D}\textsf{Sim}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}}(\mathcal {A})\le \textsf{Adv}_{\textsf{EGAT}}^{\textsf{SqInv}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}}(\mathcal {B}). \end{aligned}$$

(1)

A proof of this implication is given in the full version [1, Lemma 1].

Proof

(of Theorem 1). Let $\mathcal {A}$ be an adversary against $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$. Consider the games in Figs. 5, 7, 8.

Fig. 5.

Games $\textsf{G}_0$-$\textsf{G}_4$ for the proof of Theorem 1. $\mathcal {A}$ has access to oracles $\textsc {O}\,{:}{=}\,\{\textsc {Execute},\textsc {SendInit},\textsc {SendResp},\textsc {SendTermInit},\textsc {Reveal},\textsc {Corrupt},\textsc {Test},\textsf{H}\}$.

Game $\textsf{G}_0$. This is the original game, hence

$$\begin{aligned} \textsf{Adv}_{\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell }(\mathcal {A}) \le \left| \Pr [\textsf{G}_0\Rightarrow 1]- 1/2\right| . \end{aligned}$$

Game $\textsf{G}_1$. In game $\textsf{G}_1$, we raise flag ${\textbf {bad}}_{\text {coll}}$ whenever a server instance computes the same trace as any other accepted instance (line 69) or a user instance computes the same trace as any other accepted user instance (line 84). In this case, $\textsc {SendResp}$ or $\textsc {SendTermInit}$ return $\bot$. We do the same if a trace that is computed in an $\textsc {Execute}$ query collides with one of a previously accepted instance (line 28). Due to the difference lemma,

$$\begin{aligned} \left| \Pr [\textsf{G}_1 \Rightarrow 1] -\Pr [\textsf{G}_0 \Rightarrow 1]\right| \le \Pr [{\textbf {bad}}_{\text {coll}}]. \end{aligned}$$

Note that when ${\textbf {bad}}_{\text {coll}}$ is not raised, each instance is unique and has at most one partner. In order to bound ${\textbf {bad}}_{\text {coll}}$, recall that the trace of an oracle $\pi _{\textsf{P}}^t$ consists of $(\textsf{U},\textsf{S},x^\textsf{U}=(x^\textsf{U}_1,...,x^\textsf{U}_\ell ),\hat{x}^\textsf{U}=(\hat{x}^\textsf{U}_1,...\hat{x}^\textsf{U}_\ell ),x^\textsf{S}=(x^\textsf{S}_1,...,x^\textsf{S}_\ell ),\hat{x}^\textsf{S}=(\hat{x}^\textsf{S}_1,...,\hat{x}^\textsf{S}_\ell ))$, where at least one of the message pairs $(x^\textsf{U},\hat{x}^\textsf{U})$ or $(x^\textsf{S},\hat{x}^\textsf{S})$ was chosen by the game. Thus, ${\textbf {bad}}_{\text {coll}}$ can only happen if all those $2\cdot \ell$ set elements collide with all $2\cdot \ell$ set elements of another instance. The probability that this happens for two (fixed) sessions is $|\mathcal {G}|^{-2\ell }$, hence the union bound over $q_e$ and $q_s$ sessions yields

$$\begin{aligned} \left| \Pr [\textsf{G}_1 \Rightarrow 1] -\Pr [\textsf{G}_0 \Rightarrow 1]\right| \le \Pr [{\textbf {bad}}_{\text {coll}}]\le \left( {\begin{array}{c}q_e+q_s\\ 2\end{array}}\right) \cdot \frac{1}{|\mathcal {G}|^{2\ell }}\le \frac{(q_e+q_s)^2}{|\mathcal {G}|^{2\ell }}. \end{aligned}$$

Game $\textsf{G}_2$. In game $\textsf{G}_2$, we make the freshness explicit. To each oracle $\pi _\textsf{P}^{t}$, we assign an additional variable $\pi _\textsf{P}^{t}.\textsf{fr}$ which is updated during the game. In particular, all instances used in execute queries are marked as fresh (line 34).

An instance is fresh if the password was not corrupted yet (lines 72, 89). Otherwise, it is not fresh (lines 74, 91). For user instances we also check if there exists a fresh partner (line 87). If $\mathcal {A}$ issues a $\textsc {Corrupt}$ query later, the freshness variable will also be updated (line 103). When the session key of an instance is revealed, this instance and its potential partner instance are marked as not fresh (line 41). On a query to test, the game then only checks the freshness variable (line 44). These are only a conceptual changes, hence

$$\begin{aligned} \Pr [\textsf{G}_2 \Rightarrow 1] = \Pr [\textsf{G}_1 \Rightarrow 1]. \end{aligned}$$

Game $\textsf{G}_3$. In game $\textsf{G}_3$, we choose random keys for instances queried to $\textsc {Execute}$. We construct adversary $\mathcal {B}_1$ against $\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ in Fig. 6 and show that

$$\begin{aligned} \left| \Pr [\textsf{G}_3 \Rightarrow 1] -\Pr [\textsf{G}_2 \Rightarrow 1]\right| \le \textsf{Adv}_\textsf{EGAT}^{\textsf{GA}\text {-}\textsf{St}\textsf{CDH}}(\mathcal {B}_1). \end{aligned}$$

Fig. 6.

Adversary $\mathcal {B}_1$ against $\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ for the proof of Theorem 1. $\mathcal {A}$ has access to oracles $\textsc {O}\,{:}{=}\, \{\textsc {Execute},\textsc {SendInit},\textsc {SendResp},\textsc {SendTermInit},\textsc {Reveal},\textsc {Corrupt},\textsc {Test},\textsf{H}\}$. Oracles $\textsc {SendInit}$, $\textsc {SendResp}$, $\textsc {SendTermInit}$, $\textsc {Reveal}$, $\textsc {Corrupt}$ and $\textsc {Test}$ are defined as in $\textsf{G}_6$. Lines written in blue show how $\mathcal {B}_1$ simulates the game. (Color figure online)

Adversary $\mathcal {B}_1$ inputs a $\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ challenge $(x,y)=(g\star \tilde{x}, h\star \tilde{x})$ and has access to a decision oracle $\textsc {GA}\text {-}\textsc {DDH}(x,\cdot ,\cdot )$. First, it generates the $\textsf{crs}$ elements $(x_0,x_1)$ as in game $\textsf{G}_3$ and then runs adversary $\mathcal {A}$. Queries to $\textsc {Execute}$ are simulated as follows: It chooses random group elements $u_i,\hat{u}_i$ and $s_i,\hat{s}_i$ for user and server instances and $i\in [\ell ]$, but instead of using $(x_0,x_1)$ to compute the set elements, $\mathcal {B}_1$ uses x for the user instance and y for the server instance, independent of the password bits $b_i$ (lines to 30 to 33). We can rewrite this as

$$x^\textsf{U}_i=u_i\star x=(u_i\cdot g)\star \tilde{x}= (u_i\cdot g \cdot g_{b_i} \cdot g_{b_i}^{-1})\star \tilde{x}= \underbrace{(u_i\cdot g \cdot g_{b_i}^{-1})}_{u'_i}\star x_{b_i},$$

where $u'_i$ is the group element that the user actually needs in order to compute the session key. In the same way, $\hat{u}'_i ~= \hat{u}_i \cdot g \cdot g_{b_i}^{-1}$, $s'_i =s_i\cdot h\cdot g_{b_i}^{-1}$ and $\hat{s}'_i=\hat{s}_i\cdot h\cdot g_{b_i}^{-1}$. Note that $z_i =(z_{i,1},z_{i,2},z_{i,3})$ is implicitly set to

$$\begin{aligned} z_{i,1}&= (u'_i\cdot s'_i) \star x_{b_i} = u_i\cdot g \cdot s_i\cdot h \cdot g_{b_i}^{-1} \star \tilde{x}\nonumber ,\\ z_{i,2}&= (\hat{u}'_i \cdot s'_i) \star x_{b_i} = \hat{u}_i\cdot g \cdot s_i\cdot h \cdot g_{b_i}^{-1} \star \tilde{x},\\ z_{i,3}&= (u'_i \cdot \hat{s}'_i) \star x_{b_i} = u_i\cdot g \cdot \hat{s}_i\cdot h \cdot g_{b_i}^{-1} \star \tilde{x}\nonumber . \end{aligned}$$

Before choosing a random session key, we check if there has been a query to the random oracle $\textsf{H}$ that matches the session key (line 37–45). We iterate over the entries in T, where $\textsf{U}$, $\textsf{S}$, $x^\textsf{U}$, $\hat{x}^\textsf{U}$, $x^\textsf{S}$, $\hat{x}^\textsf{S}$ and $\textsf{pw}_{\textsf{U}\textsf{S}}$ match, and check if one of the entries in z is correct. Note that we can use the following equivalences:

$$\begin{aligned} \textsf{GA}\text {-}\textsf{CDH}_{x_{b_i}}(x^\textsf{U}_i,x^\textsf{S}_i)=z_{i,1} \quad ~~&~\Leftrightarrow&\textsf{GA}\text {-}\textsf{CDH}(x,x^\textsf{S}_i)=&~(u_i^{-1}\cdot g_{b_i})\star z_{i,1},\\ \textsf{GA}\text {-}\textsf{CDH}_{x_{b_i}}(\hat{x}^\textsf{U}_i,x^\textsf{S}_i)=z_{i,2} \quad ~~&~\Leftrightarrow&\textsf{GA}\text {-}\textsf{CDH}(x,x^\textsf{S}_i)=&~(\hat{u}_i^{-1}\cdot g_{b_i})\star z_{i,2} ,\\ \textsf{GA}\text {-}\textsf{CDH}_{x_{b_i}}(x^\textsf{U}_i,\hat{x}^\textsf{S}_i)=z_{i,3}\quad ~~&~\Leftrightarrow&\textsf{GA}\text {-}\textsf{CDH}(x,\hat{x}^\textsf{S}_i)=&~(u_i^{-1}\cdot g_{b_i})\star z_{i,3} , \end{aligned}$$

which allows us to use the restricted decision oracle $\textsc {GA}\text {-}\textsc {DDH}(x,\cdot ,\cdot )$. If one of $z_{i,1}, z_{i,2},z_{i,3}$ is correct, $\mathcal {B}_1$ aborts and outputs the solution $(g \cdot h) \star \tilde{x}$ which is respectively given by $(u_i^{-1}\cdot s_i^{-1}\cdot g_{b_i})\star z_{i,1}$, $(\hat{u}_i^{-1}\cdot s_i^{-1}\cdot g_{b_i})\star z_{i,2}$ or $(u_i^{-1}\cdot \hat{s}_i^{-1}\cdot g_{b_i})\star z_{i,3}$.

Otherwise, we store the values $u_i,\hat{u}_i$ and $s_i,\hat{s}_i$ in list $T_{\text {e}}$ together with the trace and the password (line 46) and choose a session key uniformly at random. We need list $T_{\text {e}}$ to identify relevant queries to $\textsf{H}$. In particular, if the trace and password appear in a query, we retrieve the values $u_i,\hat{u}_i$ and $s_i,\hat{s}_i$ to check whether the provided $z_i$ are correct. We do this in the same way as described above using the decision oracle (lines 09–18). If the oracle returns 1 for any $z_{i,j}$, $\mathcal {B}_1$ aborts and outputs the solution for $(g \cdot h) \star \tilde{x}$ which is respectively given by $(u_i^{-1}\cdot s_i^{-1}\cdot g_{b_i})\star z_{i,1}$, $(\hat{u}_i^{-1}\cdot s_i^{-1}\cdot g_{b_i})\star z_{i,2}$ or $(u_i^{-1}\cdot \hat{s}_i^{-1}\cdot g_{b_i})\star z_{i,3}$.

Game $\textsf{G}_4$. In game $\textsf{G}_4$, we remove the password from execute queries. In particular, we do not compute $x^\textsf{U},\hat{x}^\textsf{U},x^\textsf{S},\hat{x}^\textsf{S}$ to the basis $x_{b_i}$, but simply use $\tilde{x}$. Note that the values have the same distribution as in the previous game. Also, the group elements $u,\hat{u},s$ and $\hat{s}$ are not used to derive the key. Hence, this change is not observable by $\mathcal {A}$ and

$$\begin{aligned} \Pr [\textsf{G}_4 \Rightarrow 1] = \Pr [\textsf{G}_3 \Rightarrow 1]. \end{aligned}$$

Game $\textsf{G}_5$. $\textsf{G}_5$ is given in Fig. 7. In this game we want to replace the session keys by random for all fresh instances in oracles $\textsc {SendResp}$ and $\textsc {SendTermInit}$ (lines 62, 83). Therefore, we introduce an additional independent random oracle $T_{\text {s}}$ which maps only the trace of an instance to a key (lines 63, 84). We keep partner instances consistent, i.e., in case the adversary queries $\textsc {SendTermInit}$ for a user instance and there exists a fresh partner instance, then we retrieve the corresponding key from $T_{\text {s}}$ and also assign it to this instance (line 78). For all instances that are not fresh, we simply compute the correct key using random oracle $\textsf{H}$ (lines 66–69, 87–90). If a session is fresh and there is an inconsistency between T and $T_{\text {s}}$, we raise flag ${\textbf {bad}}$. This happens in the following cases:

• a server instance is about to compute the session key, the password was not corrupted, but there already exists an entry in T with the correct password and z (lines 60–61).

• a user instance is about to compute the session key, there exists no partner instance and the password was not corrupted, but there already exists an entry in T with the correct password and z (lines 81–82).

• the random oracle is queried on some trace that appears in $T_{\text {s}}$ together with the correct password and z (lines 36–47). At this point, we also check if the password was corrupted in the meantime and if this is the case and the adversary issues the correct query, we output the key stored in $T_{\text {s}}$ (line 46) as this instance cannot be tested. This case corresponds to perfect forward secrecy which we cover in the full version of the paper [1, Appendix E].

When ${\textbf {bad}}$ is not raised, there is no difference between $\textsf{G}_4$ and $\textsf{G}_5$. Hence,

$$\begin{aligned} \left| \Pr [\textsf{G}_5 \Rightarrow 1] -\Pr [\textsf{G}_4 \Rightarrow 1]\right| \le \Pr [\textsf{G}_5\Rightarrow {\textbf {bad}}]. \end{aligned}$$

Fig. 7.

Game $\textsf{G}_5$ for the proof of Theorem 1. $\mathcal {A}$ has access to oracles $\textsc {O}\,{:}{=}\, \{\textsc {Execute}$, $\textsc {SendInit}$, $\textsc {SendResp}$, $\textsc {SendTermInit}$, $\textsc {Reveal}$, $\textsc {Corrupt}$, $\textsc {Test}$, $\textsf{H}\}$. $\textsc {Reveal}$, $\textsc {Test}$ and $\textsc {Corrupt}$ are defined as in Fig. 5. Differences to $\textsf{G}_4$ are highlighted in blue. (Color figure online)

Game $\textsf{G}_6$. $\textsf{G}_6$ is given in Fig. 8. In this game we remove the password from send queries and generate passwords as late as possible, that is either when the adversary issues a corrupt query (line 21) or after it has stopped with output $\beta '$ (line 07). In $\textsc {SendInit}$ and $\textsc {SendResp}$ we still choose group elements $u_i,\hat{u}_i,s_i$ and $\hat{s}_i$ uniformly at random, but now compute $x^\textsf{U}_i,\hat{x}^\textsf{U}_i,x^\textsf{S}_i$ and $\hat{x}^\textsf{S}_i$ using the origin element (lines , , and 26, 27, 51 and 52). Thus, depending on which password is chosen afterwards, we implicitly set

$$x^\textsf{U}_i=u_i\cdot \tilde{x}= (u_i\cdot g_0^{-1})\star x_0 = (u_i\cdot g_1^{-1})\star x_1$$

and analogously for $\hat{x}^\textsf{U}_i, x^\textsf{S}_i$ and $\hat{x}^\textsf{S}_i$. For all instances that are not fresh, we have to compute the real session key using $z_i=(s_i\cdot g_{b_i}^{-1}\star x^\textsf{U}_i,s_i\cdot g_{b_i}^{-1}\star \hat{x}^\textsf{U}_i,\hat{s}_i\cdot g_{b_i}^{-1}\star x^\textsf{U}_i)$ (line 70) or $z_i=(u_i\cdot g_{b_i}^{-1}\star x^\textsf{S}_i,\hat{u}_i\cdot g_{b_i}^{-1}\star x^\textsf{S}_i,u_i\cdot g_{b_i}^{-1}\star \hat{x}^\textsf{S}_i)$ (line 97). Note that the password is already defined for these instances.

Fig. 8.

Game $\textsf{G}_6$ for the proof of Theorem 1. $\mathcal {A}$ has access to oracles $\textsc {O}\,{:}{=}\, \{\textsc {Execute},\textsc {SendInit},\textsc {SendResp},\textsc {SendTermInit},\textsc {Reveal},\textsc {Corrupt},\textsc {Test},\textsf{H}\}$. Oracles $\textsc {Reveal}$ and $\textsc {Test}$ are defined as in game $\textsf{G}_4$ in Fig. 5. Oracle $\textsc {Execute}$ is defined as in Fig. 7. Differences to $\textsf{G}_5$ are highlighted in blue. (Color figure online)

Recall that event ${\textbf {bad}}$ in game $\textsf{G}_5$ is raised whenever there is an inconsistency in the random oracle queries and the keys of fresh instances. In this game, we split event ${\textbf {bad}}$ into two different events:

• ${\textbf {bad}}_{\textsf{pw}}$ captures the event that there exists more than one valid entry in T for the same trace of a fresh instance, but different passwords.

• ${\textbf {bad}}_{\text {guess}}$ happens only if ${\textbf {bad}}_{\textsf{pw}}$ does not happen and is raised if there exists a valid entry in T for the trace of a fresh instance and the correct password, where the password was not corrupted when the query to $\textsf{H}$ was made.

To identify the different events, we introduce a new set $T_{\text {bad}}$. For all fresh instances in $\textsc {SendResp}$ and $\textsc {SendTermInit}$, we now iterate over all entries in T that contain the corresponding trace. We check if the given password and z are valid for this trace by computing the real values $z'$ in the same way as for non-fresh instances. If $z=z'$, we add this entry to the set $T_{\text {bad}}$ (lines 57–63, 84–90). We essentially do the same when the random oracle $\textsf{H}$ is queried on a trace that appears in $T_{\text {s}}$. Here, the adversary specifies the password and we check if z is valid for that password using the $u_i,\hat{u}_i$ stored in $T_{\text {s}}$ for user instances and $s_i,\hat{s}_i$ for server instances. If z is valid and the instance is still fresh, we add the query to $T_{\text {bad}}$ (lines 33–45). In case the password was corrupted in the meantime, we output the key stored in $T_{\text {s}}$ as introduced in the previous game.

After the adversary terminates, we check $T_{\text {bad}}$ whether event ${\textbf {bad}}_{\textsf{pw}}$ (line 09) or event ${\textbf {bad}}_{\text {guess}}$ (line 12) occurred. We will bound these events below. First note that whenever ${\textbf {bad}}$ is raised in $\textsf{G}_5$, then either flag ${\textbf {bad}}_{\text {guess}}$ or ${\textbf {bad}}_{\textsf{pw}}$ is raised in $\textsf{G}_6$, thus

$$\begin{aligned} \Pr [\textsf{G}_5\Rightarrow {\textbf {bad}}]\le \Pr [\textsf{G}_6\Rightarrow {\textbf {bad}}_{\textsf{pw}}]+\Pr [\textsf{G}_6\Rightarrow {\textbf {bad}}_{\text {guess}}]. \end{aligned}$$

Finally, we bound the probabilities of the two events. We start with ${\textbf {bad}}_{\textsf{pw}}$. In Fig. 9, we construct adversary $\mathcal {B}_2$ against $\textsf{D}\textsf{Sim}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ that simulates $\textsf{G}_6$.

Fig. 9.

Adversary $\mathcal {B}_2$ against $\textsf{D}\textsf{Sim}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ for the proof of Theorem 1. $\mathcal {A}$ has access to oracles $\textsc {O}\,{:}{=}\, \{\textsc {Execute},\textsc {SendInit},\textsc {SendResp},\textsc {SendTermInit},\textsc {Reveal},\textsc {Corrupt},\textsc {Test},\textsf{H}\}$. Oracles $\textsc {Execute}$, $\textsc {Reveal}$, $\textsc {Corrupt}$ and $\textsc {Test}$ are defined as in $\textsf{G}_6$. Lines written in blue show how $\mathcal {B}_2$ simulates the game. (Color figure online)

We show that when ${\textbf {bad}}_{\textsf{pw}}$ occurs, then $\mathcal {B}_2$ can solve $\textsf{D}\textsf{Sim}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$. Hence,

$$\begin{aligned} \Pr [\textsf{G}_6\Rightarrow {\textbf {bad}}_{\textsf{pw}}]\le \textsf{Adv}^{\textsf{D}\textsf{Sim}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}}_\textsf{EGA}(\mathcal {B}_2). \end{aligned}$$

Adversary $\mathcal {B}_2$ inputs $(x_0,x_1,w_0,w_1)$, where $x_0=g_0\star \tilde{x}$, $x_1=g_1\star \tilde{x}$, $w_0 = h_0 \star \tilde{x}$ and $w_1 = h_1 \star \tilde{x}$ for group elements $g_0,g_1,h_0,h_1\in \mathcal {G}$ chosen uniformly at random. Adversary $\mathcal {B}_2$ also has access to decision oracles $\textsc {GA}\text {-}\textsc {DDH}_{x_j}(w_i,\cdot ,\cdot )$ for $(i,j) \in \{0,1\}^2$. It runs adversary $\mathcal {A}$ on $(x_0,x_1)$. Queries to $\textsc {SendInit}$ are simulated as follows: $\mathcal {B}_2$ chooses group elements $u_i$ and $\hat{u}_i$ uniformly at random and sets

$$\begin{aligned} x^\textsf{U}_i&=u_i\star w_0=(u_i\cdot h_0 \cdot g_0^{-1}) \star x_0=(u_i\cdot h_0 \cdot g_1^{-1}) \star x_1,\\ \hat{x}^\textsf{U}_i&=\hat{u}_i\star w_1=(\hat{u}_i\cdot h_1 \cdot g_0^{-1}) \star x_0=(\hat{u}_i\cdot h_1 \cdot g_1^{-1}) \star x_1. \end{aligned}$$

The simulation of $x^\textsf{S}_i$ and $\hat{x}^\textsf{S}_i$ in $\textsc {SendResp}$ is done in the same way, choosing random $s_i$ and $\hat{s}_i$. In case the server instance is fresh, we must check if there already exists an entry in T that causes an inconsistency. As in $\textsf{G}_6$, we iterate over all $\textsf{pw}$, z, in T that contain the trace of this instance. In particular, we must check whether

$$\begin{aligned} z_{i,1}&= \textsf{GA}\text {-}\textsf{CDH}_{x_{b_i}}(x^\textsf{U}_i,x^\textsf{S}_i) \quad \Leftrightarrow \quad \textsf{GA}\text {-}\textsf{CDH}_{x_{b_i}}(w_0,x^\textsf{U}_i)=s_i^{-1}\star z_{i,1},\\ z_{i,2}&= \textsf{GA}\text {-}\textsf{CDH}_{x_{b_i}}(\hat{x}^\textsf{U}_i,x^\textsf{S}_i) \quad \Leftrightarrow \quad \textsf{GA}\text {-}\textsf{CDH}_{x_{b_i}}(w_0,\hat{x}^\textsf{U}_i)=s_i^{-1}\star z_{i,2},\\ z_{i,3}&= \textsf{GA}\text {-}\textsf{CDH}_{x_{b_i}}(x^\textsf{U}_i,\hat{x}^\textsf{S}_i) \quad \Leftrightarrow \quad \textsf{GA}\text {-}\textsf{CDH}_{x_{b_i}}(w_1,x^\textsf{U}_i)=\hat{s}_i^{-1}\star z_{i,3}, \end{aligned}$$

which can be done with the decision oracles $\textsc {GA}\text {-}\textsc {DDH}_{x_{b_i}}(w_j,\cdot ,\cdot )$. If all $z_i$ are valid, then we add this entry to $T_{\text {bad}}$ (lines 56–59).

If the instance is not fresh, then we have to compute the correct key. We check list T for a valid entry z as explained above and if it exists, we assign this value to the session key (line 66). Otherwise, we choose a random key and add a special entry to T, which instead of z contains the secret group elements $s_i$ and $\hat{s}_i$ (line 69) so that we can patch the random oracle later. $\textsc {SendTermInit}$ is simulated analogously, using the secret group elements $u_i$ and $\hat{u}_i$.

Now we look at the random oracle queries. If the trace is contained in set $T_{\text {s}}$ which means the corresponding instance was fresh when the send query was issued, we check if z is valid using the $\textsc {GA}\text {-}\textsc {DDH}$ oracle. We do this as described above, depending on whether it is a user or a server instance (lines 25, 31). In case z is valid, we first check if the instance is still fresh (i.e., the password was not corrupted in the meantime) and if this is the case, we add the query to $T_{\text {bad}}$ (lines 28, 34). Otherwise, if the password was corrupted and is specified in the query, we return the session key stored in $T_{\text {s}}$ (lines 30, 36).

Next, we check if the query matches a special entry in T that was added in $\textsc {SendResp}$ or $\textsc {SendTermInit}$ for a non-fresh instance, which means we have to output the same key that was chosen before. Again, we can use the $\textsc {GA}\text {-}\textsc {DDH}$ oracle and differentiate between user and server instances (lines 37–44).

After $\mathcal {A}$ terminates with output $\beta '$, $\mathcal {B}_2$ chooses the passwords which have not been generated in a $\textsc {Corrupt}$ query yet. If ${\textbf {bad}}_{\textsf{pw}}$ occurred (lines 05–13), then there must be two entries in $T_{\text {bad}}$ for the same trace and different passwords $\textsf{pw}\ne \textsf{pw}'$ along with values z and $z'$. Let i be the first index where the two passwords differ, i.e., $b_i\ne b_i'$. Without loss of generality assume that $b_i=0$ and $b_i'=1$, otherwise swap $\textsf{pw},z$ and $\textsf{pw}',z'$. If the entries in $T_{\text {bad}}$ are those of a user instance, we retrieve the secret group elements $u_, \hat{u}_i$ from $T_{\text {s}}$.

Recall that the $\textsf{D}\textsf{Sim}\text {-}\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ problem requires to compute $y_0=\textsf{GA}\text {-}\textsf{CDH}_{x_0}(w_0,y)$, $y_1=\textsf{GA}\text {-}\textsf{CDH}_{x_0}(w_1,y)$, $y_2=\textsf{GA}\text {-}\textsf{CDH}_{x_1}(w_0,y)$ and $y_3=\textsf{GA}\text {-}\textsf{CDH}_{x_1}(w_1,y)$, where y can be chosen by the adversary. $\mathcal {B}_2$ sets $y=x^\textsf{S}_i$, and outputs y and

$$\begin{aligned} y_0&=u_i^{-1}\star z_{i,1}=\textsf{GA}\text {-}\textsf{CDH}_{x_0}(u_i^{-1}\star x^\textsf{U}_i,x^\textsf{S}_i)=\textsf{GA}\text {-}\textsf{CDH}_{x_0}(w_0,x^\textsf{S}_i),\\ y_1&=\hat{u}_i^{-1}\star z_{i,2}=\textsf{GA}\text {-}\textsf{CDH}_{x_0}(\hat{u}_i^{-1}\star \hat{x}^\textsf{U}_i,x^\textsf{S}_i)=\textsf{GA}\text {-}\textsf{CDH}_{x_0}(w_1,x^\textsf{S}_i),\\ y_2&= u_i^{-1}\star z_{i,1}'=\textsf{GA}\text {-}\textsf{CDH}_{x_1}(u_i^{-1}\star x^\textsf{U}_i,x^\textsf{S}_i)=\textsf{GA}\text {-}\textsf{CDH}_{x_1}(w_0,x^\textsf{S}_i),\\ y_3&= \hat{u}_i^{-1}\star z_{i,2}'=\textsf{GA}\text {-}\textsf{CDH}_{x_1}(\hat{u}_i^{-1}\star \hat{x}^\textsf{U}_i,x^\textsf{S}_i)=\textsf{GA}\text {-}\textsf{CDH}_{x_1}(w_1,x^\textsf{S}_i). \end{aligned}$$

If the instance is a server instance, $\mathcal {B}_2$ outputs $(y,y_0,y_1,y_2,y_3)=(x^\textsf{U}_i,s_i^{-1}\star z_{i,1} , \hat{s}_i^{-1}\star z_{i,3} , s_i^{-1}\star z_{i,1}', \hat{s}_i^{-1}\star z_{i,3}')$. This concludes the analysis of ${\textbf {bad}}_{\textsf{pw}}$.

Next, we analyze event ${\textbf {bad}}_{\text {guess}}$. Recall that ${\textbf {bad}}_{\text {guess}}$ happens only if ${\textbf {bad}}_{\textsf{pw}}$ does not happen. Hence, for each instance there is at most one entry in $T_{\text {bad}}$ and the size of $T_{\text {bad}}$ is at most $q_s$. As all entries were added before the corresponding password was sampled, the probability is bounded by

$$\begin{aligned} \Pr [\textsf{G}_6\Rightarrow {\textbf {bad}}_{\text {guess}}]\le \frac{q_s}{|\mathcal{P}\mathcal{W}|}. \end{aligned}$$

Finally, note that if none of the bad events happens in $\textsf{G}_6$, all session keys output by $\textsc {Test}$ are uniformly random and the adversary can only guess $\beta$. Hence, $\Pr [\textsf{G}_6\Rightarrow 1]=\frac{1}{2}$. Collecting the probabilities and using Eq. 1 yields the bound in Theorem 1.    $\square$

7 $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$: Three-Round PAKE from Group Actions

In this section we present a second modification of $\mathsf {GA\text {-}PAKE}_\ell$, which can be securely instantiated with an $\textsf{EGAT}$. The protocol $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$ extends $\mathsf {GA\text {-}PAKE}_\ell$ by a commitment that has to be sent before sending the actual messages. This ensures that the server cannot choose the set elements depending on the message it receives from the user which was the crucial step in the attack against $\mathsf {GA\text {-}PAKE}_\ell$. In the second round, the user sends its message to the server and only after receiving that message, the server sends its message to the user. The protocol is sketched in Fig. 10 and its security is established in Theorem 2. While this protocol adds two rounds to the original protocol, the total computational cost is lower than for $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$.

Fig. 10.

PAKE protocol $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$ from group actions.

Theorem 2

(Security of $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$). For any adversary $\mathcal {A}$ against $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$ that issues at most $q_e$ execute queries, $q_s$ send queries and at most $q_\textsf{G}$ and $q_\textsf{H}$ queries to random oracles $\textsf{G}$ and $\textsf{H}$, there exist an adversary $\mathcal {B}_1$ against $\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ and an adversary $\mathcal {B}_2$ against $\textsf{GA}\text {-}\textsf{Gap}\textsf{CDH}$ such that

$$\begin{aligned} \textsf{Adv}_{\mathsf {Com\text {-}GA\text {-}PAKE}_\ell }(\mathcal {A})\le&~\textsf{Adv}_\textsf{EGAT}^{\textsf{GA}\text {-}\textsf{St}\textsf{CDH}}(\mathcal {B}_1) + q_s\ell \cdot \sqrt{\textsf{Adv}_{\textsf{EGAT}}^{\textsf{GA}\text {-}\textsf{Gap}\textsf{CDH}}(\mathcal {B}_2)} + \frac{(q_s+q_e)^2}{|\mathcal {G}|^\ell } \\&+ \frac{q_\textsf{G}q_s}{|\mathcal {G}|^\ell } + \frac{2\cdot (q_\textsf{G}+q_s+q_e)^2}{2^\lambda } + \frac{q_s}{|\mathcal{P}\mathcal{W}|}, \end{aligned}$$

where $\lambda$ is the output length of $\textsf{G}$ in bits.

The proof is similar to the one of Theorem 1 so we will only sketch it here. The full proof is given in the long version of the paper [1, Appendix E].

Proof (Sketch)

After ensuring that all traces are unique, we need to deal with the commitment and in particular collisions. First, we require that there are never two inputs to the random oracle $\textsf{G}$ that return the same commitment. This is to ensure that the adversary cannot open a commitment to a different value, which might depend on previous messages.

Second, we need to ensure that after the adversary has seen a commitment, it does not query $\textsf{G}$ on the input, which is the hiding property of the commitment. What we actually do here is that we choose a random commitment in the first round. Only later we choose the input and patch the random oracle accordingly.

Now we can replace the session keys of instances which are used in execute queries. Here, the freshness condition allows the adversary to corrupt the password. However, as both $x^\textsf{S}$ and $x^\textsf{U}$ are generated by the experiment, the only chance to notice this change is to solve the $\textsf{GA}\text {-}\textsf{St}\textsf{CDH}$ problem, where the decision oracle is required to simulate instances correctly.

In order to replace the session keys of fresh instances which are used in send queries, we make the key independent of the password. The session key of a fresh instance is now defined by the trace of that instance. The only issue that may arise here is an inconsistency between the session key that is derived using the trace and the session key that is derived using the random oracle $\textsf{H}$. Whenever such an inconsistency occurs, we differentiate between two cases:

• There exists more than one valid entry in $T_{\textsf{H}}$ for the same trace of a fresh instance, but different passwords.

• There exists a valid entry in $T_{\textsf{H}}$ for the trace of a fresh instance and the correct password, where the password was not corrupted when the query to $\textsf{H}$ was made.

Finally, we bound the probabilities of the two cases. Similar to Theorem 1, we will define a new computational problem that reflects exactly the interaction in the protocol. We show that this problem is implied by $\textsf{GA}\text {-}\textsf{Gap}\textsf{CDH}$ using the reset lemma. The general idea is that the adversary can always compute the session key for one password guess, but not for a second one. After excluding this, we choose the actual password, which is possible because session keys are computed independently of the password. Thus, looking at one fixed instance, the probability that the adversary guessed the password correctly is $1/|\mathcal{P}\mathcal{W}|$.    $\square$

8 Variants of the PAKE Protocols

Both protocols $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ and $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$ require that the user and the server generate multiple random group elements and evaluate their action on certain set elements. In this section we present two optimizations that allow us to reduce the number of random group elements and the number of evaluations.

8.1 Increasing the Number of Public Parameters

In $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ and $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$ the common reference string is set to $\textsf{crs}\,{:}{=}\,(x_0,x_1)\in \mathcal {X}^2$. Increasing the number of public parameters allows to reduce the number of group action evaluations in the execution of the protocol. The idea is similar to the optimizations deployed to speed up the CSIDH-based signatures schemes SeaSign [14] and CSI-FiSh [9]. We refer to Table 1 in the introduction for an overview and example of the parameter choice.

We explain the changes on the basis of protocol $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$. The variant of $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$ is similar and is provided in the full version of the paper [1, Appendix E], together with a security analysis for both variants. For some positive integer N dividing $\ell$, we set

$$ \textsf{crs}\,{:}{=}\,(x_0,\dots , x_{2^N-1})\in \mathcal {X}^{2^N} \quad \text {and} \quad \textsf{pw}= (b_1,...,b_{\ell /N})\in \{0,...,2^N-1\}^{\ell /N}. $$

Note that as before, the password is a bitstring of length $\ell$, but it is divided into $\ell /N$ blocks of length N. In particular $x_{b_i}$ refers to one of the $2^N$ different set elements in the $\textsf{crs}$. The general outline of the protocol does not change. The only difference is that in the first step both the server and the user only generate $2 \cdot \ell / N$ random group elements (instead of $2 \cdot \ell$). Hence they only need to perform $2\cdot \ell /N$ group action evaluations in the first round and $3 \cdot \ell /N$ evaluations in the session key derivation. We write $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_{\ell ,N}$ for this variant of the protocol.

8.2 Using Twists in the Setup

Both $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}_\ell$ and $\mathsf {Com\text {-}GA\text {-}PAKE}_\ell$ require that some trusted party generates two random set elements $\textsf{crs}= (x_0,x_1)$. Here, we shortly discuss the setup where $x_1$ is replaced by the twist of $x_0$, i.e. $\textsf{crs}\,{:}{=}\, (x_0,x_0^t)$.

This simplification is particularly helpful when applied to one of the variants from the previous subsection. These modified versions require to generate $2^N$ random set elements for the $\textsf{crs}$. Using twists it suffices to generate $2^{N-1}$ elements $(x_0, \dots , x_{2^{N-1}-1}) \in \mathcal {X}^{2^{N-1}}$ and setting $x_{i+2^{N-1}} = x_i^t$ for each $i \in [0,2^{N-1}-1]$.

The security of $\textsf{X}\text {-}\textsf{GA}\text {-}\textsf{PAKE}^\textsf{t}_{\ell }$ and $\mathsf {Com\text {-}GA\text {-}PAKE^\textsf{t}_{\ell }}$ (the twisted versions of the protocols) is discussed in the full version [1, Appendices D, E].