A Generic Construction of Tightly Secure Password-Based Authenticated Key Exchange

Abstract

We propose a generic construction of password-based authenticated key exchange (PAKE) from key encapsulation mechanisms (KEM). Assuming that the KEM is oneway secure against plaintext-checkable attacks (OW-PCA), we prove that our PAKE protocol is tightly secure in the Bellare-Pointcheval-Rogaway model (EUROCRYPT 2000). Our tight security proofs require ideal ciphers and random oracles. The OW-PCA security is relatively weak and can be implemented tightly with the Diffie-Hellman assumption, which generalizes the work of Liu et al. (PKC 2023), and “almost” tightly with lattice-based assumptions, which tightens the security loss of the work of Beguinet et al. (ACNS 2023) and allows more efficient practical implementation with Kyber. Beyond these, it opens an opportunity of constructing tight PAKE based on various assumptions.

Supported by the Research Council of Norway under Project No. 324235.

1 Introduction

While authenticated key exchange (AKE) protocols require a PKI to certify user public keys, password-based AKE (PAKE) protocols allow a client and a server to establish a session key, assuming that both parties share a password in advance. A password is chosen from a small set of possible strings, referred as a dictionary. Thus, a password has low-entropy and can be memorized by humans. Hence, it is very convenient, and the design and analysis of PAKE protocols have drew a lot of attention in the past few years.

After the introduction of Encrypted-Key-Exchange (EKE) protocol by Bellovin and Merritt [12], many PAKE protocols have been proposed based on variants of the Diffie-Hellman assumptions, including the well-known SPEKE [22], SPEKE2 [6], J-PAKE [20], and CPace [19]. There are only a few exception where PAKE is constructed based on post-quantum assumptions, such as lattices [13, 23, 33] and group actions [4].

Security of PAKE. The security requirements on a PAKE protocol are resistance against offline (where an adversary performs an exhaustive search for the password offline) and online (where an active adversary tries a small number of passwords to run the protocol) dictionary attacks. Similar to the classical AKE, forward secrecy is required as well, where the session keys remain secure, even if the password is corrupted at a later point in time, and also leakage of a session key should not affect other session keys. Their security is formalized by either the indistinguishability-based (IND-based) model [10] or the universal composability (UC) framework [16].

Usually, the advantage of a PAKE protocol $\varepsilon _{\text {PAKE}}$ has the form of:

$$\begin{aligned} \varepsilon _{\text {PAKE}}\le \nicefrac {S}{|\mathcal{P}\mathcal{W}|} + L \cdot \varepsilon _{\text {Problem}}, \end{aligned}$$

(1)

where S is the number of protocol sessions, $\mathcal{P}\mathcal{W}$ is the set of all possible passwords, $\varepsilon _{\text {Problem}}$ is the advantage of attacking the underlying cryptographic hard problem, and L is called the security loss. Here we ignore the additive statistical negligible probability in Eq. (1) for simplicity. Essentially, $\nicefrac {S}{|\mathcal{P}\mathcal{W}|}$ is the success probability of online dictionary attacks and Eq. (1) shows that the best attack on the PAKE protocol is performing an online dictionary attack. This can be eliminated by restricting the online password guess in practice.

Tight Security. We say a security proof for PAKE tight if L is a small constant. All the aforementioned PAKE protocols are non-tight. For instance, according to the analysis of [8], we estimate that the security loss L for the EKE protocol is $O(q_D\cdot (S+q_D))$, where $q_D$ is the number of the adversary’s queries to an ideal cipher. The security bound for the group-action-based protocol $\textsf {Com}\text {-}\textsf {GA}\text {-}\textsf {PAKE}_\ell$ in [4] is even worse, and it contains a square root of the advantage of the underlying assumption (cf. [4, Theorem 2]), due to the Reset Lemma [9]. This means even if we set up the underlying assumption with 128-bit security, $\textsf {Com}\text {-}\textsf {GA}\text {-}\textsf {PAKE}_\ell$ in [4] has only less¹ than 64-bit.

We note that $\textsf {X}\text {-}\textsf {GA}\text {-}\textsf {PAKE}_\ell$ in [4, Section 6] has tight security by restricting to weak forward secrecy, where an adversary is not allowed to perform active attacks before password corruptions. This is a rather weak security model.

In this paper, we are interested in tightly secure PAKE with perfect forward secrecy (PFS), namely, adversaries can perform active attacks before password corruptions. From a theoretical perspective, it is interesting to analyze the possibility of constructing tightly secure PAKE and under which cryptographic assumption it is possible. From a practical perspective, it is very desirable to have tightly secure PAKE (or AKE in general), since these protocols are executed in a multi-user, multi-instance scenario. In today’s internet, the scenario size is often large. A non-tight protocol requires a larger security parameter to compensate the security loss and results in a less efficient protocol. Even if we cannot achieve full tightness, a tighter security proof is already more beneficial than a less tight one of the same protocol, since the tighter proof offers higher security guarantees.

Our Goal: Tight PAKE Beyond Diffie-Hellman (DH). There are a few exceptions that construct tight PAKE protocols with PFS, and they are all based on the DH assumption. Becerra et al. [7] proved tight security of the three-move PAK protocol [25] using the Gap DH (GDH) assumption [26] in the IND-based model, where the GDH assumption states that the Computational DH (CDH) assumption is hard even if the Decisional DH (DDH) assumption is easy. Lately, Abdalla et al. [2] proved tight security of two-move SPAKE2 in the relaxed UC framework under the GDH assumption. Very recently, Liu et al. [24] carefully used the twinning technique [17] to remove the GDH assumption and proved a variant of the EKE protocol tightly based on the CDH assumption.

Our goal is to construct tightly secure PAKE protocols from post-quantum assumptions, beyond the DH assumptions. Lattice-based assumptions are the promising post-quantum ones, and it seems inherent that they do not have any Gap-like assumption or twinning techniques, since the Decisional and Computational variants of, for instance, Learning-With-Errors (LWE) assumption [30] are equivalent.

Regarding the assumption based on group actions, as we discussed earlier, the $\textsf {Com}\text {-}\textsf {GA}\text {-}\textsf {PAKE}_\ell$ protocol in [4] needs to rewind an adversary to argue PFS, and by using the Reset Lemma it leads to a very loose bound. Apart from that, $\textsf {Com}\text {-}\textsf {GA}\text {-}\textsf {PAKE}_\ell$ applies the group action in a “bit-by-bit” (wrt the bit-length of a password) fashion and sends out the resulting element, and thus it is quite inefficient in terms of both computation and communication complexity.

Finally, we note that Liu et al. [24] did not provide a formal proof on the PFS of their protocol, but rather an informal remark. In [4], we note a huge gap between the security loss of a weak FS protocol and a PFS one. Hence, in this paper we will prove the PFS of our protocol concretely.

1.1 Our Contribution

We propose a generic construction of tightly secure PAKE protocols from key encapsulation mechanisms (KEMs) in the ideal cipher and random oracle models. We require the underlying KEM to have the following security:

• Oneway plaintext-checking (OW-PCA) security in the multi-user, multi-challenge setting, namely, adversary $\mathcal {A}$’s goal is to decapsulate one ciphertext out of many given ones, and furthermore, $\mathcal {A}$ is given an oracle to check whether a key $\textsf{k}$ is a valid decapsulation of a ciphertext $\textsf{c}$ under some user j. It is a (slight) multi-user, multi-challenge variant of the original OW-PCA [27].

• Anonymous ciphertexts under PCA, namely, the challenge ciphertexts do not leak any information about the corresponding public keys.

• Fuzzy public keys, namely, the generated public keys are indistinguishable from a random key from all the possible public keys.

Such a KEM can be tightly constructed:

• either generically from pseudorandom PKE against chosen-plaintext attacks in the multi-user, multi-challenge setting (PR-CPA security²), which states that the given challenge ciphertexts are pseudorandom. This means, as long as we have a PR-CPA secure PKE, we have a PAKE protocol that preserves the tightness of the PKE. With lattices, we do not know a tightly PR-CPA PKE, but only a scheme (i.e. Regev’s encryption [30]) tightly wrt. the number of challenges, not wrt. the number of users. This already results in a tighter PAKE protocol than the analysis from Beguinet et al. [8]. More details will be provided in “Comparison using Kyber”.

• or directly from the strong DH (stDH) assumption in a prime-order group [3]. Under this stronger assumption, our resulting PAKE protocol has $O(\lambda )$ (which corresponds to the bit-length of a group element) less than the 2DH-EKE protocol of Liu et al. [24] in terms of protocol transcripts. In fact, using the twinning technique of Cash et al. [17], we can remove the strong oracle and have our protocol under the CDH assumption, which is the same protocol as the 2DH-EKE protocol of Liu et al. Essentially, our direct instantiation abstracts the key ideas of Liu et al., and our proof for PFS gives a formal analysis of Liu et al.’s protocol.

Different to other PAKE protocol from group actions [4] and lattices as in [13], our construction is compact and does not use “bit-by-bit” approaches. Figure 1 briefly summarizes our approaches.

Fig. 1.

Overview of our construction. All implications are tight, and the blue ones are done via generic constructions. OW-PCA security is the core for our “KEM-to-PAKE” transformation. Please find additional requirements on the KEM in the text. (Color figure online)

Our proofs are in the IND-based model (aka, the so-called Bellare-Pointcheval-Rogaway (BPR) model [10]) for readability. We are optimistic that it is tightly secure in the UC framework and briefly sketch the ideas about how to lift our proofs in the BPR model to the UC framework in our full version [28].

Comparison Using Kyber [32]. There are only a few efficient PAKE protocols from lattices. We focus our comparison on the very efficient one by implementing the CAKE in [8] with Kyber. The reason of not using OCAKE in [8] is because OCAKE do not have PFS, but weak FS. Our protocol is similar to CAKE, but ours has tight reductions from the KEM security.

Unfortunately, by implementing with Kyber, our protocol does not have tight security, since we cannot prove tight PR-CPA security for Kyber, but in practice one will consider using Kyber than otherwise. Our security loss is $O(S \cdot (S+q_D))$ to the Module-LWE assumption, while the security loss of CAKE is $O(q_D\cdot (S+ q_D))$, where $q_D$ is the number of decryption queries to the ideal cipher. In practice, $q_D$ is the number of adversary $\mathcal {A}$ evaluating the symmetric cipher offline and can be large. We assume $q_D=2^{40}$.

Very different to the standard AKE, in the PAKE setting S should be very small, since S corresponds to how many attempts an adversary can perform online dictionary attacks. We usually will limit it. We assume $S \le 100 \approx 2^6$. Hence, although our security bound with Kyber is not tight, it is still much smaller than CAKE, since $S \ll q_D$. In fact, we have doubt on the security proof of CAKE in handling reply attacks³, namely, $\mathcal {A}$ can reply the first round message. To fix it, we need to introduce another multiplicative factor S, but since S is relatively small we ignore it in our comparison.

Hence, implementing with Kyber-768 (corresponding to AES-192), our protocol provides about 152-bit security, while CAKE about 112-bit security.

Open Problem. We are optimistic that our protocol can be proven tightly in the weaker and more efficient randomized half-ideal cipher model [31], and we leave the formal proof for it as an open problem.

2 Preliminaries

For an integer n, we define the notation $[n]{:}{=}\{1,\dots ,n\}$. Let ${\mathcal {X}}$ and ${\mathcal {Y}}$ be two finite sets. The notation $x {\mathop {\leftarrow }\limits ^{{}_\$}}{\mathcal {X}}$ denotes sampling an element x from ${\mathcal {X}}$ uniformly at random.

Let $\mathcal {A}$ be an algorithm. If $\mathcal {A}$ is probabilistic, then $y \leftarrow \mathcal {A}(x)$ means that the variable y is assigned to the output of $\mathcal {A}$ on input x. If $\mathcal {A}$ is deterministic, then we may write $y {:}{=}\mathcal {A}(x)$. We write $\mathcal {A}^{\mathcal {O}}$ to indicate that $\mathcal {A}$ has classical access to oracle $\mathcal {O}$, and $\mathcal {A}^{|\mathcal {O} \rangle }$ to indicate that $\mathcal {A}$ has quantum access to oracle $\mathcal {O}$ All algorithms in this paper are probabilistic polynomial-time (PPT), unless we mention it.

Games. We use code-based games [11] to define and prove security. We implicitly assume that Boolean flags are initialized to false, numerical types are initialized to 0, sets and ordered lists are initialized to $\emptyset$, and strings are initialized to the empty string $\epsilon$. The notation $\Pr [\textbf{G}^\mathcal {A}\Rightarrow 1]$ denotes the probability that the final output $\textbf{G}^{\mathcal {A}}$ of game $\textbf{G}$ running an adversary $\mathcal {A}$ is 1. Let Ev be an (classical) event. We write $\Pr [\texttt {Ev} : \textbf{G}]$ to denote the probability that Ev occurs during the game $\textbf{G}$. In our security notions throughout the paper, we let $N,\mu$ be numbers of users and challenges, respectively, which are assumed to be polynomial in the security parameter $\lambda$. For simplicity, in this paper, we do not write $\lambda$ explicitly. Instead, we assume every algorithm’s input includes $\lambda$.

2.1 Key Encapsulation Mechanism

Definition 1

(Key Encapsulation Mechanism). A KEM $\textsf{KEM}$ consists of four algorithms $(\textsf{Setup}, {\textsf{KG}}, \textsf{Encaps}, \textsf{Decaps})$ and a ciphertext space $\mathcal {C}$, a randomness space $\mathcal {R}$, and a KEM key space $\mathcal {K}$. On input security parameters, $\textsf{Setup}$ outputs a system parameter $\textsf{par}$. ${\textsf{KG}}(\textsf{par})$ outputs a public and secret key pair $(\textsf{pk},\textsf{sk})$. The encapsulation algorithm $\textsf{Encaps}$, on input $\textsf{pk}$, outputs a ciphertext $\textsf{c}\in \mathcal {C}$. We also write $\textsf{c}{:}{=}\textsf{Encaps}(\textsf{pk}; r)$ to indicate the randomness $r\in \mathcal {R}$ explicitly. The decapsulation algorithm $\textsf{Decaps}$, on input $\textsf{sk}$ and a ciphertext $\textsf{c}$, outputs a KEM key $\textsf{k}\in \mathcal {K}$ or a rejection symbol $\bot \notin \mathcal {K}$. Here $\textsf{Encaps}$ and $\textsf{Decaps}$ also take $\textsf{par}$ as input, but for simplicity, we do not write explicitly.

Definition 2

(KEM Correctness). Let $\textsf{KEM}{:}{=}(\textsf{Setup}, {\textsf{KG}}, \textsf{Encaps}, \textsf{Decaps})$ be a KEM scheme and $\mathcal {A}$ be an adversary against $\textsf{KEM}$. We say $\textsf{KEM}$ is $(1 - \delta )$-correct if

$$\begin{aligned} {\Pr \left[ { (\textsf{c}, \textsf{k}) \leftarrow \textsf{Encaps}(\textsf{pk}) \wedge \textsf{k}\ne \textsf{Decaps}(\textsf{sk}, \textsf{c})}\right] } \le \delta , \end{aligned}$$

where $\textsf{par}\leftarrow \textsf{Setup}, (\textsf{pk},\textsf{sk}) \leftarrow {\textsf{KG}}(\textsf{par})$.

Definition 3

(Implicit Rejection [14]). A KEM scheme $\textsf{KEM}= (\textsf{Setup}, {\textsf{KG}}, \textsf{Encaps}, \textsf{Decaps})$ has implicit rejection if $\textsf{Decaps}(\textsf{sk},\cdot )$ behaves as a pseudorandom function when the input ciphertext is invalid, where $\textsf{par}\leftarrow \textsf{Setup}, (\textsf{pk}, \textsf{sk}) \leftarrow {\textsf{KG}}$, and $\textsf{sk}$ is the key of the pseudorandom function. That is, if an input ciphertext $\textsf{c}$ is invalid, then $\textsf{Decaps}(\textsf{sk}, \textsf{c})$ will output a pseudorandom key $\textsf{k}$ instead of a rejection symbol $\bot$. A concrete example is shown in Fig. 18.

Fig. 2.

Security games $\textsf{OW}\text {-}\textsf{PCA}$ and $\textsf{OW}\text {-}\textsf{rPCA}$ for KEM scheme $\textsf{KEM}$.

$\textsf{OW}\text {-}\textsf{PCA}$ Security. Let $\textsf{KEM}= (\textsf{Setup}, {\textsf{KG}}, \textsf{Encaps}, \textsf{Decaps})$ be a KEM scheme with ciphertext space $\mathcal {C}$. In Definitions 4 and 5, we define two variants of one-wayness under plaintext-checking attacks ($\mathsf {OW\text {-} PCA}$) security for $\textsf{KEM}$ [27] in the multi-user, multi-challenge setting. They will be used for the tight security proof of our PAKE protocol and can be instantiated tightly from the Diffie-Hellman assumption and Learning-With-Errors assumption. Instead of writing ‘m’ in the abbreviation, we mention the explicit numbers of users and challenge ciphertexts as $N$ and $\mu$ in the abbreviation of security.

Definition 4

(Multi-user-challenge OW-PCA security). Let $N$ and $\mu$ be the numbers of users and challenge ciphertexts per user, respectively. Let $\mathcal {A}$ be an adversary against $\textsf{KEM}$. We define the $(N, \mu )$-$\text {OW}\text {-}\text {PCA}$ advantage function of $\mathcal {A}$ against $\textsf{KEM}$

$$\begin{aligned} \textsf{Adv}^{(N, \mu )\text {-}\textsf{OW}\text {-}\textsf{PCA}}_{\textsf{KEM}}(\mathcal {A}) {:}{=}\Pr \left[ \textsf{OW}\text {-}\textsf{PCA}^{(N, \mu ), \mathcal {A}}_{\textsf{KEM}} \Rightarrow 1 \right] , \end{aligned}$$

where the game $\textsf{OW}\text {-}\textsf{PCA}^{(N, \mu ), \mathcal {A}}_{\textsf{KEM}}$ is defined in Fig. 2. We say $\textsf{KEM}$ is $\text {OW}\text {-}\text {PCA}$ secure if $\textsf{Adv}^{(N,\mu )\text {-}\textsf{OW}\text {-}\textsf{PCA}}_{\textsf{KEM}}(\mathcal {A})$ is negligible for any $\mathcal {A}$.

Definition 5

(OW-PCA security under random ciphertexts). Let $N$ and $\mu$ be the number of users and the number of challenge ciphertexts per user, respectively. Let $\mathcal {A}$ be an adversary against $\textsf{KEM}$. We define the $(N, \mu )$-$\text {OW}\text {-}\text {rPCA}$ advantage function of $\mathcal {A}$

$$\begin{aligned} \textsf{Adv}^{(N, \mu )\text {-}\textsf{OW}\text {-}\textsf{rPCA}}_{\textsf{KEM}}(\mathcal {A}) {:}{=}\Pr \left[ \textsf{OW}\text {-}\textsf{rPCA}^{(N, \mu ), \mathcal {A}}_{\textsf{KEM}} \Rightarrow 1 \right] , \end{aligned}$$

where $\textsf{OW}\text {-}\textsf{rPCA}^{(N, \mu ), \mathcal {A}}_{\textsf{KEM}}$ is defined in Fig. 2. $\textsf{KEM}$ is $\text {OW}\text {-}\text {rPCA}$ secure if $\textsf{Adv}^{(N, \mu )\text {-}\textsf{OW}\text {-}\textsf{rPCA}}_{\textsf{KEM}}(\mathcal {A})$ is negligible for any $\mathcal {A}$.

Fig. 3.

Security games $\textsf{FUZZY}$ and $\textsf{ANO}\text {-}\textsf{PCA}$ for KEM scheme $\textsf{KEM}$. The $\textsc {Pco}$ oracle of $\textsf{ANO}\text {-}\textsf{PCA}$ is the same as the one of $\textsf{OW}\text {-}\textsf{PCA}$ (and $\textsf{OW}\text {-}\textsf{rPCA}$) in Fig. 2.

Definition 6

(Fuzzy public keys). Let $N$ be the number of users. Let $\mathcal {A}$ be an adversary against $\textsf{KEM}$. We define the advantage function of $\mathcal {A}$ against the fuzzyness of $\textsf{KEM}$

$$\begin{aligned} \textsf{Adv}^{N\text {-}\textsf{FUZZY}}_{\textsf{KEM}}(\mathcal {A}) {:}{=}\left| \Pr \left[ \textsf{FUZZY}^{N, \mathcal {A}}_{\textsf{KEM}, 0} \Rightarrow 1 \right] - \Pr \left[ \textsf{FUZZY}^{N, \mathcal {A}}_{\textsf{KEM}, 1} \Rightarrow 1 \right] \right| , \end{aligned}$$

where the game $\textsf{FUZZY}^{N, \mathcal {A}}_{\textsf{KEM}, b} (b \in \{0,1\})$ is defined in Fig. 3. We say $\textsf{KEM}$ has fuzzy public keys if $\textsf{Adv}^{N\text {-}\textsf{FUZZY}}_{\textsf{KEM}}(\mathcal {A})$ is negligible for any $\mathcal {A}$.

Definition 7

(Anonymous ciphertexts under PCA attacks). Let $N$ and $\mu$ be the numbers of users and challenge ciphertexts per user, respectively. Let $\mathcal {A}$ be an adversary against $\textsf{KEM}$. We define the advantage function of $\mathcal {A}$ against the ciphertext anonymity (under PCA attacks) of $\textsf{KEM}$

$$\begin{aligned} \textsf{Adv}^{(N,\mu )\text {-}{\textsf{ANO}}}_{\textsf{KEM}}(\mathcal {A}) {:}{=}\left| \Pr \left[ \textsf{ANO}\text {-}\textsf{PCA}^{(N,\mu ), \mathcal {A}}_{\textsf{KEM}, 0} \Rightarrow 1 \right] - \Pr \left[ \textsf{ANO}\text {-}\textsf{PCA}^{(N,\mu ), \mathcal {A}}_{\textsf{KEM}, 1} \Rightarrow 1 \right] \right| , \end{aligned}$$

where the game $\textsf{ANO}\text {-}\textsf{PCA}^{(N, \mu ), \mathcal {A}}_{\textsf{KEM}, b} (b \in \{0,1\})$ is defined in Fig. 3. We say $\textsf{KEM}$ has anonymous ciphertexts under PCA attacks (or simply, anonymous ciphertexts) if $\textsf{Adv}^{(N, \mu )\text {-}{\textsf{ANO}}}_{\textsf{KEM}}(\mathcal {A})$ is negligible for any $\mathcal {A}$.

It is easy to see that if $\textsf{KEM}$ is $\text {OW}\text {-}\text {PCA}$ secure and has anonymous ciphertexts under PCA attacks, then it is also $\text {OW}\text {-}\text {rPCA}$ secure, as stated in Lemma 1

Lemma 1

($\textsf{OW}\text {-}\textsf{PCA}+ \textsf{ANO}\text {-}\textsf{PCA}\Rightarrow \textsf{OW}\text {-}\textsf{rPCA}$). Let $N$ and $\mu$ be the numbers of users and challenge ciphertexts per user, respectively. Let $\mathcal {A}$ be an adversary against $\textsf{KEM}$. We have

$$\begin{aligned} \textsf{Adv}^{(N, \mu )\text {-}\textsf{OW}\text {-}\textsf{rPCA}}_{\textsf{KEM}}(\mathcal {A}) \le \textsf{Adv}^{(N, \mu )\text {-}\textsf{OW}\text {-}\textsf{PCA}}_{\textsf{KEM}}(\mathcal {A}) + \textsf{Adv}^{(N,\mu )\text {-}{\textsf{ANO}}}_{\textsf{KEM}}(\mathcal {A}) \end{aligned}$$

2.2 Public-Key Encryption

Public-Key Encryption. A PKE scheme $\textsf{PKE}$ consists of four algorithms $(\textsf{Setup}, {\textsf{KG}}, \textsf{Enc}, \textsf{Dec})$ and a message space $\mathcal {M}$, a randomness space $\mathcal {R}$, and a ciphertext space $\mathcal {C}$. $\textsf{Setup}$ outputs a system parameter $\textsf{par}$. ${\textsf{KG}}(\textsf{par})$ outputs a public and secret key pair $(\textsf{pk},\textsf{sk})$. The encryption algorithm $\textsf{Enc}$, on input $\textsf{pk}$ and a message $m\in \mathcal {M}$, outputs a ciphertext $\textsf{c}\in \mathcal {C}$. We also write $\textsf{c}:= \textsf{Enc}(\textsf{pk}, m; r)$ to indicate the randomness $r\in \mathcal {R}$ explicitly. The decryption algorithm $\textsf{Dec}$, on input $\textsf{sk}$ and a ciphertext $\textsf{c}$, outputs a message $m' \in \mathcal {M}$ or a rejection symbol $\bot \notin \mathcal {M}$.

Definition 8

(PKE Correctness). Let $\textsf{PKE}:= (\textsf{Setup}, {\textsf{KG}}, \textsf{Enc}, \textsf{Dec})$ be a PKE scheme with message space $\mathcal {M}$ and $\mathcal {A}$ be an adversary against $\textsf{PKE}$. The $\textsf{COR}$ advantage of $\mathcal {A}$ is defined as

$$ {\textsf{Adv}}^{\textsf{COR}}_{\textsf{PKE}}(\mathcal {A}) := \Pr \left[ \textsf{COR}^{\mathcal {A}}_{\textsf{PKE}} \Rightarrow 1 \right] , $$

where the COR game is defined in Fig. 4. If there exists a constant $\delta$ such that for all adversary $\mathcal {A}$, ${\textsf{Adv}}^{\textsf{COR}}_{\textsf{PKE}}(\mathcal {A}) \le \delta$, then we say $\textsf{PKE}$ is $(1-\delta )$-correct.

Fig. 4.

The $\textsf{COR}$ game for a PKE scheme $\textsf{PKE}$ and $\mathcal {A}$. $\mathcal {A}$ might have access to some oracle $O$ (e.g., random oracles). It depends on the specific reduction.

We define fuzzyness for PKE, which is essentially the same as the one for KEM (cf. Definition 6).

Definition 9

(Fuzzy public key). Let $N$ be the number of users. We say $\textsf{PKE}$ has fuzzy public keys if for any $\mathcal {A}$, the advantage function of $\mathcal {A}$ against the fuzzyness of $\textsf{PKE}$

$$\begin{aligned} \textsf{Adv}^{N\text {-}\textsf{FUZZY}}_{\textsf{PKE}}(\mathcal {A}) {:}{=}\left| \Pr \left[ \textsf{FUZZY}^{N, \mathcal {A}}_{\textsf{PKE}, 0} \Rightarrow 1 \right] - \Pr \left[ \textsf{FUZZY}^{N, \mathcal {A}}_{\textsf{PKE}, 1} \Rightarrow 1 \right] \right| \end{aligned}$$

is negligible. The game $\textsf{FUZZY}^{N, \mathcal {A}}_{\textsf{PKE}, b} (b \in \{0,1\})$ is defined in Fig. 3.

Pseudorandom ciphertext. Let $\textsf{PKE}:= ({\textsf{KG}}, \textsf{Enc}, \textsf{Dec})$ be a public-key encryption scheme with message space $\mathcal {M}$ and ciphertext space $\mathcal {C}$. We define $\text {PR}\text {-}\text {CPA}$ (multi-challenge pseudorandomness under chosen-plaintext attacks) security in Fig. 5.

Definition 10

(Multi-user-challange PR-CPA security). Let $N$ and $\mu$ be the numbers of users and challenge ciphertexts per user. Let $\mathcal {A}= (\mathcal {A}_0, \mathcal {A}_1)$ be an adversary against $\textsf{PKE}$. Consider the games ${\textsf{PR}\text{- }\textsf{CPA}}^{(N, \mu ), \mathcal {A}}_{\textsf{PKE},b}$ $(b \in \{0,1\})$ defined in Fig. 5. We define the $(N, \mu )$-$\text {PR}\text {-}\text {CPA}$ advantage function

$$\begin{aligned} \textsf{Adv}^{(N, \mu )\text {-}\textsf{PR}\text{- }\textsf{CPA}}_{\textsf{PKE}}(\mathcal {A}) := \left| \Pr \left[ {\textsf{PR}\text{- }\textsf{CPA}}^{(N, \mu ), \mathcal {A}}_{\textsf{PKE},0} \Rightarrow 1 \right] - \Pr \left[ {\textsf{PR}\text{- }\textsf{CPA}}^{(N, \mu ), \mathcal {A}}_{\textsf{PKE},1} \Rightarrow 1 \right] \right| . \end{aligned}$$

$\textsf{PKE}$ is $\text {PR}\text {-}\text {CPA}$ secure if $\textsf{Adv}^{(N, \mu )\text {-}\textsf{PR}\text{- }\textsf{CPA}}_{\textsf{PKE}}(\mathcal {A})$ is negligible for any $\mathcal {A}$.

Fig. 5.

Security game $\textsf{PR}\text{- }\textsf{CPA}$ for PKE scheme $\textsf{PKE}$.

3 Password-Based Authenticated Key Exchange

3.1 Definition of PAKE

A two-message PAKE protocol $\textsf{PAKE}:= (\textsf{Setup}, \textsf{Init}, \textsf{Resp}, \textsf{TerInit})$ consists of four algorithms. The setup algorithm $\textsf{Setup}$, on input security parameter $1^\lambda$, outputs global PAKE protocol parameters $\textsf{par}$. For simplicity, we ignore the input of $\textsf{Setup}$ and write $\textsf{par}\leftarrow \textsf{Setup}$.

Let $\textsf{U}$ be a user, $\textsf{S}$ be a server, and $\textsf{pw}$ be the password shared between $\textsf{U}$ and $\textsf{S}$. Since we consider the client-server setting, to initiate a session, $\textsf{U}$ will send the first protocol message. $\textsf{U}$ runs the client’s initialization algorithm $\textsf{Init}$, which takes the identities $\textsf{U}, \textsf{S}$ and password $\textsf{pw}$ as inputs and outputs a client message $\textsf{M}_\textsf{U}$ and session state $\textsf{st}$, and then $\textsf{U}$ sends $\textsf{M}_\textsf{U}$ to $\textsf{S}$. On receiving $\textsf{M}_\textsf{U}$, $\textsf{S}$ runs the server’s derivation algorithm $\textsf{Resp}$, which takes identities $\textsf{U}$ and $\textsf{S}$ and the received message $\textsf{M}_\textsf{U}$ as input, together with the password $\textsf{pw}$, to generate a server message $\textsf{M}_\textsf{S}$ and a session key $\textsf{SK}_\textsf{S}$. $\textsf{S}$ sends $\textsf{M}_\textsf{S}$ to $\textsf{U}$. Finally, on receiving $\textsf{M}_\textsf{S}$, $\textsf{U}$ runs the client’s derivation algorithm $\textsf{TerInit}$ which inputs $\textsf{U}, \textsf{S},$ the session state $\textsf{st}$ generated before, the received message $\textsf{M}_\textsf{S}$, and password $\textsf{pw}$, to generate a session key $\textsf{sk}'_\textsf{U}$. In two-message PAKE protocols, the server does not need to save session state since it can compute the session key right after receiving the user’s message.

Fig. 6.

Illustration for a two-message PAKE protocol execution between a user $\textsf{U}$ and a server $\textsf{S}$.

We define the correctness of PAKE protocols, stating that an honestly execution between user $\textsf{U}$ and server $\textsf{S}$ (with the same password $\textsf{pw}_{\textsf{U}, \textsf{S}}$) as in Fig. 6 will produce the same session key $\textsf{SK}_\textsf{U}= \textsf{SK}_\textsf{S}$.

Definition 11

(PAKE Correctness). Let $\textsf{PAKE}:= (\textsf{Setup}, \textsf{Init}, \textsf{Resp}, \textsf{TerInit})$ be a PAKE protocol and let $\textsf{U}$ and $\textsf{S}$ be a user-server pair with password $\textsf{pw}$. We say $\textsf{PAKE}$ is $\rho$-correct, if for any PAKE system parameter $\textsf{par}\leftarrow \textsf{Setup}$, the following probability is at least $\rho$.

3.2 Security Model of PAKE

We consider indistinguishability(IND)-based security of PAKE protocols. In this section, we define the multi-$\texttt{test}$ variant of the Bellare-Pointcheval-Rogaway model [1, 5, 10]. We simply denoted it as the $\textsf{BPR}$ model.

In the $\textsf{BPR}$ model, we consider a name space of users $\mathcal {U}$ and a name space of servers $\mathcal {S}$, which are assumed to be disjoint. Oracles provided in this model rejects queries inconsistent withe these name spaces.

We denote the session key space by $\mathcal{S}\mathcal{K}$. Password are bit strings of $\ell$ and the password space is defined as $\mathcal{P}\mathcal{W}\subsetneq \{0,1\}^\ell$. Each pair of user and server $\textsf{U}\times \textsf{S}\in \mathcal {U}\times \mathcal {S}$ holds a shared password $\textsf{pw}_{\textsf{U}, \textsf{S}} \in \mathcal{P}\mathcal{W}$.

Let $\textsf{P}$ denotes a party (either a user or server). Each party in $\mathcal {U}\cup \mathcal {S}$ has multiple instances $\pi ^i_\textsf{P}$ (i is some index) and each instance has its internal state. The state of an instance $\pi ^i_\textsf{P}$ is a tuple $(\texttt{e}, \texttt{tr}, \texttt{key}, \texttt{acc})$ where

• $\texttt{e}$ is the ephemeral secret chosen by $\textsf{P}$.

• $\texttt{tr}$ is the trace of the instance, i.e., the names of user and server involved in the instance and the messages sent and received by $\textsf{P}$ in the instance.

• $\texttt{key}$ is the accepted session key of $\pi ^i_\textsf{P}$.

• $\texttt{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, $\texttt{acc}= \bot$ (which means undefined).

• $\texttt{test}$ is a Boolean flag that indicates whether the instance has been queried to the $\textsc {Test}$ oracle (which will be defined later).

To access individual components of the state, we write $\pi ^i_\textsf{P}.(\texttt{e}, \texttt{tr}, \texttt{key}, \texttt{acc})$. We define partnership via matching instance trace.

Definition 12

(Partnering). A user instance $\pi ^{t_0}_\textsf{U}$ and a server instance $\pi ^{t_1}_\textsf{S}$ are partnered if and only if

$$\begin{aligned} \pi ^{t_0}_\textsf{U}.\texttt{acc}= \textbf{true}= \pi ^{t_1}_\textsf{S}.\texttt{acc}\quad \textbf{and} \quad \pi ^{t_0}_\textsf{U}.\texttt{tr}= \pi ^{t_1}_\textsf{S}.\texttt{tr}\end{aligned}$$

Two user instances are never partnered, neither are two server instances. We define a partnership predicate $\textsf{Partner}(\pi ^{t_0}_\textsf{U}, \pi ^{t_1}_\textsf{S})$ which outputs $\textbf{true}$ if and only if $\pi ^{t_0}_\textsf{U}$ and $\pi ^{t_1}_\textsf{S}$ are partnered.

Security Game. The security game is played with an adversary $\mathcal {A}$. The experiment draws a random challenge bit $\beta \leftarrow \{0,1\}$, generates the public parameters, and outputs the public parameters to $\mathcal {A}$. $\mathcal {A}$ is allowed to query the following oracles:

• $\textsc {Execute}(\textsf{U}, t_1, \textsf{S}, t_2)$: This oracle outputs the protocol messages of an honest protocol execution between instances $\pi ^{t_1}_\textsf{U}$ and $\pi ^{t_2}_\textsf{S}$. By querying this oracle, the adversary launches passive attacks.

• $\textsc {SendInit}, \textsc {SendResp}, \textsc {SendTerInit}$: These oracles model active attacks. By querying these oracles, the adversary sends protocol messages to protocol instances. For sake of simplicity, we assume that the adversary does not use these oracles to launch passive attacks (which are already captured by the $\textsc {Execute}$ oracle).

• $\textsc {Reveal}(\textsf{P}, t)$: By this oracle, the adversary reveals the session key of $\pi ^t_\textsf{P}$.

• $\textsc {Test}(\textsf{P}, t)$: If $\pi ^t_\textsf{P}$ is fresh (which will be defined later), then, depending on the challenge bit $\beta$, the oracle outputs either the session key of $\pi ^t_\textsf{P}$ or a uniformly random key. Otherwise, the oracle outputs $\bot$. After this query, the flag $\pi ^t_\textsf{P}.\texttt{test}$ will be set as $\textbf{true}$.

We denote the game by $\textsf{BPR}_{\textsf{PAKE}}$. The pseudocode is given in $\textbf{G}_0$ in Fig. 8, instantiated with our PAKE protocol. Before defining PAKE security, we define freshness to avoid trivial attacks in this model.

Definition 13

(Freshness). An instance $\pi ^t_\textsf{P}$ is fresh if and only if

• 1. $\pi ^t_\textsf{P}$ is accepted.

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

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

  • (a) $\pi ^t_\textsf{P}$ accepted during a query to $\textsc {Execute}$.

  • (b) There exists more than one (not necessarily fresh) partner instance⁴.

  • (c) A unique fresh partner instance exists.

  • (d) No partner instance exists and the password of $\textsf{P}$ was not corrupted prior to $\pi ^t_\textsf{P}$ is accepted.

By these definitions, we are ready to define the security of PAKE protocols.

Definition 14

(Security of PAKE). Let $\textsf{PAKE}$ be a PAKE protocol and $\mathcal {A}$ be an adversary. The advantage of $\mathcal {A}$ against $\textsf{PAKE}$ is defined as

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

A PAKE protocol is considered secure if the best the adversary can do is to perform an online dictionary attack. Concretely, $\textsf{PAKE}$ is secure if for any adversary $\mathcal {A}$, $\textsf{Adv}^{\textsf{BPR}}_{\textsf{PAKE}}(\mathcal {A})$ is negligibly close to $\frac{S}{|\mathcal{P}\mathcal{W}|}$ when passwords in the security game are drawn independently and uniformly from $\mathcal{P}\mathcal{W}$. Here $S$ is the number of send queries made by $\mathcal {A}$ (i.e., the number of sessions during the game $\textsf{BPR}_{\textsf{PAKE}}$).

4 Our Generic Construction of PAKE

Construction. Let $\textsf{KEM}= (\textsf{Setup}, \textsf{KG}, \textsf{Encaps}, \textsf{Decaps})$ be a KEM scheme with public key space $\mathcal{P}\mathcal{K}$, ciphertext space $\mathcal {C}$, and KEM key space $\mathcal {K}$. We also require $\textsf{KEM}$ to have implicit rejection. Let $\textsf{IC}_1= (\textsf{E}_1, \textsf{D}_1)$ be a symmetric encryption with key space $\mathcal{P}\mathcal{W}$, plaintext space $\mathcal{P}\mathcal{K}$, and ciphertext space $\mathcal {E}_1$. Let $\textsf{IC}_2= (\textsf{E}_2, \textsf{D}_2)$ be a symmetric encryption with key space $\mathcal{P}\mathcal{W}$, plaintext space $\mathcal {C}$, and ciphertext space $\mathcal {E}_2$.

Fig. 7.

Our PAKE protocol $\varPi$.

We construct our two-message PAKE protocol $\varPi = (\textsf{Init}, \textsf{Resp}, \textsf{TerInit})$ as shown in Fig. 6, where $\mathcal{S}\mathcal{K}$ is the session key space of $\textsf{PAKE}$ and $\textsf{H}:\{0,1\}^* \rightarrow \mathcal{S}\mathcal{K}$ is a hash function which is used to derive the session key. The system parameter $\textsf{par}$ is generated by $\textsf{par}\leftarrow \textsf{Setup}$.

The correctness of $\varPi$ is dependent on $\textsf{KEM}$. In Fig. 7, one honest execution of $\varPi$ includes one $\textsf{KEM}$ encapsulation and decapsulation. So, if $\textsf{KEM}$ is $(1-\delta )$-correct, then $\varPi$ is also $(1-\delta )$-correct.

Theorem 1

Let $\textsf{H}$ be random oracle and $\textsf{IC}_1$ and $\textsf{IC}_2$ be ideal ciphers. If $\textsf{KEM}$ is $(1-\delta )$-correct and has implicit rejection, fuzzy public keys, anonymous ciphertexts, $\text {OW}\text {-}\text {PCA}$ security, and $\textsf{OW}\text {-}\textsf{rPCA}$ security (cf. Definitions 4 to 7), then the PAKE protocol $\varPi$ in Fig. 7 is secure (wrt Definition 14).

Concretely, for any $\mathcal {A}$ against $\varPi$, there are adversaries $\mathcal {B}_{1}$-$\mathcal {B}_{6}$ with $\textbf{T}(\mathcal {A}) \approx \textbf{T}(\mathcal {B}_i) (1 \le i \le 6)$ and

$$\begin{aligned} \textsf{Adv}^{\textsf{BPR}}_{\varPi }(\mathcal {A}) & \le \ S/ |\mathcal{P}\mathcal{W}| + \textsf{Adv}^{q_1\text {-}\textsf{FUZZY}}_{\textsf{KEM}}(\mathcal {B}_1) + \textsf{Adv}^{(S, q_2+ S)\text {-}\textsf{OW}\text {-}\textsf{rPCA}}_{\textsf{KEM}}(\mathcal {B}_4) \\ & + \textsf{Adv}^{(S,1)\text {-}\textsf{OW}\text {-}\textsf{PCA}}_{\textsf{KEM}}(\mathcal {B}_2) + \textsf{Adv}^{(S+ q_2, S)\text {-}\textsf{OW}\text {-}\textsf{PCA}}_{\textsf{KEM}}(\mathcal {B}_5) \\ &+ \textsf{Adv}^{(S, 1)\text {-}{\textsf{ANO}}}_{\textsf{KEM}}(\mathcal {B}_3) + \textsf{Adv}^{(S+ q_1, S)\text {-}{\textsf{ANO}}}_{\textsf{KEM}}(\mathcal {B}_6) + S\cdot \delta \\ & + S^2 (\eta _{pk} + \eta _{ct} ) + \frac{(q_1^2 + S^2)}{|\mathcal {E}_1|} + \frac{(q_2^2 + S^2)}{|\mathcal {E}_2|} + \frac{q_1^2 }{|\mathcal{P}\mathcal{K}|} + \frac{q_2^2}{|\mathcal {C}|} + \frac{(q_{\textsf{H}}^2 + S^2)}{|\mathcal{S}\mathcal{K}|}, \end{aligned}$$

where $q_1, q_2, q_{\textsf{H}}$ are the numbers of $\mathcal {A}$ queries to $\textsf{IC}_1, \textsf{IC}_2,$ and $\textsf{H}$ respectively. $S$ is the number of sessions $\mathcal {A}$ established in the security game. $\eta _{pk}$ and $\eta _{ct}$ are the collision probabilities of $\textsf{KG}$ and $\textsf{Encaps}$, respectively.

Remark 1 (Implementation of Ideal Ciphers)

The implementation of $\textsf{IC}_1$ and $\textsf{IC}_2$ depends on the concrete instantiation of the underlying KEM scheme $\textsf{KEM}$. Beguinet et al. provides an implementation if $\textsf{KEM}$ is instantiated with the Kyber KEM [32] in [8, Section 5.2]. More implementation for group-based schemes and lattice-based schemes can be found in [31].

Remark 2

We require $\textsf{KEM}$ to have implicit rejection (cf. Definition 3) because this simplifies our security proof. More concretely, if the underlying KEM $\textsf{KEM}$ has implicit rejection, then we only require $\text {OW}\text {-}\text {PCA}$ security to finish our tight proof. Otherwise, we need the OW-PCVA (cf. [21, Definition 2.1]) security to detect whether the $\textsf{c}$ is valid in the proof.

4.1 Proof of Theorem 1

Let $\mathcal {A}$ be an adversary against $\textsf{PAKE}$ in the $\textsf{BPR}$ game, where $N$ is the number of parties. Every user-server pair $(\textsf{U}, \textsf{S}) \in \mathcal {U}\times \mathcal {S}$ is associated with a password $\textsf{pw}_{\textsf{U}, \textsf{S}}$. The game sequences $\textbf{G}_{0}$-$\textbf{G}_{12}$ of the proof are given in Figs. 8, 9, 11, 14.

Fig. 8.

Games in proving Theorem 1. $\mathcal {A}$ has access to the set of PAKE oracles $\{\textsc {Execute},\textsc {SendInit},\textsc {SendResp}, \textsc {SendTerInit}, \textsc {Corrupt}, \textsc {Reveal}, \textsc {Test}\}$, random oracle $\textsf{H}$, and ideal ciphers $\textsf{IC}_1= (\textsf{E}_1, \textsf{D}_1)$ and $\textsf{IC}_2= (\textsf{E}_2, \textsf{D}_2)$.

During the game sequences in this proof, we exclude the collisions of outputs of $\textsf{KG}$ and $\textsf{Encaps}$ in $\textsc {Execute}, \textsc {SendInit}, \textsc {SendResp},$ and $\textsc {SendTerInit}$. We also exclude the collisions of outputs of ideal ciphers and random oracle, i.e., $\textsf{IC}_1= (\textsf{E}_1, \textsf{D}_1)$, $\textsf{IC}_2= (\textsf{E}_2, \textsf{D}_2)$, and $\textsf{H}$. If such a collision happens at any time, then we abort the game. For readability, we do not explicitly define such collision events in the codes of games sequences.

By the assumption of Theorem 1, the collision probabilities of the outputs of $\textsf{KG}$ and $\textsf{Encaps}$ are $\eta _{pk}$ and $\eta _{ct}$, and $S$ is the number of sessions generated (i.e., the total number of queries to $\textsc {Execute}, \textsc {SendInit}, \textsc {SendResp},$ and $\textsc {SendTerInit}$) during the game and $q_1$, $q_2$, and $q_{\textsf{H}}$ are the numbers of queries to $\textsf{IC}_1$, $\textsf{IC}_2$, and $\textsf{H}$, respectively. By birthday bounds and union bounds, such collision events happen within probability $S^2 (\eta _{pk} + \eta _{ct} ) + \frac{(q_1^2 + S^2)}{|\mathcal {E}_1|} + \frac{(q_2^2 + S^2)}{|\mathcal {E}_2|} + \frac{q_1^2 }{|\mathcal{P}\mathcal{K}|} + \frac{q_2^2}{|\mathcal {C}|} + \frac{(q_{\textsf{H}}^2 + S^2)}{|\mathcal{S}\mathcal{K}|}$. Game $\textbf{G}_0$ is the same as $\textsf{BPR}_{\textsf{PAKE}}$ except that we define such collision events in $\textbf{G}_0$, we have

$$\begin{aligned} &\left| \Pr \left[ \textsf{BPR}_{\textsf{PAKE}}^\mathcal {A}\Rightarrow 1 \right] - {\Pr \left[ {\textbf{G}^\mathcal {A}_0 \Rightarrow 1}\right] } \right| \\ {} &\le S^2 (\eta _{pk} + \eta _{ct} ) + \frac{(q_1^2 + S^2)}{|\mathcal {E}_1|} + \frac{(q_2^2 + S^2)}{|\mathcal {E}_2|} + \frac{q_1^2 }{|\mathcal{P}\mathcal{K}|} + \frac{q_2^2}{|\mathcal {C}|} + \frac{(q_{\textsf{H}}^2 + S^2)}{|\mathcal{S}\mathcal{K}|} \end{aligned}$$

Moreover, excluding these collisions imply that different instances have different traces and each instance (user’s or server’s) has at most one partnering instance. By the construction of $\textsf{PAKE}$, different instances will have different session keys, since the hash function $\textsf{H}$ take the trace of instance as input.

  . Instead of using the $\textsf{Freshness}$ procedure in the $\textsc {Test}$ oracle, we assign an additional variable $\texttt{fr}$ to each instance $\pi$ to explicitly indicate the freshness of $\pi$. Whenever $\mathcal {A}$ issues an oracle query related to $\pi$, we will update $\pi .\texttt{fr}$ in real time according to the freshness definition (cf. Definition 13). This change is conceptual, so we have

$$\begin{aligned} {\Pr \left[ {\textbf{G}^\mathcal {A}_0 \Rightarrow 1}\right] } = {\Pr \left[ {\textbf{G}^\mathcal {A}_1 \Rightarrow 1}\right] } \end{aligned}$$

To save space, for games $\textbf{G}_2$ to $\textbf{G}_x$, instead of presenting the whole codes of the game, we only present the codes of changed oracles.

Fig. 9.

Oracles $\textsc {Execute}$ and $\textsf{D}_1$ in the games sequence $\textbf{G}_1$-$\textbf{G}_5$.

  . We change the output of $\textsf{D}_1$. When $\mathcal {A}$ queries $\textsf{D}_1(\textsf{pw}, e_1)$ where $e_1$ is not generated from $\textsf{E}_1(\textsf{pw}, \cdot )$, we generate $\textsf{pk}$ via $(\textsf{pk}, \textsf{sk}) \leftarrow \textsf{KG}$ instead of $\textsf{pk}{\mathop {\leftarrow }\limits ^{{}_\$}}\mathcal{P}\mathcal{K}$. Such $(\textsf{pk}, \textsf{sk})$ is recorded in $\mathcal {L}_{\textsf{key}}$. cf. Lines 20 ro 22.

The difference between $\textbf{G}_1$ and $\textbf{G}_2$ can be bounded by using the fuzzyness of $\textsf{KEM}$. The bound is given in Lemma 2. For readability, we continue the proof of Lemma 1 and postpone the proof of Lemma 2 to our full version [28].

Lemma 2

With notations and assumptions from $\textbf{G}_1$ and $\textbf{G}_2$ in the proof of Theorem 1, there is an adversary $\mathcal {B}_{1}$ with $\textbf{T}(\mathcal {B}_1) \approx \textbf{T}(\mathcal {A})$ and

$$\begin{aligned} \left| {\Pr \left[ {\textbf{G}^\mathcal {A}_1 \Rightarrow 1}\right] } - {\Pr \left[ {\textbf{G}^\mathcal {A}_2 \Rightarrow 1}\right] } \right| \le \textsf{Adv}^{q_1\text {-}\textsf{FUZZY}}_{\textsf{KEM}}(\mathcal {B}_1) \end{aligned}$$

After this change, all $\textsf{pk}$ generated by querying $\textsf{D}_1$ (i.e., there exists $(\textsf{pw}, e_1)$ s.t. $(\textsf{pw}, \textsf{pk}, e_1, \text {dec}) \in \mathcal {L}_1$) will always have a secret key $\textsf{sk}$ such that $(\textsf{pk}, \textsf{sk}) \in \mathcal {L}_{\textsf{key}}$. This fact is crucial for our later simulation.

  . In this game, session keys of instances generated in $\textsc {Execute}$ are all uniformly at random and independent of $\textsf{H}$ (cf. Lines 10 to 11).

Let $\textsf{Query}_{\text {exec}}$ be the event that $\mathcal {A}$ queries the hash input of the session key of an instance generated in $\textsc {Execute}$. Since $\textsf{H}$ is a random oracle, if $\textsf{Query}_{\text {exec}}$ does not happen, then $\mathcal {A}$ cannot detect the modification made in $\textbf{G}_3$. We have

$$\begin{aligned} \left| {\Pr \left[ {\textbf{G}^\mathcal {A}_2 \Rightarrow 1}\right] } - {\Pr \left[ {\textbf{G}^\mathcal {A}_3 \Rightarrow 1}\right] } \right| \le {\Pr \left[ {\textsf{Query}_{\text {exec}}}\right] } \end{aligned}$$

We construct an adversary $\mathcal {B}_2$ against the $\textsf{OW}\text {-}\textsf{PCA}$ security of $\textsf{KEM}$ in Fig. 10 such that $\textbf{T}(\mathcal {B}_2) \approx \textbf{T}(\mathcal {A})$ and ${\Pr \left[ {\textsf{Query}_{\text {exec}}}\right] } \le \textsf{Adv}^{(S,1)\text {-}\textsf{OW}\text {-}\textsf{PCA}}_{\textsf{KEM}}(\mathcal {B}_2)$. Concretely, $\mathcal {B}_2$ inputs a $\textsf{OW}\text {-}\textsf{PCA}$ challenge $(\textsf{par}, \textbf{pk}, \textbf{c})$ and has access to a plaintext checking oracle $\textsc {Pco}$. Since $\mathcal {A}$’s number of queries to $\textsc {Execute}$ is $S$ and there is only one KEM ciphertext generated per query to $\textsc {Execute}$, we need at most $S$ challenge public keys and one challenge ciphertexts per public key.

Fig. 10.

Reduction $\mathcal {B}_2$ in bounding the probability difference between $\textbf{G}_2$ and $\textbf{G}_3$. Highlighted parts show how $\mathcal {B}_2$ uses $\textsc {Pco}$ and challenge input to simulate $\textbf{G}_3$. All other oracles (except $\textsc {Execute}$ and $\textsf{H}$) are the same as in $\textbf{G}_2$.

$\mathcal {B}_2$ uses $(i^*,j^*,\textsf{k}^*)$ to store its OW solution and uses $\mathcal {L}_{\textsc {E}}$ to record the intended hash input of session keys generated in $\textsc {Execute}$ (cf. Line 24). Although $\mathcal {B}_2$ does not have secret keys of $\textbf{pk}$ and KEM keys of $\textbf{c}$, it can still simulate $\textbf{G}_3$ since this information is not required in simulating $\textsc {Execute}$. Moreover, $\mathcal {B}_2$ uses $\mathcal {L}_{\textsc {E}}$ and $\textsc {Pco}$ to determine whether $\textsf{Query}_{\text {exec}}$ happens (cf. Lines 10 to 13).

If $\mathcal {A}$ queried $\textsf{H}(\textsf{U}, \textsf{S}, e_1, e_2, \textsf{pk}, \textsf{c}, \textsf{k}, \textsf{pw})$, where $(\textsf{U}, \textsf{S}, e_1, e_2, \textsf{pk}, \textsf{c}, \textsf{k},\textsf{pw})$ is the intended hash input of a session key $\textsf{SK}$ generated in $\textsc {Execute}$, then by the construction of $\textsf{PAKE}$ and Lines 21 to 24, there exists $\textsf{cnt}^* \in [S]$ such that $(\textsf{U}, \textsf{S}, e_1, e_2, (\textsf{pk}, \textsf{cnt}^*), \textsf{c}, \textsf{pw}) \in \mathcal {L}_{\textsc {E}}$, $\textsf{c}= \textbf{c}[\textsf{cnt}^*, 1]$, and $\textsf{k}= \textsf{Decaps}(\textsf{sk}, \textsf{c})$, where $\textsf{sk}$ is the secret key of $\textbf{pk}[\textsf{cnt}^*]$. This means that $\textsf{k}$ is the OW solution of $\textbf{c}[\textsf{cnt}^*, 1]$, and thus $\mathcal {B}_2$ records the OW solution (cf. Line 13) and returns it when the game ends. Therefore, we have

$$\begin{aligned} \left| {\Pr \left[ {\textbf{G}^\mathcal {A}_2 \Rightarrow 1}\right] } - {\Pr \left[ {\textbf{G}^\mathcal {A}_3 \Rightarrow 1}\right] } \right| \le {\Pr \left[ {\textsf{Query}_{\text {exec}}}\right] } \le \textsf{Adv}^{(S,1)\text {-}\textsf{OW}\text {-}\textsf{PCA}}_{\textsf{KEM}}(\mathcal {B}_2). \end{aligned}$$

  . We change the generation of $\textsf{c}$ in $\textsc {Execute}$ (cf. Line 06). In this game, $\textsf{c}$ is sampled from $\mathcal {C}$ uniformly at random instead of using $\textsf{Encaps}$. Moreover, we no longer store the information about $\textsf{pk}$, $\textsf{sk}$, $\textsf{c}$, and $\textsf{k}$ in the outputting instances from $\textsc {Execute}$ (cf. Lines 14 to 15). The later modification is conceptual since the game does not need this information to simulate $\textsc {Execute}$.

The difference between $\textbf{G}_3$ and $\textbf{G}_4$ can be bounded by using the ciphertext anonymity of $\textsf{KEM}$. The bound is given in Lemma 3. We continue the proof of Theorem 1 and postpone the proof of Lemma 3 to our full version [28].

Lemma 3

With notations and assumptions from $\textbf{G}_3$ and $\textbf{G}_4$ in the proof of Theorem 1, there is an adversary $\mathcal {B}_{3}$ with $\textbf{T}(\mathcal {B}_3) \approx \textbf{T}(\mathcal {A})$ and

$$\begin{aligned} \left| {\Pr \left[ {\textbf{G}^\mathcal {A}_3 \Rightarrow 1}\right] } - {\Pr \left[ {\textbf{G}^\mathcal {A}_4 \Rightarrow 1}\right] } \right| \le \textsf{Adv}^{(S, 1)\text {-}{\textsf{ANO}}}_{\textsf{KEM}}(\mathcal {B}_3) \end{aligned}$$

  . We postpone the generation of $\textsf{pk}$ and $\textsf{c}$ in $\textsc {Execute}$. Concretely, when $\mathcal {A}$ issues a query $(\textsf{U}, t_1, \textsf{S}, t_2)$ to $\textsc {Execute}$, we sample $e_1$ and $e_2$ uniformly at random (cf. Lines 07 to 08) and postpone the generation of $\textsf{pk}$ and $\textsf{c}$ and usage of $\textsf{IC}_1$ and $\textsf{IC}_2$ to the time that $\mathcal {A}$ queries $\textsf{D}_1(\textsf{pw}_{\textsf{U}, \textsf{S}}, e_1)$ or $\textsf{D}_2(\textsf{pw}_{\textsf{U}, \textsf{S}}, e_2)$, respectively. The change made in $\textbf{G}_2$ ensures that $\textsf{pk}$ output by $\textsf{D}_1(\textsf{pw}_{\textsf{U}, \textsf{S}}, e_1)$ is generated using $\textsf{KG}$, and the change made in $\textbf{G}_4$ ensures that $\textsf{c}$ output by $\textsf{D}_2(\textsf{pw}_{\textsf{U}, \textsf{S}}, e_2)$ is generated via uniformly sampling over $\mathcal {C}$. Therefore, $\textbf{G}_5$ is conceptually equivalent to $\textbf{G}_4$, which means

$$\begin{aligned} {\Pr \left[ {\textbf{G}^\mathcal {A}_4 \Rightarrow 1}\right] } = {\Pr \left[ {\textbf{G}^\mathcal {A}_5 \Rightarrow 1}\right] } \end{aligned}$$

  We rewrite the codes of $\textsc {SendInit}$, $\textsc {SendResp}$, and $\textsc {SendTerInit}$ in Fig. 11. In this game, $\textsc {SendResp}$ and $\textsc {SendTerInit}$ compute session keys based on the freshness of instances. $\textsc {SendResp}$ in $\textbf{G}_6$ is equivalent to the one in $\textbf{G}_5$. For $\textsc {SendTerInit}$ in $\textbf{G}_6$, if the user instance $\pi ^{t_1}_{\textsf{U}}$ has a matching server instance and such instance is fresh, then we make these two instances have the same session key (cf. Line 46). These changes are for further game transitions and they are conceptual if $\textsf{KEM}$ has perfect correctness. Here we need to consider the correctness error of $\textsf{KEM}$ since now we directly set up $\pi ^{t_1}_{\textsf{U}}$’s session key without decapsulation. There are at most $S$ queries to $\textsc {SendTerInit}$, by a union bound, we have

$$\begin{aligned} \left| {\Pr \left[ {\textbf{G}^\mathcal {A}_5 \Rightarrow 1}\right] } - {\Pr \left[ {\textbf{G}^\mathcal {A}_6 \Rightarrow 1}\right] }\right| \le S\cdot \delta . \end{aligned}$$

Fig. 11.

Oracles $\textsc {SendInit}, \textsc {SendResp}$, and $\textsc {SendTerInit}$ in games $\textbf{G}_6$-$\textbf{G}_{10}$. For any user $\textsf{U}$, $\mathcal {L}^{\textsf{U}}_{1}$ records all $e_1$ sent by $\textsf{U}$. Similarly, $\mathcal {L}^{\textsf{S}}_{2}$ records all $e_2$ sent by server $\textsf{S}$. All these lists are initialized as $\emptyset$.

  We use two flags $\textsf{Guess}_\text {user}$ and $\textsf{Guess}_\text {ser}$ (which are initialized as $\textbf{false}$) to indicate whether the following events happen:

• When $\mathcal {A}$ queries $\textsc {SendResp}(\textsf{S}, t_2, \textsf{U}, e_1)$, if $(\textsf{U}, \textsf{S})$ is uncorrupted, $e_1$ is not generated from $\textsf{U}$’s instance (cf. Line 37), and $\exists \textsf{pk}$ such that $e_1$ is generated via querying $\textsf{E}_1(\textsf{pw}_{\textsf{U},\textsf{S}}, \textsf{pk})$, then we set $\textsf{Guess}_\text {ser}$ as $\textbf{true}$ (cf. Lines 23 to 24).

• When $\mathcal {A}$ queries $\textsc {SendTerInit}(\textsf{U}, t_1, \textsf{S}, e_2)$, if $\pi ^{t_1}_{\textsf{U}}$ does not have matching session, $(\textsf{U}, \textsf{S})$ is uncorrupted, $e_2$ is not generated from $\textsf{S}$’s instance (cf. Line 30), and $\exists \textsf{c}$ such that $e_2$ is generated via querying $\textsf{E}_2(\textsf{pw}_{\textsf{U},\textsf{S}}, \textsf{c})$, then we set $\textsf{Guess}_\text {user}$ as $\textbf{true}$ (cf. Lines 53 to 53).

These two flags are internal and do not influence the game, and thus $\textbf{G}7$ is equivalent to $\textbf{G}_6$.

$$\begin{aligned} {\Pr \left[ {\textbf{G}^\mathcal {A}_6 \Rightarrow 1}\right] } = {\Pr \left[ {\textbf{G}^\mathcal {A}_7 \Rightarrow 1}\right] }. \end{aligned}$$

This step is crucial for our proof. Looking ahead, $\mathcal {A}$ triggered $\textsf{Guess}_\text {user}$ (or $\textsf{Guess}_\text {ser}$, similarly) means that $\mathcal {A}$ queried $\textsf{E}_1(\textsf{pw}_{\textsf{U}, \textsf{S}}, \textsf{pk})$ for some $\textsf{pk}$ without corrupting $\textsf{pw}_{\textsf{U}, \textsf{S}}$. In this case, such $\textsf{pk}$ is controlled by $\mathcal {A}$ (i.e., not output by the security game), and thus we cannot embed challenge public key into such $\textsf{pk}$ when constructing reduction. Such events happen means that the adversary performs a successful online dictionary attack. We delay the analysis of the happening probability of such events.

  Fresh user instances that do not have matching session and do not trigger $\textsf{Guess}_\text {user}$ will generate uniformly random session keys. Concretely, when $\mathcal {A}$ queries $\textsc {SendTerInit}(\textsf{U}, t_1, \textsf{S}, e_2)$, if $\pi ^{t_1}_{\textsf{U}}$ does not have matching instance, $(\textsf{U}, \textsf{S})$ is uncorrupted, and $e_2$ does not trigger $\textsf{Guess}_\text {user}$, then we sample the session key uniformly at random and independent of $\textsf{H}$ (cf. Lines 55 ro 56).

Fig. 12.

Reduction $\mathcal {B}_4$ in bounding the probability difference between $\textbf{G}_7$ and $\textbf{G}_8$. Highlighted parts show how $\mathcal {B}_4$ uses $\textsc {Pco}$ and challenge input to simulate $\textbf{G}_8$. $\mathcal {A}_4$ also uses a procedure $\textsf{Patch}$ to patch $\textsf{H}$. All other oracles not shown in the figure are the same as in $\textbf{G}_8$ (cf. Figs. 8, 9 and 11).

Since session keys in $\textbf{G}_7$ are generated via random oracle $\textsf{H}$, to distinguish $\textbf{G}_8$ and $\textbf{G}_7$, $\mathcal {A}$ needs to query one of the intended hash inputs of such random session keys. Let $\textsf{Query}_{\text {send}}$ be such querying event. To bound the happening probability of $\textsf{Query}_{\text {send}}$, we construct an reduction $\mathcal {B}_4$ with $\textbf{T}(\mathcal {A}) \approx \textbf{T}(\mathcal {B}_4)$ in Fig. 12 which attacks $\textsf{OW}\text {-}\textsf{rPCA}$ security of $\textsf{KEM}$. $\mathcal {B}_4$ works as follows:

• 1. On input a $\textsf{OW}\text {-}\textsf{rPCA}$ challenge $(\textsf{par}, \textbf{pk}, \textbf{c})$, $\mathcal {B}_4$ embeds public keys in $\textbf{pk}$ into queries to $\textsc {SendInit}$ (cf. Line 02) and embeds challenge ciphertexts in $\textsf{D}_2$ (cf. Line 15). Counter $\textsf{cnt}_1$ and $\textsf{cnt}_2$ are used to record the indexes of embedded public keys and ciphertexts, respectively.

• 2. Since $\mathcal {B}_4$ does not have secret keys of challenge public keys (cf. Line 02), it cannot decrypt KEM ciphertexts and thus cannot directly compute session keys of user instances or determine whether $\mathcal {A}$ has queried the hash input of such session keys (even if these keys are not fresh). To deal with it, we use RO patching technique to make the simulation consistent.

  Concretely, we define a procedure $\textsf{Patch}$ which uses $\textsc {Pco}$ oracle to determine if $\mathcal {A}$ has queried the intended hash input of the session key of some specific user instances. If so, it returns the recorded session key. Otherwise, it samples a random session key, records this session key in $\mathcal {L}'_{\text {SK}}$, and returns it. Later, if $\mathcal {A}$’s RO query matches a recorded session key, then $\mathcal {B}_4$ patches the RO and returns this key (cf. Lines 20 to 22).

  When $\mathcal {A}$ queries $\textsc {SendTerInit}(\textsf{U}, t_1, \textsf{S}, e_2)$, where $\pi ^{t_1}_{\textsf{U}}$ does not have fresh matching instance and either $e_2$ triggers $\textsf{Guess}_\text {user}$ or $(\textsf{U}, \textsf{S})$ is corrupted, $\mathcal {B}_4$ uses the procedure to compute the session key (cf. Lines 42 and 49).

• 3. When $\mathcal {A}$ queries $\textsc {SendTerInit}(\textsf{U}, t_1, \textsf{S}, e_2)$, if $\pi ^{t_1}_{\textsf{U}}$ does not have fresh matching instance, $(\textsf{U}, \textsf{S})$ is corrupted, and $e_2$ does not trigger $\textsf{Guess}_\text {user}$, then $e_2$ is not generated by querying $\textsf{E}_2(\textsf{pw}_{\textsf{U}, \textsf{S}}, e_2)$, which means that $\textsf{c}= \textsf{D}_2(\textsf{pw}_{\textsf{U}, \textsf{S}}, e_2)$ is one of the embedded ciphertext (cf. Line 15). $\mathcal {B}_4$ records such query in $\mathcal {L}_{\text {SK}}$ (cf. Line 46) to determine whether $\textsf{Query}_{\text {send}}$ happens. When $\mathcal {A}$ queried $\textsf{H}(\textsf{U}, \textsf{S}, e_1, e_2, \textsf{pk}, \textsf{c}, \textsf{k}, \textsf{pw}_{\textsf{U},\textsf{S}})$, if this query match one record in $\mathcal {L}_{\text {SK}}$ and $\textsf{k}$ is the decapsulated key of a embedded challenge ciphertext $\textsf{c}$ (cf. Line 23), then this RO query is the intended hash input of one of the session keys recorded in Line 46. In this case, $\textsf{Query}_{\text {send}}$ will be triggered, and $\mathcal {B}_4$ will use $(i^*, j^*, \textsf{k}^*)$ to record the OW solution of $\textsf{c}$ (cf. Line 25).

Since $\mathcal {A}$’s numbers of queries to $\textsf{Init}$ and $\textsf{D}_2$ are $S$ and $q_2$, respectively, $\mathcal {B}_4$ needs at most $S$ challenge public keys and $(q_2+ S)$ challenge ciphertexts per public keys during the simulation. If $\textsf{Query}_{\text {send}}$ happens, then $\mathcal {B}_4$ finds the OW solution of one of the challenge ciphertexts. Therefore, we have

$$\begin{aligned} \left| {\Pr \left[ {\textbf{G}^\mathcal {A}_7 \Rightarrow 1}\right] } - {\Pr \left[ {\textbf{G}^\mathcal {A}_8 \Rightarrow 1}\right] } \right| \le {\Pr \left[ {\textsf{Query}_{\text {send}}}\right] } \le \textsf{Adv}^{(S, q_2+ S)\text {-}\textsf{OW}\text {-}\textsf{rPCA}}_{\textsf{KEM}}(\mathcal {B}_4) \end{aligned}$$

  We change $\textsc {SendInit}$ and $\textsc {SendResp}$.

• 1. In $\textsc {SendInit}$, instead of generating $(\textsf{pk}, \textsf{sk}) \leftarrow \textsf{KG}$ and $e_1{:}{=}\textsf{E}_1(\textsf{pw}_{\textsf{U},\textsf{S}}, \textsf{pk})$, we firstly sample $e_1$ uniformly at random and then generate $(\textsf{pk}, \textsf{sk})$ by querying $\textsf{D}_1(\textsf{pw}_{\textsf{U}, \textsf{S}}, e_1)$ (cf. Lines 34 to 36).

• 2. Fresh server instances that do not trigger $\textsf{Guess}_\text {ser}$ will generate uniformly random session keys. Concretely, when $\mathcal {A}$ queries $\textsc {SendResp}(\textsf{S}, t_2, \textsf{U}, e_1)$, if $(\textsf{U}, \textsf{S})$ is uncorrupted and $e_1$ does not trigger $\textsf{Guess}_\text {ser}$, then we sample the session key uniformly at random and independent of $\textsf{H}$ (cf. Lines 25 to 26).

Fig. 13.

Reduction $\mathcal {B}_5$ in bounding the probability difference between $\textbf{G}_8$ and $\textbf{G}_9$. Highlighted parts show how $\mathcal {B}_5$ uses $\textsc {Pco}$ and challenge input to simulate $\textbf{G}_9$. All other oracles not shown in the figure are the same as in $\textbf{G}_8$ (cf. Figs. 8, 9 and 11). Procedure $\textsf{Patch}$ is the same as the one shown in Fig. 12.

Similar to our argument in bounding $\textbf{G}_7$ and $\textbf{G}_8$, to distinguish $\textbf{G}_8$ and $\textbf{G}_9$, $\mathcal {A}$ needs to query one of the intended hash inputs of such random session keys. Let $\textsf{Query}_{\text {resp}}$ be such querying event. We construct an reduction $\mathcal {B}_5$ with $\textbf{T}(\mathcal {A}) \approx \textbf{T}(\mathcal {B}_5)$ in Fig. 12 to bound the happening probability of $\textsf{Query}_{\text {resp}}$. $\mathcal {B}_5$ attacks $\textsf{OW}\text {-}\textsf{PCA}$ security of $\textsf{KEM}$ and works as follows:

• 1. On input a $\textsf{OW}\text {-}\textsf{PCA}$ challenge $(\textsf{par}, \textbf{pk}, \textbf{c})$, $\mathcal {B}_5$ embeds challenge public keys $\textbf{pk}$ into queries to $\textsf{D}_1$ (cf. Line 31). By Lines 34 to 36, public keys generated in $\textsc {SendInit}$ are also from $\textbf{pk}$. Similar to $\mathcal {B}_4$, $\mathcal {B}_5$ uses the $\textsf{Patch}$ procedure in Fig. 12 to compute the session keys of user instances. Counter $\textsf{cnt}_1$ and vector of counters $\textsf{cnt}_2$ are used to record the indexes of embedded public keys and ciphertexts, respectively.

• 2. When $\mathcal {A}$ queries $\textsc {SendResp}(\textsf{S}, t_2, \textsf{U}, e_1)$, if $\pi ^{t_2}_{\textsf{S}}$ is fresh (which means that $(\textsf{U}, \textsf{S})$ is uncorrupted) and $e_1$ does not trigger $\textsf{Guess}_\text {ser}$, then by our definition of $\textsf{Guess}_\text {ser}$, $e_1$ is not generated by querying $\textsf{E}_1(\textsf{pw}_{\textsf{U}, \textsf{S}}, \textsf{pk})$. This means that $\textsf{pk}= \textsf{D}_1(\textsf{pw}_{\textsf{U}, \textsf{S}}, e_1)$ is one of the embedded public key (cf. Line 31). In this case, $\mathcal {B}_5$ embeds one challenge ciphertext with respect to $\textsf{pk}$ (cf. Line 50) and records such query in $\mathcal {L}_{\text {SK}}$ (cf. Line 51) to determine whether $\textsf{Query}_{\text {resp}}$ happens. When $\mathcal {A}$ queried $\textsf{H}(\textsf{U}, \textsf{S}, e_1, e_2, \textsf{pk}, \textsf{c}, \textsf{k}, \textsf{pw}_{\textsf{U},\textsf{S}})$, if this query match one record in $\mathcal {L}_{\text {SK}}$ and $\textsf{k}$ is the decapsulated key of a embedded challenge ciphertext $\textsf{c}$ (cf. Line 59), then this RO query is the intended hash input of one of the session keys recorded in Line 51. In this case, $\textsf{Query}_{\text {resp}}$ will be triggered, and $\mathcal {B}_5$ will use $(i^*, j^*, \textsf{k}^*)$ to record the OW solution of the embedded challenge ciphertext $\textsf{c}$ (cf. Line 60).

Since $\mathcal {A}$’s numbers of queries to $(\textsc {SendInit}, \textsc {SendResp})$ and $\textsf{D}_2$ are $S$ and $q_2$ respectively, $\mathcal {B}_5$ needs at most $S+ q_2$ challenge public keys and $S$ challenge ciphertexts per public keys during the simulation. If $\textsf{Query}_{\text {resp}}$ happens, then $\mathcal {B}_5$ finds the OW solution of one of challenge ciphertexts in $\textbf{c}$. Therefore, we have

$$\begin{aligned} \left| {\Pr \left[ {\textbf{G}^\mathcal {A}_8 \Rightarrow 1}\right] } - {\Pr \left[ {\textbf{G}^\mathcal {A}_9 \Rightarrow 1}\right] } \right| \le {\Pr \left[ {\textsf{Query}_{\text {resp}}}\right] } \le \textsf{Adv}^{(S+ q_2, S)\text {-}\textsf{OW}\text {-}\textsf{PCA}}_{\textsf{KEM}}(\mathcal {B}_5) \end{aligned}$$

  We sample KEM ciphertext uniformly at random for server instances that are fresh and do not trigger $\textsf{Query}_{\text {resp}}$ (cf. Line 27). Similar to the argument of bounding $\textbf{G}_3$ and $\textbf{G}_4$ (cf. Lemma 3), We can use the ciphertext anonymity of $\textsf{KEM}$ to upper bound the probability difference between $\textbf{G}_9$ and $\textbf{G}_{10}$. The bound is given in Lemma 4. We continue the proof of Theorem 1 and postpone the proof of Lemma 4 to our full version [28].

Lemma 4

With notations and assumptions from $\textbf{G}_9$ and $\textbf{G}_{10}$ in the proof of Theorem 1, there is an adversary $\mathcal {B}_{6}$ with $\textbf{T}(\mathcal {B}_6) \approx \textbf{T}(\mathcal {A})$ and

$$\begin{aligned} \left| {\Pr \left[ {\textbf{G}^\mathcal {A}_9 \Rightarrow 1}\right] } - {\Pr \left[ {\textbf{G}^\mathcal {A}_{10} \Rightarrow 1}\right] } \right| \le \textsf{Adv}^{(S+ q_1, S)\text {-}{\textsf{ANO}}}_{\textsf{KEM}}(\mathcal {B}_6) \end{aligned}$$

In game transition $\textbf{G}_{10}$-$\textbf{G}_{12}$ (shown in Fig. 14), we bound the happening probabilities of $\textsf{Guess}_\text {ser}$ and $\textsf{Guess}_\text {user}$.

Fig. 14.

Oracles $\textsc {SendInit}, \textsc {SendResp}$, and $\textsc {SendTerInit}$ in games $\textbf{G}_{10}$-$\textbf{G}_{12}$.

  We do not use passwords to simulate the protocol messages of fresh instances that do not trigger $\textsf{Guess}_\text {ser}$ and $\textsf{Guess}_\text {user}$. Concretely, we change $\textsc {SendInit}, \textsc {SendResp},$ and $\textsc {SendTerInit}$ as follows:

• In $\textsc {SendResp}$, if the server instance $\pi ^{t_2}_{\textsf{S}}$ is fresh and does not trigger $\textsf{Guess}_\text {ser}$, then we sample $e_2$ uniformly at random and without using $\textsf{pw}_{\textsf{U}, \textsf{S}}$ and $\textsf{c}$ (cf. Lines 33 to 34). Moreover, we only store $e_2$ as the ephemeral secret of $\pi ^{t_2}_{\textsf{S}}$ (cf. Line 41). These changes are conceptual since we do not need $\textsf{c}$ to compute the session key and if $\mathcal {A}$ queries $\textsf{D}_2(\textsf{pw}_{\textsf{U}, \textsf{S}}, e_2)$ later, then we will return random $\textsf{c}$ (which are the same as in $\textbf{G}_{10}$).

• Similarly, in $\textsc {SendInit}$, we generate $e_1$ uniformly at random and without using $\textsf{pw}_{\textsf{U}, \textsf{S}}$ and $\textsf{pk}$ (cf. Lines 49 to 52) and only store $e_1$ as the ephemeral secret of $\pi ^{t_1}_{\textsf{U}}$ (cf. Lines 52 to 53 and Line 59). Later, if $\mathcal {A}$ corrupts $(\textsf{U}, \textsf{S})$ and queries $\textsc {SendTerInit}$ to finish the user instance $\pi ^{t_1}_{\textsf{U}}$, we retrieve necessary information to compute the session key (cf. Lines 82 to 83). These changes are also conceptual, since session keys of such instances are independently and uniformly random. We have

  $$\begin{aligned} {\Pr \left[ {\textbf{G}^\mathcal {A}_{10} \Rightarrow 1}\right] } = {\Pr \left[ {\textbf{G}^\mathcal {A}_{11} \Rightarrow 1}\right] } \end{aligned}$$

  We postpone the generation of passwords and the determination of whether $\textsf{Guess}_\text {user}$ or $\textsf{Guess}_\text {ser}$ happen. For simplicity, we define event $\textsf{GUESS}$ as $\textsf{Guess}_\text {user}\vee \textsf{Guess}_\text {ser}$.

• 1. We generate passwords as late as possible. passwords are generated only when $\mathcal {A}$ issues $\textsc {Corrupt}$ queries or after $\mathcal {A}$ ends with output $b'$ (cf. Lines 06, 07 to 15).

• 2. Since the passwords of uncorrupted parties do not exist before $\mathcal {A}$ terminates, we cannot determine whether $\textsf{GUESS}$ happens when $\mathcal {A}$ is running. To deal with it, we postpone such determination. When $\mathcal {A}$ issues $\textsc {SendResp}$ or $\textsc {SendTerInit}$ queries, we records all potential passwords that may match the actual password of the specific user-server pair (cf. Lines 37 to 38 and Lines 76 to 78). After $\mathcal {A}$ outputs $b'$, the passwords of uncorrupted user-server pairs are generated, and then we use these passwords to determine whether $\textsf{Guess}_\text {user}$ or $\textsf{Guess}_\text {ser}$ happen (cf. Lines 06 to 11).

• 3. Now all fresh instances will accept random session keys independent of $\textsf{H}$ and passwords (Lines 40 and 79).

If $\textsf{GUESS}$ does not happen in both game, then these changes are conceptual. We have

$$\begin{aligned} {\Pr \left[ {\textbf{G}^\mathcal {A}_{11} \Rightarrow 1 \ | \ \lnot \textsf{GUESS}\text { in } \textbf{G}^\mathcal {A}_{11}}\right] } = {\Pr \left[ {\textbf{G}^\mathcal {A}_{12} \Rightarrow 1 \ | \ \lnot \textsf{GUESS}\text { in } \textbf{G}^\mathcal {A}_{12}}\right] } \end{aligned}$$

We claim that $\textsf{GUESS}$ happens in $\textbf{G}_{11}$ if and only if it happens in $\textbf{G}_{12}$. It is straightforward to see that $\textsf{GUESS}$ happens in $\textbf{G}_{11}$ then it also happens in $\textbf{G}_{12}$, since in $\textbf{G}_{12}$ we records all potential passwords in $\mathcal {L}_{\text {pw}}$ that may trigger $\textsf{GUESS}$ in $\textbf{G}_{11}$. If $\textsf{GUESS}$ happens in $\textbf{G}_{12}$, then there exists $\textsf{pw}_{\textsf{U}, \textsf{S}} \in \mathcal {L}_{\text {pw}}$. Moreover, $\textsf{pw}_{\textsf{U}, \textsf{S}}$ is recorded in $\mathcal {L}_{\text {pw}}$ only if $(\textsf{U}, \textsf{S})$ is uncorrupted. By (cf. Lines 37 to 38 and Lines 76 to 78), $\textsf{pw}_{\textsf{U}, \textsf{S}} \in \mathcal {L}_{\text {pw}}$ means that there exists $(\textsf{pk}, e_1)$ (resp., $(\textsf{c}, e_2)$) such that $e_1\notin \mathcal {L}^{\textsf{U}}_{1}$ (resp., $e_2\notin \mathcal {L}^{\textsf{S}}_{2}$) and $(\textsf{pw}_{\textsf{U}, \textsf{S}}, \textsf{pk}, e_1, \text {enc}) \in \mathcal {L}_1$ (resp., $(\textsf{pw}_{\textsf{U}, \textsf{S}}, \textsf{c}, e_2, \text {enc}) \in \mathcal {L}_2$), and thus either $\textsf{Guess}_\text {user}$ or $\textsf{Guess}_\text {ser}$ will be triggered in $\textbf{G}_{11}$. Therefore, if $\textsf{GUESS}$ happens in $\textbf{G}_{12}$, then $\textsf{GUESS}$ also happens in $\textbf{G}_{11}$. Now we have

$$\begin{aligned} \left| {\Pr \left[ {\textbf{G}^\mathcal {A}_{11} \Rightarrow 1}\right] } - {\Pr \left[ {\textbf{G}^\mathcal {A}_{12} \Rightarrow 1}\right] }\right| \le {\Pr \left[ {\textsf{GUESS}\text { in } \textbf{G}^\mathcal {A}_{11}}\right] } = {\Pr \left[ {\textsf{GUESS}\text { in } \textbf{G}^\mathcal {A}_{12}}\right] } \end{aligned}$$

Furthermore, we claim that every query to $\textsc {SendResp}$ or $\textsc {SendTerInit}$ will add at most one password into $\mathcal {L}_{\text {pw}}$. That is, at most one password will be recorded in $\mathcal {L}_{\text {pw}}$ in every execution of Lines 37 to 38 or Lines 76 to 78. To see this, suppose that there are two passwords $\textsf{pw}$ and $\textsf{pw}'$ are recorded during a execution of Lines 37 to 38. By Line 37, we have $(\textsf{pw}, \textsf{c}, e_2, \text {enc}) \in \mathcal {L}_2$ and $(\textsf{pw}', \textsf{c}', e_2, \text {enc}) \in \mathcal {L}_2$ for some $\textsf{c}$ and $\textsf{c}'$. This means that $e_2$ is generated by querying $\textsf{E}_2(\textsf{pw}, \textsf{c})$ and $\textsf{E}_2(\textsf{pw}', \textsf{c}')$, which is impossible since we simulate $\textsf{E}_2$ in a collision-free way. Similar argument applies for Lines 76 to 78. Therefore, every query to $\textsc {SendResp}$ or $\textsc {SendTerInit}$ will add at most one password into $\mathcal {L}_{\text {pw}}$.

Fig. 15.

Final game $\textbf{G}_{12}$ in proving Theorem 1. $\mathcal {A}$ has access to the set of PAKE oracles $\{\textsc {Execute}, \textsc {SendInit}, \textsc {SendResp}, \textsc {SendTerInit}, \textsc {Corrupt}, \textsc {Reveal}, \textsc {Test}\}$, random oracle $\textsf{H}$, and ideal ciphers $\textsf{IC}_1= (\textsf{E}_1, \textsf{D}_1)$ and $\textsf{IC}_2= (\textsf{E}_2, \textsf{D}_2)$. Oracles $\textsc {Reveal}$ and $\textsc {Test}$ are the same as in $\textbf{G}_{1}$ (cf. Fig. 8) so we omit their description here.

Now we can bound the happening probability of $\textsf{GUESS}$ in $\textbf{G}_{12}$. A clean description of $\textbf{G}_{12}$ is given in Fig. 15. In $\textbf{G}_{12}$, passwords of uncorrupted user-server pairs are undefined before $\mathcal {A}$ issues $\textsc {Corrupt}$ queries or ends with output $b'$. Moreover, oracles $\textsc {Execute}, \textsc {SendInit}, \textsc {SendResp}$, and $\textsc {SendTerInit}$ can be simulated without using uncorrupted passwords. Therefore, uncorrupted passwords are perfectly hidden from $\mathcal {A}$’s view. Since $\mathcal {A}$ issues $S$ queries to $\textsc {SendResp}$ and $\textsc {SendTerInit}$, we have $|\mathcal {L}_{\text {pw}}| \le S$ and

$$\begin{aligned} {\Pr \left[ {\textsf{GUESS}\text { in } \textbf{G}^\mathcal {A}_{12}}\right] } \le \frac{S}{|\mathcal{P}\mathcal{W}|} \end{aligned}$$

All fresh instances in $\textbf{G}_{12}$ will accept independently and uniformly random session keys, so we also have

$$\begin{aligned} {\Pr \left[ {\textbf{G}^\mathcal {A}_{12} \Rightarrow 1}\right] } = \frac{1}{2} \end{aligned}$$

Combining all the probability differences in the games sequence, we have

$$\begin{aligned} \textsf{Adv}^{\textsf{BPR}}_{\varPi }(\mathcal {A}) & \le \ \frac{S}{|\mathcal{P}\mathcal{W}|} + \textsf{Adv}^{q_1\text {-}\textsf{FUZZY}}_{\textsf{KEM}}(\mathcal {B}_1) + \textsf{Adv}^{(S, q_2+ S)\text {-}\textsf{OW}\text {-}\textsf{rPCA}}_{\textsf{KEM}}(\mathcal {B}_4) \\ & + \textsf{Adv}^{(S,1)\text {-}\textsf{OW}\text {-}\textsf{PCA}}_{\textsf{KEM}}(\mathcal {B}_2) + \textsf{Adv}^{(S+ q_2, S)\text {-}\textsf{OW}\text {-}\textsf{PCA}}_{\textsf{KEM}}(\mathcal {B}_5) \\ &+ \textsf{Adv}^{(S, 1)\text {-}{\textsf{ANO}}}_{\textsf{KEM}}(\mathcal {B}_3) + \textsf{Adv}^{(S+ q_1, S)\text {-}{\textsf{ANO}}}_{\textsf{KEM}}(\mathcal {B}_6) + S\cdot \delta \\ & + S^2 (\eta _{pk} + \eta _{ct} ) + \frac{(q_1^2 + S^2)}{|\mathcal {E}_1|} + \frac{(q_2^2 + S^2)}{|\mathcal {E}_2|} + \frac{q_1^2 }{|\mathcal{P}\mathcal{K}|} + \frac{q_2^2}{|\mathcal {C}|} + \frac{(q_{\textsf{H}}^2 + S^2)}{|\mathcal{S}\mathcal{K}|} \end{aligned}$$

5 Instantiations of the Underlying KEM

5.1 Direct Diffie-Hellman-Based Constructions

Diffie-Hellman Assumptions. We recall the multi-user and multi-challenge strong Diffie-Hellman assumption. Let $\mathcal {G}$ be a group generation algorithm that on input security parameters outputs a group description $(\mathbb {G}, g, p)$, where $p$ is an odd prime and $\mathbb {G}$ is a $p$-order group with generator $g$.

Definition 15

(Multi-Instance $\textsf{stDH}$ [3]). Let $N$ and $\mu$ be integers. We say the $\textsf{stDH}$ problem is hard on $\mathcal {G}$, if for any $\mathcal {A}$, the $(N, \mu )$-$\textsf{stDH}$ advantage of $\mathcal {A}$ against $\mathcal {G}$

$$\begin{aligned} {\textsf{Adv}}^{(N, \mu )\text {-}\textsf{stDH}}_{\mathcal {G}}(\mathcal {A}) {:}{=}{\Pr \left[ {\textsf{stDH}^{(N, \mu ), \mathcal {A}}_{\mathcal {G}} \Rightarrow 1}\right] }. \end{aligned}$$

is negligible, where $\textsf{stDH}^{(N, \mu ), \mathcal {A}}_{\mathcal {G}}$ is defined in Fig. 16.

Fig. 16.

Security games $\textsf{OW}\text {-}\textsf{PCA}$ and $\textsf{OW}\text {-}\textsf{rPCA}$ for KEM scheme $\textsf{KEM}$.

Construction based on strong DH. In Fig. 17, we construct a KEM scheme $\textsf{KEM}_{\textsf{stDH}}$ with plaintext space $\mathbb {G}$ and ciphertext space of $\mathbb {G}$. $\textsf{KEM}_{\textsf{stDH}}$ is essentially the hashed ElGamal KEM [3, 17].

Fig. 17.

KEM scheme $\textsf{KEM}_{\textsf{stDH}}= (\textsf{Setup}_1, \textsf{KG}_1, \textsf{Encaps}_1, \textsf{Decaps}_1)$.

$\textsf{KEM}_{\textsf{stDH}}$ has perfect public key fuzzyness and ciphertext anonymity (even under PCA). This is because $X{\mathop {\leftarrow }\limits ^{{}_\$}}\mathbb {G}$ is equivalent to $(x{\mathop {\leftarrow }\limits ^{{}_\$}}{\mathbb {Z}}_{p}, X{:}{=}g^{x})$. Therefore, we have

$$ \textsf{Adv}^{(N, \mu )\text {-}{\textsf{ANO}}}_{\textsf{KEM}_{\textsf{stDH}}}(\mathcal {A}) = 0, \ \textsf{Adv}^{N\text {-}\textsf{FUZZY}}_{\textsf{KEM}_{\textsf{stDH}}}(\mathcal {A}) = 0 $$

for any integers $N$ and $\mu$, and adversary $\mathcal {A}$ (even unbounded).

It is well-known that the hash ElGamal KEM is tightly IND-CCA secure (which implies $\text {OW}\text {-}\text {PCA}$ security) if the (1, 1)-$\textsf{stDH}$ assumption holds [15]. By using the random self-reducibility of Diffie-Hellman assumption, one can show that the $(N, \mu )$-$\text {OW}\text {-}\text {PCA}$ security can be tightly reduced to the (1, 1)-$\textsf{stDH}$ assumption.

5.2 Generic Constructions

Let $\textsf{PKE}_0= ({\textsf{KG}}_0, \textsf{Enc}_0, \textsf{Dec}_0)$ be a PKE scheme with public key space $\mathcal{P}\mathcal{K}$, message space $\mathcal {M}$, randomness space $\mathcal {R}$, and ciphertext space $\mathcal {C}$. Let $\ell$ and $L$ be integers. Let $\textsf{G}: \mathcal{P}\mathcal{K}\times \mathcal {M}\rightarrow \mathcal {R}$, $\textsf{H}: \mathcal{P}\mathcal{K}\times \mathcal {M}\times \mathcal {C}\rightarrow \{0,1\}^L$, and $\textsf{H}': \mathcal{P}\mathcal{K}\times \{0,1\}^\ell \times \mathcal {C}\rightarrow \{0,1\}^L$ be hash functions. Let $\textsf{PKE}_0= (\textsf{Setup}_0, {\textsf{KG}}_0, \textsf{Enc}_0, \textsf{Dec}_0)$ be a PKE scheme. In Fig. 18, we define a generic transformation for KEM schemes. We denote such transformation as . is essentially a combination of the $\textsf{T}$ transformation and the transformation in [21]. $\textsf{KEM}$ has the same public key space and ciphertext space with $\textsf{PKE}_0$. The $\textsf{Setup}$ algorithm of $\textsf{KEM}$ is the same as the one of $\textsf{PKE}_0$.

Fig. 18.

KEM scheme $\textsf{KEM}= (\textsf{Setup}, \textsf{KG}, \textsf{Encaps}, \textsf{Decaps})$ from the generic transformation , where $\textsf{G},\textsf{H}$, and $\textsf{H}'$ are hash functions, $\textsf{PKE}_0= (\textsf{Setup}_0, {\textsf{KG}}_0, \textsf{Enc}_0, \textsf{Dec}_0)$ is a PKE scheme, and $\textsf{Setup}= \textsf{Setup}_0$.

  We follow the correctness proof of [21, Theorem 3.1]. $\textsf{Decaps}$ has decapsulation error if its input is $\textsf{c}= \textsf{Enc}_0(\textsf{pk}, m'; \textsf{G}(\textsf{pk}, m'))$ for some $m'$ and $\textsf{Dec}_0(\textsf{sk}, \textsf{c}) \ne m'$. If $\textsf{PKE}_0$ is $(1 - \delta _{\textsf{PKE}_0})$-correct, such event happens within probability $q_{\textsf{G}}\cdot \delta _{\textsf{PKE}_0}$ if we treat $\textsf{G}$ as a random oracle and assume $\textsf{G}$ will be queried at most $q_{\textsf{G}}$ times. Therefore, $\textsf{KEM}$ is $(1 - q_{\textsf{G}}\cdot \delta _{\textsf{PKE}_0})$-correct.

Security. In Theorems 2 to 4, we show if $\textsf{PKE}_0$ has fuzzy public keys and $\text {PR}\text {-}\text {CPA}$ security, then $\textsf{KEM}$ has fuzzy public keys, anonymous ciphertexts (under PCA attacks), and $\text {OW}\text {-}\text {(r)PCA}$ security.

It is easy to see transformation preserves the public key fuzzyness of the underlying PKE.

Theorem 2

Let $N$ be the number of users. If $\textsf{PKE}_0$ has fuzzy public keys, then in Fig. 18 also has fuzzy public keys. Concretely, for any adversary $\mathcal {A}$ against $\textsf{KEM}$, there exists an adversary $\mathcal {B}$ with $\textbf{T}(\mathcal {A}) \approx \textbf{T}(\mathcal {B})$ and

$$ \textsf{Adv}^{N\text {-}\textsf{FUZZY}}_{\textsf{KEM}}(\mathcal {A}) \le \textsf{Adv}^{N\text {-}\textsf{FUZZY}}_{\textsf{PKE}_0}(\mathcal {B}) $$

Theorems 3 and 4 show shat if $\textsf{PKE}_0$ is $\text {PR}\text {-}\text {CPA}$ secure, then has $\text {OW}\text {-}\text {CPA}$ security and ciphertext anonymity under PCA attacks. For readability, we postpone their proofs to our full version [28].

Theorem 3

Let $N$ and $\mu$ be the numbers of users and challenge ciphertexts per user. If $\textsf{PKE}_0$ is $\text {PR}\text {-}\text {CPA}$ secure and $(1-\delta )$-correct and $\textsf{G}, \textsf{H},$ and $\textsf{H}'$ be random oracles, then has anonymous ciphertext under PCA attacks (cf. Definition 7).

Concretely, for any $\mathcal {A}$ against $\textsf{KEM}$, there exists $\mathcal {B}= (\mathcal {B}_0, \mathcal {B}_1)$ with $\textbf{T}(\mathcal {A}) \approx \textbf{T}(\mathcal {B})$ and

$$\begin{aligned} \textsf{Adv}^{(N,\mu )\text {-}{\textsf{ANO}}}_{\textsf{KEM}}(\mathcal {A}) & \le 2 \textsf{Adv}^{(N, \mu )\text {-}\textsf{PR}\text{- }\textsf{CPA}}_{\textsf{PKE}_0}(\mathcal {B}) + 2 Nq_{\textsf{G}}\cdot \delta + \frac{N\mu q_{\textsf{G}}}{|\mathcal {M}|} \\ & + \frac{2 N(q_{\textsf{H}'}+ q_{\textsc {Pco}})}{2^\ell } + \frac{N^2\mu ^2 + q_{\textsf{G}}^2}{|\mathcal {R}|} + \frac{2 N^2\mu ^2 + q_{\textsf{H}}^2 + q_{\textsf{H}'}^2}{2^L}, \end{aligned}$$

where $q_{\textsf{G}}, q_{\textsf{H}}, q_{\textsf{H}'}$, and $q_{\textsc {Pco}}$ are the numbers of $\mathcal {A}$’s queries to $\textsf{G}, \textsf{H}, \textsf{H}',$ and $\textsc {Pco}$.

Theorem 4

Let $N$ and $\mu$ be the numbers of users and challenge ciphertexts per user. If $\textsf{PKE}_0$ is $\text {PR}\text {-}\text {CPA}$ secure and $\textsf{G}, \textsf{H},$ and $\textsf{H}'$ be random oracles, then is $\text {OW}\text {-}\text {PCA}$ secure.

Concretely, for any $\mathcal {A}$ against $\textsf{KEM}$’s $(N, \mu )$-$\textsf{OW}\text {-}\textsf{PCA}$ security, there exists $\mathcal {B}$ with $\textbf{T}(\mathcal {A}) \approx \textbf{T}(\mathcal {B})$ and

$$\begin{aligned} \textsf{Adv}^{(N,\mu )\text {-}\textsf{OW}\text {-}\textsf{PCA}}_{\textsf{KEM}}(\mathcal {A}) & \le 2 \textsf{Adv}^{(N, \mu )\text {-}\textsf{PR}\text{- }\textsf{CPA}}_{\textsf{PKE}_0}(\mathcal {B}) + 2 Nq_{\textsf{G}}\cdot \delta + \frac{N\mu (q_{\textsf{G}}+ q_{\textsf{H}})}{|\mathcal {M}|} \\ & + \frac{2 N(q_{\textsf{H}'}+ q_{\textsc {Pco}})}{2^\ell } + \frac{N^2\mu ^2 + q_{\textsf{G}}^2}{|\mathcal {R}|} + \frac{2 N^2\mu ^2 + q_{\textsf{H}}^2 + q_{\textsf{H}'}^2}{2^L}, \end{aligned}$$

where $q_{\textsf{G}}, q_{\textsf{H}}, q_{\textsf{H}'}$, and $q_{\textsc {Pco}}$ are the numbers of $\mathcal {A}$’s queries to $\textsf{G}, \textsf{H}, \textsf{H}',$ and $\textsc {Pco}$.

By combining Lemma 1 and Theorems 3 and 4, we have Theorem 5.

Theorem 5

Let $N$ and $\mu$ be the numbers of users and challenge ciphertexts per user. If $\textsf{PKE}_0$ is $\text {PR}\text {-}\text {CPA}$ secure and $\textsf{G}, \textsf{H},$ and $\textsf{H}'$ be random oracles, then is $\text {OW}\text {-}\text {rPCA}$ secure.

Concretely, for any $\mathcal {A}$ against $\textsf{KEM}$’s $(N, \mu )$-$\textsf{OW}\text {-}\textsf{rPCA}$ security, there exists $\mathcal {B}$ with $\textbf{T}(\mathcal {A}) \approx \textbf{T}(\mathcal {B})$ and

$$\begin{aligned} \textsf{Adv}^{(N,\mu )\text {-}\textsf{OW}\text {-}\textsf{rPCA}}_{\textsf{KEM}}(\mathcal {A}) & \le 4 \textsf{Adv}^{(N, \mu )\text {-}\textsf{PR}\text{- }\textsf{CPA}}_{\textsf{PKE}_0}(\mathcal {B}) + 4 Nq_{\textsf{G}}\cdot \delta + \frac{N\mu (2 q_{\textsf{G}}+ q_{\textsf{H}})}{|\mathcal {M}|} \\ & + \frac{4 N(q_{\textsf{H}'}+ q_{\textsc {Pco}})}{2^\ell } + \frac{2(N^2\mu ^2 + q_{\textsf{G}}^2)}{|\mathcal {R}|} + \frac{2( 2N^2\mu ^2 + q_{\textsf{H}}^2 + q_{\textsf{H}'}^2)}{2^L}, \end{aligned}$$

where $q_{\textsf{G}}, q_{\textsf{H}}, q_{\textsf{H}'}$, and $q_{\textsc {Pco}}$ are the numbers of $\mathcal {A}$’s queries to $\textsf{G}, \textsf{H}, \textsf{H}',$ and $\textsc {Pco}$.

5.3 Lattice-Based Instantiations

We discuss two lattice-based instantiations of the PAKE protocol $\varPi$ (Fig. 7). The first one is the well-known Regev’s encryption [29, 30] which is based on learning with error (LWE) assumption. The second one is the Kyber.PKE scheme [32], which is based on the module LWE (MLWE) assumption. For simplicity, we only discuss the security loss of these schemes (from their assumptions) and the final security loss of $\varPi$ instantiated with these schemes. For more background about lattices, please refer to [18, 29, 30, 32].

Let $\lambda$ the security parameter. Let $S$ and $q_{\textsf{IC}}$ be the number of session and the number of $\mathcal {A}$’s queries to ideal ciphers $(\textsf{IC}_1, \textsf{IC}_2)$ in Fig. 7. Let $\epsilon _{\textsf{LWE}}$ and $\epsilon _{\textsf{mlwe}}$ be the best computational advantage against the LWE and MLWE assumptions, respectively. We use $\textsf{negl}(\lambda )$ to denote negligible (about $\lambda$) statistical terms. Such terms do not influence tightness.

Regev Encryption. We use the multi-bit version of Regev’s encryption, denoted as $\textsf{PKE}_\textsf{Regev}$, in [29]. As shown in [29, Lemma 7.3, Lemma 7.4], the public keys of this scheme are indistinguishable from random by using a LWE problem instance, and the ciphertexts are pseudorandom under random public keys. Suppose this scheme encrypts $\varTheta (\lambda )$ bits, then we have

$$\begin{aligned} \textsf{Adv}^{N\text {-}\textsf{FUZZY}}_{\textsf{PKE}_\textsf{Regev}}(\mathcal {A}) \le O(N\lambda ) \cdot \epsilon _{\textsf{LWE}}, \ \textsf{Adv}^{(N, \mu )\text {-}\textsf{PR}\text{- }\textsf{CPA}}_{\textsf{PKE}_\textsf{Regev}}(\mathcal {A}) \le O(N\lambda ) \cdot \epsilon _{\textsf{LWE}}+ \textsf{negl}(\lambda ) \end{aligned}$$

We can use the transformation to transform $\textsf{PKE}_\textsf{Regev}$ into a KEM scheme and then use the KEM scheme to instantiate $\varPi$ (Fig. 7). By plugging these bounds into Theorems 3 to 5 and then Theorem 1, we have

$$\begin{aligned} \textsf{Adv}^{\textsf{BPR}}_{{\varPi [\textsf{PKE}_\textsf{Regev}]} }(\mathcal {A}) \le O(\lambda \cdot (q_{\textsf{IC}}+ S) ) \cdot \epsilon _{\textsf{LWE}}\end{aligned}$$

Kyber PKE. We consider the Kyber.CPAPKE scheme (denoted as $\textsf{PKE}_{\textsf{kyber}}$) in [32]. The pseudorandomness and fuzzyness proofs of $\textsf{PKE}_{\textsf{kyber}}$ are the same as in [8, Lemmata 1 and 2, Corollary 1]. Since the MLWE assumption does not have random self-reducibility, we can use a standard hybrid argument to extend such proofs to multi-user-challenge setting. We have

$$\begin{aligned} \textsf{Adv}^{N\text {-}\textsf{FUZZY}}_{\textsf{PKE}_\textsf{Regev}}(\mathcal {A}) \le N\cdot \epsilon _{\textsf{mlwe}}, \ \textsf{Adv}^{(N, \mu )\text {-}\textsf{PR}\text{- }\textsf{CPA}}_{\textsf{PKE}_\textsf{Regev}}(\mathcal {A}) \le N\mu \cdot 2 \epsilon _{\textsf{mlwe}}\end{aligned}$$

By using the transformation, we can transform $\textsf{PKE}_{\textsf{kyber}}$ into a KEM scheme. Then we use the KEM scheme to instantiate $\varPi$ (Fig. 7). By Theorems 1 and 3 to 5, we have

$$\begin{aligned} \textsf{Adv}^{\textsf{BPR}}_{{\varPi [\textsf{PKE}_{\textsf{kyber}}} }(\mathcal {A}) \le O(S\cdot (q_{\textsf{IC}}+ S) ) \cdot \epsilon _{\textsf{mlwe}}\end{aligned}$$