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 2021/696

The "quantum annoying" property of password-authenticated key exchange protocols

Edward Eaton and Douglas Stebila


During the Crypto Forum Research Group (CFRG)'s standardization of password-authenticated key exchange (PAKE) protocols, a novel property emerged: a PAKE scheme is said to be ``quantum-annoying'' if a quantum computer can compromise the security of the scheme, but only by solving one discrete logarithm for each guess of a password. Considering that early quantum computers will likely take quite long to solve even a single discrete logarithm, a quantum-annoying PAKE, combined with a large password space, could delay the need for a post-quantum replacement by years, or even decades. In this paper, we make the first steps towards formalizing the quantum-annoying property. We consider a classical adversary in an extension of the generic group model in which the adversary has access to an oracle that solves discrete logarithms. While this idealized model does not fully capture the range of operations available to an adversary with a general-purpose quantum computer, this model does allow us to quantify security in terms of the number of discrete logarithms solved. We apply this approach to the CPace protocol, a balanced PAKE advancing through the CFRG standardization process, and show that the CPaceBase variant is secure in the generic group model with a discrete logarithm oracle.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
password-authenticated key exchangepost-quantumquantum-annoyinggeneric group model
Contact author(s)
eeaton @ uwaterloo ca
dstebila @ uwaterloo ca
2021-05-28: received
Short URL
Creative Commons Attribution


      author = {Edward Eaton and Douglas Stebila},
      title = {The "quantum annoying" property of password-authenticated key exchange protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2021/696},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/696}},
      url = {https://eprint.iacr.org/2021/696}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.