Paper 2025/154

Shadowfax: Hybrid Security and Deniability for AKEMs

Abstract

As cryptographic protocols transition to post-quantum security, most adopt hybrid solutions combining classical and post-quantum assumptions. This shift often sacrifices efficiency, compactness, or even security. One such property is deniability, which enables users to plausibly deny authorship of potentially incriminating messages. While classical protocols like X3DH key agreement (used in Signal and WhatsApp) provide deniability, post-quantum protocols like PQXDH and Apple's iMessage with PQ3 do not. This work addresses this gap by investigating how to efficiently preserve deniability in post-quantum protocols. Specifically, we propose two hybrid schemes for authenticated key encapsulation mechanisms (AKEMs). The first is a black-box construction that preserves deniability when both constituent AKEMs are deniable. The second is Shadowfax, a non-black-box AKEM that achieves hybrid security, integrating a classical non-interactive key exchange, a post-quantum key encapsulation mechanism, and a post-quantum ring signature. Shadowfax satisfies deniability in both dishonest and honest receiver settings, relying on statistical security in the former and on a single pre- or post-quantum assumption in the latter. Finally, we provide several portable implementations of Shadowfax. When instantiated with standardised components (ML-KEM and Falcon), Shadowfax yields ciphertexts of 1728 bytes and public keys of 2036 bytes, with encapsulation and decapsulation costs of 1.8M and 0.7M cycles on an Apple M1 Pro.

Note: Revised introduction. Implementation section includes additional instantiations with standardised components.