International Association
for Cryptologic Research

Recent years have seen many advances in provably secure messaging protocols, both in features and detailed security proofs. However, some important areas of the design space have not yet been explored.

In this work we design the first provably secure protocol that at the same time achieves (i) strong resilience against fine-grained compromise, (ii) post-quantum security, and (iii) immediate decryption with constant-size overhead. Besides these main design goals, we prove that our protocol achieves even stronger security than protocols previously conjectured to be in this space. Finally, we introduce a novel definition of offline deniability suitable for our setting, and prove that our protocol meets it, notably when combined with a post-quantum initial key exchange.

We use game-based security notions to be able to prove post-quantum and strong compromise resilience. At a technical level, we build on the SM protocol and security notion from [1], but the security properties that we aim for require a different proof approach. Our work shows how these properties can be simultaneously achieved, and our temporal healing and offline deniability notions are of independent interest.