Hugo Beguinet
email: hugo.beguinet@ens.fr

Céline Chevalier
email: celine.chevalier@ens.fr

David Pointcheval
email: david.pointcheval@ens.fr

Thomas Ricosset
email: thomas.ricosset@thalesgroup.com

Mélissa Rossi
email: melissa.rossi@ssi.gouv.fr

GeT a CAKE: Generic Transformations from Key Encaspulation Mechanisms to Password Authenticated Key Exchanges

Keywords: Key Encapsulation Mechanism, Password-Authenticated Key Exchange, Universal Composability

Password Authenticated Key Exchange (PAKE) have become a key building block in many security products as they provide interesting efficiency/security trade-offs. Indeed, a PAKE allows to dispense with the heavy public key infrastructures and its efficiency and portability make it well suited for applications such as Internet of Things or e-passports. With the emerging quantum threat and the effervescent development of post-quantum public key algorithms in the last five years, one would wonder how to modify existing password authenticated key exchange protocols that currently rely on Diffie-Hellman problems in order to include newly introduced and soon-to-be-standardized post-quantum key encapsulation mechanisms (KEM). A generic solution is desirable for maintaining modularity and adaptability with the many post-quantum KEM that have been introduced. In this paper, we propose two new generic and natural constructions proven in the Universal Composability (UC) model to transform, in a black-box manner, a KEM into a PAKE with very limited performance overhead: one or two extra symmetric encryptions. Behind the simplicity of the designs, establishing security proofs in the UC model is actually non-trivial and requires some additional properties on the underlying KEM like fuzziness and anonymity. Luckily, post-quantum KEM protocols often enjoy these two extra properties. As a demonstration, we prove that it is possible to apply our transformations to Crystals-Kyber, a lattice-based post-quantum KEM that will soon be standardized by the National Institute of Standards and Technology (NIST). In a nutshell, this work opens up the possibility to securely include postquantum cryptography in PAKE-based real-world protocols.

Introduction

A Password Authenticated Key Exchange (PAKE) protocol allows two users to derive a secret key over insecure channels only with the premise of sharing the same low entropy password. PAKE has become increasingly relevant in recent years due to the proliferation of connected devices and the growing demand for secure communication in scenarios where a public key infrastructure (PKI) may not be practical or desirable. It is particularly appealing for use cases like the Internet of Things (IoT) or e-passports, where portability, independence, and efficiency are important considerations. For IoT devices, for example, PKI is not feasible because of the number of devices and their limited computing resources and connectivity. PAKE allows these devices to securely communicate with each other using a simple password that can be easily changed if compromised. Similarly, in the case of e-passport, PAKE can be used to establish secure communication between the passport and a reader without the need for a PKI. It allows for a more portable and independent solution, as no central authority is necessary to verify a passport's authenticity. Overall, PAKE offers a trade-off between security and efficiency as compared to traditional authenticated key exchange protocols in certain circumstances.

Security models for PAKEs The security of PAKE will always be weaker than the security of PKI-based authenticated key exchange. Indeed, the presence of a low-entropy password allows powerful dictionary attacks. The conceptual idea in the PAKE security models is to accept the possibility of such dictionary attacks but to prove that they must be made online, i.e. that no password validity test is accessible offline. This slight security regression compared to authenticated key exchange is often accepted because online dictionary attacks are rarely relevant in practical contexts and the efficiency gain of PAKE is much higher. Moreover one can always block a user after a certain number of failed attempts. More formally, for proving the security of PAKE, the dictionary attacks should then be materialized in the existing security models for authenticated key exchange. Several solutions have emerged and have been refined over the last decade. Today, there are two main security models for PAKE protocols: the Bellare-Pointcheval-Rogaway [BPR00] and the Universal Composability (UC) model [Can01,CR03] with its PAKE's version [CHK + 05]. The BPR model, introduced by Bellare, Pointcheval, and Rogaway, is a game-based security model that uses specific games to evaluate the ability of an adversary to break the protocol. On the other hand, the UC model, introduced by Canetti, is a simulation-based model that provides strictly better security guarantees, as stated in the original UC PAKE paper [CHK + 05].

Existing work on PAKE. The concept of PAKE was formalized and analyzed during the 1990s by Bellovin and Meritt with the Encrypted Key Exchange (EKE) protocol [BM92]. Since then, various PAKE protocols have been proposed, with some standardized by organizations such as the Internet Engineering Task Force (IETF) [Sch17]. Over the years, two main categories of PAKE appeared.

The first use passwords to obscure the exchanged messages while the second use them as part of the randomness to build the necessary material, like the group generator. Post-quantum threat. While vastly used in current security products like IoT or e-passports, all these PAKE constructions rely on the Diffie-Hellman key exchange to provide cryptographic security. It raises concerns about their long-term security, as the emergence of quantum computing in recent years threatens any Diffie-Hellman-based key exchange, and thus any currently used PAKE. Indeed, quantum computers would potentially break, even retroactively, the mathematical foundations of many current cryptographic systems including the difficulty of the Diffie-Hellman problem. Therefore, it is crucial to carefully consider the long-term security of PAKE protocols and design them accordingly. In response to this potential threat to current cryptographic systems, the National Institute of Standards and Technology (NIST) has launched a standardization process for post-quantum cryptographic primitives in 2017. The goal of this campaign is to provide new post-quantum standards for two basic and crucial cryptographic building blocks: Key Encapsulation Mechanisms (KEMs) and digital signatures. These two families of public-key algorithms may be used on their own but more importantly, the future standards are destined to be included as black-boxes in internet and IoT protocols to complement the pre-quantum bricks. Many different families of mathematical problems were used for the design of candidate algorithms like error correcting codes or lattices. The analysis of the different candidate algorithms is currently ongoing but the NIST has announced a first set of standards in 2022 including the lattice-based KEM Crystals-Kyber [SAB + 22]. More recently, specific PAKE constructions using post-quantum cryptography, in particular, lattices assumptions, were introduced. However most lattice constructions are either proven in weaker security models [GDLL17] or using mechanisms that are highly inefficient in practice [BCV19,ZY17].

Our Contributions

This paper proposes the first generic constructions to transform a black-box KEM into a PAKE. The idea is natural and inspired from EKE and OEKE. In high level, it consists in encrypting the public key using the password as a secret key. A second modification consists in either encrypting the ciphertext with that same password or adding an authentication tag. The first transformation is called CAKE, derived from K(EM-to-P)AKE, and the second transformation is called OCAKE. Both constructions are graphically sketched later in the paper in Figures 5 and6. By design, they are simple, efficient and easy to implement. However, the price for such simplicity must be paid on the analysis side.

Let us first intuitively discuss the requirements on the KEM for achieving formal security. Consider a KEM where the public key is designed with a particular shape, for example, the public key might always be composed of small coefficients. When encrypted, the distribution of the sent message would look uniformly distributed. However, any attacker may perform an offline dictionary attack: given an encrypted public key, it will be possible to leverage the particular public key form as a condition for the valid password. In such case, the correct password will be the one that decrypts to a public key with small coefficients. Hence, an indistinguishability property on the distribution of the public key, called fuzziness (formally defined in Definition 3), will be required to avoid offline dictionary attacks. Likewise, such property on the ciphertext, called anonymity (formally defined in Definition 4), will be essential. In addition, another important property should be fulfilled by the symmectric encryption to construct such PAKE. The needed property is ensured by the Ideal Cipher (IC) model [BPR00]. It consists in assuming that the encryption behaves like a random permutation on every key. While it does not retain clear weaknesses to use a relaxed model, an ideal cipher is necessary to unwrap the proofs of our theorems.

In this paper, we successfully prove our CAKE and OCAKE constructions in the UC model assuming the above properties, the random oracle model (ROM) and the erasure model stating that any obsolete internal information is erased.

Why two constructions? Similarly to EKE and OEKE, CAKE and OCAKE offer slightly different security/efficiency trade-offs. Let us compare both constructions:

-The first construction, CAKE, consists in encrypting both exchanged messages. It leads to an implicitly authenticated key exchange protocol based on passwords. However a participant is not sure that the opposing party is able to obtain the session key. This assurance can only be achieved by explicit authentication. The security model for proving CAKE is very strong as it captures adaptive corruptions. In other words, the model allows an attacker to corrupt a user and thus obtain all its internal state in an adaptive way during an ongoing execution of the protocol. -In order to add explicit authentication of the receiver, one usually includes a key-confirmation tag. In this case, one can remark with OCAKE that only one symmetric encryption is required. The second encryption is just replaced by the authentication that provides an explicit authentication to the receiver. However, this construction can only be proven secure in the static corruption model where the attacker may still corrupt users but the choice should be made before the execution of the protocol. Additionally, it is here possible to add an explicit client authentication at the end of the exchange to provide mutual explicit authentication.

In complement, we propose to show that the assumed properties on the KEM are not just artifacts that allow our proof to work. They are actually verified in concrete KEMs. We choose the example of Crystals-Kyber [SAB + 22] as our guinea pig for applying our transformations. Crystals-Kyber is a future NIST post-quantum standard. We formally demonstrate that Kyber validates fuzziness and anonymity leading up to security statements for CAKE-Kyber (Theorem 3) and OCAKE-Kyber (Theorem 4).

Outline of the paper

In Section 2, we introduce the preliminary notions on KEM, their security properties with some lattice definitions and a brief introduction to Kyber. In Section 3, we provide all the necessary information about PAKEs and their security in the UC model. In Section 4, we present both our KEM to PAKE transformations along with their security statements. For space reasons, the proofs are sketched in the main body of the paper and the full proofs are detailed in Appendices A and B. Finally, we demonstrate our techniques on Kyber in Section 5.

Preliminaries

Notations

We note scalars, vectors, and matrices with lowercase plain (i.e. n), lowercase bold (i.e. e), and uppercase bold (i.e. A), respectively. We denote by negl(κ) a negligible function of a security parameter κ. Given a finite set S, the notation x ←$ S means a uniformly random assignment of an element of S to the variable x. We note KEM the denomination of a key exchange mechanism and refer to KEM for the specific key encapsulation mechanism algorithm.

Key Encapsulation Mechanism

Even if the Key Encapsulation Mechanism's denomination is relatively recent, KEMs have been widely used throughout the history of public key cryptography. The first illustration is the fact that ElGamal [ElG85], based on the Diffie-Hellman key exchange, can be easily seen as a KEM. We will demonstrate later in this section that it enjoys several security notions, such as semantic security, fuzziness, and anonymity. Thereafter, with the NIST competition, many new researches have conducted to the introduction of KEM using a wide variety of -KeyGen: Returns a of pair public-secret keys (pk, sk) ∈ P × SK -Encaps: Takes a public key pk ∈ P as input to produce a ciphertext c ∈ C and a key K ∈ K. The ciphertext c is called an encapsulation of the key K;

-Decaps: Takes a secret key sk ∈ SK and an encapsulation c ∈ C as input, and outputs K ∈ K.

where SK, P, C, and K are the sets of secret keys, public keys, ciphertexts and session keys.

The formalization of the sets P, C, and K will impact the security notions presented in the sequel.

Correctness. The correctness of a KEM requires that, for a security parameter κ,

Pr (pk, sk) ←$ KeyGen(1 κ ) (c, K) ← Encaps(pk) : Decaps(sk, c) = K > 1 -negl(κ).
Security Notions. The usual security notion for KEM is semantic security, also known as indistinguishability:

Definition 2 (Indistinguishability). We define the advantage of any adversary A in deciding the key of the KEM by:

Adv ind KEM (A) = Pr D R [A(c, K) = 1] -Pr D $ [A(c, K ′ ) = 1] .
where we consider the real and random distributions

D R = {(pk, sk) ← KeyGen(1 κ ); (c, K) ← Encaps(pk) : (c, K)}, D $ = {(pk, sk) ← KeyGen(1 κ ); (c, K) ← Encaps(pk); K ′ ←$ K : (c, K ′ )}.
In all the advantage definitions, we will denote Adv ind KEM (t) the maximal advantage any adversary can have within time t. Let us introduce additional properties for KEMs, on the distributions of the public keys and of the encapsulations. We will denote by fuzziness the randomness of public keys, and by anonymity the randomness of the encapsulation. The latter is the usual definition, when the ciphertext distribution does not depend on the public key, and thus does not leak any information about the recipient.

Definition 3 (Fuzzy KEM).

A KEM is said fuzzy if the distribution of the public keys output by the KeyGen algorithm are computationally indistinguishable from uniform keys in P. More formally, we define the advantage of any adversary A in breaking the fuzziness of the KEM by:

Adv fuzzy KEM (A) = Pr D R [A(pk) = 1] -Pr D $ [A(pk) = 1] ,
where

D R = {(pk, sk) ← KeyGen(1 κ ) : pk} and D $ = {pk ←$ P : pk}.
Definition 4 (Anonymous KEM). A KEM is said anonymous if the distribution of the ciphertexts outputted by the Encaps algorithm are computationally indistinguishable from uniform ciphertexts in C. More formally, we define the advantage of any adversary A in breaking the anonymity of the KEM by:

Adv ano KEM (A) = Pr D R [A(c) = 1] -Pr D $ [A(c) = 1] ,
where

D R = {(pk, sk) ← KeyGen(1 κ ); (c, K) ← Encaps(pk) : c} and D $ = {c ←$ C : c}.
ElGamal Key Encapsulation Mechanism. In order to illustrate the above notions, let us consider the particular KEM derived from the so-called ElGamal encryption scheme [ElG85]. Let G be a group of prime order q, spanned by an element g:

-KeyGen(1 κ ): chooses a random x ←$ Z q and sets sk ← x, pk ← g x , with SK = Z q and P = G; -Encaps(pk): chooses a random r ←$ Z q and sets c ← g r , K ← pk r , with

C = G and K = G; -Decaps(sk, c): outputs K ← c sk .
It is well-know that the indistinguishability of this KEM relies on the Decisional Diffie-Hellman assumption. From the above description, this is clear that public keys are uniformly distributed in G, hence this KEM is fuzzy; and the ciphertexts are also uniformly distributed in G, thus this KEM is also anonymous. Note that the ElGamal KEM actually validates even stronger properties: perfect fuzziness (or smoothness) and perfect anonymity. The perfect nature comes from the fact that these notions are no longer computational but statistically ensured. As will be later stated in Remark 1, these properties are less common for postquantum KEM protocols and thus will not be considered as requirements for our constructions.

Learning with Errors

Three rounds of the NIST standardization campaign are already over and one type of hardness assumption seems to be more enticing: lattices. Lattice problems provide strong worst-case to average-case reductions, making them excellent candidates for long-term security. Indeed state of the art algorithm using quantum adversaries are not far more efficient compared to current existing algorithm to solve LWE. In this section, we introduce the Learning With Errors (LWE) [Reg06] assumptions. It can be divided into two problems: a decisional and a search problems. Both are assumed intractable in reasonable time, even for a quantum computer. Let us introduce the decisional version.

We directly consider this problem in a module structure named Module-LWE (we refer to [LS15] for more details). We define R q as the ring Z q [X]/(X n + 1). Let β η be the distribution on R q where each coefficient of the polynomial is generated according to a centered binomial distribution with parameter 2η. We define the oracle O mlwe m,k,η that outputs samples of the form

(A, b = A • s + e) with s ←$ β k η , A ←$ R m×k q
, and e ←$ β m η .

Definition 5 (Decisional MLWE m,k,η Problem). Given a set of parameters m, k, η ∈ N, the advantage of any probabilistic polynomial time algorithm A in deciding the d-MLWE over R q is:

Adv d-mlwe m,k,η (A) = Pr[(A, b) ← O mlwe m,k,η : A(A, b) = 1] -Pr[(A, b) ←$ R m×k q × R m q : A(A, b) = 1]
.

CRYSTALS-Kyber

Crystals-Kyber, also known as Kyber, is a Module-LWE-based KEM that is one of the most efficient post-quantum solutions. It was introduced in response to the NIST call for standardization of post-quantum primitives and was accepted as the first post-quantum standard for key exchange in 2022. In its original paper [BDK + 18], Kyber is proposed as a KEM that is secure against chosen-plaintext attacks (CPA-secure) and then achieves chosen-ciphertext attacks (CCA-secure) with the Fujisaki-Okamoto transform.

In Figure 1, we present the CPA-secure version of Kyber, where R q is the ring Z q [X]/(X n + 1). Following the last supplemented version (3.0) [SAB + 22], the suggested parameters are defined as follows: (X n + 1) is the 2n-th cyclotomic polynomial where n and q are equal respectively to 256 and q = 3329.

Additionally, for the sake of efficiency, Kyber includes an optimization using a compression function that can be thought of as a bit cut. While we do not use this compression in our protocol for the sake of clarity, it should be included in any implementation of our protocols using Kyber for maximum efficiency and correctness. We refer to the most recent NIST submission package [SAB + 22] for more detailed information.

3 Password Authenticated Key Exchange

Introduction to PAKE

Initially introduced by Bellovin and Merritt [BM92], a Password-Authenticated Key Exchange (PAKE) is a protocol that allows two parties to establish a shared secret session key over an insecure communication channel using a password as the only authentication means. The goal of PAKEs is to ensure that the key exchange is secure even if the password is weak or stolen by an attacker, the only possible attack being an online exhaustive search, which can be detected and stopped using some organizational action.

Kyber.KeyGen(1 κ )

1 : ρ, σ ←$ {0, 1} κ 2 : A ← R k×k q := Sam(ρ) 3 : (s, e) ← β k η × β k η := Sam(σ) 4 : b ← A • s + e 5 : return (pk = (ρ, b), sk = s) Kyber.Encaps(pk = (ρ, b)) 1 : τ ←$ {0, 1} κ 2 : m ←$ {0, 1} n ⊆ Rq 3 : A ← R k×k q := Sam(ρ) 4 : (r, e ′ , e") ← β k η × β k η × βη := Sam(τ ) 5 : u ← A T • r + e ′ 6 : v ← b T • r + e" + q 2 • m 7 : return c ← (u, v) Kyber.Decaps(sk = s, c = (u, v)) 1 : return 2 q v -s T • u
Fig. 1. Simplified Kyber KEM: Kyber.KeyGen, Kyber.Encaps, Kyber.Decaps PAKE protocols are handy when strong authentication is required while other forms of authentication (certificates) are not usable. They are often used in combination with other protocols to provide a secure channel for communication.

PAKE protocols might be vulnerable to two types of attacks: offline-dictionary attacks and online-dictionary attacks. The former occurs when an attacker gains knowledge of the password using pre computed lists of common passwords and exchanged information. Whereas, the latter involves an attacker actively trying to obtain the password by attempting to log in with different guesses. PAKE protocols often implement measures such as limiting the number of tries an attacker can make to guess the password to protect against online-dictionary attacks. Consequently, the security of a PAKE protocol ultimately relies on its resistance to offline-dictionary attacks. In other words, the strength of a PAKE protocol is determined by how difficult it is for an attacker to guess the password from the public transcript, even if it has a lof of time and resources.

The Universal Composability (UC) Model

Overview of the UC Framework. The Universal Composability (UC) model [Can01] is a simulation-based model in which an environment Z attempts to differentiate the output of a protocol execution Π in the real world from the output generated in an ideal world. In the real world, the execution takes place between parties and an potential adversary. In the ideal world, dummy players and an ideal adversary or simulator S interact solely with an ideal functionality F to compute a specific function f . The ideal functionality can be informally defined as a trusted party that honestly and unconditionally responds to any query. A schematic representation is given in Figure 2. The original paper [Can01] only uses sid as session identifiers, but a improved version of the UC model was published in [CR03] introducing subsession identifiers ssid. For more clarity, throughout this article we use ssid for (sid, ssid). More explicitly, two ssid could theoretically be equal on different sessions sid, but by setting ssid := (sid, ssid), we enforce the uniqueness of ssid. This uniqueness is necessary in the proofs provided in Appendices A and B.

The goal of the UC model is to emulate the protocol Π using the ideal functionality. If the emulation is performed such that the environment Z cannot distinguish (1) Π's outputs with possible interactions with an adversary A from (2) the outputs of dummy parties and a simulator interacting with the ideal functionality F, then one can state that Π UC-emulates F.

In our case, the protocols are Password-Based Authenticated Key Exchange (PAKE) and the ideal functionalities used throughout the paper specifically designed for PAKEs [CHK + 05,ACCP08] are F pwKE and F pwKE-sA (defined in Figures 3 and4).

Ideal Functionality F pwKE . We present here the ideal functionality that is used for PAKEs. A detailed description of the functionality is provided in Figure 3. It consists of three types of queries: NewSession, TestPwd and NewKey:

-NewSession allows a party to initialize a connection to another opposing party using its password. The functionality F pwKE uses this query to record the connection as well as the initial party's password. -TestPwd models the unique online password test (online dictionary attacks) that is enabled through the execution of a PAKE. This query additionally impacts the view of the ideal functionality. Querying TestPwd changes the view of F pwKE in the exchange of two parties by altering the behavior of the next query NewKey, according to the correct or incorrect guess. -NewKey interface allows to give parties a session key consistent with the state of their record. If two fresh entities do not share/use the same password then PAKE Ideal Functionality: FpwKE

Session Initialization

On (NewSession, ssid, pw, Pi, Pj) from Pi:

-Sends (NewSession, ssid, Pi, Pj) to A.

-If this is the first NewSession query, or if it is the second NewSession query and there is a record (ssid, Pj, Pi, pw ′ , ⋆) ∈ L, then record (ssid, Pi, Pj, pw, fresh) in L.

Active attack

Upon receiving a query (TestPwd, ssid, Pi, pw ′ ) from the adversary A, if there exists record (ssid, Pi, Pj, pw, fresh) ∈ L, do:

-If pw = pw ′ mark the record as compromised and reply to A with "correct guess".

-If pw ̸ = pw ′ , mark the record as interrupted and reply to A with "wrong guess".

Key Generation

Upon receiving a query (NewKey, ssid, Pi, SK) from S, where SK ∈ {keys}, if there is a record of the form (ssid, Pi, Pj, pw, status) ∈ L, for any value status, and this is the first NewKey query for Pi:

-If status = compromised, or if one of the players Pi or Pj is corrupted then send (ssid, SK) to Pi; -If status = fresh and there is a record (ssid, Pj, Pi, pw ′ , status ′ ) with pw ′ = pw, and a session key SK ′ has been sent to Pj, that was fresh at that time, then send (ssid, SK ′ ) to Pi; -Else, choose a random key SK ′ whose length is k and send (ssid, SK ′ ) to Pi.

Update the record as completed. F pwKE does not give them the same key. Contrarily, if they do, this oracle returns the same key for both parties. However the behavior is more refined than that and takes account possible alterations from TestPwd (more details in Figure 5).

Ideal Functionality with server authentication F pwKE-sA . We present a variation F pwKE-sA of the previous ideal functionality to add explicit server authentication. A detailed description of the functionality is provided in Figure 4.

in each record in L (defined in Figure 3 and 4), we add a component role ∈ {client, server}. From this point forward, L has components of the form (ssid, P i , P j , pw, status, role). -If the client queries NewKey at a time when the server still has not queried NewKey in the same session ssid, then F pwKE-sA does nothing. -If P i and P j do not share the same password: then the client gets abort whatever the status is.

PAKE Ideal Functionality with server Authentication: FpwKE-sA

Session Initialization

On (NewSession, ssid, role, pw, Pi, Pj) from Pi:

-Sends (NewSession, ssid, role, Pi, Pj) to A.

-If this is the first NewSession query, or if it is the second NewSession query and there is a record (ssid, Pj, Pi, pw ′ , ⋆, ⋆) ∈ L, then record (ssid, Pi, Pj, pw, fresh, role) in L.

Active attack

Upon receiving a query (TestPwd, ssid, Pi, pw ′ ) from the adversary A, if there exists record (ssid, Pi, Pj, pw, fresh, role) ∈ L, do:

-If pw = pw ′ mark the record as compromised and reply to A with "correct guess".

-If pw ̸ = pw ′ , mark the record as interrupted and reply to A with "wrong guess".

Key Generation

Upon receiving a query (NewKey, ssid, Pi, SK) from S, where SK ∈ {keys}, if there is a record of the form (ssid, Pi, Pj, pw, status, role) ∈ L, for any value status, and this is the first NewKey query for Pi:

if role = client • If status = compromised, or if one of the players Pi or Pj is corrupted and there exists two records (ssid, Pi, Pj, pw, client) and (ssid, Pj, Pi, pw, server) then send (ssid, SK) to Pi; • Else if status = fresh and there is a record (ssid, Pj, Pi, pw ′ , client ′ ) with pw ′ = pw, and a session key SK ′ has been sent to Pj, that was fresh at that time, then send (ssid, SK ′ ) to Pi. Else if pw ′ ̸ = pw, choose a random key SK ′ whose length is k and send (ssid, SK ′ ) to Pi. • Else if status = fresh, and if no record completed record exists for Pj in ssid do nothing.

• Else if status = interrupted, send (ssid, error) to Pi. -if role = server • If status = compromised, or if one of the players Pi or Pj is corrupted then send (ssid, SK) to Pi; • Else if status = fresh or status = interrupted, choose a random key SK ′ ∈ {keys} and send (ssid, SK ′ ) to Pi.
Update the record as completed. Model. To prove that a protocol UC-emulates F pwKE or F pwKE-sA , we first need to set the model and assumptions for the proof. In this paper, we consider the Random Oracle Model (ROM) and the Ideal Cipher (IC) model. We also make use of the erasure model and assume that the adversary A is able to perform either adaptive or static corruptions, depending on the protocol.

Random Oracle. We use the definition of ROM introduced by Hofheinz and Müller-Quade [HM04] recalled in Figure 12 from Appendix C. This assumption provides a powerful tool that coherently responds to queries and generates answers that are uniformly random and independent of the input of the query.

Ideal Cipher. The ideal cipher model was first introduced in [BPR00]. It considers that a cipher behaves as a perfectly independent random permutation for every key used.We will generalize it a little bit by differentiating the input set and the output set, and then considering random bijections for every key. This model is presented in more details in Figure 13 from Appendix C.

Corruption. As mentioned earlier, we consider two types of corruptions in this paper: static corruptions and adaptive corruptions. Static corruptions allow the adversary to obtain the password of a party prior to the execution of the protocol. This means that during a simulation, the simulator knows which parties have been corrupted. Adaptive corruptions allow the adversary to corrupt any party during the execution of the protocol by revealing the password and internal state of the party. The adaptive corruption functionality is defined in Figure 14 of Appendix C.

Erasure model. The erasure model is a simple but powerful assumption. In this model, we assume that any internal information that is no longer useful ceases to exist. Therefore, in the event of information leakage, or adaptive corruption, previous internal information is not leaked as it no longer exists.

4 Two Pieces of One Cake: Study of EKE and OEKE

In this study, we propose to examine the use of KEM with specific properties in the context of EKE and One-Way Encrypted Key Exchange (OEKE). We first introduce an evolved version of EKE called CAKE, that provides implicit authentication only, and then extend it to OEKE using a variant called OCAKE, that additionally provides explicit authentication of the receiver. We prove the security of these protocols in the Universal Composability (UC) model, assuming three properties of the KEM: semantic security, fuzziness, and anonymity. These two studies offer a balance between security properties and efficiency: CAKE handles adaptive corruptions, while OCAKE is proven secure in a relaxed model that only allows static corruptions to provide explicit authentication.

Alice : A, pw ssid Bob : B, pw (pk, sk) ← KEM.KeyGen(1 κ ) Epk ← E1(ssid∥pw, pk) A, Epk pk ← D1(ssid∥pw, Epk) (c, K) ← KEM.Encaps(pk) Ec ← E2(ssid∥pw, c) B, Ec c ′ ← D2(ssid∥pw, Ec) K ′ ← KEM.Decaps(sk, c ′ ) SK ← H(ssid, A, B, Epk, Ec, K ′ ) SK ← H(ssid, A, B, Epk, Ec, K)
Fig. 5. CAKE with (E1, D1), (E2, D2) two pairs of ideal ciphers. E1 is a bijection from P to P ′ while E2 is a bijection from C to C ′ .

CAKE

In this subsection, we present a study of the K(EM)-EKE protocol, referred to as CAKE. This protocol is based on the use of generic KEM in EKE and is the most conservative of the two constructions we propose.

To study CAKE properly, as well as expressing the necessary properties on the underlying KEM, we first fix a KEM (KeyGen, Encaps, Decaps) with the sets SK, P, C, and K as in Definition 1. Next, we define two ideal cipher pairs (E 1 , D 1 ) and (E 2 , D 2 ). We additionally define a set of keys Key and two sets P ′ and C ′ respectively bijections from P and C where both of them offer easy uniform sampling:

E 1 : Key × P → P ′ E 2 : Key × C → C ′ D 1 : Key × P ′ → P D 2 : Key × C ′ → C
The actual keys of the ideal ciphers are the concatenations of the ssid and the passwords, to ensure independent bijections between different executions of the protocol. We introduce a description of CAKE in Figure 5 along with its security theorem based on the fuzziness and anonymity of the underlying KEM in the ROM and IC models, while allowing adaptive corruptions.

Theorem 1. Let (E 1 , D 1 ), (E 2 , D 2 ) be two pairs of ideal ciphers and H be a random oracle. We note q D1 (resp. q D2 ) the maximal number of queries to the decryption oracle D 1 (resp. D 2 ). We also note q E1 (resp. q E2 ) the maximal number of queries to the encryption oracle E 1 (resp. E 2 ) explicitly asked by the adversary. Finally, we note q s the number of sessions. The CAKE protocol described in Figure 5 using KEM, a key encapsulation mechanism that is both fuzzy (Def. 3) and anonymous (Def. 4) ensuring semantic security, UC-emulates F pwKE in the erasure model with adaptive corruptions. More precisely, if we define Adv cake KEM (A) the advantage of an adversary A to break the above claim, it is bounded by

(2q s + q D1 + q D2 ) • Adv ind KEM (t) + (q s + q D1 ) • Adv fuzzy KEM (t) + q D1 • (q s + q D2 ) • Adv ano KEM (t) + q H • q s • 2 -λ k + q 2 E1 • 2 -λp-1 + q 2 E2 • 2 -λc-1 ,
where λ k is the bit-length of the encapsulated keys, λ p the bit-length of the public keys, and λ c the bit-length of the ciphertexts, for the KEM scheme.

Sketch of Proof: In the subsequent games, we denote Pr[G] the probability for the environment Z to output 1 in the simulated game G. The goal is to prove that Pr[G] is close to the probability to output 1 in the ideal game, while starting from the real game G 0 . The sequence of games will end with G 9 that only uses the ideal functionality F pwKE , and is thus the ideal game. The complete proof can be found in the Appendix A. We present here a sketch of proof:

G 0 :
(pk, sk) ← KEM.KeyGen(1 κ ) Epk ← E(ssid∥pw, pk) A, Epk pk ← D(ssid∥pw, Epk) (c, K) ← KEM.Encaps(pk) Auth ← H1(ssid, A, B, pw, Epk, c, K) B, c, Auth K ′ ← KEM.Decaps(sk, c) H1(ssid, A, B, pw, Epk, c, K ′ ) ? = Auth SK ← H2(ssid, A, B, Epk, c, Auth, K) SK ← H2(ssid, A, B, Epk, c, Auth, K)
Fig. 6. OCAKE with (E, D) an ideal cipher. E is a bijection from P to P ′ .

instead of a Diffie-Hellman based key exchange.

In this setting, we only handle static corruptions in the security model. Indeed, it would have been possible to include adaptive corruptions in the security model with a statistical notion for the anonymity, i.e. perfect anonymity. But the computational property of our anonymity definition (see Definition 4) is more realistic for post-quantum KEM protocols. And thus here, adaptive corruptions cannot be handled by our proof in the UC-framework: in case of honest transcripts, we must generate a random c, on behalf of Bob. In case of Alice's corruption, one can program E in order to set a specific (pk, sk), but if the simulator commits on a specific c, then it cannot remain consistent. In particular, the adversary could have tried many passwords when decrypting Epk, hence one cannot anticipate the public key for c.

In order to thoroughly study this approach, we outline the modifications in Fig. 6. We remove one encryption on the server flow to change it into an authentication. However for the sake of the proof, we have to slightly change how the hash query is usually done. Instead of using the public transcript, we use part of the secret information for the sake of the simulation in the security proof. Lastly we use F pwKE-sA in Fig. 4: the PAKE ideal functionality with explicit authentication of the server.

Theorem 2. Let (E, D) be a pair of ideal cipher. Let H 1 and H 2 be two random oracles. We note q D the maximal number of queries to the decryption oracle D. We also note q E the maximal number of queries to the encryption oracle E, explicitly asked by the adversary. And we note q s the number of sessions. The OCAKE protocol described in Figure 6 using KEM, a key encapsulation mechanism that is both fuzzy (Def. 3) and anonymous (Def. 4) while ensuring semantic security, UC-emulates F pwKE-sA in the erasure model with static corruptions. More precisely, if we define Adv ocake KEM (A) the advantage of an adversary A to break the above claim is bounded by

(q s + q D ) • Adv fuzzy KEM (t) + (q s + q D + 1) • Adv ind KEM (t) + q D • Adv ano KEM (A) + (q H1 + 2q s ) 2 • 2 -λH 1 -1 + q 2 E • 2 -λp-1 + (q H1 + q H2 ) • q s • 2 -λ k ,
where λ k is the bit-length of the encapsulated keys, λ p the bit-length of the public keys for the KEM scheme, and λ H1 the bit-length of the authentication tag.

Sketch of Proof: Similarly to the proof of Theorem 1, in the subsequent games, we denote Pr[G] the probability for the environment Z to output 1 in the simulated game G. The goal is to prove that Pr[G] is close to the probability to output 1 in the ideal game, while starting from the real game G 0 . The sequence of games will end with G 8 that only uses the ideal functionality F pwKE-sA , and is thus the ideal game. The complete proof can be found in the Appendix B. We present here a sketch of proof:

G 0 : Real world protocol using the following assumptions: erasure model, random oracle, ideal cipher, static corruption and lastly a fuzzy and anonymous KEM, which is also indistinguishable. G 1 : Honest simulation of two random oracles H 1 , H 2 and an ideal cipher (E, D)

from Figure 6, where we abort in case of collision during explicit encryption calls. Additionally a private simulation of each random oracle H * 1 , H * 2 used for the simulation when S does not know any passwords. We also exclude collisions on H 1 and H * 1 . G 2 : Embedding of the secret keys during the simulation of D. Additional remarks :

Removing the cipher on pk and keeping it on c like OEKE is not possible.

To follow strictly its framework one would need a perfectly anonymous KEM otherwise the client could construct a subset attack using the gap of a misconstructed cipher on decryption. Furthermore, we place our study in the context of quantum-secure KEM and none of them allows for perfect anonymity. Therefore the strict OEKE framework is not an enticing approach for longterm usability.

This protocol is only secure against static corruptions. An adversary allowed to apply adaptive corruptions could corrupt the client a reception of (c, Auth) before it computes Decaps. The adversary would then obtain sk because Decaps needs it and implies that the erasure is not applied. Knowing sk, a random c ←$ C is easily recognizable from a honestly built one leading the adversary to distinguish the simulation in the above proof. Adding an authentication of the client afterwards for mutual authentication is entirely possible. The proof extensively use tricks before the derivation of the session key to either extract private information or to send indistinguishable random elements. Since this is done before, either the client would send a honest authentication, a perfectly indistinguishable one or a recognizable wrong one.

5 Crystal-Kyber

Security Properties

Crystals-Kyber has been introduced in Section 2. For the following results, we set

P = {0, 1} κ × R k q , SK = β k η , C = R k q × R q and K = {0, 1} n .
First of all, we recall the indistinguishability property of Crystals-Kyber [BDK + 18]: Lemma 1. Kyber on parameters (k, η, q, n) is an indistinguishable KEM:

Adv ind Kyber (A) ≤ Adv d-mlwe k,k,η (t) + Adv d-mlwe k+1,k,η (t)
Next, let us verify the anonymity and fuzziness properties guaranteed by Kyber.

Lemma 2. Crystals-Kyber is an anonymous KEM in C = R k q × R q :

Adv ano Kyber (A) ≤ Adv d-mlwe k,k,η (t) + Adv d-mlwe k+1,k,η (t) Proof. Let sample a public key pk ←$ (A, b), by definition of Kyber in Figure 1 c = (u, v) with u = A T • r + e ′ v = b T • r + e ′′ + q 2 • m We can rewrite c as: u v ← A b T r + e ′ e ′′ + q 2 • m It forms a Module-LWE instance A b T , u v provided that (A, b) is uni- formly random on R k×k q
×R k q which is true under the d-MLWE k,k,η assumption. This directly gives:

Adv ano Kyber (A) ≤ Adv d-mlwe k+1,k,η (t) + Adv d-mlwe k,k,η (t) ⊓ ⊔
To prove anonimity in lemma 2, Kyber needs to ensure the decisional MLWE argument, therefore:

Corollary 1. Crystals-Kyber is a fuzzy KEM with P = R k q :

Adv fuzzy Kyber (A) ≤ Adv d-mlwe k,k,η (t)

Theorem 3. Let (E 1 , D 1 ), (E 2 , D 2 ) be two pairs of ideal ciphers, and H a random oracle. We note q D1 (resp. q D2 ) the maximal number of queries to the decryption oracle D 1 (resp. D 2 ), explicitly asked by the adversary, and q s the number of session. The CAKE protocol from Figure 5 instantiated with Kyber UC-emulates F pwKE in the erasure model with adaptive corruptions:

Adv cake Kyber (A) ≤ ((5q s + 3q D1 + 2q D2 ) + 2q D1 • (q s + q D2 )) • Adv d-mlwe k+1,k,η (t) + q H • q s • 2 -n + q -kn • (q 2 E1 • 2 -κ + q 2 E2 • q -n )/2
Theorem 4. Let (E, D) be an ideal cipher, and H 1 , H 2 two random oracles. We note q D the maximal number of queries to the decryption oracle D, explicitly asked by the adversary, and q s the number of session. The OCAKE protocol from Figure 6 instantiated with Kyber UC-emulates F pwKE-sA in the erasure model with static corruptions:

Adv ocake Kyber (A) ≤ 2 • q D • (Adv d-mlwe k+1,k,η (t)) + 3 • q D • (Adv d-mlwe k,k,η (t)) + (q H1 + q H2 ) • q s • 2 -n + q 2 E • 2 -κ + q H1 • 2 -n

Instantiation of the Block Cipher

To prove the UC-security of both CAKE-Kyber and OCAKE-Kyber, the ideal cipher model is crucial. More precisely it needs to ensure that finding a collision on the encryption is statistically impossible without querying a decryption oracle. It removes both the following approaches out of the equation: stream cipher and one time pad. The conception of a relevant block cipher for our transformations is actually nontrivial. In fact, the underlying sets, like R q , are not convenient for building a symmetric block cipher statistically following the necessary ideal properties. We present here a solution issued from known ad-hoc techniques. We believe that it can be improved for better performance but this task is left as future work.

To keep light notations, we do not encrypt the seed of A, and thus consider the encryption of an element in R k q ∼ Z n×k q for the public key. We can do the same with R k q × R q ∼ Z n×(k+1) q

for the ciphertext. To encrypt pk ∈ R k q ∼ Z n×k q , we can first encode pk into {0, . . . q nk -1}, and then use a block cipher on ℓ-bits, such that 2 ℓ-1 ≤ q nk < 2 ℓ . We thus have an encoding/decoding from R k q to {0, 1} ℓ that can be seen as a superset of {0, . . . q nk -1}. Let us thus consider all these encodings equivalent.

From (E, D) on ℓ-bit blocks and κ-bit keys, we can build a permutation onto the restricted set {0, . . . q nk -1}: one defines the encryption scheme with key K on b ∈ R k q ∼ {0, . . . q nk -1} as E ′ K (b) = E K (. . . E K (b) . . .), stopping at the first element in {0, . . . q nk -1}. Decryption works the same way, and will stop at the right place as all ignored intermediate values are outside the expected set.

Actually, the number of iterations will be small, as there is a probability less than 1/2 at each step. This technique is vulnerable to timing attacks, but one can always include virtual loops.

We emphasize that this study is done without using the optimized Kyber (without) the compression, decompression functions. However, these two functions map elements of Z q to Z q ′ with q ′ < q, therefore the study remains similar.

Parameters

The bounds in Theorems 3 and 4 are slightly looser than the ones that constrain the choice of parameters for Kyber. Thus, some adaptations of the obtained security levels are necessary. We propose to recompute the security level for the set of parameters taken from Kyber's last submission to the NIST [SAB + 22] and choosing parameters that allow to reach around 100 bits of security against quantum adversaries. While this can be argued to be weak, PAKE are not used in highly critical applications but in highly efficient ones. Hence, 100 bits of security against quantum adversaries would constitute a mid to long-term security target.

We present in Table 1 the security estimations for CAKE-Kyber and OCAKE-Kyber obtained with the pq-crystal estimate [DS21] against a quantum adversary with KYBER768 and KYBER1024 parameters. The security/efficiency trade-off between CAKE and OCAKE is confirmed in this example. According to Table 1, CAKE provides more conservative assumptions as an adaptive adversary are included in the model however it is less efficient that its OCAKE alternative.

Conclusion and perspectives

In this article we characterize the necessary properties for a key encapsulation mechanism to be used in a password authenticated key exchange and more precisely in both EKE and OEKE. Additionally we prove that these properties are respected by the newly standardized Kyber. To supplement this study we introduce a set of possible parameters for Kyber, ensuring around 100 bit of security. Lastly we propose a cipher respecting statistically ideal cipher properties for the application of both CAKE (Fig. 5) and (OCAKE Fig. 6). While our work focuses on post-quantum alternatives, one could improve our results by supposing a random self-reducible KEM (like El-Gamal). Random selfreducibility implies that arbitrarily many independant instances can be reduced to only one such instance. Although current post-quantum schemes are not selfreducible KEM but such an assumption would lead to tighter reductions and it would allow for SPEKE or CPace constructions to be generalized to more KEM protocols.

Game G 0.2 : In this game, we simulate an ideal cipher from the first exchange of the protocol. The simulation of this oracle needs to be consistent, meaning that any query that has already been asked should return the same answer as the first time it was asked. Additionally, the simulation needs to capture the properties of an ideal cipher, which means simulating each encryption as a random bijection for each key (actually, for each ssid∥pw). But for the following simulation, we will need to avoid collisions during adversary's encryption with different inputs. Then, the simulator uses a list called Λ 1 for encryption and decryption queries on each oracle. Λ 1 is composed of tuples of the form (ssid, pw, pk, sk, E 1 ∨ D 1 , Epk), even if the component sk will only appear later. S simulates E 1 and D 1 as follows:

-On E 1 (ssid∥pw, pk):

• If there exists a record (ssid, pw, pk, ⋆, ⋆, Epk) ∈ Λ 1 then S returns Epk.

• Else, S samples Epk ←$ P ′ . If Epk already exists in Λ 1 , S aborts, else S records (ssid, pw, pk, ⊥, E 1 , Epk) in Λ 1 and returns Epk. -On D 1 (ssid∥pw, Epk):

• If there is a record (ssid, pw, pk, ⋆, ⋆, Epk) ∈ Λ 1 , S returns pk.

• Else, S samples pk ←$ P, records (ssid, pw, pk, ⊥, D 1 , Epk) in Λ 1 , and returns pk.

Analysis: Under the assumption of the Ideal Cipher model depicted by its ideal functionality, Z can distinguish the real execution of the protocol from this game if S aborts. Assuming the cardinal of P is 2 λp , and if A makes up to q E1 queries to the encryption oracle then by the birthday paradox bound:

| Pr[G 0.2 ] -Pr[G 0.1 ] | ≤ q 2 E1 • 2 -λp-1
Game G 0.3 : This game handles the simulation of the second ideal cipher for the encryption of the ciphertext c. Equally to the previous game, S uses a list Λ 2 . Λ 2 is a list of items (ssid, pw, c, K, E 2 ∨ D 2 , Ec), even if the component K will only appear later. S simulates E 2 and D 2 as follows:

-On E 2 (ssid∥pw, c):

• If there exists a record (ssid, pw, c, ⋆, ⋆, Ec) ∈ Λ 2 then S returns Ec.

• Else, S samples Ec ←$ C ′ . If Ec already exists in Λ 2 , S aborts, else S records (ssid, pw, c, ⊥, E 2 , Ec) in Λ 2 and returns Ec. -On D 2 (ssid∥pw, Ec):

• If there is a record (ssid, pw, c, ⋆, ⋆, Ec) ∈ Λ 2 , S returns c.

• Else, S samples c ←$ C, records (ssid, pw, c, ⊥, D 2 , Ec) in Λ 2 , and returns c.

Analysis: Similarly to the simulation of E 1 , Z is able to distinguish this simulation from the previous game if and only if S aborts. Assuming the cardinal of C is 2 λc , and if A makes up to q E2 queries to the encryption oracle then by the birthday paradox bound:

| Pr[G 0.3 ] -Pr[G 0.2 ] | ≤ q 2 E2 • 2 -λc-1 Eventually, as G 1 = G 0.3 , | Pr[G 1 ] -Pr[G 0 ] | ≤ q 2 E1 • 2 -λp-1 + q 2 E2 • 2 -λc-1 .
Game G 2 : Embedding of the Secrets. In this game we embed the associated secret keys in the simulation of both D 1 and D 2 . We do it in two steps, first dealing with D 1 in G 1.1 and then with D 2 in G 2 = G 1.2 :

Game G 1.1 : We change the simulation of D 1 and introduce the component sk in the records in Λ 1 :

-On D 1 (ssid∥pw, Epk):

• If there is a record (ssid, pw, pk, ⋆, ⋆, Epk) ∈ Λ 1 , S returns pk.

• Else, S builds (pk, sk) ← KeyGen(1 κ ), records (ssid, pw, pk, sk, D 1 , Epk) in Λ 1 , and returns pk.

Analysis:

The unique difference is a real public key instead of a random public key, which is exactly the fuzziness of the KEM, that we apply q ′ D1 times in a hybrid sequence of games:

| Pr[G 1.1 ] -Pr[G 1 ] | ≤ q ′ D1 • Adv fuzzy KEM (t)
We stress that q ′ D1 will be the number of all the queries to D 1 done by the simulator and by the adversary. This might be larger than the sole number q D1 of queries asked by the adversary.

Game G 1.2 : Similarly to the previous subgame we change the simulation of D 2 , and introduce the component K in the records in Λ 2 , but only for specific decryption calls by the simulator itself, with an additional input pk, that has necessarily been generated during the above simulation of D 1 :

-On D * 2 (ssid∥pw, Ec, pk), by S: • If there is a record (ssid, pw, c, ⋆, ⋆, Ec) ∈ Λ 2 , S returns c.

• If there is no record (ssid, pw, pk, ⋆, D 1 , ⋆) ∈ Λ 1 , S aborts.

• Else, S builds (c, K) ← Encaps(pk), records (ssid, pw, c, K, D 2 , Ec) in Λ 2 , and returns c. -On D 2 (ssid∥pw, Ec), by A, there is no change:

• If there is a record (ssid, pw, c, ⋆, ⋆, Ec) ∈ Λ 2 , S returns c.

• Else, S samples c ←$ C, records (ssid, pw, c, ⊥, D 2 , Ec) in Λ 2 , and returns c.

We will have to make sure the simulation never aborts here, with pk randomly generated (not under control of the adversary), without needing sk.

Analysis: As above, the unique difference is a real ciphertext instead of a random ciphertext, which is exactly the anonymity of the KEM, that we apply q * D2 times (the number of explicit D * 2 queries by the simulator) in a hybrid sequence of games, by guessing the good D 1 -query for pk:

| Pr[G 1.2 ] -Pr[G 1.1 ] | ≤ q D1 • q * D2 • Adv ano KEM (t) As G 2 = G 1.2 , | Pr[G 2 ] -Pr[G 1 ] | ≤ q ′ D1 • Adv fuzzy KEM (t) + q D1 • q * D2 • Adv ano KEM (t).
Game G 3 : Simulation of Alice's Initialization. In this game, S simulates the first flow of Alice, using D 1 instead of E 1 : it samples Epk ←$ P ′ , asks for pk ← D 1 (ssid∥pw A , Epk), which also generates sk, and sends Epk to Bob. This makes no difference from the previous game:

| Pr[G 3 ] -Pr[G 2 ] | = 0.
Game G 4 : Simulation of Bob's Answer. In this game, S simulates the second flow from an honest Bob, upon receiving Epk. The behavior of S depends on the origin of the message Epk: whether it comes from a honest Alice, or from the adversary A, that has corrupted, or not, Alice. We thus do it in two steps, from G 3 , with G 3.1 that deals with honestly generated Epk, and G 4 = G 3.2 that deals with adversarially generated Epk.

Game G 3.1 : Epk comes from Alice. Epk comes from the above simulation, with (pw A , pk, sk, D 1 , Epk) in Λ 1 . S asks for pk ′ ← D 1 (ssid∥pw B , Epk), which is either pk if the passwords are the same, or another pk ′ , with associated sk ′ . S samples Ec ←$ C ′ , asks for c ← D * 2 (ssid∥pw B , Ec, pk ′ ), computes K ← Decaps(sk ′ , c), and sends Ec to Alice. This makes no difference from the previous game, as pk ′ really comes from D 1 .

Game G 3.2 : Epk comes from A. From the uniqueness of Epk in Λ 1 , from explicit encryption E 1 (or no record at all), S can extract at most one pair (pw, pk) used by A:

-If pw = pw B , with pk: S continues as Bob would do. It builds (c, K) ← Encaps(pk), Ec ← E 1 (ssid∥pw B , c), and SK ← H(ssid, P i , P j , Epk, Ec, K). -Else (pw ̸ = pw B , or pw = ⊥): S asks for pk ← D 1 (ssid∥pw B , Epk), with sk, samples Ec ← C ′ , asks for c ← D * 2 (ssid∥pw B , Ec, pk), computes K ← Decaps(sk, c), and SK ← H(ssid, P i , P j , Epk, Ec, K).

This makes no difference from the previous game. As this last game

G 3.2 is G 4 , | Pr[G 4 ] -Pr[G 3 ] | = 0.
Game G 5 : Preparation of Alice's Reaction. We create a new list Λ Epk , with records of the form (ssid, Epk), initialized as an empty list. We first update the simulation of the first flow of Alice: for a new session with ssid, if there is a record (ssid, Epk) ∈ Λ Epk , S uses this Epk, otherwise it samples an Epk ←$ P ′ , and adds (ssid, Epk) to Λ Epk .

For any query D 2 (ssid∥pw, Ec) asked by the adversary or the simulator:

-If there is a record (ssid, pw, c, ⋆, ⋆, Ec) ∈ Λ 2 , S returns c.

-If there is a record (ssid, Epk) ∈ Λ Epk it uses Epk, otherwise it samples an Epk ←$ P ′ , and adds (ssid, Epk) to Λ Epk . Then, S first asks for pk ′ ← D 1 (ssid∥pw, Epk), with sk ′ , and then asks for D * 2 (ssid∥pw, Ec, pk ′ ) with K ′ .

This makes no difference from the previous game, if we take care of the additional D 1 queries, as Epk is still randomly sampled in

P ′ : | Pr[G 5 ] -Pr[G 4 ] | = 0.
Game G 6 : Simulation of Alice's Reaction. In this game, S simulates the key computation by Alice, upon receiving Ec, which has been sent by either an honest Bob or the adversary. S first recovers Alice's secret key sk generated during the first honest flow. Then, we proceed in two steps, from G 5 , with G 5.1 that deals with honestly generated Ec, and G 6 = G 5.2 that deals with adversarially generated Ec.

Game G 5.1 : Ec comes from Bob. We thus have (ssid, pw, c, K,

D 2 , Ec) in Λ 2 . If pw = pw A , we have both equalities c = c ′ ← D 2 (ssid∥pw A , Ec) and K = K ′ ← Decaps(sk, c ′ ):
then Alice and Bob have the same final session keys SK = SK ′ ← H(ssid, P i , P j , Epk, Ec, K ′ ). If pw ̸ = pw A , we have both inequalities (excepted by chance) c ̸ = c ′ ← D 2 (ssid∥pw A , Ec) and K ̸ = K ′ ← Decaps(sk, c ′ ): then SK ′ ← H(ssid, P i , P j , Epk, Ec, K ′ ) is independent from the SK computed by Bob, excepted with random equality, which makes no difference from the previous game.

Game G 5.2 : Ec comes from A. From the uniqueness of Ec in Λ 2 , from explicit encryption E 2 (or no record at all), S can extract at most one pair (pw, c) used by A:

-If pw = pw A , with c: S computes K ′ ← Decaps(sk, c) as well as the session key SK ′ ← H(ssid, P i , P j , Epk, Ec, K ′ ). -Else (pw ̸ = pw A , or pw = ⊥): S asks for c ′ ← D 2 (ssid∥pw A , Ec), computes K ′ ← Decaps(sk, c ′ ), and gets SK ′ ← H(ssid, P i , P j , Epk, Ec, K ′ ).

We stress that we use the above simulation of D 2 . This makes no difference from the previous game. As this last game

G 5.2 is G 6 , | Pr[G 6 ] -Pr[G 5 ] | = 0.
Game G 7 : Random Session Keys. Thanks to the above simulation of the ideal ciphers, S has the ability to extract the tentative password used by the adversary. It will be given access to two boolean functions;

-GoodPwd with input (ssid, P i , pw) that answers whether this is the correct password of party P i . -SamePwd with input (ssid, P i , P j ) that answers whether P i and P j share the same password.

We first replace session key K generation, for honest players, without knowing the passwords, by using SamePwd when it did not extract the password and GoodPwd when it successfully extracted pw using a private random oracle H * K onto K, in G 6.1 . We then replace the final session key SK generation in G 7 = G 6.2 .

Game G 6.1 : Random K ′ . We first use a private random oracle H * K onto K to replace K by random K ′ , in some situations: On Bob's Side: Upon receiving Epk -From an honest Alice, instead of setting SK ← H(ssid, P i , P j , Epk, Ec, K), if SamePwd(ssid, P i , P j ) = true, one sets K ′ ← H * K (ssid, success) otherwise one sets K ′ ← H * K (ssid, fail B ), and updates the definition SK ← H(ssid, P i , P j , Epk, Ec, K ′ ).

-From A, with extracted password pw: if GoodPwd(ssid, P j , pw) = true, one keeps SK ← H(ssid, P i , P j , Epk, Ec, K); else one sets K ′ ← H * K (ssid, fail B ), and updates the definition SK ← H(ssid, P i , P j , Epk, Ec, K ′ ). On Alice's Side: Upon receiving Ec -From an honest Bob, instead of setting SK ← H(ssid, P i , P j , Epk, Ec, K), if SamePwd(ssid, P i , P j ) = true, one sets K ′ ← H * K (ssid, success) otherwise one sets K ′ ← H * K (ssid, fail A ), and updates the definition SK ← H(ssid, P i , P j , Epk, Ec, K ′ ).

-From A, with extracted password pw: if GoodPwd(ssid, P i , pw) = true, one keeps SK ← H(ssid, P i , P j , Epk, Ec, K ′ ); else sets K ′ ← H * K (ssid, fail A ), and updates the definition SK ← H(ssid, P i , P j , Epk, Ec, K ′ ).

Analysis: We replace real keys K by random independent keys K ′ , excepted when interacting with the adversary that has guessed the password. In all the modified sessions, K has been generated from a fresh KEM instance: From an honest Alice, Bob always uses a pk coming from D 1 and a c coming from D * 2 ; if this comes from A, unless the password was correctly guessed, pk also comes from D 1 and c from D * 2 . On Alice's side, unless the password was correctly guessed by the adversary, pk also comes from D 1 and c from D * 2 , thanks to the list Λ Epk that prepared Epk in advance for any session. We can thus proceed with a sequence of hybrid games, replacing real keys by random keys.

-On Bob's side, the pairs come from D 1 and D * 2 , with known (pk, sk) and (c, K), with a unique call D * 2 per session: we can simply successively replace (pk, c, K) by (pk, c, K ′ ), using the indistinguishability of the KEM: the gap is bounded by q ′ D1 • Adv ind KEM (t). -On Alice's side, the pairs come from D 1 and D * 2 , with known (pk, sk) and (c, K), but will have multiple generations per session: essentially, for each query D 2 , such a tuple must be created. We can successively replace (pk, c, K) by (pk, c, K ′ ), using the indistinguishability of the KEM: the gap is bounded by q ′ D2 • Adv ind KEM (t), where q ′ D2 is the number of all the queries to D 2 asked by the simulator and by the adversary.

We thus have

| Pr[G 6.1 ] -Pr[G 6 ] | ≤ (q ′ D1 + q ′ D2 ) • Adv ind KEM (t).
Game G 6.2 : Random SK. We now replace SK by random SK ′ , in some situations:

On Bob's Side: Upon receiving Epk -From an honest Alice, instead of setting SK ← H(ssid, P i , P j , Epk, Ec, K), if SamePwd(ssid, P i , P j ) = true, one updates the generation by SK ← H * (ssid, P i , P j , Epk, Ec, success), otherwise one uses the generation SK ← H * (ssid, P i , P j , Epk, Ec, fail B ).

-From A, with extracted password pw: if GoodPwd(ssid, P j , pw) = true, one keeps SK ← H(ssid, P i , P j , Epk, Ec, K); else one uses the generation SK ← H * (ssid, P i , P j , Epk, Ec, fail B ). On Alice's Side: Upon receiving Ec -From an honest Bob, instead of setting SK ← H(ssid, P i , P j , Epk, Ec, K), if SamePwd(ssid, P i , P j ) = true, one updates the generation by SK ← H * (ssid, P i , P j , Epk, Ec, success), otherwise one uses the generation SK ← H * (ssid, P i , P j , Epk, Ec, fail 1 ). -From A, with extracted password pw: if GoodPwd(ssid, P i , pw) = true, one keeps SK ← H(ssid, P i , P j , Epk, Ec, K ′ ); else one uses the generation SK ← H * (ssid, P i , P j , Epk, Ec, fail A ).

The only way for the environment to detect the difference is to have a call H(ssid, P i , P j , Epk, Ec, K) that has been replaced by a call to H . But in the previous game, all the K that are in such changes are truly random, and there are at most 2q s such changes, where q s is the number of sessions: We thus have

| Pr[G 6.2 ] -Pr[G 6.1 ] | ≤ q H • q s /2 λ k , where λ k is the length of K. As this last game G 6.2 is G 7 , | Pr[G 7 ] -Pr[G 6 ] | ≤ (q ′ D1 + q ′ D2 ) • Adv ind KEM (t) + q H • q s /2 λ k .
Game G 8 : Adaptive Corruptions. Since the values K and K ′ are not needed anymore to generate SK, we can postpone some evaluations that need the passwords of honest players, when corruptions happen:

-Alice's initialization: S uses or adds Epk in Λ Epk and sends it. We postpone the evaluation of pk ← D 1 (ssid∥pw A , Epk) with sk, at corruption time, to provide sk. -Bob's answer to honest Epk: S samples Ec ←$ C ′ and sends it. We postpone the evaluations c ← D * 2 (ssid∥pw B , Ec, pk) and K ← Decaps(sk, c), at corruption time, to provide K. The evaluation of SK uses H * , with inputs depending on similar or different passwords.

-Alice's reaction to honest Ec: The evaluation of SK uses H * , with inputs depending on similar or different passwords.

In case of late corruptions, after SK has been set, from the knowledge of the passwords, one can program the random oracle H to make it consistent with K ′ obtained from H * :

if Alice is corrupted, from pw A , for all the (ssid, P i , P j , Epk, Ec, status, SK) in Λ H * , involving Alice as P i , one queries pk ← D 1 (ssid∥pw A , Epk) with sk, and c ← D 2 (ssid∥pw A , Ec). This always succeeds as Epk was a fresh value. Then one can compute K ← Decaps(sk, c) to add (ssid, P i , P j , Epk, Ec, K, SK) in Λ H . -if Bob is corrupted, from pw B , for all the (ssid, P i , P j , Epk, Ec, status, SK) in Λ H * , involving Bob as P j , one queries pk ← D 1 (ssid∥pw B , Epk) with sk, and c ← D 2 (ssid∥pw B , Ec). This always succeeds as Epk has not been obtained as an encryption under E 1 (otherwise SK has already been generated with H).

Then one computes K ← Decaps(sk, c) to add (ssid, P i , P j , Epk, Ec, K, SK) in Λ H .

In the previous game, we have already excluded queries on these specific inputs, so all these programmings are possible:

| Pr[G 8 ] -Pr[G 7 ] | = 0.
Game G 9 : Adding the Full F pwKE Interface. In this game we add the full F pwKE interface to fully model the ideal world. First, S simulates its use of GoodPwd by querying TestPwd to F pwKE on input (ssid, P i , pw) to test if pw is the password associated to P i in ssid. Then, for key generation, when a value K can be computed, and SK ← H(ssid, P i , P j , Epk, Ec, K), then one queries F pwKE on (NewKey, ssid, P, SK), for any party P . Let us show this provides the same output as in the previous game: First, in the simulation, if S has extracted the password used by the adversary, then a TestPwd query has been sent to F pwKE . According to the ideal functionality two cases arise, according to the correct guess:

-If the guess is incorrect: the record is marked as interrupted.

-If the guess is correct: the record is marked as compromised.

If the session is compromised, NewKey(ssid, P i , SK) returns SK to P i , which are the cases where we kept the definition of SK with H. If the session is interrupted it returns a random SK ′ to P i , which are the cases where we used H * with fail. This behavior of NewKey is exactly the one from that has been simulated by S and therefore remains indistinguishable. Now assuming that S could not extract a password: it has sent random flow Epk and Ec and used its private oracle H * to build a random session key for each party. Since S does not know the parties' passwords it is not able to tell if it needs to derive the same session key for both of them. Now, even though S derived the same session key SK using H * on behalf of Alice and Bob, by definition of the NewKey interface:

-Two honest parties in a fresh session, using the same password, derive the same session key, because of a success status. -Two honest parties in a fresh session, not using the same passwords, derive two random different session keys, because of the fail status.

Laslty on NewSession, S does nothing more than what is described in the simulation. Only F pwKE does his internal computation. Hence, we have | Pr[G 9 ] -Pr[G 8 ] | = 0, and this game is perfectly indistinguishable from the ideal world. Note that now the private oracle H does not need its status component anymore because it is handled by F pwKE entirely. The global gap is thus:

| Pr[G 9 ] -Pr[G 0 ] | ≤ q 2 E1 • 2 -λp-1 + q 2 E2 • 2 -λc-1 + q ′ D1 • Adv fuzzy KEM (t) + q D1 • q * D2 • Adv ano KEM (t) + (q ′ D1 + q ′ D2 ) • Adv ind KEM (t) + q H •
q s /2 λ k where we denote the global numbers of queries asked by the adversary q E1 , q D1 , q E2 , q D2 , and q H . But we also need to count the number of queries to D 1 , D 2 and D * 2 by the adversary and the simulator, at some point of the simulation:

B Proof of Theorem 2

Game G 0 : In this game we present a formalization of the OCAKE protocol using the random oracle model and the ideal cipher model. Our simulation is set in the erasure model, in which secret information is erased from the memory of each party when it is no longer needed during the protocol execution. The protocol is executed in an adversarial environment, denoted as Z, in which the parties can be statistically corrupted by an adversary A to leak their private state. In our simulation, Alice is referred to as P i (the initiator) and Bob is referred to as P j (the responder). Additionally, pw A represents Alice's password and pw B represents Bob's password, while pw represents an arbitrary password usually used by the adversary.

Game G 1 : Simulation of F IC and F RO . This game builds the simulation from S of the different oracles namely: the ideal cipher and the random oracle.

It is subdivisided into three subgames and each subgame represents respectively the simulation of two different random oracles and one ideal cipher, starting from G 0 , with G 0.1 , G 0.2 , and G 0.3 = G 1 :

Game G 0.1 : In this subgame, S models the random oracle H 1 used for authentication, where on each query the oracle returns a uniformly random answer. We will also need to exclude collisions. To remain consistent with previous answers S uses a list Λ H1 of tuples (ssid, P i , P j , Epk, c, pw, K, Auth). This list is initially set as empty, then on a query H 1 (ssid, P i , P j , Epk, c, pw, K), S uses Λ H1 to simulate it as follows:

-If a record (ssid, P i , P j , Epk, c, pw, K, Auth) exists in Λ H1 , S returns Auth.

-Else, S samples a random Auth, if Auth already exists as a previous answer, S aborts, else S records (ssid, P i , P j , Epk, c, pw, K, Auth) in Λ H1 , and returns Auth.

However throughout the simulation, S will have to simulate H 1 while not knowing K nor pw, for generating Auth. S uses a private oracle H * 1 to record values in a list Λ H * 1 of items (ssid, P i , P j , Epk, c, status, Auth). S simulates H * 1 as follows on input (ssid, P i , P j , Epk, c, status), where status can be success or fail, where success can lead to an accepted authentication with Auth, whereas a failure will lead to a failed Auth meaning an abortion:

-If a record (ssid, P i , P j , Epk, c, status, Auth) exists in Λ H * 1 , S returns Auth. -Else, S samples a random Auth, if Auth already exists as a previous answer, S aborts, else S, records (ssid, P i , P j , Epk, c, status, Auth) in Λ H * 1 , and returns Auth.

Additionally we set a query to H 1 with K = ⊥ to return special character ∅ to force the authentication fail.

Analysis: Under the assumption of the Random Oracle model depicted by its ideal functionality, Z can distinguish the real execution of the protocol from this game if S aborts. Assuming the output length of H 1 and H * 1 to be λ H1 , and q ′ H1 being the global number of queries to H 1 and H * 1 (by both the simulator and the adversary), the birthday paradox gives:

| Pr[G 0.1 ] -Pr[G 0 ] | ≤ q ′ H1 2 • 2 -λH 1 -1
Game G 0.2 : In this subgame, S models the random oracle H 2 to build session keys, where on each query the oracle returns a uniformly random answer. To remain consistent with previous answers S uses a list Λ H2 of tuples (ssid, P i , P j , Epk, c, Auth, K, SK). This list is initially set as empty, and on a query H 2 (ssid, P i , P j , Epk, c, Auth, K, SK), S uses Λ H2 to simulate it as follows:

-If a record (ssid, P i , P j , Epk, c, Auth, K, SK) exists in Λ H2 , S returns SK.

-Else, S samples a random SK, records (ssid, P i , P j , Epk, c, Auth, K, SK) in Λ H2 , and returns SK.

However throughout the simulation, S will have to simulate H 2 while not knowing K, for generating SK. S uses a private oracle H * 2 to record values in a list Λ H * 2 of items (ssid, P i , P j , Epk, c, Auth, status, SK). S simulates H * 2 as follows on input (ssid, P i , P j , Epk, c, Auth, status), where status can be success, fail A , or fail B , where both success would lead to the same key SK, whereas a failure will lead to independent keys:

-If a record (ssid, P i , P j , Epk, Ec, status, SK) exists in Λ H * 2 , S returns SK. -Else, S samples a random SK, records (ssid, P i , P j , Epk, c, Auth, status, SK) in Λ H * 2 , and returns SK. This simulation is perfectly identical to G 0.1 . Game G 0.3 : In this game, we simulate an ideal cipher from the first exchange of the protocol. The simulation of this oracle needs to be consistent, meaning that any query that has already been asked should return the same answer as the first time it was asked. Additionally, the simulation needs to capture the properties of an ideal cipher, which means simulating each encryption as a random bijection for each key (actually, for each ssid∥pw). But for the following simulation, we will need to avoid collisions during adversary's encryption with different inputs. Then, the simulator uses a list called Λ E for encryption and decryption queries on each oracle. Λ E is composed of tuples of the form (ssid, pw, pk, E ∨ D, Epk), even if the component sk will only appear later. S simulates E and D as follows:

-On E(ssid∥pw, pk):

• If there exists a record (ssid, pw, pk, ⋆, ⋆, Epk) ∈ Λ E then S returns Epk.

is G 5 , | Pr[G 5 ] -Pr[G 4 ] | = 0.
Game G 6 : Simulation of Alice's Reaction. In this game, S simulates the key computation by Alice, upon receiving (c, Auth), which has been sent by either an honest Bob or the adversary. S first recovers Alice's secret key sk generated during the first honest flow. Then, we proceed in two steps, from G 5 , with G 5.1 that deals with honestly generated (c, Auth), and G 6 = G 5.2 that deals with adversarially generated (c, Auth).

Game G 5.1 : (c, Auth) comes from Bob. If pw = pw A , we have both equalities K = K ′ ← Decaps(sk, c ′ ) and Auth = H 1 (ssid, P i , P j , pw, Epk, c, K ′ ): then Alice and Bob have the same final session key SK = SK ′ ← H 2 (ssid, P i , P j , Epk, c, Auth, K ′ ).

If pw ̸ = pw A , we have both inequalities (excepted by chance) K ̸ = K ′ ← Decaps(sk, c ′ ) and Auth ̸ = Auth ′ : then SK ′ ← H 2 (ssid, P i , P j , Epk, c, Auth, K ′ ) is independent from the SK computed by Bob, excepted with random equality, which makes no difference from the previous game.

Game G 5.2 : (c, Auth) comes from A. From the uniqueness of Auth (from G 0.1 ) in Λ H1 , from explicit query to H 1 (or no record at all), S can extract at most one pair (pw, K) used by A:

-

If pw = pw A , with (c, Auth): S computes K ′ ← Decaps(sk, c), Auth ′ ← H 1 (ssid, P i , P j , Epk, c, pw, K ′ ), and SK ′ ← H 2 (ssid, P i , P j , Epk, c, Auth ′ , K ′ ). -Else (pw ̸ = pw A , or pw = ⊥): S computes K ′ ← Decaps(sk, c), Auth ′ ←
H 1 (ssid, P i , P j , Epk, c, pw, K ′ ), and aborts.

As we have excluded collisions on H 1 , the latter case leads to Auth ̸ = Auth, and thus to an abort: this makes no difference from the previous game. As this last game G

5.2 is G 6 , | Pr[G 6 ] -Pr[G 5 ] | = 0.
Game G 7 : Random Session Keys. Thanks to the above simulation of the ideal cipher and the random oracle, S has the ability to extract the tentative password used by the adversary. It will be given access to two boolean functions;

-GoodPwd with input (ssid, P i , pw) that answers whether this is the correct password of party P i . -SamePwd with input (ssid, P i , P j ) that answers whether P i and P j share the same password.

We first replace session key K generation, for honest players, without knowing the passwords, by using SamePwd when it did not extract the password and GoodPwd when it successfully extracted pw, using two private random oracles H * A and H * K onto respectively {0, 1} λH 1 and K, in G 6.1 . We then replace the authentication Auth in G 6.2 and lastly the final session key SK generation in G 7 = G 6.3 . Game G 6.1 : Random K ′ . We first use a private random oracle H * K onto K to replace K by random K ′ , in some situations: On Bob's Side: Upon receiving Epk -From an honest Alice, instead of using K to compute the authentication tag Auth ← H 1 (ssid, P i , P j , Epk, c, pw B , K) and the final session key SK ← H 2 (ssid, P i , P j , Epk, c, Auth, K), if SamePwd(ssid, P i , P j ) = true, one sets K ′ ← H * K (ssid, success) otherwise one sets K ′ ← H * K (ssid, fail B ), and updates the definition of both Auth ← H 1 (ssid, P i , P j , Epk, c, pw B , K ′ ) and SK ← H 2 (ssid, P i , P j , Epk, c, Auth ′ , K ′ ).

-From A, with extracted password pw: if GoodPwd(ssid, P j , pw) = true, one keeps the tag Auth ← H 1 (ssid, P i , P j , Epk, c, pw, K) and the key SK ← H 2 (ssid, P i , P j , Epk, c, Auth, K); else one sets K ′ ← H * K (ssid, fail B ), and updates the definitions: Auth ← H 1 (ssid, P i , P j , Epk, c, pw B , K ′ ) and SK ← H 2 (ssid, P i , P j , Epk, c, Auth ′ , K ′ ). On Alice's Side: Upon receiving (c, Auth)

-From an honest Bob, instead of using K to compute the authentication tag Auth ← H 1 (ssid, P i , P j , Epk, c, pw A , K) and the final session key SK ← H 2 (ssid, P i , P j , Epk, c, Auth, K), if SamePwd(ssid, P i , P j ) = true, one sets K ′ ← H * K (ssid, success) otherwise one sets K ′ ← H * K (ssid, fail A ) and lastly updates the definition Auth ′ ← H 1 (ssid, P i , P j , Epk, c, pw A , K ′ ). In the former case, Auth = Auth ′ , since then authentication succeeded S computes SK ← H 2 (ssid, P i , P j , Epk, c, Auth ′ , K ′ ) otherwise Auth ̸ = Auth ′ , S aborts.

-From A, with extracted password pw: if GoodPwd(ssid, P i , pw) = true, one keeps the tag Auth ← H 1 (ssid, P i , P j , Epk, c, pw, K) and the key SK ← H 2 (ssid, P i , P j , Epk, Ec, K); else one sets K ′ ← H * K (ssid, fail A ), and updates the definitions Auth ′ ← H 1 (ssid, P i , P j , Epk, c, pw A , K ′ ), since Auth ̸ = Auth ′ : S aborts.

Analysis: In this simulation we still use passwords. We replace real keys K by random independent keys K ′ , except when interacting with the adversary that has guessed the password or when an abort occurs due to a failed authentication: Auth ̸ = Auth ′ . In all the modified sessions, K has been generated from a fresh KEM instance: From an honest Alice, Bob always uses a pk coming from D, a (c, K) coming from Encaps(pk) and Auth built honestly; if this comes from A, unless the password was correctly guessed, pk also comes from D, (c, K) from Encaps(pk) and Auth built honestly. On Alice's side, unless the password was correctly guessed by the adversary, pk also comes from D. However c can be random, but S uses H 1 to extract the password pw and get (sk, pk) from D. If at some point either S can not build Auth ′ or builds Auth ′ ̸ = Auth then it aborts due to a failed authentication. Note that S does not abort if and only if both (c, K) really come from an Encaps(pk) and Auth has been built honestly. We can thus proceed with a sequence of hybrid games, replacing real keys by random keys.

-On Bob's side, pk comes from D, c is simulated by S and Auth built accordingly, with known (pk, sk) and (c, K), we can simply successively replace (pk, c, K) by (pk, c, K ′ ), using the indistinguishability of the KEM: the gap is bounded by q ′ D • Adv ind KEM (t). -On Alice's side, the pairs come from D and more importantly (c, Auth) has been built honestly otherwise S would have aborted. Using Auth the simulation is done with known (pk, sk) and (c, K). We can replace (pk, c, K) by (pk, c, K ′ ), using the indistinguishability of the KEM: because the Auth has been honestly computed only one tuple needs to be replaced while S has knowledge of pw the gap is bounded by Adv ind KEM (t). We thus have | Pr[G 6.1 ] -Pr[G 6 ] | ≤ (1 + q ′ D ) • Adv ind KEM (t).

Game G 6.2 : Random Auth. We now remove knowledge on the passwords from S, it can only use GoodPwd and SamePwd. We replace Auth by random Auth ′ in some situations:

On Bob's Side: Upon receiving Epk -From an honest Alice, instead of using the password to compute the following tag Auth ← H 1 (ssid, P i , P j , Epk, c, pw B , K), one first gets c ←$ C then, if SamePwd(ssid, P i , P j ) = true, one updates the generation by Auth ← H * 1 (ssid, P i , P j , Epk, c, success), otherwise one uses the generation Auth ← H * 1 (ssid, P i , P j , Epk, c, fail). -From A, with extracted password pw: if GoodPwd(ssid, P j , pw) = true, one keeps Auth ← H 1 (ssid, P i , P j , Epk, c, pw, K); else one gets c ∈ C and uses the generation Auth ← H * 1 (ssid, P i , P j , Epk, c, fail). On Alice's Side: Upon receiving (c, Auth)

-From an honest Bob, instead of using the password to compute the tag Auth ′ ← H 1 (ssid, P i , P j , Epk, c, pw A , K), if SamePwd(ssid, P i , P j ) = true, one updates the generation by Auth ′ ← H * 1 (ssid, P i , P j , Epk, c, success), otherwise S aborts because the authentication is bound to fail.

-From A, with extracted password pw: if GoodPwd(ssid, P i , pw) = true, one keeps Auth ′ ← H 1 (ssid, P i , P j , Epk, c, pw, K); else whether password are different or H 1 has not been queried to obtain Auth, one aborts as the authentication is bound to fail.

Note that according to H 2 behavior, when the Auth is bound to fail (i.e. when status = fail), Bob derives a random key still even though Alice will abort. The environment can make this game fails using two ways. First on Bob's behalf we replaced c built from an Encaps with c ←$ C. Since the KEM is anonymous the adversary can distinguish this simulation by querying q D times D to break the anonimity. Lastly it can try to query H 1 on an input that has been replaced by H * 1 . But in the previous game, all the K that are in such changes are truly random, and there are at most 2q s such changes, where q s is the number of sessions: We thus have | Pr[G 6.2 ] -Pr[G 6.1 ] | ≤ q D • Adv ano KEM (A) + q H1 • q s /2 λ k , where λ k is the length of K.

Game G 6.3 : Random SK. We now replace SK by random SK ′ , in some situations: On Bob's Side: Upon receiving Epk -From an honest Alice, instead of using K to compute the key SK ← H 2 (ssid, P i , P j , Epk, c, Auth, K), if SamePwd(ssid, P i , P j ) = true, one updates the generation by SK ← H * 2 (ssid, P i , P j , Epk, c, Auth, success), otherwise one uses the generation SK ← H * 2 (ssid, P i , P j , Epk, c, Auth, fail). -From A, with extracted password pw: If GoodPwd(ssid, P j , pw) = true, one keeps SK ← H 2 (ssid, P i , P j , Epk, c, Auth, K); else one uses the generation SK ← H * 2 (ssid, P i , P j , Epk, c, Auth, fail). On Alice's Side: Upon receiving (c, Auth)

-From an honest Bob, instead of using K to compute the key SK ← H 2 (ssid, P i , P j , pw, Epk, c, K), if SamePwd(ssid, P i , P j ) = true, one updates the generation by SK ← H * 2 (ssid, P i , P j , Epk, c, Auth, success). -From A, with extracted password pw: if GoodPwd(ssid, P i , pw) = true and Auth = Auth ′ therefore one keeps SK ← H 2 (ssid, P i , P j , Epk, c, Auth ′ , K ′ ).

The only way for the environment to detect the difference is to have a call H 2 (ssid, P i , P j , Epk, c, Auth, K) that has been replaced by a call to H * 2 . But in the previous game, all the K that are in such changes are truly random, and there are at most 2q s such changes, where q s is the number of sessions: We thus have | Pr[G 6.3 ] -Pr[G 6.2 ] | ≤ q H2 • q s /2 λ k , where λ k is the length of K.

As this last game

G 6.3 is G 7 , | Pr[G 7 ] -Pr[G 6 ] | ≤ (1 + q ′ D ) • Adv ind KEM (t) + q D • Adv ano KEM (A) + (q H1 + q H2 ) • q s /2 λ k .
Game G 8 : Adding the Full F pwKE-sA Interface. In this game we add the full F pwKE-sA interface to fully model the ideal world. First, S simulates its use of GoodPwd by querying TestPwd to F pwKE-sA on input (ssid, P i , pw) to test if pw is the password associated to P i in ssid. Secondly, SamePwd on (ssid, P i , P j ) perfectly embodies the equality that F pwKE-sA does internally with knowledge of the passwords when using records (P i , P j , pw, status). Note that here status represents client and server unline the previous game with success and fail. Then, for key generation, when a value K can be computed, and SK ← H 2 (ssid, P i , P j , Epk, c, Auth, K), then one queries the ideal functionnality F pwKE-sA on (NewKey, ssid, P, SK), for any party P . Let us show this provides the same output as in the previous game: First, in the simulation, if S has extracted the password used by the adversary, then a TestPwd query has been sent to F pwKE-sA . According to the ideal functionality two cases arise, according to the correct guess:

-If the guess is incorrect: the record is marked as interrupted.

-If the guess is correct: the record is marked as compromised.

If the session is compromised, F pwKE-sA returns (ssid, SK) to P i on query to NewKey with (ssid, P i , SK). These are the cases where we kept the definition of SK with H 2 . If the session is interrupted it returns a random SK ′ to the server and set an error for the client, which are the cases where we used H * 1 with fail. This behavior of NewKey is exactly the one from that has been simulated by S and therefore remains indistinguishable. Now assuming that S could not extract a password: it has sent random flow Epk and (c, Auth) and used its private oracles H * 1 and H * 2 to build a random session key for each party. Since S does not know the parties' passwords it used SamePwd to obtain know if they use the same password. By definition of the NewKey interface:

-Two honest parties in a fresh session using the same password, derive the same session key, because of a success status. -Two honest parties in a fresh session not using the same passwords: the client is returned abort from F pwKE-sA while the server obtains a random session key because of the fail status.

Hence, we have | Pr[G 8 ] -Pr[G 7 ] | = 0, and this game is perfectly indistinguishable from the ideal world. The global gap is thus:

| Pr[G 9 ] -Pr[G 0 ] | ≤ q ′ D • Adv fuzzy KEM (t) + (1 + q ′ D ) • Adv ind KEM (t) + q D • Adv ano KEM (A) + q ′ H1 2 • 2 -λH 1 -1 + q 2 E • 2 -λp-1 + q s • 2 -λH 1 + (q H1 + q H2 ) • q s • 2 -λ k
where we denote the global numbers of queries asked by the adversary q E , q D , and q H . But we also need to count the number of queries to H 1 and D by the adversary and the simulator, at some point of the simulation:

the global number of queries asked to D is q s (for initialization by Alice or answer by Bob) plus q D ; -the global number of queries asked to H 1 is q s (for answer by Bob) plus q H .

  EKE [BM92] and OEKE [BCP03] are typical examples of the former. And SPEKE [Mac01] or CPace [AHH22] are examples for the latter. While many different PAKE designs have been introduced, not all are proven in the strong UC security model. In the previous examples of PAKE constructions, EKE [DHP + 18], OEKE [ACCP08] and CPace [AHH21] have been proven in the UC model.

  structures. Let us cite a few examples: SABER [DKRV18,DKR + 20], Crystals-Kyber [BDK + 18,SAB + 22], NewHope [ADPS16,PAA + 19] on lattice-based assumptions or alternatively McEliece[McE78,ABC + 22] on code-based assumptions. Definition 1 (Key Encapsulation Mechanism). A Key Encapsulation Mechanism (KEM) is a triple of algorithms (KeyGen, Encaps, Decaps):

Fig. 2 .

 2 Fig. 2. Real versus Ideal world: Z capability.

Fig. 3 .

 3 Fig. 3. FpwKE: the ideal Functionality of a PAKE.

Fig. 4 .

 4 Fig. 4. FpwKE-sA: the ideal Functionality of a PAKE with server explicit authentication.

G 3 :

 3 Simulation of an adversary finding Auth by chance. G 4 : Simulation of Alice's initialization with D instead of E. G 5 : Simulation of Bob's answer with (c, Auth). G 6 : Simulation of Alice's reaction, using the Auth and the abortion in case the authentication is not verified. G 7 : Random session keys, where we replace all the unknown authentication tags Auth and keys SK by random values, except for correctly guessed passwords G 8 : Using on queries from F pwKE-sA to detail the simulator in the ideal world. A precise simulator is defined in Appendix B with Figures 10 and 11. ⊓ ⊔ Remark 2. Comparatively to remark 1, instantiated with the KEM derived from ElGamal presented in Section 2, OCAKE-ElGamal is exactly OEKE [ACCP08].

OnFig. 9 .

 9 Fig. 8. Simulation of the behavior against Z and FpwKE in proof of Theorem 1.

  Embedding of the secrets during the simulation of D 1 and D 2 . G 3 : Simulation of Alice's initialization with D 1 instead of E 1 . G 4 : Simulation of Bob's answer with D 2 instead of E 2 . G 5 : Preparation of Alice's reaction, by anticipating all the possible public keys decrypted by D 1 when a query is asked to D 2 . G 6 : Simulation of Alice's reaction, using the previous simulation of D 2 . G 7 : Random session keys, where we replace all the unknown keys SK by random values. G 8 : Adaptive corruptions, where we program the random oracle H and provide the secret values in case of corruption. G 9 : Using on queries from F pwKE to detail the simulator in the ideal world. Instantiated with the KEM derived from ElGamal presented in Section 2, CAKE-ElGamal is exactly the famous EKE [BM92]. But the proof technique actually differs because ElGamal enjoys perfect fuzziness (or smoothness) and perfect anonymity, which facilitate the EKE security proof. However, postquantum algorithms cannot validate all these strong properties.

	A precise simulator is defined in Appendix A with Figures 7, 8 and 9.	⊓ ⊔
	Remark 1. 4.2 OCAKE
	In this subsection, we modify the above CAKE protocol by adding explicit au-
	thentication of the receiver, which allows to remove one encryption. The modifi-
	cations are based on the OEKE [BCP03] protocol but with generic KEM protocols

Real world protocol using the following assumptions: erasure model, random oracle, ideal cipher, adaptive corruption and lastly a fuzzy and anonymous KEM, which is also indistinguishable. G 1 : Honest simulation of the random oracle H and the pairs of ideal ciphers (E 1 , D 1 ) and (E 2 , D 2 ) from Figure

5

, where we abort in case of collision during explicit encryption calls. Additionally, a private simulation of a random oracle H * used for the simulation when S cannot extract private information. G 2 :

Alice : A, pw ssid Bob : B, pw

Table 1 .

 1 Bit security estimates of CAKE-Kyber and OCAKE-Kyber using parameters from version 3.0 of the NIST [SAB + 22] against a quantum adversary. Estimation done using python script from pqcrystals github [DS21].

	Kyber parameters	Bit-sec against quantum
		adversaries obtained
		with [DS21]
	Kyber1024	102
		CAKE -Kyber
	Kyber768	98
	Kyber1024	162
		OCAKE -Kyber

  • Else, S samples Epk ←$ P ′ . If Epk already exists in Λ E , S aborts, else S records (ssid, pw, pk, E, Epk) in Λ E and returns Epk.-On D(ssid∥pw, Epk):• If there is a record (ssid, pw, pk, ⋆, ⋆, Epk) ∈ Λ E , S returns pk. • Else, S samples pk ←$ P, records (ssid, pw, pk, D, Epk) in Λ E , and returns pk. Game G 4.1 : Epk comes from Alice. Epk comes from the above simulation, with (pw A , pk, sk, D, Epk) in Λ E . S asks for pk ′ ← D(ssid∥pw B , Epk), which is either pk if the passwords are the same, or another pk ′ , with associated sk ′ . S builds c ← Encaps(pk ′ ), computes K ← Decaps(sk ′ , c), and sends c to Alice, together with Auth = H 1 (ssid, P i , P j , Epk, c, pw B , K) This makes no difference from the previous game, as pk ′ really comes from D. Game G 4.2 : Epk comes from A. From the uniqueness of Epk in Λ E , from explicit encryption E (or no record at all), S can extract at most one pair (pw, pk) used by A: -If pw = pw B , with pk: S continues as Bob does, with (c, K) ← Encaps(pk), it gets Auth ← H 1 (ssid, P i , P j , Epk, c, pw, K), and builds accordingly SK ← H 2 (ssid, P i , P j , Epk, c, Auth, K). -Else (pw ̸ = pw B , or pw = ⊥): S asks for pk ← D(ssid∥pw B , Epk), with sk, gets (c, K) ← Encaps(pk) and Auth ← H 1 (ssid, P i , P j , pw, Epk, c, K), and SK ← H 2 (ssid, P i , P j , Epk, c, Auth, K). makes no difference from the previous game. As this last game G 4.2

	This

Acknowledgements. We would like to thank Olivier Blazy and Henri Gilbert respectively for useful discussions about password-authenticated key exchange protocols and their security and symmetric encryption for the PAKE practicability. This work was supported in part by the French Programme d'Investissement d'Avenir (PIA) under national project RESQUE. The first author was also supported by ANRT under the program CIFRE N°2021/0645.

Supplementary Material

These appendices are for the reviewer convenience.

A Proof of Theorem 1

Game G 0 : In this game we present a formalization of the CAKE protocol using the random oracle model and the ideal cipher model. Our simulation is set in the erasure model, in which secret information is erased from the memory of each party when it is no longer needed during the protocol execution. The protocol is executed in an adversarial environment, denoted as Z, in which the parties can be adaptively corrupted by an adversary A to leak their private state. In our simulation, Alice is referred to as P i (the initiator) and Bob is referred to as P j (the responder). Additionally, pw A represents Alice's password and pw B represents Bob's password, while pw represents an arbitrary password usually used by the adversary.

Game G 1 : Simulation of F IC and F RO . This game builds the simulation from S of the different oracles namely: the ideal cipher and the random oracle. It is subdivisided into three subgames and each subgame represents respectively the simulation of the random oracle and two differently modeled ideal ciphers, starting from G 0 , with G 0.1 , G 0.2 , and G 0.3 = G 1 : Game G 0.1 : In this subgame, S models the random oracle H, where on each query the oracle returns a uniformly random answer. To remain consistent with previous answers S uses a list Λ H of tuples (ssid, P i , P j , Epk, Ec, K, SK). This list is initially set as empty and grows as the number of queries to H piles up in the different sessions. On query H(ssid, P i , P j , Epk, Ec, K), S uses Λ H to simulate it as follows:

-If a record (ssid, P i , P j , Epk, Ec, K, SK) exists in Λ H , S returns SK.

-Else, S samples a random SK, records (ssid, P i , P j , Epk, Ec, K, SK) in Λ H , and returns SK.

However throughout the simulation, S will have to simulate H while not knowing K, for generating SK. S uses a private oracle H * to record values in a list Λ H * of items (ssid, P i , P j , Epk, Ec, status, SK). S simulates H * as follows on input (ssid, P i , P j , Epk, Ec, status), where status can be success, fail A , or fail B , where both success would lead to the same key SK, whereas a failure will lead to independent keys:

-If a record (ssid, P i , P j , Epk, Ec, status, SK) exists in Λ H * , S returns SK.

-Else, S samples a random SK, records (ssid, P i , P j , Epk, Ec, status, SK) in Λ H * , and returns SK.

This simulation is perfectly identical to G 0 .

the global number of queries asked to D 1 is q s (for initialization by Alice or answer by Bob) plus q D1 , and q D2 , as all the queries to D 2 make a call to D 1 ; -the global number of queries asked to D 2 is q s (for answer by Bob) plus q D2 ; -the global number of queries asked to D * 2 is q s (for answer by Bob) plus q D2 . Hence,

sample SK ←$ {0, 1} λH and record

sample SK ←$ {0, 1} λH and record:

Else, S builds (pk, sk) ← KeyGen(1 κ ) records (ssid, pw, pk, sk, D1, Epk) ∈ Λ1 returns pk.

Else: S records : Analysis: Under the assumption of the Ideal Cipher model depicted by its ideal functionality, Z can distinguish the real execution of the protocol from this game if S aborts. Assuming the cardinal of P is 2 λp , and if A makes up to q E queries to the encryption oracle then by the birthday paradox bound:

Game G 2 : Embedding of the Secrets. In this game we embed the associated secret keys in the simulation of D and introduce the component sk in the records in Λ E :

-On D 1 (ssid∥pw, Epk):

• If there is a record (ssid, pw, pk, ⋆, ⋆, Epk) ∈ Λ E , S returns pk.

• Else, S builds (pk, sk) ← KeyGen(1 κ ), records (ssid, pw, pk, sk, D, Epk) in Λ E , and returns pk.

Analysis:

The unique difference is a real public key instead of a random public key, which is exactly the fuzziness of the KEM, that we apply q ′ D1 times in a hybrid sequence of games:

We stress that q ′ D will be the number of all the queries to D done by the simulator and by the adversary. This might be larger than the sole number q D of queries asked by the adversary.

Game G 3 : A randomly guessing Auth. In this game we model the capacity of the adversary to randomly guess Auth, without asking the right query to H 1 . If such a case happens, S now aborts.

Analysis: In such a case, Alice asks a fresh query to H 1 which provides a random answer:

|

Game G 4 : Simulation of Alice's Initialization. In this game, S simulates the first flow of Alice, using D instead of E: it samples Epk ←$ P ′ , asks for pk ← D(ssid∥pw A , Epk), which also generates sk, and sends Epk to Bob. This makes no difference from the previous game:

Game G 5 : Simulation of Bob's Answer. In this game, S simulates the second flow from an honest Bob, upon receiving Epk. The behavior of S depends on the origin of the message Epk: whether it comes from a honest Alice, or from the adversary A, that has corrupted, or not, Alice. We thus do it in two steps, from G 4 , with G 4.1 that deals with honestly generated Epk, and G 5 = G 4.2 that deals with adversarially generated Epk.

Laslty on NewSession, S sends Epk on behalf of the client and does nothing for the server Only F pwKE does his internal computation. The simulation of both H 1 and H 2 are independant of the status component as it is handle by F pwKE-sA . Additionally we have,

On H1(ssid, Pi, Pj, Epk, c, pw, K)

sample Auth ←$ {0, 1} λH 1 and record

sample Auth ←$ {0, 1} λH 1 and record:

C IF

Functionnality FRO

On security parameter k, with parties P1, . . . , Pn and adversary S.

1. FRO keeps a list L (which is initially empty) of pairs of bitstrings. 2. Upon receiving a value (sid, m) (with m ∈ {0, 1} * ) from some party Pi or from S, do:

-If there is a pair (m, h) or some ( h ∈ {0, 1} k ) in the list L, set h := h.

-If there is no such pair, choose uniformly h ∈ {0, 1} k and store the pair (m, h) in L.

Adaptive Corruption

On (AdaptiveCorruption, sid, Pi) from A, if there exists a record < sid, Pi, Pj, pw > then :

if (sid, K) was output to Pi, send (sid, Pj, pw, K) to A.

otherwise send (sid, Pj, pw, ⊥) to A.