A Universally Composable PAKE with Zero Communication Cost

A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to agree upon a cryptographic key, when the only information shared in advance is a low-entropy password. The standard security notion for PAKE (Canetti et al., Eurocrypt 2005) is in the Universally Composable (UC) framework. We show that unlike most UC security notions, UC PAKE does not imply correctness. While Canetti et al. has briefly noticed this issue, we present the first comprehensive study of correctness in UC PAKE:

1. 1.

   We show that TrivialPAKE, a no-message protocol that does not satisfy correctness, is a UC PAKE;

2. 2.

   We propose nine approaches to guaranteeing correctness in the UC security notion of PAKE, and show that seven of them are equivalent, whereas the other two are unachievable;

3. 3.

   We prove that a direct solution, namely changing the UC PAKE functionality to incorporate correctness, is impossible;

4. 4.

   Finally, we show how to naturally incorporate correctness by changing the model—we view PAKE as a three-party protocol, with the man-in-the-middle adversary as the third party.

In this way, we hope to shed some light on the very nature of UC-security in the man-in-the-middle setting.

1. 1.

   The cases of [17, 25] are especially problematic, since their (asymmetric) PAKE protocols use a UC-secure authenticated key exchange (AKE) protocol as a building block, and their modelings of UC AKE also do not guarantee correctness. Therefore, a proof of PAKE correctness would need a separate correctness notion for AKE: roughly, that there exists an efficient algorithm \(\textsf{Gen}\) such that if we run it twice and obtain two key pairs (pk, sk) and \((pk',sk')\), then two AKE parties with inputs \((pk,pk',sk)\) and \((pk',pk,sk')\) should output the same key (assuming there is no adversarial interference). Such structural requirement is not mentioned in any of the aforementioned works (and in particular, the \(\mathsf {Key.Gen}\) algorithm in [25, Fig. 6] is undefined; a similar problem appears in [20]). The exact requirement of AKE correctness used in [17, 20, 25] is out of the scope of this work.

2. 2.

   The \(\textsf{role}\) field might be necessary for the description of the protocol when the algorithms of the two parties are not identical (especially when one party must wait for the other party’s message before starting its own session; see [10, Figure 5] for an example), but it has nothing to do with the security of the protocol.

3. 3.

   The functionality in Fig. 2 lets the ideal adversary \(\mathcal {S}\) learn whether its password guess is correct or not. This is necessary for the simulation of some PAKE protocols but not for others. The variant where \(\mathcal {S}\) does not learn this information is called implicitly-only PAKE; see [14] for further discussion. We follow the standard PAKE functionality, but note that all theorems below apply to implicitly-only PAKE as well.

4. 4.

   We can assume w.l.o.g. that \(\mathcal {Z}\) never reuses a session id, i.e., it never sends \((\textsf{NewSession}, sid, \textsf{P}, \cdot , \cdot , \cdot )\) to \(\textsf{P}\) twice (otherwise the second message will be ignored in both the real world and the ideal world).

5. 5.

   The purpose of considering \(\textsf{NoOutput}\) is to rule out the “empty” protocol mentioned in Sect. 1, where \(\textsf{P}\) and \(\textsf{P}'\) simply don’t do anything (and \(\mathcal {S}\) also doesn’t do anything). Although our primary focus is to rule out protocols like TrivialPAKE, with the requirement on \(\textsf{NoOutput}\) in place and with how we define correctness (Definition 4), we can formally rule out the “empty” protocol as well.

6. 6.

   More precisely, assume w.l.o.g. that \(\mathcal {S}\) sends \((\textsf{NewKey}, sid, \textsf{P}, \cdot )\) first and \((\textsf{NewKey}, sid, \textsf{P}', \cdot )\) next. Then when \(\mathcal {S}\) sends \((\textsf{NewKey}, sid, \textsf{P}, \cdot )\), \(\mathcal {F}_{\text {PAKE}}\) enters the third case, so \(\textsf{P}\) receives and outputs (sid, K) for \(K \leftarrow \{0,1\}^\lambda \); when \(\mathcal {S}\) sends \((\textsf{NewKey}, sid, \textsf{P}, \cdot )\), \(\mathcal {F}_{\text {PAKE}}\) enters the second case, so \(\textsf{P}\) receives and outputs \((sid, K')\) for \(K':=K\).

7. 7.

   This is w.l.o.g. because any environment \(\mathcal {Z}\) can be converted into another environment \(\mathcal {Z}'\) that behaves exactly like \(\mathcal {Z}\), except that \(\mathcal {Z}'\) additionally sends \((\textsf{Modify}, sid)\) when \(\mathcal {Z}\) instructs the adversary to modify a protocol message for the first time in session sid. Obviously the distinguishing advantages of \(\mathcal {Z}\) and \(\mathcal {Z}'\) are equal.

8. 8.

   In fact \(\mathcal {Z}'\) does not need to output anything, since we rely on the fact that \(\Pr [\textsf{SpuriousGuess}(\mathcal {S},\mathcal {Z}')]\) is negligible, rather than the distinguishing advantage of \(\mathcal {Z}'\) is negligible; whether \(\textsf{SpuriousGuess}(\mathcal {S},\mathcal {Z}')\) happens or not is already determined before \(\mathcal {Z}'\) finally outputs a bit.

9. 9.

   Formally, r is a random variable depending on the random tape of \(\mathcal {Z}\), and all probabilities below are also taken over the random tape of \(\mathcal {Z}\).

10. 10.

    \(0^\lambda \) can be replaced by any string in \(\{0,1\}^\lambda \).

11. 11.

    This can be viewed as a priority system. In programs of this form, we assign the action y a lower priority than sending m to \(\textsf{X}\), all processing done by \(\textsf{X}\), all messages sent by \(\textsf{X}\) as a result, and so on.

12. 12.

    Technically, \(\textsf{Output}\) must be sent by every honest party. Additionally, it must be sent some polynomial number of times, not just once, to allow protocols with multiple rounds. See [21] for details.

Authors and Affiliations

1. Aarhus University, Aarhus, Denmark

   Lawrence Roy

2. Oregon State University, Corvallis, USA

   Jiayu Xu

Corresponding author

Correspondence to Lawrence Roy .

Editors and Affiliations

1. Georgia Institute of Technology, Atlanta, GA, USA

   Alexandra Boldyreva

2. Georgia Institute of Technology, Atlanta, GA, USA

   Vladimir Kolesnikov

Reprints and permissions

© 2023 International Association for Cryptologic Research

Policies and ethics