MLS(Messaging Layer Security)とグループ鍵管理

解きたい問題：グループになると鍵管理が一気に破綻する

Signal のダブルラチェットは、2者間のエンドツーエンド暗号を前方秘匿性（PFS）付きで美しく解きます。ところがこれをグループへ素朴に拡張すると、コストが爆発します。

素朴な拡張、いわゆるペアワイズ方式（client fanout）では、N 人のグループ内で全メンバーのペアごとにダブルラチェットを張ります。送信者は同じ平文を相手ごとに個別の鍵で暗号化し、N-1 通を送る。これだけなら送信のたびに O(N) で済みますが、本当に痛いのは鍵更新です。誰か1人の端末が漏れた疑いがあり鍵を切り替えたいとき、その人は自分が関わる全ペアの鍵を作り直す必要があり、グループ全体では更新コストが O(N) に膨らみます。1人の離脱で残り全員が鍵を貼り直す――数千人規模ではこれが現実的に回らなくなります。

**MLS（Messaging Layer Security, RFC 9420）**は、この「グループでの鍵更新が線形コストになる」問題を、全員を1本の木に並べることで O(log N) に落とすために設計されたプロトコルです。

TreeKEM：全員を二分木に並べ、更新をパスに限定する

MLS の心臓部が TreeKEM です。発想はこうです。グループの全メンバーを**左平衡二分木（left-balanced binary tree; ratchet tree）の葉（leaf）**に配置し、葉から根（root）までの各中間ノードに鍵ペアを持たせます。各ノードの秘密鍵は、その部分木に属するメンバー全員だけが知っている、という不変条件を保ちます。根のノード鍵から導かれる値が、その epoch のグループ秘密の源になります。

ここで効くのが木の性質です。あるメンバー（葉）が自分の鍵を更新したいとき、影響を受けるのは自分から根までの直接パス（direct path）上のノードだけで、その本数は木の高さ、つまり log2(N) です。残りのノードは無関係なので触りません。

            root
           /    \
        n1        n2
       /  \      /  \
     A     B   C     D     ← 葉（メンバー）

A が鍵更新するとき触るのは A→n1→root の log N 本だけ。
n2 とその子（C,D の鍵）は一切変わらない。

更新時、A は自分のパス上の各ノードに新しい鍵ペアを生成します。問題は「新しいノード秘密鍵を、その部分木の他メンバーにどう安全に配るか」です。TreeKEM はここでcopath（コパス）を使います。パス上の各ノードについて、その兄弟部分木のルート公開鍵で新しいノード秘密（の種）を暗号化するのです。

A が n1 の新秘密を更新 → 兄弟 B の公開鍵で暗号化して B に配る
A が root の新秘密を更新 → 兄弟部分木 n2 のルート公開鍵で暗号化
                           （これ1通で C と D の両方に届く）

肝は最後の行です。n2 のルート公開鍵で1回暗号化するだけで、その下にいる C と D の両方が（n2 の秘密鍵を共有しているので）復号できます。だからパス全体でも暗号文の数は部分木の数、すなわち O(log N) に収まる。ペアワイズなら N-1 人へ個別に配るところを、木構造が「部分木のルートへ1通」へ畳み込むわけです。

epoch と Commit：状態遷移をグループ全員で揃える

MLS のグループ状態は epoch（世代番号）で管理されます。参加・離脱・鍵更新といった変更は、まず Proposal（提案）として表明され、それらを1つの Commit がまとめて適用し、epoch を1つ進めます。Commit を適用すると、グループ全員が同じ新しいルート鍵に到達し、そこから HKDF で各種の鍵（暗号化鍵、認証鍵、次 epoch への secret など）を導きます。

epoch n
  Proposal: Add(E),  Remove(B),  Update(A) …
  Commit ──▶ ルート鍵が再導出され epoch n+1 へ
              全員が同じ epoch_secret を共有

なぜ Commit でまとめるのか。鍵を変える操作（特に Update と Remove）はどれも TreeKEM のパス更新を伴い、それを個別に流すと epoch の整合が崩れます。Commit に束ねて順序付けて適用することで、全メンバーの ratchet tree が完全に同じ形・同じ鍵へ収束する。DS が Commit を全員へ同じ順で配送するのは、この収束を保証するためです。

前方秘匿性と PCS をグループ規模で両立する

前方秘匿性とダブルラチェットの記事で見た二つの性質を、MLS は epoch 単位で達成します。

• 前方秘匿性（PFS）：epoch が進むと前 epoch の鍵素材は HKDF で一方向に更新され、古いものは破棄される。後で端末を奪われても、過去 epoch のグループ鍵は遡って復元できない。
• post-compromise security（PCS, 将来回復性）：あるメンバーが自分の leaf を Update（新しい鍵ペアでパスを張り直し Commit）すると、攻撃者が知らない新しい乱数がルート鍵に注入される。これ以降のグループ鍵は攻撃者の手から外れ、安全が回復する。

つまり PCS のための「攻撃者を締め出す更新」が、ペアワイズなら O(N) かかるところ、TreeKEM では1人の Update＝O(log N) で済みます。これが MLS の決定的な利点です。離脱も同様で、Remove は対象の leaf を空（blank）にしてパスを張り直す Commit を流すだけ。残ったメンバーは新ルート鍵へ移り、抜けた人は新 epoch の鍵を導出できないため、以後のメッセージから締め出される（後方秘匿性）。

非同期参加：相手がオフラインでも追加できる

グループに人を追加するとき、相手がオンラインで鍵交換に応じられるとは限りません。MLS はこれを KeyPackage で非同期に解きます。各メンバーはあらかじめ、自分の身元鍵（証明書付き）と使い捨ての公開鍵をまとめた KeyPackage を DS に預けておく。誰かを追加したいメンバーは、その KeyPackage を取得し、Add Proposal と Commit を作り、新メンバーに必要な現グループ状態（Welcome メッセージ）を相手の公開鍵で暗号化して渡します。

新メンバー E の KeyPackage を取得
  ├─ Add(E) を Commit に含めて木に leaf を1つ足す
  └─ Welcome を E の KeyPackage 公開鍵で暗号化
      → E はオフラインでも、再接続後に Welcome を復号して合流

KeyPackage の使い捨て公開鍵が、Signal の X3DH における one-time prekey と同じ役割を果たし、追加処理に前方秘匿性を与えます。

まとめ

グループのエンドツーエンド暗号で最大の難所は、参加・離脱・鍵更新を全員ぶん線形にやると破綻することです。MLS はメンバーを二分木の葉に並べ、TreeKEM で更新を自分から根までのパス（O(log N)）に限定し、copath の兄弟ルート公開鍵へ1通ずつ暗号化することで配布量も対数に抑えます。変更は Commit にまとめて epoch を進め、全員を同一状態へ収束させながら、前方秘匿性（過去の保護）と post-compromise security（1人の Update で将来を回復）をグループ規模で両立させます。非同期参加は KeyPackage と Welcome で解決します。

土台となる2者間の前方秘匿性・PCS の考え方は 前方秘匿性とダブルラチェット、鍵更新に注入する乱数の源は Diffie-Hellman、パス上の鍵を一方向に導く仕組みは HKDF と併せて押さえると、なぜ TreeKEM が「大規模でも漏れに強い」のかが原理から腑に落ちます。