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.
- 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.
- 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.
- 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.
- Passive, static adversary. The adversary reads the whole log but adds no entries. Its knowledge is one fixed set 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 . Every public derivation step is a definite rule with a list of premises and one conclusion.
Rules and closure. A rule lets whoever knows all premises learn . Two kinds occur:
- a KDF edge : the child secret is a one-way function of the parent ;
- a wrap : a public ciphertext of the payload under the key .
For a set of rules and a set of atoms , the closure is the least set that contains and contains whenever it contains all premises of a rule . We say is derivable from under when .
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:
- (least) for every closed under ;
- (monotone) and imply ;
- (cut) implies , and so ;
- (composition) if and then ;
- (last step) if and , some rule of concludes and has all its premises in . In particular, if no rule of concludes and , then .
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 to a log gives the transcript of together with the rules of , 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 and epoch roots .
- is secret from knowledge when .
- Forward secrecy for member states : for all , is secret from .
- Post-compromise security from against : for all , is secret from .
- Removal security of a member removed at with knowledge : every with is secret from .
- Add security of a member joining at with knowledge : every with is secret from .
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 and wraps it under some keys. The commit heals a compromise if is secret from afterwards. A key is confined from if , where is the rule set in force after the commit, for instance the transcript together with the commit.
Healing iff confinement. Let be keys with every wrap in . Assume freshness: every rule of that concludes has the form for some . Assume . Then
so the commit heals if and only if every wrap key is confined from .
Proof. () apply the wrap. () by the last-step law some rule concludes with derivable premises; by freshness it is a wrap under some , and its only premise is derivable. ∎
The hypothesis 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 or the recipient’s . Symbolically it is the pair of rules and . Freshness must then list both sides.
Two-sided wraps. If both sides and of each listed pair are in , these are the only rules concluding , and , then is derivable from iff some or some is. If moreover every sender key is erased (not derivable), then is derivable iff some recipient key is.
A public wrap gives no forward secrecy against its recipient key. If both sides of a two-sided wrap of are published and is derivable from , then is not secret from , whatever happened to .
Proof. The first part is healing-iff-confinement with key list . The second applies the 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 and , then . No secret derived from is confined from anyone who derives .
Top-down trees. Index tree positions by bit strings, with the root and the child of on side . A tree of depth is derived top-down when contains every KDF edge with . Then every holder of the root derives every node secret: for all whenever . 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 shows ; 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 derives every node of every epoch , 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 (a list of rules) added to a transcript delivers to a duplicate-free list of recipients with initial knowledge . It is in the cover class when
- no recipient derives from alone;
- (separation) no rule of has all its premises in and in for two distinct recipients ;
- every recipient derives under .
Rules of may conclude intermediate secrets that other rules of 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 counts every published rule; it bounds the number of wraps when contains only wraps.
Bounded sharing. Replace (2) by (-separation): for every rule of , at most distinct recipients derive all its premises under . Under (1), (3) and -separation, , so, for , .
Cover lower bound. A commit in the cover class has . For a group of members, where the committer rekeys the others, this is .
Proof. First a decomposition: anything derivable under is derivable under alone, or some rule of has all its premises derivable under alone (the first rule of used in the derivation). By (1) and (3) every recipient thus has a rule whose premises it derives under . By -separation the map is at most -to-one. A pigeonhole count, by induction on that splits off the recipients served by the head rule, gives . Separation is -separation with , 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 members the bounded form gives : a schedule in which every published rule can be opened by at most of the recipients pays at least that many rules. A common way to meet separation is through owned material. If every rule of has a premise that is either an identity key, derivable under only by its owner, or a secret that no recipient derives under (such as a fresh intermediate key of the commit), then separation holds and the bound applies. A two-level commit, which wraps a fresh to each identity key and then wraps under , 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 to all three, although none of them could derive 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 together with the log, for instance by replaying the log from its start. The log is permanent, so recovery is available to whoever holds at any later time.
Recovery exposure. Let be a set of epochs such that for every : the epochs can recover. Let . Then
- for every ;
- post-compromise security against fails from every that is at most some ;
- if the member state at some epoch still holds , forward secrecy fails as soon as contains an epoch .
Proof. (1) is monotonicity in the start set; (2) and (3) instantiate (1). ∎
The statement is restricted to the epochs 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 the theorem asserts nothing, and post-compromise security from an beyond every element of 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 , 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 samples a fresh leaf secret and derives from by a KDF, from the leaf up to the root . Each is also wrapped under the key of the copath node at that level, the sibling subtree whose members need it. The commit publishes KDF edges and wraps.
Path commit. Assume is injective, no rule of concludes any (), and contains no . Write for the commit and for . Then for every ,
Hence the new root is secret from if and only if the leaf secret and every copath key are confined from . The commit has rules, of which are wraps.
Proof. Induction on . At level the only rules concluding are the KDF edge from and the wrap under , so healing-iff-confinement with keys gives . ∎
For in a full tree () the commit beats the 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 once to the identity key of each of the other members. It needs no tree and no shared keys.
Flat rebuild. Let the identity-key map be injective and assume no rule of concludes or an identity key, is not an identity key, and . Then:
- (healing) is secret from iff no recipient’s identity key is derivable from ;
- (delivery) each recipient holding its own identity key derives ;
- (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 ;
- (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 no other identity key, since by the least law (closure law 1) the set contains the start set and is closed under ; this gives separation, and freshness of gives condition 1. (4) is the cover bound together with the count . ∎
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 rules (in a full tree), of them wraps, and needs confined subtree keys; the flat rebuild publishes 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 , 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 , every accepting recipient checks , and is injective, then all accepting recipients hold the same payload.
Proof. and injectivity. ∎
Symbolically injectivity is all that is needed. Computationally 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 -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 ; the analysis of “Tackling Adaptive Corruptions in Multicast Encryption Protocols” (TCC 2007) reduces the loss to for key graphs of depth , quasi-polynomial for depth , 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 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.
Related work
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.