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

[Nick Sullivan <[e-mail]>]

Hi John,

I'm encouraged by your enthusiasm. There was a risk that this document
would be misinterpreted as *just another segmented encryption scheme*,
rather than what it really is: a new basic interface for symmetric
cryptography. The inspiration for this framing goes to the FLOE authors,
I'm just extending their work and filling in some gaps.

I'll look into finding a slot for a side meeting.

Best,
Nick

On Wed, Jul 15, 2026 at 2:50 PM John Mattsson <[e-mail]>
wrote:

> I would personally be fine with an IETF–CFRG split.
>
> Will raAE and SEAL be discussed anywhere in Vienna (CFRG, DISPATCH,
> Hackathon, side-meeting, etc.)? I think they should be.
>
> Standardizing raAE and defining interoperable formats for its use would be
> one of the most useful ideas I have seen in a long time. I believe such a
> specification would see broad adoption across a wide range of protocols and
> applications.
>
> Cheers,
> John Preuß Mattsson
>
> *From: *Nick Sullivan <[e-mail]>
> *Date: *Wednesday, 15 July 2026 at 15:06
> *To: *Martin Thomson <[e-mail]>; [e-mail] <[e-mail]>
> *Cc: *[e-mail] <
> [e-mail]>;
> [e-mail] <
> [e-mail]>
> *Subject: *[CFRG] Re: Random-access authenticated encryption (raAE) draft
>
> Hi Martin,
>
> Following up on your point that this belongs in the IETF. After some
> reflection, I propose a pressure test: run raAE and SEAL through the
> two-lane model in draft-sullivan-crypto-publication (
> https://datatracker.ietf.org/doc/draft-sullivan-crypto-publication/) the
> pattern generalized from the HPKE WG. SEAL sits at the same abstraction
> layer as HPKE, so it could be a good test of the model.
>
> The two lanes:
>
>   engineering lane (IETF)   |   research lane (CFRG)
>                             |
>   MLS (attachments)         |
>   file encryption (TBD)     |
>   MoQ (?)   OpenPGP (?)     |
>            |                |
>            v                |
>          SEAL <------------------>  raAE
>      concrete raAE          |    abstract primitive
>      via dispatch           |    analogous to AEAD
>
>
> Consumers pool their requirements into SEAL, the engineering piece, which
> goes to dispatch to find its IETF home. raAE stays in CFRG as the security
> foundation for SEAL: the abstract definition, requirements, and security
> reductions for random-access authenticated encryption, building on
> validated public research. The file encryption John suggested in this
> thread could become its own working group or land in an existing one, with
> SEAL under the hood.
>
> There are concrete benefits over current designs for the potential
> consumers marked with a question mark:
> - MoQ adopted an SFrame-based scheme for end-to-end objects in March
> (draft-ietf-moq-secure-objects). It encrypts a whole object in one AEAD
> call, and the draft notes that a large object must arrive in full before
> any validation can start. A SEAL payload validates segment by segment as
> bytes arrive, and a reader can verify one segment of a cached object
> without reading the rest.
> - OpenPGP verifies a signature only after decrypting and hashing the
> entire message. A SEIPD v3 built on SEAL would sign the one snapshot value,
> so a reader verifies a signature over any part of a message without reading
> the rest. raAE also helps with editing.
>
> I've cc'd the authors of both in case there's interest. There are also
> opportunities to consolidate other designs under the raAE primitive
> interface, even if SEAL is not the exact raAE chosen.
>
> What do you think?
>
> Best,
> Nick
>
> On Tue, Jul 14, 2026 at 10:06 AM Nick Sullivan <
> [e-mail]> wrote:
>
> Hi Martin,
>
> I’m not sure I fully agree. Something like SEAL-simple or SEAL-attachment
> is probably pure engineering, but it seems like it would be useful to have
> a comprehensive research-adjacent document like this to lean on for
> analysis.
>
> Nick
>
> On Tue, Jul 14, 2026 at 9:01 AM Martin Thomson <[e-mail]> wrote:
>
> Hi Nick,
>
> I'm going to suggest a DISPATCH outcome for this, which does not involve
> CFRG.  I think that this is pure engineering and the IETF should be the
> place to take it up.  The usual requirements apply, of course: we need to
> see the receipts on customers for the mechanism, etc...
>
> On Tue, Jul 14, 2026, at 00:54, Nick Sullivan wrote:
> > 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
> > <
> https://www.ietf.org/archive/id/draft-sullivan-cfrg-raae-02.html#name-seal-simple-implementation-
> >,
> > 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
> > _______________________________________________
> > CFRG mailing list -- [e-mail]
> > To unsubscribe send an email to [e-mail]
>
> _______________________________________________
> CFRG mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
>
>