International Association
for Cryptologic Research

The Fast IDentity Online (FIDO) Alliance develops open standards to replace password-based authentication methods by token-based solutions. The latest protocol suite FIDO2 provides such a promising alternative which many key players have already adopted or are willing to. The central authentication mechanism WebAuthn uses cryptographic keys stored on the device to authenticate clients to a relying party via a challenge-response protocol. Yet, this approach leaves several open issues about post-quantum secure instantiations and methods for recovery of credentials. Recently Frymann et al. (CCS 2020, ACNS 2023, EuroS&P 2023) made significant progress to advance the security of FIDO2 sys- tems. Following a suggestion by device manufacturer Yubico, they considered a WebAuthn-compliant mechanism to store recovery information at the relying party. If required, the client can recover essential data with the help of a backup authenticator device. They analyzed the Diffie-Hellman based scheme, showing that it provides basic authentication and privacy features. One of their solutions also provides a post-quantum secure variant, but only for a weaker version of authentication security. Our starting point is to note that the security definitions of Fry- mann et al., especially the privacy notion, do not seem to capture real threats appropriately. We thus strengthen the notions. De- spite this strengthening, we show a generic construction based on (anonymous) KEMs and signature schemes. It follows that, us- ing post-quantum secure instances, like Kyber and Dilitihium, one immediately obtains a post-quantum and strongly secure solution.