Paper 2022/770

Password-Authenticated Key Exchange from Group Actions

Michel Abdalla, DFINITY, Zürich, Switzerland, École Normale Supérieure - PSL
Thorsten Eisenhofer, Ruhr University Bochum
Eike Kiltz, Ruhr University Bochum
Sabrina Kunzweiler, Ruhr University Bochum
Doreen Riepel, Ruhr University Bochum

We present two provably secure password-authenticated key exchange (PAKE) protocols based on a commutative group action. To date the most important instantiation of isogeny-based group actions is given by CSIDH. To model the properties more accurately, we extend the framework of cryptographic group actions (Alamati et al., ASIACRYPT 2020) by the ability of computing the quadratic twist of an elliptic curve. This property is always present in the CSIDH setting and turns out to be crucial in the security analysis of our PAKE protocols. Despite the resemblance, the translation of Diffie-Hellman based PAKE protocols to group actions either does not work with known techniques or is insecure ("How not to create an isogeny-based PAKE", Azarderakhsh et al., ACNS 2020). We overcome the difficulties mentioned in previous work by using a "bit-by-bit" approach, where each password bit is considered separately. Our first protocol $\mathsf{X\text{-}GA\text{-}PAKE}_\ell$ can be executed in a single round. Both parties need to send two set elements for each password bit in order to prevent offline dictionary attacks. The second protocol $\mathsf{Com\text{-}GA\text{-}PAKE}_\ell$ requires only one set element per password bit, but one party has to send a commitment on its message first. We also discuss different optimizations that can be used to reduce the computational cost. We provide comprehensive security proofs for our base protocols and deduce security for the optimized versions.

Available format(s)
Cryptographic protocols
Publication info
isogenies group actions password-authenticated key exchange post-quantum cryptography
Contact author(s)
michel abdalla @ ens fr
thorsten eisenhofer @ rub de
eike kiltz @ rub de
sabrina kunzweiler @ rub de
doreen riepel @ rub de
2022-06-16: approved
2022-06-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Michel Abdalla and Thorsten Eisenhofer and Eike Kiltz and Sabrina Kunzweiler and Doreen Riepel},
      title = {Password-Authenticated Key Exchange from Group Actions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/770},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.