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

[Wang Guilin <[e-mail]>]

> 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.

Does this mean that some changes in ciphertext do not affect decryption?

raAE may relate to CDC (Content-Defined Chunking), a technology used in cloud backup setting. Here is a paper from the team of Prof. Kenny Paterson.

Breaking and Fixing Content-Defined Chunking. CCS 2025: 2294-2308

Cheers,

Guilin

发件人：Martin Thomson <[e-mail]<mailto:[e-mail]>>
收件人：[e-mail] <[e-mail]<mailto:[e-mail]>>
时 间：2026-07-14 16:02:33
主 题：[CFRG] Re: Random-access authenticated encryption (raAE) draft

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]<mailto:[e-mail]>
> To unsubscribe send an email to [e-mail]<mailto:[e-mail]>

_______________________________________________
CFRG mailing list -- [e-mail]<mailto:[e-mail]>
To unsubscribe send an email to [e-mail]<mailto:[e-mail]>