Paper 2018/954

Efficient Ratcheting: Almost-Optimal Guarantees for Secure Messaging

Daniel Jost, Ueli Maurer, and Marta Mularczyk

Abstract

In the era of mass surveillance and information breaches, privacy of Internet communication, and messaging in particular, is a growing concern. As secure messaging protocols are executed on the not-so-secure end-user devices, and because their sessions are long-lived, they aim to guarantee strong security even if secret states and local randomness can be exposed. The most basic security properties, including forward secrecy, can be achieved using standard techniques such as authenticated encryption. Modern protocols, such as Signal, go one step further and additionally provide the so-called backward secrecy, or healing from state exposures. These additional guarantees come at the price of a slight efficiency loss (they require public-key primitives). On the opposite side of the spectrum is the work by Jaeger and Stepanovs and by Poettering and Rösler, which characterizes the optimal security a secure-messaging scheme can achieve. However, their proof-of-concept constructions suffer from an extreme efficiency loss compared to Signal. Moreover, this caveat seems inherent. In this paper, we explore the area in between. That is, our starting point are the basic, efficient constructions. We then ask the question: how far can we go towards the optimal security without losing too much efficiency? We present a construction with guarantees much stronger than those achieved by Signal, and slightly weaker than optimal, yet its efficiency is closer to that of Signal (we only use standard public-key cryptography). On a technical level, achieving optimal guarantees inherently requires key-updating public-key primitives, where the update information is allowed to be public. We consider secret update information instead. Since a state exposure temporally breaks confidentiality, we carefully design such secretly-updatable primitives whose security degrades gracefully if the supposedly secret update information leaks.

Note: Fixed a couple of minor issues. Thanks to Joseph Jaeger and Paul Rösler for the valuable feedback.