eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2023/1513

Making an Asymmetric PAKE Quantum-Annoying by Hiding Group Elements

Marcel Tiepelt, KASTEL, Karlsruhe Institute of Technology
Edward Eaton, National Research Council Canada
Douglas Stebila, University of Waterloo

The KHAPE-HMQV protocol is a state-of-the-art highly efficient asymmetric password-authenticated key exchange protocol that provides several desirable security properties, but has the drawback of being vulnerable to quantum adversaries due to its reliance on discrete logarithm-based building blocks: solving a single discrete logarithm allows the attacker to perform an offline dictionary attack and recover the password. We show how to modify KHAPE-HMQV to make the protocol quantum-annoying: a classical adversary who has the additional ability to solve discrete logarithms can only break the protocol by solving a discrete logarithm for each guess of the password. While not fully resistant to attacks by quantum computers, a quantum-annoying protocol could offer some resistance to quantum adversaries for whom discrete logarithms are relatively expensive. Our modification to the protocol is small: encryption (using an ideal cipher) is added to one message. Our analysis uses the same ideal cipher model assumption as the original analysis of KHAPE, and quantum annoyingness is modelled using an extension of the generic group model which gives a classical adversary a discrete logarithm oracle.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ESORICS 2023
password-authenticated key exchangequantum-resistantquantum-annoyinggeneric group model
Contact author(s)
marcel tiepelt @ kit edu
2024-01-12: revised
2023-10-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marcel Tiepelt and Edward Eaton and Douglas Stebila},
      title = {Making an Asymmetric PAKE Quantum-Annoying by Hiding Group Elements},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1513},
      year = {2023},
      doi = {10.1007/978-3-031-50594-2_9},
      note = {\url{https://eprint.iacr.org/2023/1513}},
      url = {https://eprint.iacr.org/2023/1513}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.