Douglas Stebila

The “quantum annoying” property of password-authenticated key exchange protocols

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.

Keywords: password-authenticated key exchange, post-quantum, quantum-annoying, generic group model

Reference

Edward Eaton, Douglas Stebila. The “quantum annoying” property of password-authenticated key exchange protocols. In Jung Hee Cheon, Jean-Pierre Tillich, editors, Proc. 12th International Conference on Post-Quantum Cryptography (PQCrypto) 2021, LNCS, vol. 12841, pp. 154–173. Springer, July 2021. © Springer.

Download

BibTeX

@inproceedings{PQCrypto:EatSte21,
 	Author = {Edward Eaton and Douglas Stebila},
 	Booktitle = {Proc. 12th International Conference on Post-Quantum Cryptography (PQCrypto) 2021},
 	Doi = {10.1007/978-3-030-81293-5_9},
 	Editor = {Jung Hee Cheon and Jean-Pierre Tillich},
 	Month = {July},
 	Pages = {154--173},
 	Publisher = {Springer},
 	Series = {LNCS},
 	Title = {The ``quantum annoying'' property of password-authenticated key exchange protocols},
 	Volume = {12841},
 	Year = {2021}
 }

Funding

• Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery grant RGPIN-2016-05146
• NSERC Discovery Accelerator Supplement grant RGPIN-2016-05146
• NSERC Alexander Graham Bell Canada Graduate Scholarship