[MLS] SlimMLS

[Raphael Robert <[e-mail]>]

Hi everyone,

We want to share draft-robert-mls-slim [1], an MLS extension to address efficiency issues with PQ resistant cipher suites.

TL;DR: The idea behind SlimMLS [1] is to significantly reduce the additional overhead of PQ cipher suites in a way that is complementary to draft-ietf-mls-combiner [2]. It gives applications more flexibility to optimize in different deployment scenarios and is intended to preserve the all MLS security guarantees.

Introduction/Context
---

MLS was designed to support large groups. Section 2.1 of RFC9750 says

> A group may be […] as large as hundreds of thousands [of clients].

And Section 6 says

> Messaging systems that implement MLS […] aim to scale to groups with tens of thousands of members.

When using PQ cipher suites, groups of that size can become impractical because the O(log n) update complexity hides a large constant factor. Consider the following minimal viable PQ secure example setting: A 1,000-member group with Ed25519 signatures, an ML-KEM768/X25519 hybrid KEM, a full tree, and small credentials (see appendix for size breakdown):

- Individual update Commit: ~25 KB per delivered Commit
- Welcome: ~2.6 MB
- Catching up after 100 update Commits: ~2.5 MB

For larger groups and/or groups with a PQ signature scheme or larger credentials, those sizes balloon even further.

Idea
---

The idea behind SlimMLS is to mitigate this issue. It changes MLS in three major ways:

- Replace large objects (PQ keys, credentials, etc.) with hash references
- Avoid unnecessary upload and download of large objects (building on ideas from draft-mularczyk-mls-splitcommit [3])
- Reduce the number of signatures required for update Commits and KeyPackages (building on ideas from draft-kohbrok-mls-fewer-signatures [4])

Distinguishing between large objects and their references gives applications more flexibility to optimize distribution, especially in the server-assisted scenario. For example, it allows clients to download large objects selectively as needed and de-duplicate between groups.

In the default mode, where clients fetch and verify the referenced objects needed for vanilla MLS validation, these modifications are intended to preserve the relevant MLS security guarantees.

Impact
---

Revisiting the example above, SlimMLS reduces payload size significantly (see appendix for size breakdown):

- Individual update Commit: ~26 KB upload, but only ~3 KB download (~90% reduction
- Welcome: ~370 KB (~86% reduction)
- Catching up after 100 update Commits: ~200 KB (~92% reduction)

In short, SlimMLS makes MLS significantly more efficient for PQ cipher suites and gives applications more flexibility to trade off membership authentication and download size.

Relation to other drafts
---

SlimMLS is complementary to draft-ietf-mls-combiner. Where draft-ietf-mls-combiner allows applications to independently control the frequency of PQ and traditional updates by linking two groups with different ciphersuites. SlimMLS reduces the size of the payloads incurred by the PQ group.

While the intention behind SlimMLS is not to impact the security guarantees of MLS, it could optionally be used in a mode where clients decide to only selectively download the full leaf information (credentials, signatures, signature keys). In that scenario, SlimMLS can cater to the same use cases Partial MLS [5] was designed for. It’s an open quest whether this is desired, given the obvious impact on the authentication guarantees.

We’ve published the draft on the datatracker [1] and are looking forward to your feedback, as well as a discussion at IETF 126 in Vienna.

Raphael & Konrad

---

[1] https://datatracker.ietf.org/doc/draft-robert-mls-slim/

[2] https://datatracker.ietf.org/doc/draft-ietf-mls-combiner/

[3] https://datatracker.ietf.org/doc/draft-mularczyk-mls-splitcommit/

[4] https://datatracker.ietf.org/doc/draft-kohbrok-mls-fewer-signatures/

[5] https://datatracker.ietf.org/doc/draft-ietf-mls-partial/


Appendix
---

Payload size breakdown for a 1,000-member group, 10 path nodes, ML-
KEM768/X25519, Ed25519, full tree, small credentials.

For simplicity, the following lists the dominant large objects per message and groups all remaining objects, references, signatures, credentials, MACs, framing, and vector overhead into a single "smaller objects and overhead" line.

For more size calculations (other group sizes, ciphersuites, sparse trees, etc.), use the message size calculation script in the draft repo: https://github.com/raphaelrobert/slim-mls

Vanilla MLS example:

Individual update Commit:

11 HPKEPublicKey = 11 * 1,218 = 13,398 B
(1 committer leaf key + 10 path-node keys)
10 UpdatePath HPKECiphertext = 10 * 1,171 = 11,710 B
Smaller objects and overhead = 358 B

Total = 25,466 B ~= 25 KB

Welcome:

1,999 HPKEPublicKey = 1,999 * 1,218 = 2,434,782 B
(1,000 leaf keys + 999 parent-node keys)
Smaller objects and overhead = 186,463 B

Total = 2,621,245 B ~= 2.6 MB

Catch-up after 100 Commits:

100 * Individual update Commit
= 100 * 25,466 B
= 2,546,600 B ~= 2.5 MB

SlimMLS example:

Individual update Commit:

Upload: same dominant HPKE objects as vanilla MLS

11 HPKEPublicKey = 11 * 1,218 = 13,398 B
10 UpdatePath HPKECiphertext = 10 * 1,171 = 11,710 B
Smaller objects and overhead = 1,037 B

Total upload = 26,145 B ~= 26 KB

Download:

1 HPKEPublicKey = 1,218 B
1 UpdatePath HPKECiphertext  = 1,171 B
Smaller objects and overhead = 740 B

Total download = 3,129 B ~= 3 KB

Welcome:

10 HPKEPublicKey = 10 * 1,218 = 12,180 B
(joiner's copath keys)
Smaller objects and overhead = 360,398 B

Total = 372,578 B ~= 370 KB

Catch-up:

99 Commits with basic delivery, without downloading public keys not needed for
processing:

1 UpdatePath HPKECiphertext  = 1,171 B
Smaller objects and overhead = 739 B

99 * (1,171 B + 739 B)
= 99 * 1,910 B
= 189,090 B

Final Commit with update-capable delivery:

1 HPKEPublicKey = 1,218 B
1 UpdatePath HPKECiphertext  = 1,171 B
Smaller objects and overhead = 740 B

Total final Commit = 3,129 B

Total catch-up:
189,090 B + 3,129 B = 192,219 B ~= 200 KB