International Association
for Cryptologic Research

Registered Attribute-Based Encryption (RABE) enhances traditional attribute-based encryption by allowing users to register their own public keys, while a key curator transparently aggregates these keys into a compact master public key, addressing key escrow issues. In long-term applications, the compromise of users' secret keys becomes a significant risk, making key revocation a critical functionality. In this paper, we initiate a formal study of key revocation mechanisms for RABE and introduce two types: Deletable Registered Attribute-Based Encryption (DRABE) and Directly Revocable Registered Attribute-Based Encryption (RRABE). The key distinction between these two approaches lies in how the revocation process is managed. In DRABE, the key curator handles revocation by deleting previously registered keys and updating the master public key. In contrast, RRABE bypasses the need for such updates, allowing the encryptor to directly specify a set of revoked users during encryption. Our primary contribution is the construction of DRABE, where we propose a generic framework based on Slotted Registered Attribute-Based Encryption (sRABE), a primitive introduced by Hohenberger et al. at EUROCRYPT 2023. This generic construction inherits the predicate structure of the underlying sRABE scheme, enabling DRABE to support a wide range of predicates. By instantiating our construction with existing sRABE schemes, we obtain efficient pairing-based DRABE schemes for a bounded number of users, as well as schemes for an unbounded number of users, though the latter relies on non-black-box cryptographic techniques. For RRABE, we propose a semi-generic construction for Boolean formulae, utilizing RABE schemes that support these predicates.

The past year has marked significant progress in secure messaging technologies. In March 2023, the Messaging Layer Security (MLS) protocol was standardized by the IETF, followed by Signal's introduction in May 2023 of PQXDH, a post-quantum alternative to the X3DH handshake. In the first part of this presentation, we identify scalability challenges that may hinder the widespread adoption of MLS and Signal in a post-quantum context, particularly in regions with limited mobile data plans. This analysis is backed by real-world quantitative data. In the second part of this talk, we propose a novel protocol with improved bandwidth consumption. It incorporates efficient post-quantum primitives, specifically multi-recipient public key encryption (mPKEs), optimized for secure messaging. We anticipate that our approach will be an order of magnitude more efficient than direct adaptations of existing protocols in practical scenarios.

In this talk, we first systematically analyze the privacy offered by Signal and MLS and observe a critical shortcoming of MLS compared to Signal. In short, MLS leaks much more _metadata_ than Signal. In privacy-critical scenarios, dismissing this metadata leakage puts at risk the users who may otherwise believe that MLS offers the exact same level of security as Signal. We then propose an efficient and provably secure solution to bootstrap the current MLS to be as metadata-hiding (or, in some metrics, even more) as Signal. Our key insight is to leverage the existence of a _unique_ continuously evolving group secret key shared by the group to perform an anonymous membership authentication protocol.

The Signal protocol is a secure instant messaging protocol that underlies the security of numerous applications such as WhatsApp, Skype, Facebook Messenger among many others. The Signal protocol consists of two sub-protocols known as the X3DH protocol and the double ratchet protocol, where the latter has recently gained much attention. For instance, Alwen, Coretti, and Dodis (Eurocrypt’19) provided a concrete security model along with a generic construction based on simple building blocks that are instantiable from versatile assumptions, including post-quantum ones. In contrast, as far as we are aware, works focusing on the X3DH protocol seem limited. In this work, we cast the X3DH protocol as a specific type of authenticated key exchange (AKE) protocol, which we call a Signal-conforming AKE protocol, and formally define its security model based on the vast prior works on AKE protocols. We then provide the first efficient generic construction of a Signal-conforming AKE protocol based on standard cryptographic primitives such as key encapsulation mechanisms (KEM) and signature schemes. Specifically, this results in the first post-quantum secure replacement of the X3DH protocol based on well-established assumptions. Similar to the X3DH protocol, our Signal-conforming AKE protocol offers a strong (or stronger) flavor of security, where the exchanged key remains secure even when all the non-trivial combinations of the long-term secrets and session-specific secrets are compromised. Moreover, our protocol has a weak flavor of deniability and we further show how to progressively strengthen it using ring signatures and/or non-interactive zero-knowledge proof systems. Finally, we provide a full-fledged, generic C implementation of our (weakly deniable) protocol. We instantiate it with several Round 3 candidates (finalists and alternates) to the NIST post-quantum standardization process and compare the resulting bandwidth and computation performances. Our implementation is publicly available.

The Signal protocol is a secure instant messaging protocol that underlies the security of numerous applications such as WhatsApp, Skype, Facebook Messenger among many others. The Signal protocol consists of two sub-protocols known as the X3DH protocol and the double ratchet protocol, where the latter has recently gained much attention. For instance, Alwen, Coretti, and Dodis (Eurocrypt'19) provided a concrete security model along with a generic construction based on simple building blocks that are instantiable from versatile assumptions, including post-quantum ones. In contrast, as far as we are aware, works focusing on the X3DH protocol seem limited. In this work, we cast the X3DH protocol as a specific type of authenticated key exchange (AKE) protocol, which we call a Signal-conforming AKE protocol, and formally define its security model based on the vast prior work on AKE protocols. We then provide the first efficient generic construction of a Signal-conforming AKE protocol based on standard cryptographic primitives such as key encapsulation mechanisms (KEM) and signature schemes. Specifically, this results in the first post-quantum secure replacement of the X3DH protocol on well-established assumptions. Similar to the X3DH protocol, our Signal-conforming AKE protocol offers a strong (or stronger) flavor of security, where the exchanged key remains secure even when all the non-trivial combinations of the long-term secrets and session-specific secrets are compromised. Moreover, our protocol has a weak flavor of deniability and we further show how to strengthen it using ring signatures. Finally, we provide a full-fledged, generic C implementation of our (weakly deniable) protocol. We instantiate it with several Round 3 candidates (finalists and alternates) to the NIST post-quantum standardization process and compare the resulting bandwidth and computation performances. Our implementation is publicly available.