Research / 2025 –

Group key schedules as reachability

Draft · the definitions and theorems on this page are machine-checked in Lean; independent review is in progress.

A symbolic theory of group key schedules over an ordered, authenticated log: secrecy as non-reachability in a derivation graph, healing as confinement of wrap keys, the collapse of top-down derived trees, a lower bound on the number of published rules (wraps or KDF edges) under a separation hypothesis, and the epochs a long-term recovery key exposes, with two schedules worked out and every statement checked in Lean.

Key schedulesSymbolic securityLower bounds
N − 1
published rules (wraps or KDF edges) needed to rekey N members when no rule is usable by two recipients; the flat rebuild meets it with wraps only
d
wraps for a bottom-up path commit in a tree of depth d, which heals iff the leaf secret and every copath key are confined
1
wrap suffices once one key is shared, so the separation hypothesis of the bound cannot be dropped

A group that shares a secret has to replace it from time to time: when a member leaves, when a member’s device is compromised, and routinely so that old traffic stays private. A key schedule says how. Each replacement, a commit, samples fresh secrets, derives further secrets from them, and publishes ciphertexts from which the intended members recover the new group secret. This article treats schedules whose ciphertexts are posted to an ordered, authenticated log, and studies them as a reachability problem. Which secrets lie in the closure of an adversary’s knowledge under the derivation edges that the log makes public?

The model is symbolic: perfect cryptography, no probabilities, a passive adversary. Inside it the results are exact. The security predicates are definitions, and unfolding them proves nothing. The content is in four theorems and in how they compose: healing is equivalent to confinement of the wrap keys, top-down derivation from a shared root confines nothing from a holder of that root, a cover argument bounds the number of published rules from below, and a long-term recovery key exposes every epoch it can recover. Two schedules are then worked out from these. All statements are checked in Lean 4 with the core library only, and the code blocks below concatenate, in reading order, into one file that compiles with no sorry and no added axioms.

The host log

The log is the only shared medium. I assume the following about it and use nothing else.

Host assumptions.

  1. Total order per view. Each client sees the log as a finite sequence of entries. Entries are only appended, never reordered or removed. The position of a commit in the sequence is its epoch.
  2. Authenticated entries and membership. Every entry is signed by its author, and the member set at each position is a function of the prefix up to that position. Two clients holding the same prefix therefore compute the same membership and the same public state.
  3. Agreement between views is an extra assumption. Signed log heads with inclusion and consistency proofs give only fork consistency: a host can show two clients different logs, each internally consistent. Clients can be assured they share one view only if equivocation would be detected, for example by gossiping heads between clients or by having independent witnesses co-sign them. Every result below is about a single view.
  4. Passive, static adversary. The adversary reads the whole log but adds no entries. Its knowledge is one fixed set CC of secrets, which merges what was corrupted with when it was corrupted; time enters only through epoch indices in hypotheses.

Under these assumptions a commit is key transport by one author at one position of a sequence everyone agrees on. Concurrent commits need no merging, because the order decides, and public group state needs no separate agreement, because it is recomputed from the prefix. What is left is the question this article answers: which secrets the published edges make reachable, and how many edges a commit must publish. One thing the log does not give is agreement on the secret itself. A signature binds ciphertexts, not their plaintexts; the last section returns to this.

The symbolic model

Secrets are opaque atoms of a type α\alpha. Every public derivation step is a definite rule with a list of premises and one conclusion.

Rules and closure. A rule ρ=(π1,…,πk⇒c)\rho = (\pi_1,\ldots,\pi_k \Rightarrow c) lets whoever knows all premises πi\pi_i learn cc. Two kinds occur:

  • a KDF edge [ p ]⇒c[\,p\,] \Rightarrow c: the child secret cc is a one-way function of the parent pp;
  • a wrap [ k ]⇒x[\,k\,] \Rightarrow x: a public ciphertext of the payload xx under the key kk.

For a set of rules RR and a set of atoms SS, the closure ClR(S)\mathrm{Cl}_R(S) is the least set that contains SS and contains cc whenever it contains all premises of a rule (π⇒c)∈R(\pi \Rightarrow c) \in R. We say xx is derivable from SS under RR when x∈ClR(S)x \in \mathrm{Cl}_R(S).

The closure is an inductive predicate. Its two constructors are the two clauses of the definition.

namespace KeySched

/-- A definite rule: from all premises, conclude the conclusion. -/
structure Rule (α : Type) where
  prem  : List α
  concl : α
  deriving DecidableEq

/-- A (possibly infinite) set of rules, given by its membership predicate. -/
abbrev RuleSet (α : Type) := Rule α → Prop

/-- KDF edge: knowing the parent secret yields the child secret. -/
def kdf {α : Type} (parent child : α) : Rule α := ⟨[parent], child⟩

/-- Wrap: a public ciphertext of `payload` under `key`. -/
def wrap {α : Type} (key payload : α) : Rule α := ⟨[key], payload⟩

/-- The rules in a finite list. -/
def ofList {α : Type} (L : List (Rule α)) : RuleSet α := fun r => r ∈ L

/-- Union of two rule sets. -/
def RuleSet.union {α : Type} (R R' : RuleSet α) : RuleSet α := fun r => R r ∨ R' r

/-- Closure: the least set containing `S` and closed under the rules `R`. -/
inductive Derivable {α : Type} (R : RuleSet α) (S : α → Prop) : α → Prop where
  | base {a : α} : S a → Derivable R S a
  | rule (r : Rule α) : R r → (∀ p, p ∈ r.prem → Derivable R S p) → Derivable R S r.concl

Closure laws. For all rule sets and atom sets:

  1. (least) ClR(S)⊆X\mathrm{Cl}_R(S) \subseteq X for every X⊇SX \supseteq S closed under RR;
  2. (monotone) S⊆S′S \subseteq S' and R⊆R′R \subseteq R' imply ClR(S)⊆ClR′(S′)\mathrm{Cl}_R(S) \subseteq \mathrm{Cl}_{R'}(S');
  3. (cut) S′⊆ClR(S)S' \subseteq \mathrm{Cl}_R(S) implies ClR(S′)⊆ClR(S)\mathrm{Cl}_R(S') \subseteq \mathrm{Cl}_R(S), and so ClR(ClR(S))=ClR(S)\mathrm{Cl}_R(\mathrm{Cl}_R(S)) = \mathrm{Cl}_R(S);
  4. (composition) if a∈ClR1(S)a \in \mathrm{Cl}_{R_1}(S) and b∈ClR2(S∪{a})b \in \mathrm{Cl}_{R_2}(S \cup \{a\}) then b∈ClR1∪R2(S)b \in \mathrm{Cl}_{R_1 \cup R_2}(S);
  5. (last step) if x∈ClR(S)x \in \mathrm{Cl}_R(S) and x∉Sx \notin S, some rule of RR concludes xx and has all its premises in ClR(S)\mathrm{Cl}_R(S). In particular, if no rule of RR concludes xx and x∉Sx \notin S, then x∉ClR(S)x \notin \mathrm{Cl}_R(S).

Proof. (1) to (3) by induction on the derivation; (4) is (2) followed by (3); (5) is case analysis on the last constructor. ∎

section Basic
variable {α : Type}

theorem derivable_least {R : RuleSet α} {S X : α → Prop}
    (hS : ∀ a, S a → X a)
    (hR : ∀ r, R r → (∀ p, p ∈ r.prem → X p) → X r.concl) :
    ∀ {a}, Derivable R S a → X a := by
  intro a d
  induction d with
  | base h => exact hS _ h
  | rule r hr _ ih => exact hR r hr ih

theorem mono_S {R : RuleSet α} {S T : α → Prop} (h : ∀ a, S a → T a) :
    ∀ {a}, Derivable R S a → Derivable R T a := by
  intro a d
  induction d with
  | base hs => exact .base (h _ hs)
  | rule r hr _ ih => exact .rule r hr ih

theorem mono_R {R R' : RuleSet α} {S : α → Prop} (h : ∀ r, R r → R' r) :
    ∀ {a}, Derivable R S a → Derivable R' S a := by
  intro a d
  induction d with
  | base hs => exact .base hs
  | rule r hr _ ih => exact .rule r (h r hr) ih

theorem cut {R : RuleSet α} {S T : α → Prop} (h : ∀ a, T a → Derivable R S a) :
    ∀ {a}, Derivable R T a → Derivable R S a := by
  intro a d
  induction d with
  | base ht => exact h _ ht
  | rule r hr _ ih => exact .rule r hr ih

theorem idem {R : RuleSet α} {S : α → Prop} {a : α} :
    Derivable R (Derivable R S) a ↔ Derivable R S a :=
  ⟨cut (fun _ h => h), .base⟩

theorem compose {R₁ R₂ : RuleSet α} {S : α → Prop} {a b : α}
    (ha : Derivable R₁ S a) (hb : Derivable R₂ (fun x => S x ∨ x = a) b) :
    Derivable (R₁.union R₂) S b := by
  have hb' := mono_R (R' := R₁.union R₂) (fun r h => Or.inr h) hb
  refine cut ?_ hb'
  intro x hx
  cases hx with
  | inl hs => exact .base hs
  | inr he => subst he; exact mono_R (fun r h => Or.inl h) ha

/-- Knowing a wrap key yields its payload. -/
theorem heal_of_key {R : RuleSet α} {S : α → Prop} {k r' : α}
    (hw : R (wrap k r')) (dk : Derivable R S k) : Derivable R S r' :=
  Derivable.rule (wrap k r') hw (fun p hp => by
    simp [wrap] at hp
    subst hp
    exact dk)

theorem last_step {R : RuleSet α} {S : α → Prop} {x : α}
    (d : Derivable R S x) (hx : ¬ S x) :
    ∃ ru, R ru ∧ ru.concl = x ∧ ∀ p, p ∈ ru.prem → Derivable R S p := by
  cases d with
  | base h => exact absurd h hx
  | rule ru hr hp => exact ⟨ru, hr, rfl, hp⟩

theorem not_derivable_of_fresh {T : RuleSet α} {K : α → Prop} {r' : α}
    (hT : ∀ ru, T ru → ru.concl ≠ r') (hK : ¬ K r') : ¬ Derivable T K r' := by
  intro d
  obtain ⟨ru, hr, hc, _⟩ := last_step d hK
  exact hT ru hr hc

end Basic

A log is a sequence of entries, and each entry publishes a finite list of rules. The transcript of a log is the union of the rules of its entries. Appending a commit WW to a log LL gives the transcript of LL together with the rules of WW, and every transcript of a prefix is contained in the transcript of the whole log.

/-- A log: a sequence of entries, each publishing a finite list of rules. -/
abbrev Log (α : Type) := List (List (Rule α))

/-- The transcript of a log: every rule published by some entry. -/
def Log.rules {α : Type} (L : Log α) : RuleSet α := fun r => ∃ c, c ∈ L ∧ r ∈ c

theorem Log.rules_snoc {α : Type} (L : Log α) (W : List (Rule α)) (r : Rule α) :
    (L ++ [W]).rules r ↔ (L.rules.union (ofList W)) r := by
  simp only [Log.rules, RuleSet.union, ofList, List.mem_append, List.mem_singleton]
  constructor
  · intro ⟨c, hc, hr⟩
    rcases hc with hc | hc
    · exact Or.inl ⟨c, hc, hr⟩
    · subst hc; exact Or.inr hr
  · intro h
    rcases h with ⟨c, hc, hr⟩ | h
    · exact ⟨c, Or.inl hc, hr⟩
    · exact ⟨W, Or.inr rfl, h⟩

theorem Log.rules_prefix {α : Type} (L L' : Log α) (r : Rule α) (h : L.rules r) :
    (L ++ L').rules r := by
  obtain ⟨c, hc, hr⟩ := h
  exact ⟨c, List.mem_append_left _ hc, hr⟩

Security as non-reachability

Secrecy predicates. Fix a transcript TT and epoch roots root:N→α\mathit{root} : \mathbb{N} \to \alpha.

  • tt is secret from knowledge KK when t∉ClT(K)t \notin \mathrm{Cl}_T(K).
  • Forward secrecy for member states ste\mathit{st}_e: for all j<ej \lt e, rootj\mathit{root}_j is secret from ste\mathit{st}_e.
  • Post-compromise security from hh against CC: for all m≥hm \ge h, rootm\mathit{root}_m is secret from CC.
  • Removal security of a member removed at rem\mathit{rem} with knowledge KremK_{\mathit{rem}}: every roote\mathit{root}_e with e≥reme \ge \mathit{rem} is secret from KremK_{\mathit{rem}}.
  • Add security of a member joining at join\mathit{join} with knowledge KjoinK_{\mathit{join}}: every roote\mathit{root}_e with e<joine \lt \mathit{join} is secret from KjoinK_{\mathit{join}}.

These are definitions. The Lean lemmas secret_iff, FS_iff and so on only unfold them; they do not show that the symbolic predicates match computational notions such as real-or-random indistinguishability under adaptive corruption. What they do give for free is the direction of monotonicity. Secrecy is antitone in both the transcript and the knowledge, so a secret broken at some prefix of the log stays broken at every extension, and leaking more never restores secrecy.

section Security
variable {α : Type}

def Secret (T : RuleSet α) (K : α → Prop) (t : α) : Prop :=
  ∀ x, Derivable T K x → x ≠ t

def FS (T : RuleSet α) (state : Nat → α → Prop) (root : Nat → α) : Prop :=
  ∀ e j, j < e → Secret T (state e) (root j)

def PCS (T : RuleSet α) (C : α → Prop) (root : Nat → α) (h : Nat) : Prop :=
  ∀ m, h ≤ m → Secret T C (root m)

def RemovalSec (T : RuleSet α) (Krem : α → Prop) (root : Nat → α) (rem : Nat) : Prop :=
  ∀ e, rem ≤ e → Secret T Krem (root e)

def AddSec (T : RuleSet α) (Kjoin : α → Prop) (root : Nat → α) (join : Nat) : Prop :=
  ∀ e, e < join → Secret T Kjoin (root e)

theorem secret_iff {T : RuleSet α} {K : α → Prop} {t : α} :
    Secret T K t ↔ ¬ Derivable T K t := by
  constructor
  · intro h d; exact h t d rfl
  · intro h x d e; subst e; exact h d

theorem FS_iff {T : RuleSet α} {state : Nat → α → Prop} {root : Nat → α} :
    FS T state root ↔ ∀ e j, j < e → ¬ Derivable T (state e) (root j) := by
  simp only [FS, secret_iff]

theorem PCS_iff {T : RuleSet α} {C : α → Prop} {root : Nat → α} {h : Nat} :
    PCS T C root h ↔ ∀ m, h ≤ m → ¬ Derivable T C (root m) := by
  simp only [PCS, secret_iff]

theorem RemovalSec_iff {T : RuleSet α} {K : α → Prop} {root : Nat → α} {rem : Nat} :
    RemovalSec T K root rem ↔ ∀ e, rem ≤ e → ¬ Derivable T K (root e) := by
  simp only [RemovalSec, secret_iff]

theorem AddSec_iff {T : RuleSet α} {K : α → Prop} {root : Nat → α} {join : Nat} :
    AddSec T K root join ↔ ∀ e, e < join → ¬ Derivable T K (root e) := by
  simp only [AddSec, secret_iff]

theorem secret_antitone {T T' : RuleSet α} {K K' : α → Prop} {t : α}
    (hT : ∀ r, T r → T' r) (hK : ∀ a, K a → K' a) :
    Secret T' K' t → Secret T K t := by
  intro h x d
  exact h x (mono_R hT (mono_S hK d))

theorem attack_persists {T T' : RuleSet α} {K K' : α → Prop} {t : α}
    (hT : ∀ r, T r → T' r) (hK : ∀ a, K a → K' a)
    (d : Derivable T K t) : ¬ Secret T' K' t := by
  rw [secret_iff]; intro h; exact h (mono_R hT (mono_S hK d))

/-- Secrecy against a log implies secrecy against each of its prefixes. -/
theorem secret_of_extension {L L' : Log α} {K : α → Prop} {t : α} :
    Secret (L ++ L').rules K t → Secret L.rules K t :=
  secret_antitone (Log.rules_prefix L L') (fun _ h => h)

end Security

Healing is confinement

A commit introduces a fresh secret r′r' and wraps it under some keys. The commit heals a compromise CC if r′r' is secret from CC afterwards. A key kk is confined from CC if k∉ClR(C)k \notin \mathrm{Cl}_R(C), where RR is the rule set in force after the commit, for instance the transcript TT together with the commit.

Healing iff confinement. Let k1,…,knk_1, \ldots, k_n be keys with every wrap [ki]⇒r′[k_i] \Rightarrow r' in RR. Assume freshness: every rule of RR that concludes r′r' has the form [ki]⇒r′[k_i] \Rightarrow r' for some ii. Assume r′∉Cr' \notin C. Then

r′∈ClR(C)  ⟺  ∃i,  ki∈ClR(C),r' \in \mathrm{Cl}_R(C) \iff \exists i,\; k_i \in \mathrm{Cl}_R(C),

so the commit heals CC if and only if every wrap key is confined from CC.

Proof. (⇐\Leftarrow) apply the wrap. (⇒\Rightarrow) by the last-step law some rule concludes r′r' with derivable premises; by freshness it is a wrap under some kik_i, and its only premise kik_i is derivable. ∎

The hypothesis r′∉Cr' \notin C says that the committer is honest and its randomness was not corrupted at commit time. It is necessary: an adversary that holds a member’s signing key can post commits whose fresh secret it chose, and the model, being passive, excludes this.

section Heal
variable {α : Type}

theorem heal_iff {R : RuleSet α} {C : α → Prop} {r' : α} {keys : List α}
    (hwrap  : ∀ k, k ∈ keys → R (wrap k r'))
    (hfresh : ∀ ru, R ru → ru.concl = r' → ∃ k, k ∈ keys ∧ ru.prem = [k])
    (hC : ¬ C r') :
    Derivable R C r' ↔ ∃ k, k ∈ keys ∧ Derivable R C k := by
  constructor
  · intro d
    obtain ⟨ru, hr, hc, hp⟩ := last_step d hC
    obtain ⟨k, hk, hpk⟩ := hfresh ru hr hc
    exact ⟨k, hk, hp k (by rw [hpk]; simp)⟩
  · intro ⟨k, hk, dk⟩
    exact heal_of_key (hwrap k hk) dk

theorem heal_secret_iff {R : RuleSet α} {C : α → Prop} {r' : α} {keys : List α}
    (hwrap  : ∀ k, k ∈ keys → R (wrap k r'))
    (hfresh : ∀ ru, R ru → ru.concl = r' → ∃ k, k ∈ keys ∧ ru.prem = [k])
    (hC : ¬ C r') :
    Secret R C r' ↔ ∀ k, k ∈ keys → Secret R C k := by
  rw [secret_iff, heal_iff hwrap hfresh hC]
  constructor
  · intro h k hk; rw [secret_iff]; intro dk; exact h ⟨k, hk, dk⟩
  · intro h ⟨k, hk, dk⟩; exact (secret_iff.mp (h k hk)) dk

A wrap built from a key exchange opens under either private key, the sender’s aa or the recipient’s bb. Symbolically it is the pair of rules [a]⇒x[a] \Rightarrow x and [b]⇒x[b] \Rightarrow x. Freshness must then list both sides.

Two-sided wraps. If both sides [ai]⇒r′[a_i] \Rightarrow r' and [bi]⇒r′[b_i] \Rightarrow r' of each listed pair (ai,bi)(a_i, b_i) are in RR, these are the only rules concluding r′r', and r′∉Cr' \notin C, then r′r' is derivable from CC iff some aia_i or some bib_i is. If moreover every sender key aia_i is erased (not derivable), then r′r' is derivable iff some recipient key bib_i is.

A public wrap gives no forward secrecy against its recipient key. If both sides of a two-sided wrap of xx are published and bb is derivable from SS, then xx is not secret from SS, whatever happened to aa.

Proof. The first part is healing-iff-confinement with key list a1,…,an,b1,…,bna_1, \ldots, a_n, b_1, \ldots, b_n. The second applies the bb side of the wrap. ∎

The second statement is the reason a fresh ephemeral sender key does not protect a ciphertext that stays on a permanent log: a later compromise of the recipient’s static key opens it.

/-- A key-exchange style wrap: it opens under either private key. -/
def dhWrap (a b payload : α) : List (Rule α) := [wrap a payload, wrap b payload]

theorem dh_heal_iff {R : RuleSet α} {C : α → Prop} {r' : α} {ws : List (α × α)}
    (hwrap  : ∀ w, w ∈ ws → R (wrap w.1 r') ∧ R (wrap w.2 r'))
    (hfresh : ∀ ru, R ru → ru.concl = r' →
       ∃ w, w ∈ ws ∧ (ru.prem = [w.1] ∨ ru.prem = [w.2]))
    (hC : ¬ C r') :
    Derivable R C r' ↔ ∃ w, w ∈ ws ∧ (Derivable R C w.1 ∨ Derivable R C w.2) := by
  rw [heal_iff (keys := ws.map Prod.fst ++ ws.map Prod.snd)]
  · constructor
    · intro ⟨k, hk, dk⟩
      rcases List.mem_append.mp hk with h | h
      · obtain ⟨w, hw, e⟩ := List.mem_map.mp h; subst e; exact ⟨w, hw, Or.inl dk⟩
      · obtain ⟨w, hw, e⟩ := List.mem_map.mp h; subst e; exact ⟨w, hw, Or.inr dk⟩
    · intro ⟨w, hw, h⟩
      rcases h with dk | dk
      · exact ⟨w.1, List.mem_append_left _ (List.mem_map_of_mem _ hw), dk⟩
      · exact ⟨w.2, List.mem_append_right _ (List.mem_map_of_mem _ hw), dk⟩
  · intro k hk
    rcases List.mem_append.mp hk with h | h
    · obtain ⟨w, hw, e⟩ := List.mem_map.mp h; subst e; exact (hwrap w hw).1
    · obtain ⟨w, hw, e⟩ := List.mem_map.mp h; subst e; exact (hwrap w hw).2
  · intro ru hr hc
    obtain ⟨w, hw, h⟩ := hfresh ru hr hc
    rcases h with e | e
    · exact ⟨w.1, List.mem_append_left _ (List.mem_map_of_mem _ hw), e⟩
    · exact ⟨w.2, List.mem_append_right _ (List.mem_map_of_mem _ hw), e⟩
  · exact hC

theorem dh_heal_erased {R : RuleSet α} {C : α → Prop} {r' : α} {ws : List (α × α)}
    (hwrap  : ∀ w, w ∈ ws → R (wrap w.1 r') ∧ R (wrap w.2 r'))
    (hfresh : ∀ ru, R ru → ru.concl = r' →
       ∃ w, w ∈ ws ∧ (ru.prem = [w.1] ∨ ru.prem = [w.2]))
    (hC : ¬ C r') (herase : ∀ w, w ∈ ws → ¬ Derivable R C w.1) :
    Derivable R C r' ↔ ∃ w, w ∈ ws ∧ Derivable R C w.2 := by
  rw [dh_heal_iff hwrap hfresh hC]
  constructor
  · intro ⟨w, hw, h⟩
    rcases h with h | h
    · exact absurd h (herase w hw)
    · exact ⟨w, hw, h⟩
  · intro ⟨w, hw, h⟩; exact ⟨w, hw, Or.inr h⟩

theorem public_wrap_no_fs {R : RuleSet α} {S : α → Prop} {a b x : α}
    (hw : ∀ ru, ru ∈ dhWrap a b x → R ru) (db : Derivable R S b) :
    ¬ Secret R S x := by
  rw [secret_iff]; intro h
  exact h (heal_of_key (hw _ (by simp [dhWrap])) db)

end Heal

Top-down derivation confines nothing

Healing needs confined wrap keys, and the next result says where such keys cannot come from. It is a general fact about derivation, stated first for any rule set and then for trees.

Below the root. If k∈ClR({ρ})k \in \mathrm{Cl}_R(\{\rho\}) and ρ∈ClR(C)\rho \in \mathrm{Cl}_R(C), then k∈ClR(C)k \in \mathrm{Cl}_R(C). No secret derived from ρ\rho is confined from anyone who derives ρ\rho.

Top-down trees. Index tree positions by bit strings, with [ ][\,] the root and b::pb :: p the child of pp on side bb. A tree of depth dd is derived top-down when RR contains every KDF edge [node(p)]⇒node(b::p)[\mathit{node}(p)] \Rightarrow \mathit{node}(b :: p) with ∣p∣<d|p| \lt d. Then every holder of the root derives every node secret: node(p)∈ClR(C)\mathit{node}(p) \in \mathrm{Cl}_R(C) for all ∣p∣≤d|p| \le d whenever node([ ])∈ClR(C)\mathit{node}([\,]) \in \mathrm{Cl}_R(C). Consequently a commit that wraps its fresh secret only under node keys of such a tree does not heal a compromise of the root.

Proof. The first part is the cut law. For trees, induction on pp shows node(p)∈Cl({node([ ])})\mathit{node}(p) \in \mathrm{Cl}(\{\mathit{node}([\,])\}); then apply the first part, and for the consequence apply the wrap. ∎

Read contrapositively, the theorem is a constraint on any schedule. A key that should be confined from a member must not be derivable from anything that member holds; in particular it cannot be handed down by KDF from a root that more members share. It has to come from somewhere else: sampled fresh and wrapped to the members who should hold it, as in key graphs, or derived bottom-up inside the subtree, as in the path schedule below. The theorem does not choose between these; it only rules out top-down derivation from shared material.

The same argument propagates along epochs. Suppose each epoch’s tree is derived top-down from its root, and each epoch’s commit wraps the next root under some node key of the current tree. Then a holder of rootj\mathit{root}_j derives every node of every epoch m≥jm \ge j, so post-compromise security fails from every later epoch.

section Collapse
variable {α : Type}

theorem below_root_not_confined {R : RuleSet α} {C : α → Prop} {ρ k : α}
    (hk : Derivable R (fun x => x = ρ) k) (hρ : Derivable R C ρ) :
    Derivable R C k :=
  cut (fun a ha => by subst ha; exact hρ) hk

/-- KDF edges of a tree of depth `d`, derived from the root downwards. -/
def topDown (node : List Bool → α) (d : Nat) : RuleSet α :=
  fun r => ∃ p b, p.length < d ∧ r = kdf (node p) (node (b :: p))

theorem collapse (node : List Bool → α) (d : Nat) :
    ∀ p : List Bool, p.length ≤ d →
      Derivable (topDown node d) (fun x => x = node []) (node p) := by
  intro p
  induction p with
  | nil => intro _; exact .base rfl
  | cons b p ih =>
    intro hl
    have hl' : p.length < d := by simp at hl; omega
    exact Derivable.rule (kdf (node p) (node (b :: p))) ⟨p, b, hl', rfl⟩
      (fun q hq => by
        simp [kdf] at hq
        subst hq
        exact ih (by omega))

theorem collapse_from {R : RuleSet α} {S : α → Prop} (node : List Bool → α) (d : Nat)
    (hTree : ∀ r, topDown node d r → R r)
    (hroot : Derivable R S (node [])) :
    ∀ p : List Bool, p.length ≤ d → Derivable R S (node p) :=
  fun p hp => below_root_not_confined (mono_R hTree (collapse node d p hp)) hroot

theorem topDown_wrap_no_heal {R : RuleSet α} {C : α → Prop} (node : List Bool → α)
    (d : Nat) (hTree : ∀ r, topDown node d r → R r)
    (hroot : Derivable R C (node []))
    {p : List Bool} (hp : p.length ≤ d) {r' : α} (hw : R (wrap (node p) r')) :
    ¬ Secret R C r' := by
  rw [secret_iff]; intro h
  exact h (heal_of_key hw (collapse_from node d hTree hroot p hp))

theorem collapse_forever {R : RuleSet α} (node : Nat → List Bool → α) (d : Nat)
    (hTree : ∀ j r, topDown (node j) d r → R r)
    (hWrap : ∀ j, ∃ p : List Bool, p.length ≤ d ∧ R (wrap (node j p) (node (j+1) [])))
    {S : α → Prop} {j : Nat} (hj : Derivable R S (node j [])) :
    ∀ k, Derivable R S (node (j + k) []) := by
  intro k
  induction k with
  | zero => exact hj
  | succ k ih =>
    obtain ⟨p, hp, hw⟩ := hWrap (j + k)
    exact heal_of_key hw (collapse_from (node (j + k)) d (hTree (j + k)) ih p hp)

theorem collapse_forever_nodes {R : RuleSet α} (node : Nat → List Bool → α) (d : Nat)
    (hTree : ∀ j r, topDown (node j) d r → R r)
    (hWrap : ∀ j, ∃ p : List Bool, p.length ≤ d ∧ R (wrap (node j p) (node (j+1) [])))
    {S : α → Prop} {j : Nat} (hj : Derivable R S (node j [])) :
    ∀ m, j ≤ m → ∀ p : List Bool, p.length ≤ d → Derivable R S (node m p) := by
  intro m hm p hp
  have e : m = j + (m - j) := by omega
  have hr := collapse_forever node d hTree hWrap hj (m - j)
  rw [← e] at hr
  exact collapse_from (node m) d (hTree m) hr p hp

theorem topDown_chain_no_pcs {R : RuleSet α} (node : Nat → List Bool → α) (d : Nat)
    (hTree : ∀ j r, topDown (node j) d r → R r)
    (hWrap : ∀ j, ∃ p : List Bool, p.length ≤ d ∧ R (wrap (node j p) (node (j+1) [])))
    {C : α → Prop} {j : Nat} (hj : C (node j [])) :
    ∀ h, j ≤ h → ¬ PCS R C (fun e => node e []) h := by
  intro h hh
  rw [PCS_iff]; intro H
  exact H h (Nat.le_refl h)
    (collapse_forever_nodes node d hTree hWrap (S := C) (.base hj) h hh [] (by simp))

end Collapse

How many rules a commit publishes

Count the rules a commit publishes. With confined keys shared by subgroups, a commit can reach many members with few rules, so a lower bound needs a hypothesis that rules out sharing. The right one is about what a recipient can open before the commit.

Cover class. A commit WW (a list of rules) added to a transcript TT delivers r′r' to a duplicate-free list of recipients m1,…,mnm_1, \ldots, m_n with initial knowledge KmK_{m}. It is in the cover class when

  1. no recipient derives r′r' from TT alone;
  2. (separation) no rule of WW has all its premises in ClT(Km)\mathrm{Cl}_T(K_m) and in ClT(Km′)\mathrm{Cl}_T(K_{m'}) for two distinct recipients m≠m′m \ne m';
  3. every recipient derives r′r' under T∪WT \cup W.

Rules of WW may conclude intermediate secrets that other rules of WW use: multi-level commits are allowed. Symbolically a KDF edge and a wrap are rules of the same shape, a single premise and a conclusion, so ∣W∣|W| counts every published rule; it bounds the number of wraps when WW contains only wraps.

Bounded sharing. Replace (2) by (kk-separation): for every rule of WW, at most kk distinct recipients derive all its premises under TT. Under (1), (3) and kk-separation, n≤k⋅∣W∣n \le k \cdot |W|, so, for k≥1k \ge 1, ∣W∣≥⌈n/k⌉|W| \ge \lceil n / k \rceil.

Cover lower bound. A commit in the cover class has ∣W∣≥n|W| \ge n. For a group of NN members, where the committer rekeys the n=N−1n = N - 1 others, this is ∣W∣≥N−1|W| \ge N - 1.

Proof. First a decomposition: anything derivable under T∪WT \cup W is derivable under TT alone, or some rule of WW has all its premises derivable under TT alone (the first rule of WW used in the derivation). By (1) and (3) every recipient mm thus has a rule wm∈Ww_m \in W whose premises it derives under TT. By kk-separation the map m↦wmm \mapsto w_m is at most kk-to-one. A pigeonhole count, by induction on WW that splits off the recipients served by the head rule, gives n≤k⋅∣W∣n \le k \cdot |W|. Separation is kk-separation with k=1k = 1, since a duplicate-free list whose elements are pairwise equal has length at most one; this gives the cover bound. ∎

The decomposition, and the split of recipients by whether they open the head rule, use case analysis on undecidable propositions, so these proofs depend on classical logic. For NN members the bounded form gives ∣W∣≥⌈(N−1)/k⌉|W| \ge \lceil (N-1)/k \rceil: a schedule in which every published rule can be opened by at most kk of the recipients pays at least that many rules. A common way to meet separation is through owned material. If every rule of WW has a premise that is either an identity key, derivable under TT only by its owner, or a secret that no recipient derives under TT (such as a fresh intermediate key of the commit), then separation holds and the bound applies. A two-level commit, which wraps a fresh gg to each identity key and then wraps r′r' under gg, is of this form.

section Cost

theorem len_split {β : Type} (f : β → Bool) : ∀ l : List β,
    l.length = (l.filter f).length + (l.filter (fun x => !f x)).length := by
  intro l
  induction l with
  | nil => rfl
  | cons x l ih => cases h : f x <;> simp [List.filter_cons, h] <;> omega

theorem nodup_le_one {β : Type} : ∀ (l : List β), l.Nodup →
    (∀ a b, a ∈ l → b ∈ l → a = b) → l.length ≤ 1
  | [], _, _ => by simp
  | [_], _, _ => by simp
  | a :: b :: _, hnd, h => by
    have e : a = b := h a b (by simp) (by simp)
    subst e
    simp at hnd

theorem pigeonK {β γ : Type} (P : β → γ → Prop) (k : Nat)
    (hk : ∀ y (l : List β), l.Nodup → (∀ x, x ∈ l → P x y) → l.length ≤ k) :
    ∀ (l₂ : List γ) (l₁ : List β), l₁.Nodup →
      (∀ x, x ∈ l₁ → ∃ y, y ∈ l₂ ∧ P x y) → l₁.length ≤ k * l₂.length := by
  intro l₂
  induction l₂ with
  | nil =>
    intro l₁ _ hcov
    cases l₁ with
    | nil => simp
    | cons x _ =>
      obtain ⟨y, hy, _⟩ := hcov x (List.mem_cons_self x _)
      simp at hy
  | cons y l₂ ih =>
    intro l₁ hnd hcov
    let g : β → Bool := fun x => @decide (P x y) (Classical.propDecidable _)
    have h1 : (l₁.filter g).length ≤ k :=
      hk y _ (hnd.sublist (List.filter_sublist l₁)) (by
        intro x hx
        have := (List.mem_filter.mp hx).2
        exact @of_decide_eq_true _ (Classical.propDecidable _) this)
    have h2 : (l₁.filter (fun x => !g x)).length ≤ k * l₂.length :=
      ih _ (hnd.sublist (List.filter_sublist l₁)) (by
        intro x hx
        obtain ⟨hx1, hx2⟩ := List.mem_filter.mp hx
        have hn : ¬ P x y := by
          intro hp
          have : g x = true := @decide_eq_true _ (Classical.propDecidable _) hp
          simp [this] at hx2
        obtain ⟨y', hy', hp⟩ := hcov x hx1
        rcases List.mem_cons.mp hy' with e | h
        · subst e; exact absurd hp hn
        · exact ⟨y', h, hp⟩)
    rw [len_split g l₁, List.length_cons, Nat.mul_succ]
    omega

variable {α : Type}

theorem first_rule {R W : RuleSet α} {S : α → Prop} :
    ∀ {x}, Derivable (R.union W) S x →
      Derivable R S x ∨ ∃ w, W w ∧ ∀ p, p ∈ w.prem → Derivable R S p := by
  intro x d
  induction d with
  | base h => exact Or.inl (.base h)
  | rule r hr _ ih =>
    by_cases hall : ∀ p, p ∈ r.prem → Derivable R S p
    · cases hr with
      | inl hR => exact Or.inl (.rule r hR hall)
      | inr hW => exact Or.inr ⟨r, hW, hall⟩
    · obtain ⟨p, hp⟩ := Classical.not_forall.mp hall
      have hp1 : p ∈ r.prem :=
        Classical.byContradiction (fun h => hp (fun h' => absurd h' h))
      have hp2 : ¬ Derivable R S p := fun h => hp (fun _ => h)
      cases ih p hp1 with
      | inl h => exact absurd h hp2
      | inr h => exact Or.inr h

theorem cover_k_lower_bound {M : Type}
    (T : RuleSet α) (W : List (Rule α)) (r' : α) (K : M → α → Prop) (rcpt : List M) (k : Nat)
    (hnd : rcpt.Nodup)
    (hnotT : ∀ m, m ∈ rcpt → ¬ Derivable T (K m) r')
    (hksep : ∀ w, w ∈ W → ∀ l : List M, l.Nodup →
       (∀ m, m ∈ l → m ∈ rcpt ∧ ∀ p, p ∈ w.prem → Derivable T (K m) p) → l.length ≤ k)
    (hdeliver : ∀ m, m ∈ rcpt → Derivable (T.union (ofList W)) (K m) r') :
    rcpt.length ≤ k * W.length := by
  refine pigeonK (fun m (w : Rule α) =>
      w ∈ W ∧ m ∈ rcpt ∧ ∀ p, p ∈ w.prem → Derivable T (K m) p) k ?_ W rcpt hnd ?_
  · intro w l hl hP
    cases l with
    | nil => exact Nat.zero_le _
    | cons m l' =>
      exact hksep w (hP m (List.mem_cons_self m l')).1 _ hl (fun m' hm' => (hP m' hm').2)
  · intro m hm
    cases first_rule (hdeliver m hm) with
    | inl h => exact absurd h (hnotT m hm)
    | inr h => obtain ⟨w, hw, hp⟩ := h; exact ⟨w, hw, hw, hm, hp⟩

theorem cover_lower_bound {M : Type}
    (T : RuleSet α) (W : List (Rule α)) (r' : α) (K : M → α → Prop) (rcpt : List M)
    (hnd : rcpt.Nodup)
    (hnotT : ∀ m, m ∈ rcpt → ¬ Derivable T (K m) r')
    (hsep : ∀ w, w ∈ W → ∀ m m', m ∈ rcpt → m' ∈ rcpt →
       (∀ p, p ∈ w.prem → Derivable T (K m) p) →
       (∀ p, p ∈ w.prem → Derivable T (K m') p) → m = m')
    (hdeliver : ∀ m, m ∈ rcpt → Derivable (T.union (ofList W)) (K m) r') :
    rcpt.length ≤ W.length := by
  have h := cover_k_lower_bound T W r' K rcpt 1 hnd hnotT (by
    intro w hw l hl hP
    exact nodup_le_one l hl (fun a b ha hb =>
      hsep w hw a b (hP a ha).1 (hP b hb).1 (hP a ha).2 (hP b hb).2)) hdeliver
  rw [Nat.one_mul] at h
  exact h

theorem owned_lower_bound {M : Type}
    (T : RuleSet α) (W : List (Rule α)) (r' : α) (K : M → α → Prop) (rcpt : List M)
    (hnd : rcpt.Nodup)
    (hnotT : ∀ m, m ∈ rcpt → ¬ Derivable T (K m) r')
    (own : α → M → Prop)
    (hown : ∀ m, m ∈ rcpt → ∀ x o, own x o → Derivable T (K m) x → o = m)
    (hrule : ∀ w, w ∈ W → ∃ p, p ∈ w.prem ∧
       ((∃ o, own p o) ∨ ∀ m, m ∈ rcpt → ¬ Derivable T (K m) p))
    (hdeliver : ∀ m, m ∈ rcpt → Derivable (T.union (ofList W)) (K m) r') :
    rcpt.length ≤ W.length := by
  refine cover_lower_bound T W r' K rcpt hnd hnotT ?_ hdeliver
  intro w hw m m' hm hm' h1 h2
  obtain ⟨p, hp, h⟩ := hrule w hw
  rcases h with ⟨o, ho⟩ | hn
  · have e1 := hown m hm p o ho (h1 p hp)
    have e2 := hown m' hm' p o ho (h2 p hp)
    rw [← e1, ← e2]
  · exact absurd (h1 p hp) (hn m hm)

theorem idk_lower_bound {M : Type} (idk : M → α)
    (T : RuleSet α) (W : List (Rule α)) (r' : α) (K : M → α → Prop) (rcpt : List M)
    (hnd : rcpt.Nodup)
    (hnotT : ∀ m, m ∈ rcpt → ¬ Derivable T (K m) r')
    (hpriv : ∀ m, m ∈ rcpt → ∀ o, Derivable T (K m) (idk o) → o = m)
    (hrule : ∀ w, w ∈ W → ∃ p, p ∈ w.prem ∧
       ((∃ o, p = idk o) ∨ ∀ m, m ∈ rcpt → ¬ Derivable T (K m) p))
    (hdeliver : ∀ m, m ∈ rcpt → Derivable (T.union (ofList W)) (K m) r') :
    rcpt.length ≤ W.length :=
  owned_lower_bound T W r' K rcpt hnd hnotT (fun x o => x = idk o)
    (by intro m hm x o e d; subst e; exact hpriv m hm o d) hrule hdeliver

/-- Two levels: a fresh `g` to each identity key, then `r'` under `g`. -/
def twoLevel {M : Type} (idk : M → α) (g r' : α) (rcpt : List M) : List (Rule α) :=
  rcpt.map (fun m => wrap (idk m) g) ++ [wrap g r']

theorem twoLevel_covered {M : Type} (idk : M → α) (g r' : α) (rcpt : List M)
    (T : RuleSet α) (K : M → α → Prop)
    (hg : ∀ m, m ∈ rcpt → ¬ Derivable T (K m) g) :
    ∀ w, w ∈ twoLevel idk g r' rcpt → ∃ p, p ∈ w.prem ∧
       ((∃ o, p = idk o) ∨ ∀ m, m ∈ rcpt → ¬ Derivable T (K m) p) := by
  intro w hw
  rcases List.mem_append.mp hw with h | h
  · obtain ⟨m, _, e⟩ := List.mem_map.mp h
    subst e; exact ⟨idk m, by simp [wrap], Or.inl ⟨m, rfl⟩⟩
  · simp at h; subst h; exact ⟨g, by simp [wrap], Or.inr hg⟩

end Cost

Separation cannot be dropped. In the smallest example three recipients each hold a private key of their own and one shared key, the transcript is empty, and a single wrap delivers r′r' to all three, although none of them could derive r′r' before. Only separation fails, and the bound fails with it. This is why key graphs, which keep shared subgroup keys confined, remove a member with logarithmically many wraps. Here a rule is one published derivation step (a pairwise wrap or a KDF edge), not a ciphertext bit: broadcast encryption can also serve many recipients with one ciphertext, and the bound says nothing about it.

theorem separation_needed :
    (∀ m : Fin 3, ¬ Derivable (fun _ => False : RuleSet Nat)
        (fun x => x = 0 ∨ x = 200 + m.val) 100) ∧
    (∀ m : Fin 3, Derivable (RuleSet.union (fun _ => False) (ofList [wrap 0 100]))
        (fun x => x = 0 ∨ x = 200 + m.val) 100) ∧
    [wrap (0 : Nat) 100].length < ([0, 1, 2] : List (Fin 3)).length := by
  refine ⟨fun m => not_derivable_of_fresh (fun _ h => h.elim) (by omega),
          fun _ => heal_of_key (Or.inr (List.mem_singleton.mpr rfl)) (.base (Or.inl rfl)),
          by decide⟩

What a long-term recovery key exposes

Suppose a member can recover epoch secrets from a long-term key rkrk together with the log, for instance by replaying the log from its start. The log is permanent, so recovery is available to whoever holds rkrk at any later time.

Recovery exposure. Let EE be a set of epochs such that roote∈ClT({rk})\mathit{root}_e \in \mathrm{Cl}_T(\{rk\}) for every e∈Ee \in E: the epochs rkrk can recover. Let rk∈Crk \in C. Then

  1. roote∈ClT(C)\mathit{root}_e \in \mathrm{Cl}_T(C) for every e∈Ee \in E;
  2. post-compromise security against CC fails from every hh that is at most some e∈Ee \in E;
  3. if the member state at some epoch ee still holds rkrk, forward secrecy fails as soon as EE contains an epoch j<ej \lt e.

Proof. (1) is monotonicity in the start set; (2) and (3) instantiate (1). ∎

The statement is restricted to the epochs rkrk can actually recover. A member’s recovery set is normally its tenure, from joining to removal, and possibly only the epochs whose commits carry a wrap to it. Outside EE the theorem asserts nothing, and post-compromise security from an hh beyond every element of EE is not refuted by it.

section Recovery
variable {α : Type}

theorem recovery_derives {T : RuleSet α} {root : Nat → α} {rk : α} {E : Nat → Prop}
    (hrec : ∀ e, E e → Derivable T (fun x => x = rk) (root e))
    {C : α → Prop} (hC : C rk) : ∀ e, E e → Derivable T C (root e) :=
  fun e he => mono_S (fun x hx => by subst hx; exact hC) (hrec e he)

theorem recovery_no_pcs {T : RuleSet α} {root : Nat → α} {rk : α} {E : Nat → Prop}
    (hrec : ∀ e, E e → Derivable T (fun x => x = rk) (root e))
    {C : α → Prop} (hC : C rk) :
    ∀ h, (∃ e, h ≤ e ∧ E e) → ¬ PCS T C root h := by
  intro h ⟨e, hle, he⟩
  rw [PCS_iff]; intro H
  exact H e hle (recovery_derives hrec hC e he)

theorem recovery_no_fs {T : RuleSet α} {root : Nat → α} {rk : α} {E : Nat → Prop}
    (hrec : ∀ e, E e → Derivable T (fun x => x = rk) (root e))
    {st : Nat → α → Prop} {j e : Nat} (hj : E j) (hje : j < e) (hst : st e rk) :
    ¬ FS T st root := by
  rw [FS_iff]; intro H
  exact H e j hje (recovery_derives hrec hst j hj)

end Recovery

Two schedules

Both schedules below are expressed as one commit appended to a transcript TT, so the presence of every KDF edge and wrap and the freshness hypotheses are lemmas about the commit, not assumptions.

Bottom-up path secrets

A member at depth dd samples a fresh leaf secret s0s_0 and derives si+1s_{i+1} from sis_i by a KDF, from the leaf up to the root sds_d. Each si+1s_{i+1} is also wrapped under the key cpi+1cp_{i+1} of the copath node at that level, the sibling subtree whose members need it. The commit publishes dd KDF edges and dd wraps.

Path commit. Assume ss is injective, no rule of TT concludes any si+1s_{i+1} (i<di \lt d), and CC contains no si+1s_{i+1}. Write WW for the commit and Cl\mathrm{Cl} for ClT∪W\mathrm{Cl}_{T \cup W}. Then for every i≤di \le d,

si∈Cl(C)  ⟺  s0∈Cl(C)  ∨  ∃j, 1≤j≤i, cpj∈Cl(C).s_i \in \mathrm{Cl}(C) \iff s_0 \in \mathrm{Cl}(C) \;\lor\; \exists j,\ 1 \le j \le i,\ cp_j \in \mathrm{Cl}(C).

Hence the new root sds_d is secret from CC if and only if the leaf secret and every copath key cp1,…,cpdcp_1, \ldots, cp_d are confined from CC. The commit has 2d2d rules, of which dd are wraps.

Proof. Induction on ii. At level i+1i+1 the only rules concluding si+1s_{i+1} are the KDF edge from sis_i and the wrap under cpi+1cp_{i+1}, so healing-iff-confinement with keys [si,cpi+1][s_i, cp_{i+1}] gives si+1∈Cl(C)  ⟺  si∈Cl(C)∨cpi+1∈Cl(C)s_{i+1} \in \mathrm{Cl}(C) \iff s_i \in \mathrm{Cl}(C) \lor cp_{i+1} \in \mathrm{Cl}(C). ∎

For d≥3d \ge 3 in a full tree (2d<N−12d \lt N - 1) the commit beats the N−1N - 1 bound, which is possible because it is not in the cover class: a copath key is shared by every member of its subtree, which is exactly what separation forbids. Its healing condition is the confinement of those shared keys, which is possible because each subtree’s key was derived inside that subtree, bottom-up, rather than handed down from a root that non-members of the subtree hold. The count assumes every copath node has a key. Where a copath subtree has none, the commit must wrap to its members separately, and the number of wraps grows accordingly.

section Path
variable {α : Type}

theorem path_iff {R : RuleSet α} {C : α → Prop} (s cp : Nat → α) (d : Nat)
    (hkdf  : ∀ i, i < d → R (kdf (s i) (s (i+1))))
    (hwrap : ∀ i, i < d → R (wrap (cp (i+1)) (s (i+1))))
    (hfresh : ∀ i, i < d → ∀ ru, R ru → ru.concl = s (i+1) →
                ru.prem = [s i] ∨ ru.prem = [cp (i+1)])
    (hC : ∀ i, i < d → ¬ C (s (i+1))) :
    ∀ i, i ≤ d → (Derivable R C (s i) ↔
      Derivable R C (s 0) ∨ ∃ j, 1 ≤ j ∧ j ≤ i ∧ Derivable R C (cp j)) := by
  intro i
  induction i with
  | zero =>
    intro _
    constructor
    · intro h; exact Or.inl h
    · intro h
      cases h with
      | inl h => exact h
      | inr h => obtain ⟨j, h1, h2, _⟩ := h; omega
  | succ i ih =>
    intro hi
    have hi' : i < d := by omega
    have step := heal_iff (R := R) (C := C) (r' := s (i+1)) (keys := [s i, cp (i+1)])
      (by
        intro k hk
        simp at hk
        cases hk with
        | inl e => subst e; exact hkdf i hi'
        | inr e => subst e; exact hwrap i hi')
      (by
        intro ru hr hc
        cases hfresh i hi' ru hr hc with
        | inl e => exact ⟨s i, by simp, e⟩
        | inr e => exact ⟨cp (i+1), by simp, e⟩)
      (hC i hi')
    have step' : Derivable R C (s (i+1)) ↔
        Derivable R C (s i) ∨ Derivable R C (cp (i+1)) := by
      rw [step]
      constructor
      · intro ⟨k, hk, dk⟩
        simp at hk
        cases hk with
        | inl e => subst e; exact Or.inl dk
        | inr e => subst e; exact Or.inr dk
      · intro h
        cases h with
        | inl h => exact ⟨_, by simp, h⟩
        | inr h => exact ⟨_, by simp, h⟩
    rw [step', ih (by omega)]
    constructor
    · intro h
      cases h with
      | inl h =>
        cases h with
        | inl h0 => exact Or.inl h0
        | inr h => obtain ⟨j, a, b, c⟩ := h; exact Or.inr ⟨j, a, by omega, c⟩
      | inr h => exact Or.inr ⟨i+1, by omega, by omega, h⟩
    · intro h
      cases h with
      | inl h0 => exact Or.inl (Or.inl h0)
      | inr h =>
        obtain ⟨j, a, b, c⟩ := h
        by_cases hj : j = i + 1
        · subst hj; exact Or.inr c
        · exact Or.inl (Or.inr ⟨j, a, by omega, c⟩)

/-- The wraps of a path commit: one per level. -/
def pathWraps (s cp : Nat → α) (d : Nat) : List (Rule α) :=
  (List.range d).map (fun i => wrap (cp (i+1)) (s (i+1)))

/-- A path commit: `d` KDF edges up the path and `d` copath wraps. -/
def pathCommit (s cp : Nat → α) (d : Nat) : List (Rule α) :=
  (List.range d).map (fun i => kdf (s i) (s (i+1))) ++ pathWraps s cp d

theorem pathCommit_cost (s cp : Nat → α) (d : Nat) :
    (pathCommit s cp d).length = 2 * d ∧ (pathWraps s cp d).length = d := by
  simp [pathCommit, pathWraps]; omega

theorem pathCommit_iff {T : RuleSet α} {C : α → Prop} (s cp : Nat → α) (d : Nat)
    (hsinj : ∀ i j, s i = s j → i = j)
    (hT : ∀ ru, T ru → ∀ i, i < d → ru.concl ≠ s (i+1))
    (hC : ∀ i, i < d → ¬ C (s (i+1))) :
    ∀ i, i ≤ d → (Derivable (T.union (ofList (pathCommit s cp d))) C (s i) ↔
      Derivable (T.union (ofList (pathCommit s cp d))) C (s 0) ∨
      ∃ j, 1 ≤ j ∧ j ≤ i ∧ Derivable (T.union (ofList (pathCommit s cp d))) C (cp j)) := by
  apply path_iff s cp d
  · intro i hi
    exact Or.inr (List.mem_append_left _ (List.mem_map.mpr ⟨i, List.mem_range.mpr hi, rfl⟩))
  · intro i hi
    exact Or.inr (List.mem_append_right _ (List.mem_map.mpr ⟨i, List.mem_range.mpr hi, rfl⟩))
  · intro i hi ru hr hc
    rcases hr with hTr | hL
    · exact absurd hc (hT ru hTr i hi)
    · rcases List.mem_append.mp hL with h | h
      · obtain ⟨j, _, e⟩ := List.mem_map.mp h
        subst e
        have := hsinj (j+1) (i+1) hc
        have hj : j = i := by omega
        subst hj; exact Or.inl rfl
      · obtain ⟨j, _, e⟩ := List.mem_map.mp h
        subst e
        have := hsinj (j+1) (i+1) hc
        have hj : j = i := by omega
        subst hj; exact Or.inr rfl
  · exact hC

theorem pathCommit_heal_iff {T : RuleSet α} {C : α → Prop} (s cp : Nat → α) (d : Nat)
    (hsinj : ∀ i j, s i = s j → i = j)
    (hT : ∀ ru, T ru → ∀ i, i < d → ru.concl ≠ s (i+1))
    (hC : ∀ i, i < d → ¬ C (s (i+1))) :
    Secret (T.union (ofList (pathCommit s cp d))) C (s d) ↔
      ¬ Derivable (T.union (ofList (pathCommit s cp d))) C (s 0) ∧
      ∀ j, 1 ≤ j → j ≤ d → ¬ Derivable (T.union (ofList (pathCommit s cp d))) C (cp j) := by
  rw [secret_iff, pathCommit_iff s cp d hsinj hT hC d (Nat.le_refl d)]
  constructor
  · intro h
    exact ⟨fun h0 => h (Or.inl h0), fun j h1 h2 hj => h (Or.inr ⟨j, h1, h2, hj⟩)⟩
  · intro ⟨h0, hj⟩ h
    rcases h with h | ⟨j, h1, h2, h3⟩
    · exact h0 h
    · exact hj j h1 h2 h3

end Path

Flat rebuild

A flat rebuild wraps the fresh root r′r' once to the identity key of each of the N−1N - 1 other members. It needs no tree and no shared keys.

Flat rebuild. Let the identity-key map be injective and assume no rule of TT concludes r′r' or an identity key, r′r' is not an identity key, and r′∉Cr' \notin C. Then:

  1. (healing) r′r' is secret from CC iff no recipient’s identity key is derivable from CC;
  2. (delivery) each recipient holding its own identity key derives r′r';
  3. (in class) when each recipient starts with only its own identity key, the rebuild satisfies all three cover-class conditions, so the cover bound applies to it and gives N−1≤∣W∣=N−1N - 1 \le |W| = N - 1;
  4. (optimality) every commit in the cover class, multi-level ones included, has at least as many rules as the flat rebuild.

Proof. (1) is healing-iff-confinement with keys the recipients’ identity keys. (2) applies one wrap. For (3), a recipient that starts with only its own identity key derives under TT no other identity key, since by the least law (closure law 1) the set {x∣x=idk(o)⇒o=m}\{x \mid x = \mathit{idk}(o) \Rightarrow o = m\} contains the start set and is closed under TT; this gives separation, and freshness of r′r' gives condition 1. (4) is the cover bound together with the count ∣W∣=N−1|W| = N - 1. ∎

A three-member instance with natural-number atoms and an empty transcript checks that the hypotheses of (3) can all hold at once.

section Flat
variable {α : Type}

def flatWraps {M : Type} (idk : M → α) (r' : α) (rcpt : List M) : List (Rule α) :=
  rcpt.map (fun m => wrap (idk m) r')

theorem flat_cost {M : Type} (idk : M → α) (r' : α) (rcpt : List M) :
    (flatWraps idk r' rcpt).length = rcpt.length := by
  simp [flatWraps]

theorem flat_heal_iff {M : Type} {T : RuleSet α} {C : α → Prop}
    (idk : M → α) (r' : α) (rcpt : List M)
    (hfreshT : ∀ ru, T ru → ru.concl ≠ r') (hC : ¬ C r') :
    Secret (T.union (ofList (flatWraps idk r' rcpt))) C r' ↔
      ∀ m, m ∈ rcpt → Secret (T.union (ofList (flatWraps idk r' rcpt))) C (idk m) := by
  rw [heal_secret_iff (keys := rcpt.map idk)]
  · constructor
    · intro h m hm; exact h (idk m) (List.mem_map_of_mem idk hm)
    · intro h k hk
      obtain ⟨m, hm, e⟩ := List.mem_map.mp hk
      subst e; exact h m hm
  · intro k hk
    obtain ⟨m, hm, e⟩ := List.mem_map.mp hk
    subst e
    exact Or.inr (List.mem_map_of_mem (fun m => wrap (idk m) r') hm)
  · intro ru hr hc
    cases hr with
    | inl hT => exact absurd hc (hfreshT ru hT)
    | inr hW =>
      obtain ⟨m, hm, e⟩ := List.mem_map.mp hW
      subst e
      exact ⟨idk m, List.mem_map_of_mem idk hm, rfl⟩
  · exact hC

theorem flat_delivers {M : Type} {T : RuleSet α} (idk : M → α) (r' : α) (rcpt : List M)
    (K : M → α → Prop) (hown : ∀ m, K m (idk m)) :
    ∀ m, m ∈ rcpt → Derivable (T.union (ofList (flatWraps idk r' rcpt))) (K m) r' := by
  intro m hm
  exact heal_of_key (Or.inr (List.mem_map_of_mem (fun m => wrap (idk m) r') hm))
    (.base (hown m))

theorem idk_private {M : Type} {T : RuleSet α} (idk : M → α)
    (hinj : ∀ a b, idk a = idk b → a = b)
    (hT : ∀ ru, T ru → ∀ o, ru.concl ≠ idk o) (m o : M) :
    Derivable T (fun x => x = idk m) (idk o) → o = m := by
  intro d
  have key := derivable_least (R := T) (S := fun x => x = idk m)
    (X := fun x => ∀ o, x = idk o → o = m)
    (fun a ha o e => by subst ha; exact (hinj m o e).symm)
    (fun r hr _ o e => absurd e (hT r hr o)) d
  exact key o rfl

theorem flat_in_class {M : Type} {T : RuleSet α} (idk : M → α)
    (hinj : ∀ a b, idk a = idk b → a = b)
    (hT : ∀ ru, T ru → ∀ o, ru.concl ≠ idk o)
    (r' : α) (hTr : ∀ ru, T ru → ru.concl ≠ r') (hr' : ∀ o, r' ≠ idk o)
    (rcpt : List M) :
    (∀ m, m ∈ rcpt → ¬ Derivable T (fun x => x = idk m) r') ∧
    (∀ w, w ∈ flatWraps idk r' rcpt → ∀ m m', m ∈ rcpt → m' ∈ rcpt →
       (∀ p, p ∈ w.prem → Derivable T (fun x => x = idk m) p) →
       (∀ p, p ∈ w.prem → Derivable T (fun x => x = idk m') p) → m = m') ∧
    (∀ m, m ∈ rcpt →
       Derivable (T.union (ofList (flatWraps idk r' rcpt))) (fun x => x = idk m) r') := by
  refine ⟨?_, ?_, ?_⟩
  · intro m _
    exact not_derivable_of_fresh hTr (fun e => hr' m e)
  · intro w hw m m' _ _ h1 h2
    obtain ⟨o, _, e⟩ := List.mem_map.mp hw
    subst e
    have e1 := idk_private idk hinj hT m o (h1 (idk o) (by simp [wrap]))
    have e2 := idk_private idk hinj hT m' o (h2 (idk o) (by simp [wrap]))
    rw [← e1, ← e2]
  · exact flat_delivers idk r' rcpt (fun m x => x = idk m) (fun _ => rfl)

theorem flat_tight {M : Type} {T : RuleSet α} (idk : M → α)
    (hinj : ∀ a b, idk a = idk b → a = b)
    (hT : ∀ ru, T ru → ∀ o, ru.concl ≠ idk o)
    (r' : α) (hTr : ∀ ru, T ru → ru.concl ≠ r') (hr' : ∀ o, r' ≠ idk o)
    (rcpt : List M) (hnd : rcpt.Nodup) :
    rcpt.length ≤ (flatWraps idk r' rcpt).length ∧
    (flatWraps idk r' rcpt).length = rcpt.length := by
  obtain ⟨h1, h2, h3⟩ := flat_in_class (T := T) idk hinj hT r' hTr hr' rcpt
  exact ⟨cover_lower_bound T _ r' (fun m x => x = idk m) rcpt hnd h1 h2 h3,
         flat_cost idk r' rcpt⟩

theorem flat_optimal {M : Type} (idk : M → α)
    (T : RuleSet α) (W : List (Rule α)) (r' : α) (K : M → α → Prop) (rcpt : List M)
    (hnd : rcpt.Nodup)
    (hnotT : ∀ m, m ∈ rcpt → ¬ Derivable T (K m) r')
    (hsep : ∀ w, w ∈ W → ∀ m m', m ∈ rcpt → m' ∈ rcpt →
       (∀ p, p ∈ w.prem → Derivable T (K m) p) →
       (∀ p, p ∈ w.prem → Derivable T (K m') p) → m = m')
    (hdeliver : ∀ m, m ∈ rcpt → Derivable (T.union (ofList W)) (K m) r') :
    (flatWraps idk r' rcpt).length ≤ W.length := by
  rw [flat_cost]
  exact cover_lower_bound T W r' K rcpt hnd hnotT hsep hdeliver

theorem flat_witness :
    ([0, 1, 2] : List (Fin 3)).length ≤
      (flatWraps (fun o : Fin 3 => o.val) (100 : Nat) [0, 1, 2]).length :=
  (flat_tight (T := fun _ => False) (fun o : Fin 3 => o.val)
    (fun a b h => Fin.ext h) (fun _ h _ => h.elim) 100 (fun _ h => h.elim)
    (fun o h => by have := o.isLt; simp only at h; omega) [0, 1, 2] (by decide)).1

end Flat

Side by side: the path commit publishes 2d=2log⁡2N2d = 2\log_2 N rules (in a full tree), dd of them wraps, and needs confined subtree keys; the flat rebuild publishes N−1N - 1 rules, all wraps, and needs only confined identity keys. By the cover bound, no commit in the cover class, that is, none of whose rules two recipients can open, publishes fewer rules than the flat rebuild.

Agreement on the secret

Every wrap above carries the same atom r′r', so agreement on the new root is built into the model. A real commit carries one ciphertext per recipient, and the log binds the ciphertexts, not what they decrypt to. A commit with per-recipient payloads is expressible, and each recipient derives its own payload; nothing in the closure model or in the ordering of the log forces the payloads to be equal. Agreement therefore has to come from a check that recipients run before adopting the epoch.

Agreement from a binding check. If the signed entry carries a value cc, every accepting recipient checks H(payload)=cH(\text{payload}) = c, and HH is injective, then all accepting recipients hold the same payload.

Proof. H(x)=c=H(y)H(x) = c = H(y) and injectivity. ∎

Symbolically injectivity is all that is needed. Computationally HH must be a collision-resistant commitment, or a key-committing confirmation tag computed from the new secret and a hash of the whole commit, verified before the new epoch is used.

section Agreement
variable {α : Type}

def perRecipient {M : Type} (k : M → α) (pay : M → α) (rcpt : List M) : List (Rule α) :=
  rcpt.map (fun m => wrap (k m) (pay m))

theorem split_delivery {M : Type} {T : RuleSet α} (k : M → α) (pay : M → α)
    (rcpt : List M) {m : M} (hm : m ∈ rcpt) :
    Derivable (T.union (ofList (perRecipient k pay rcpt))) (fun x => x = k m) (pay m) :=
  heal_of_key (Or.inr (List.mem_map_of_mem (fun m => wrap (k m) (pay m)) hm)) (.base rfl)

theorem agreement_of_binding {β M : Type} (H : α → β)
    (hbind : ∀ x y, H x = H y → x = y) (c : β) (acc : M → α)
    (hacc : ∀ m, H (acc m) = c) : ∀ m m', acc m = acc m' :=
  fun m m' => hbind _ _ ((hacc m).trans (hacc m').symm)

end Agreement

end KeySched

Scope and open questions

The theorems are exact statements about a symbolic model of passive key secrecy, and they lose what such models always lose against computational definitions of continuous group key agreement: real-or-random indistinguishability of the epoch key, corruptions interleaved adaptively with challenges, active adversaries that inject commits, and failures or leakage of randomness. The standard passive soundness results for symbolic encryption assume, among other things, that the key graph be acyclic and that each key play a single role, so a schedule that uses one secret both as a KDF input and as a decryption key needs a separate KDF edge for each role before the symbolic results transfer. Freshness, identity-key privacy and confinement are hypotheses to be discharged for each schedule; the static compromise set does not express when a corruption happened, and the cover bound and its kk-bounded form count published rules inside their classes only.

Open questions:

  • Adaptive transfer. The healing characterisation is per commit. Lifting it to an adaptive computational statement is a generalised selective decryption problem. Naive reductions lose a factor exponential in the number of keys nn; the analysis of “Tackling Adaptive Corruptions in Multicast Encryption Protocols” (TCC 2007) reduces the loss to nO(d)n^{O(d)} for key graphs of depth dd, quasi-polynomial for depth log⁡N\log N, and “A Quasipolynomial Reduction for Generalized Selective Decryption on Trees” (CRYPTO 2015) obtains a quasi-polynomial loss for trees of any depth. For bottom-up path schedules, “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement” (IEEE S&P 2021) proves adaptive security with quasi-polynomial loss in the standard model and polynomial loss with random oracles, and “Grafting Key Trees: Efficient Key Management for Overlapping Groups” (TCC 2021) treats adaptive security of key trees. In the other direction, “The Cost of Adaptivity in Security Games on Graphs” (TCC 2021) proves lower bounds for a broad class of black-box reductions (oblivious ones) on such graph games, under which a super-polynomial loss is unavoidable for some graph families. What remains open is whether the log setting, with corruptions described by a per-interval predicate as in the next item, admits a polynomial standard-model loss through a reduction outside that class, or falls under the same barrier.
  • A safety predicate on histories. The static set CC cannot say “compromised at epoch 5, healed at epoch 7, compromised again at epoch 9”. A predicate on the sequence of corruptions and commits, with the healing theorem stated per interval, would make the per-epoch statements composable over a whole history.

Logical key hierarchies and key graphs: “Secure Group Communications Using Key Graphs” (ACM SIGCOMM 1998) and “Key Management for Multicast: Issues and Architectures” (RFC 2627, 1999); one-way function trees, the bottom-up counterpart: “Key Establishment in Large Dynamic Groups Using One-Way Function Trees” (IEEE Transactions on Software Engineering, 2003). Lower bounds for multicast rekeying: “Efficient Communication-Storage Tradeoffs for Multicast Encryption” (EUROCRYPT 1999), “A Lower Bound for Multicast Key Distribution” (IEEE INFOCOM 2001), and the symbolic bound closest to the cover argument here, “Optimal Communication Complexity of Generic Multicast Key Distribution” (EUROCRYPT 2004). Symbolic versus computational encryption: “Reconciling Two Views of Cryptography (The Computational Soundness of Formal Encryption)” (IFIP TCS 2000; Journal of Cryptology, 2002), “Adaptive Security of Symbolic Encryption” (TCC 2005) and “Tackling Adaptive Corruptions in Multicast Encryption Protocols” (TCC 2007), with the quasi-polynomial reduction of “A Quasipolynomial Reduction for Generalized Selective Decryption on Trees” (CRYPTO 2015) and the reduction lower bounds of “The Cost of Adaptivity in Security Games on Graphs” (TCC 2021); adaptive security of tree-based schedules: “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement” (IEEE S&P 2021) and “Grafting Key Trees: Efficient Key Management for Overlapping Groups” (TCC 2021). Group messaging with healing: “On Ends-to-Ends Encryption: Asynchronous Group Messaging with Strong Security Guarantees” (ACM CCS 2018), “Continuous Group Key Agreement with Active Security” (TCC 2020), “On the Price of Concurrency in Group Ratcheting Protocols” (TCC 2020), and “The Complexities of Healing in Secure Group Messaging: Why Cross-Group Effects Matter” (USENIX Security 2021), which is relevant because identity keys are shared across groups. Logs and equivocation: “Certificate Transparency Version 2.0” (RFC 9162, 2021) for inclusion and consistency proofs, and “Building Secure File Systems out of Byzantine Storage” (ACM PODC 2002) and “Secure Untrusted Data Repository” (OSDI 2004) for fork consistency.