International Association
for Cryptologic Research

The recently passed EU Digital Markets Act (DMA) will require large “gatekeeper” companies like Meta and Apple who run widely used end-to-end encrypted (E2EE) messaging apps to allow interoperability with other smaller E2EE apps, on request. Users will be able to communicate with each other across providers: for example, a user on Signal would be able to chat with a user on WhatsApp. The law itself is light on details or concrete requirements, leading to both its supporters and detractors arguing based more on speculation rather than hard evidence. One thing these opposing sides agree on is that the DMA’s interoperability mandate will require fundamental changes to the design of existing E2EE messaging. But what changes will the law require, exactly? How will these requirements be translated into new designs? Will these new designs have new security challenges? These and other critical technical questions lack clear answers today; since legal interoperability requirements under the DMA could take effect as soon as March 2024, and similar legislation has been proposed in the US, it is imperative that the community starts trying to answer these questions now. The purpose of this talk is to introduce E2EE messaging interoperability to the broader cryptography community. Our first task will be to interpret -- guided by existing legal analyses, where available -- the text of the DMA’s interoperability mandate for the community, highlighting requirements and identifying key pieces we believe will have the biggest impact on new designs. Next, we will break down the specific challenges of interoperability in three key areas: identity, protocols, and abuse prevention. For each area, we will briefly survey the landscape of possible designs, critically evaluate proposed solutions, identify novel cryptography-focused questions where more research is needed, and elaborate a minimal list of properties we believe any solution should satisfy. We also identify a set of overarching principles that should guide new designs, e.g. limiting cross-platform metadata leakage. Our goal is to bring the cryptography community into the ongoing dialogue between regulators, policy scholars, industry practitioners, and users about what interoperable E2EE messaging will look like.

Recently, the area of Key Transparency (KT) has received a lot of attention, as it allows the service provider to provide auditable and verifiable proofs regarding authenticity of public keys used by various participants. Moreover, it is highly preferable to do it in a privacy-preserving ways, so that users and auditors do not learn anything beyond what is necessary to keep the service provider accountable. Abstractly, the problem of building such systems reduces to constructing so called append-only Zero-Knowledge Sets (aZKS). Unfortunately, none of the previous aZKS constructions adequately addressed the problem of key rotation, which would provide Post-Compromise Security (PCS) in case the server in compromised. In this work we address this concern, and refine an extension of aZKS called Rotatable ZKS (RZKS). In addition to addressing the PCS concern, our notion of RZKS has several other attractive features, such as stronger soundness notion (called extractability), and the ability for a stale communication party to quickly catch up with the current epoch, while ensuring the the server did not erase any of the past data. Of independent interest, we also introduce and build a new primitive called Rotatable Verifiable Random Function (VRF), and show how to build RZKS in a modular fashion from rotatable VRF, ordered accumulators and append-only vector commitment schemes.

Generating additive secret shares of a shuffled dataset - such that neither party knows the order in which it is permuted - is a fundamental building block in many protocols, such as secure collaborative filtering, oblivious sorting, and secure function evaluation on set intersection. Traditional approaches to this problem either involve expensive public-key based crypto or using symmetric crypto on permutation networks. While public-key-based solutions are bandwidth efficient, they are computation-heavy. On the other hand, constructions based on permutation networks are communication-bound, especially when the dataset contains large elements, for e.g., feature vectors in an ML context. We design a new 2-party protocol for this task of computing secret shares of shuffled data, which we refer to as secret-shared shuffle. Our protocol is secure against a static semi-honest adversary. At the heart of our approach is a new primitive we define (which we call ``Share Translation'') that generates two sets of pseudorandom values ``correlated via the permutation''. This allows us to reduce the problem of shuffling the dataset to the problem of shuffling pseudorandom values, which enables optimizations both in computation and communication. We then design a Share Translation protocol based on oblivious transfer and puncturable PRFs. Our final protocol for secret-shared shuffle uses lightweight operations like XOR and PRGs, and in particular doesn't use public-key operations besides the base OTs. As a result, our protocol is concretely more efficient than the existing solutions. In particular, we are two-three orders of magnitude faster than public-key-based approach and one order of magnitude faster compared to the best known symmetric-key approach when the elements are moderately large.