[CFRG] Re: Random-access authenticated encryption (raAE) draft

[Mark Xue <[e-mail]>]

Thanks much for this Nick. We have need of such a primitive for our end-to-end encrypted messenger, both for encryption at rest and attachment encryption in transit. I've also looked at some of the prior work as a basis for our implementation; a draft that builds on them would be preferable. We've already made some headway on a swift implementation of an earlier version of this draft.

Mark

> From: Nick Sullivan <[e-mail]>
> Date: July 13, 2026 at 3:54:50 PM PDT
> To: CFRG <[e-mail]>
> Subject: Random-access authenticated encryption (raAE) draft
> 
> Hi all,
> 
> Writing as an author, not a chair. I've been working on a draft I want to share with the group. This is not a call for adoption, just sharing the early draft in case there's interest. Comments and reviews welcome.
> 
> The problem. Applications dealing with large encrypted objects (encrypted backups, encrypted archives, object stores) need to read any part of the object without decrypting the whole thing. They also need to verify that each part read belongs to the current object at its claimed position, without processing the entire object. Mutable objects, like encrypted file formats, encrypted disk images, and object stores that accept partial updates, also need in-place modification of any part without re-encrypting the whole. The positional and inclusion proofs should also remain valid after each modification. Take an encrypted database file or an encrypted disk image: any block is read or written by index, and a reader wants to know that the block it reads really belongs at the offset it came from in the current image, without re-hashing every block on every write. No proven security notion in the literature covers all of this under one primitive. As such, each application ends up rolling its own segmented AE layer, mostly without security proofs for the rewrite and whole-object cases.
> 
> Prior work covers pieces of the problem. CHAIN (Hoang, Reyhanitabar, Rogaway, Vizár 2015) is sequential. STREAM (same paper) supports random-access decryption of individual segments and encodes a final-segment bit for truncation detection, but has no whole-object snapshot and no in-place rewrite. Its deployed relatives (Tink Streaming AEAD, OpenPGP v2 SEIPD) are write-once streaming formats and don't expose rewrite at all. The v2 SEIPD design is itself the outcome of Efail (Poddebniak et al., USENIX 2018), where v1's whole-message integrity failed and applications acted on unauthenticated plaintext. FLOE (Fábrega, Len, Ristenpart, Rubin; ePrint 2025/2275) formalizes random-access AEAD security cleanly and gives a proven construction. This work builds on that formal foundation.
> 
> I've posted draft-sullivan-cfrg-raae-02, "Random-Access Authenticated Encryption." It covers the primitive, the security notions, the prior constructions in the space, and a concrete family of instantiations with test vectors called SEAL (Segmented Encryption and Authentication Layer), as well as a security analysis (companion paper forthcoming) and write/rewrite budgets.
> 
> The draft has two layers. raAE is the abstract primitive: the base interface and security notions come from Fábrega et al., which this document extends. SEAL is one concrete construction of raAE, parameterized by an AEAD, a KDF, and an epoch length. It has two profiles (immutable and mutable) and an optional snapshot authenticator that binds the whole segment set and updates cheaply on rewrite. A protocol that would previously have signed the whole encrypted object can sign the snapshot authenticator instead and get the same authentication scope without touching the segments. The snapshot authenticator is also not a single construction, different authenticators fit different consuming-protocol contexts. For example, settings that supply only a single CEKs and owner per object versus settings with a shared CEK (as in MLS) necessitate different authenticators.
> 
> Freshness against whole-object rollback, storage transactions, and key management are explicitly out of scope. Those belong in a consuming protocol.
> 
> The shortest path to a concrete, testable thing is to read SEAL-simple(AES-256-GCM, HKDF-SHA-256) in Appendix E, which is the degenerate case for SEAL with no rewrites or snapshot authentication and fixed legacy AEAD/KDF.
> 
> Reviews and comments on the framing, the security notions, the construction, or the scope are all useful.
> 
> Draft: https://www.ietf.org/archive/id/draft-sullivan-cfrg-raae-02.html
> 
> Best,
> Nick