International Association
for Cryptologic Research

End-to-end encryption (E2EE) allows data to be outsourced and stored on an untrusted server, such as in the cloud, without compromising its privacy. The need for stronger cryptographic guarantees for outsourced persistent data (such as encrypted files in cloud storage) has been highlighted by recent attacks on E2EE cloud storage providers, which all identify sharing as one of the main challenges. But even recently proposed E2EE cloud storage protocols which address this challenge suffer from another problem: when data is shared between a group of users, they all share access to the same, static, key material used for data encryption. This means that when the group membership changes, access control is only enforced by the server; security breaches or compelled disclosure would let even a removed member decrypt both current and future shared data. In this talk, we explore stronger security guarantees for groups of users and the data they share, and implement a practical system that delivers them. We propose to move away from the use of static keys for data encryption in the setting of file sharing. Taking inspiration from the related setting of continuous group key agreement (CGKA) [3] and the MLS standardization effort for group messaging, we introduce a new primitive, called group key progression, that enables a dynamic group of users to agree on a persistent sequence of keys. With our efficient instantiation of this primitive, called Grappa, group members can secure future and past data from former and future group members, respectively, while themselves retaining access to all of their data. We avoid expensive data re-encryption and ensure that all users in Grappa only need to keep a compact cryptographic state. Grappa uses CGKA as a core building block to transport key updates between users, hence finding a use-case for MLS beyond group messaging. In this talk, we want to share our take-aways from the journey of developing a file sharing system with strong security, from the novel theoretical building blocks, to challenges on the path to practice. On the theoretical side, we begin by showing that forward security (FS) and post-compromise security (PCS)—which are standard security notions for data in transit—are fundamentally more challenging to achieve for data at rest. Persistent data hence necessitates tailored methods to ensure strong end-to-end security. Instead of aiming for FS and PCS, we propose the new security notion of cryptographically-enforced interval access control (IAC), which gives similar guarantees in the common setting of persistent data applications where a group of users share access to the outsourced data, such as file sharing. On the practical side, we spent significant engineering effort to implement a file sharing system which utilizes Grappa to achieve both end-to-end security and IAC. In doing so, we uncovered several interesting limitations of the current cryptography ecosystem that we believe to be of interest to the RWC audience. These include the lack of support for low-level cryptographic primitives in the Web Crypto API, barriers to using MLS outside of the secure messaging context as a transport layer for Grappa, and challenges with developing new cryptographic applications for cross-platform usage.

Multi-Key Homomorphic Signatures (MKHS) allow one to evaluate a function on data signed by distinct users while producing a succinct and publicly-verifiable certificate of the correctness of the result. All the constructions of MKHS in the state of the art achieve a weak level of succinctness where signatures are succinct in the total number of inputs but grow linearly with the number of users involved in the computation. The only exception is a SNARK-based construction which relies on a strong notion of knowledge soundness in the presence of signing oracles that not only requires non-falsifiable assumptions but also encounters some impossibility results. In this work, we present the first construction of MKHS that are fully succinct (also with respect to the number of users) while achieving adaptive security under standard falsifiable assumptions. Our result is achieved through a novel combination of batch arguments for NP (BARGs) and functional commitments (FC), and yields diverse MKHS instantiations for circuits of unbounded depth based on either pairing or lattice assumptions. Additionally, our schemes support efficient verification with pre-processing, and they can easily be extended to achieve multi-hop evaluation and context-hiding.

A functional commitment (FC) scheme allows one to commit to a vector $\vec{x}$ and later produce a short opening proof of $(f, f(\vec{x}))$ for any admissible function $f$. Since their inception, FC schemes supporting ever more expressive classes of functions have been proposed. In this work, we introduce a novel primitive that we call chainable functional commitment (CFC), which extends the functionality of FCs by allowing one to 1) open to functions of multiple inputs $f(\vec x_1, \ldots, \vec x_m)$ that are committed independently, 2) while preserving the output also in committed form. We show that CFCs for quadratic polynomial maps generically imply FCs for circuits. Then, we efficiently realize CFCs for quadratic polynomials over pairing groups and lattices, resulting in the first FC schemes for circuits of unbounded depth based on either pairing-based or lattice-based falsifiable assumptions. Our FCs require fixing a-priori only the maximal width of the circuit to be evaluated, and have opening proofs whose size only depends on the depth of the circuit. Additionally, our FCs feature other nice properties such as being additively homomorphic and supporting sublinear-time verification after offline preprocessing. Using a recent transformation that constructs homomorphic signatures (HS) from FCs, we obtain the first pairing- and lattice-based realisations of HS for bounded-width, but unbounded-depth, circuits. Prior to this work, the only HS for general circuits is lattice-based and requires bounding the circuit depth at setup time.

Developing end-to-end encrypted instant messaging solutions for group conversations is an ongoing challenge that has garnered significant attention from practitioners and the cryptographic community alike. Notably, industry-leading messaging apps such as WhatsApp and Signal Messenger have adopted the Sender Keys protocol, where each group member shares their own symmetric encryption key with others. Despite its widespread adoption, Sender Keys has never been formally modelled in the cryptographic literature, raising the following natural question: What can be proven about the security of the Sender Keys protocol, and how can we practically mitigate its shortcomings? In addressing this question, we first introduce a novel security model to suit protocols like Sender Keys, deviating from conventional group key agreement-based abstractions. Our framework allows for a natural integration of two-party messaging within group messaging sessions that may be of independent interest. Leveraging this framework, we conduct the first formal analysis of the Sender Keys protocol, and prove it satisfies a weak notion of security. Towards improving security, we propose a series of efficient modifications to Sender Keys without imposing significant performance overhead. We combine these refinements into a new protocol that we call Sender Keys+, which may be of interest both in theory and practice.