Paper 2021/696

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

Edward Eaton and Douglas Stebila

Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
password-authenticated key exchangepost-quantumquantum-annoyinggeneric group model
Contact author(s)
eeaton @ uwaterloo ca
dstebila @ uwaterloo ca
History
2021-05-28: received
Short URL
https://ia.cr/2021/696
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/696,
      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.