How to Compare Bandwidth Constrained Two-Party Secure Messaging Protocols: A Quest for A More Efficient and Secure Post-Quantum Protocol

Transitioning existing classical two-party secure messaging protocols to post-quantum protocols has been an active movement in practice in recent years: Apple's PQ3 protocol and the recent Triple Ratchet protocol being investigated by the Signal team with academics (Dodis et al. Eprint'25). However, due to the large communication overhead of post-quantum primitives, numerous design choices non-existent in the classical setting are being explored, rendering comparison of secure messaging protocols difficult, if not impossible.

In this work, we thus propose a new pragmatic metric to measure how secure a messaging protocol is, enabling a concrete methodology to compare secure messaging protocols. However, as we uncover that there can be no "optimal" protocol, we set out to find the best protocol under practical scenarios. To this end, we experimentally compare various messaging protocols under real-world constraints such as bandwidth limits and messaging behaviors. Independently, we also uncover untapped optimizations which we call opportunistic sending, leading to better post-quantum messaging protocols. To capture these optimizations, we further propose sparse continuous key agreement as a fundamental building block for secure messaging protocols, which could be of independent interest.