International Association
for Cryptologic Research

There has been a recent interest to develop and standardize Robust Authenticated Encryption schemes. NIST, for example, is considering an Accordion mode for (wideblock) tweakable blockcipher, with Robust AE as a primary application. At the same time, recent attacks and applications suggest that encryption context needs to be committed. Indeed, committing security is also a design consideration in Accordion mode. In this work, we give a modular solution for this problem. We first show how to transform any wideblock tweakable blockcipher TE to a Robust AE scheme SE that commits just the key. The overhead is cheap, just a few finite-field multiplications and blockcipher calls. If one wants to commit the entire encryption context, one can simply hash the context to derive a 256-bit subkey, and uses SE on that subkey. The use of 256-bit key on SE only means that it has to rely on AES-256 but doesn't require TE to have 256-bit key. Our approach frees the Accordion designs from consideration of committing security. Moreover, it gives a big saving for several key-committing applications that don't want to pay the inherent hashing cost of full committing.

The increasing harms caused by hate, harassment, and other forms of abuse online have motivated major platforms to explore hierarchical governance. The idea is to allow communities to have designated members take on moderation and leadership duties; meanwhile, members can still escalate issues to the platform. But these promising approaches have only been explored in plaintext settings where community content is public to the platform. It is unclear how one can realize hierarchical governance in the huge and increasing number of online communities that utilize end-to-end encrypted (E2EE) messaging for privacy. This talk will argue for the importance of adapting hierarchical governance to E2EE platforms, share some of our recent work towards privacy-preserving hierarchical governance, and discuss ongoing challenges in this space.

This talk will propose a new approach for building the next generation of AEAD. In the last few years, researchers and practitioners have discovered that widely deployed AEAD schemes, designed almost two decades ago, have many limitations. These range from uncomfortably small security margins to outright security vulnerabilities. We will discuss foundational theory and concrete designs for the next generation of AEAD schemes. Our designs better support real-world workloads while retaining performance.

A line of recent work has highlighted the importance of context commitment security, which asks that authenticated encryption with associated data (AEAD) schemes will not decrypt the same adversarially-chosen ciphertext under two different, adversarially-chosen contexts (secret key, associated data, and nonce). Despite a spate of recent attacks, many open questions remain around context commitment; most obviously nothing is known about the commitment security of important schemes such as CCM, EAX, and SIV. We resolve these open questions, and more. Our approach is to, first, introduce a new framework that helps us more granularly define context commitment security in terms of what portions of a context are adversarially controlled. We go on to formulate a new security notion, called context discoverability, which can be viewed as analogous to preimage resistance from the hashing literature. We show that unrestricted context commitment security (the adversary controls all of the two contexts) implies context discoverability security for a class of schemes encompassing most schemes used in practice. Then, we show new context discovery attacks against a wide set of AEAD schemes, including CCM, EAX, SIV, GCM, and OCB3, and, by our general result, this gives new unrestricted context commitment attacks against them. Finally, we explore the case of restricted context commitment security for the original SIV mode, for which no prior attack techniques work (including our context discovery based ones). We are nevertheless able to give a novel $\bigO(2^{n/3})$ attack using Wagner's k-tree algorithm for the generalized birthday problem.

This talk will make the case, on behalf of a group of authors of many of the recent results on commitment in AEAD, that the community should prioritize and standardize AEAD designs that achieve commitment to the key, associated data, and nonce. We call this context commitment. The main benefit of such schemes is that they preclude practitioners from having to make choices about what parts of the context should be committing. While context commitment has not yet seen the same kind of attacks in practice as key commitment, we expect them to be discovered and, to get ahead of attackers, standardization efforts should therefore target context commitment. We will start our presentation by defining context commitment [BH22], highlighting in particular how it is not formally implied by key commitment. We next discuss new attacks that exploit this gap, including showing context-commitment attacks on recently proposed key commitment-secure schemes [Kra19, §3.1.1], [ADG+22, §5.3], and [D+22]. These hint at a rich landscape of possible attacks, and we briefly discuss frameworks that explore this landscape [BH22,CR22,MLGR22]. Finally, we provide an overview of recent proposals for new AEAD schemes that achieve context commitment, and discuss avenues for future work.