A Modular Design Paradigm & Immediate Decryption

Authors: Joël Alwen, Sandro Coretti, Yevgeniy Dodis
Venue: EUROCRYPT
Date: 2019
Full Version: https://eprint.iacr.org/2018/1037
Proceedings Version: https://link.springer.com/chapter/10.1007%2F978-3-030-17653-2_5

This brings us to Wickr’s peer reviewed crypto publication set to appear at EUROCRYPT 2019 this May (which was the result of concurrent work to ). Together with two cryptographers at New York University, Wickr focused on two key goals:

• Providing a clean, intuitive, and more general understanding of how to build practical 2-party SMPs.
• Making explicit (and realizing) the capability of an SMP to resist message loss and, more generally, unreliable (or even adversarial) network conditions.

Central to the the first goal is the works introduction of a new, very clean and intuitive modular (black-box) approach to building provably secure 2-party SMPs from three much simpler building blocks. This technique results in a host of interesting consequences and applications including:

1. By instantiating the building blocks with (standard) assumptions including the Decisional Deffie-Hellman (DDH) assumption, the original Double Ratchet (and Signal) protocols can be recovered. In particular, this provides a modular (and, arguably, much cleaner, more intuitive) security proof for those protocols.
2. More generally, the work shows how the building blocks can be instantiated from a variety of black-box and concrete number theoretic assumption. In particular, this gives rise to the first post-quantum (LWE based) provably secure messaging (and Double Ratchet-like) protocols.
3. The work provides a new instantiation of one of the building blocks from DDH which improves strengthens the Post Compromise Security of the original Double Ratchet at the cost of one group element per message.
4. The paradigm lays the foundations for future improvements by providing clean interfaces to work with and a generic security proof to build an SMP from any constructions realizing those interfaces. For example, in the follow up work , a tighter LWE-based construction of one of the building blocks is provided resulting in a more efficient post-quantum SMP.

The second goal in this work, centered on Message Loss Resilience, is motivated by the general desire to require minimal assumptions about the transport mechanism used by the messaging platform (and the adversaries behavior in manipulating network traffic). It is worth noting, that (as far as we know) all SMPs used in practice support at least some amount of MLR and generally allow for at least some out of order decryption of messages.

With that in mind, we define the (correctness) notion of Immediate Decryption and ensure that any protocol built according to our modular construction paradigm does indeed satisfy the notion. Essentially, the notion formally captures the intuition that regardless of the order that messages are delivered they can always be decrypted (and authenticated) on the spot with out waiting for any further communication. Crucially, this must be achieved with out compromising the security properties of FS and PCS. Whats more, while Immediate Decryption likely precludes attaining certain other strong security goals (e.g. RECOVER-security) we believe that in many (most?) real-world use cases it represents a necessary property for an SMP to have.