Annoying Everyone: Security in the Presence of Limited Quantum Adversaries

252 / BBB

2025-07-22

Dr. Marcel Tiepelt

15:45

The notion of quantum-annoyance (Eaton and Stebila, PQCrypto 2021) models password-authenticated key exchange (PAKE) security against classical adversaries with a discrete logarithm (Dlog) oracle, assuming each password guess requires one oracle query. However, quantum adversaries can violate this guarantee by combining Grover’s and Shor’s algorithms to recover passwords with fewer Dlog computations. We introduce a generalized annoyance game to quantify the effort required by adversaries to guess passwords if they can solve a computational problem. This framework enables security analyses that scale with adversarial power and password entropy, and which allows to to prove quantum query bounds for annoyance. Applying it to the CPace protocol, we recover prior classical results and derive new bounds against quantum adversaries. Our contribution provides a unified, formal foundation for evaluating PAKE robustness in the post-quantum era.