Douglas Stebila

Making an asymmetric PAKE quantum-annoying by hiding group elements

Abstract

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.

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

Reference

Marcel Tiepelt, Edward Eaton, Douglas Stebila. Making an asymmetric PAKE quantum-annoying by hiding group elements. In Mauro Conti, Gene Tsudik, editors, Proc. 28th European Symposium on Research in Computer Security (ESORICS) 2023, LNCS, vol. 14344, pp. 168–188. Springer, September 2023. © Springer.

Download

BibTeX

@inproceedings{ESORICS:TieEatSte23,
 	Author = {Marcel Tiepelt and Edward Eaton and Douglas Stebila},
 	Booktitle = {Proc. 28th European Symposium on Research in Computer Security (ESORICS) 2023},
 	Doi = {10.1007/978-3-031-50594-2_9},
 	Editor = {Mauro Conti and Gene Tsudik},
 	Month = {September},
 	Pages = {168--188},
 	Publisher = {Springer},
 	Series = {LNCS},
 	Title = {Making an asymmetric {PAKE} quantum-annoying by hiding group elements},
 	Volume = {14344},
 	Year = {2023}
 }

Funding

• Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery grant RGPIN-2022-03187
• Natural Sciences and Engineering Research Council of Canada (NSERC) Alliance grant ALLRP 578463-22.
• topic Engineering Secure Systems of the Helmholtz Association (HGF)
• KASTEL Security Research Labs