Research / 2023 –

Keys that are never stored

A wallet key re-derived on demand from factors: derivability sets as monotone access structures, AND/OR key combination realising every monotone formula, a threshold key-derivation service, a two-of-three construction, and what a pairing check does and does not give, all in a symbolic model checked in Lean.

Access structuresThreshold cryptographySymbolic protocol models
up-closed
exactly the families of coalitions that arise as derivability sets, over any finite set of parties
2 of 3
identity, device, recovery: with threshold 1 ≤ t ≤ n no single party derives the key, and every pair of factors does
t − 1
shares of the threshold service derive neither its master secret nor any identity key

A signing key does not have to sit anywhere. It can be recomputed whenever it is needed from several factors and then erased. One factor can come from a threshold key-derivation service, which evaluates a function of its master secret at the user’s authenticated identity. Another can be a secret that a passkey (platform authenticator) releases through a PRF-style extension. A third can be a recovery code. Several kinds of party then touch the key: the identity provider, the service nodes, the device, whoever keeps the recovery code, a key-store service that keeps ciphertexts, whoever sets the service’s derivation policy, and whoever supplies the code that runs once the key is rebuilt.

The question is which sets of these parties, by pooling what they hold, can compute the key. This article answers it exactly in a symbolic model, in the style of “On the security of public key protocols” (IEEE Transactions on Information Theory, 1983). Secrets are opaque atoms, and the only way to learn an atom is to apply a public rule. In order, the article shows:

  1. The family of coalitions that derive a key is always up-closed, and, over a finite set of parties, every up-closed family arises this way.
  2. Combining keys with a KDF realises AND, and wrapping one key under several realises OR, so every monotone formula over factors is realisable.
  3. Two general necessity results: whoever can change the derivation policy can, by installing one rule, stand in for the holder of the binding atom (in particular for an identity provider whose only secret is that atom) in every coalition that is qualified once given it, and whoever supplies the code that runs after reconstruction can, by emitting one ciphertext, make itself a qualified coalition on its own.
  4. An exact analysis of the threshold service, and a two-of-three construction built on it.
  5. A pairing check: what it gives (correctness and binding) and what it does not give (confidentiality).

All definitions and proofs below are Lean 4 (core library only). The code blocks, read in order, form one file that compiles with no sorry and no added axioms.

The symbolic model

Rules and derivability. A rule p1,…,pk⊢cp_1, \dots, p_k \vdash c says that anyone who knows all the premises pip_i can compute the conclusion cc. For a set of rules RR and a start set SS, DerR(S)\mathrm{Der}_R(S) is the least set that contains SS and is closed under RR.

Three kinds of rule are used throughout:

  • kdf(x,y)\mathrm{kdf}(x, y) is x⊢yx \vdash y, a one-way derivation.
  • kdf2(a,b,c)\mathrm{kdf2}(a, b, c) is a,b⊢ca, b \vdash c, that is c=KDF(a ∥ b)c = \mathrm{KDF}(a \,\|\, b).
  • wrap(k,m)\mathrm{wrap}(k, m) is k⊢mk \vdash m. It stands for a ciphertext of mm under kk that anyone may read, so knowing kk gives mm.

A rule set is a predicate on rules, so it can be infinite (one rule per identity, for example). Derivability is an inductive predicate:

namespace Keyless

/-! ## Section 1. Rules and closure -/

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

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

/-- A KDF edge with one input. -/
def kdf {α : Type} (parent child : α) : Rule α := ⟨[parent], child⟩

/-- A KDF edge with two inputs: `child = KDF(a ‖ b)`. -/
def kdf2 {α : Type} (a b child : α) : Rule α := ⟨[a, b], child⟩

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

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

Five facts about the closure are used repeatedly. It is the least rule-closed superset of the start set. It grows with the start set and with the rules. It is transitive (cut). And a derived atom that is not in the start set was produced by some rule whose premises are themselves derivable (last-step inversion).

section Basic
variable {α : Type}

/-- The closure is contained in every rule-closed superset of `S`. -/
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

/-- Monotone in the start set. -/
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

/-- Monotone in the rules. -/
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

/-- Cut: if everything in `T` is derivable from `S`, so is everything
    derivable from `T`. -/
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

/-- Last-step inversion. -/
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⟩

/-- An atom that no rule concludes is derivable only if it is initially known. -/
theorem not_concl_base {R : RuleSet α} {S : α → Prop} {x : α}
    (d : Derivable R S x) (h : ∀ r, R r → r.concl ≠ x) : S x := by
  cases d with
  | base h' => exact h'
  | rule r hr _ => exact absurd rfl (h r hr)

end Basic

Derivability sets

Derivability set. A scheme consists of a rule set RR, a holding relation (which atoms each party holds) and a key MM. A coalition CC is a set of parties, and it knows the union of its members’ atoms. The derivability set of the scheme is

D(R,hold,M)={ C  :  M∈DerR(⋃p∈Chold(p)) }.\mathcal{D}(R, \mathrm{hold}, M) = \lbrace\, C \;:\; M \in \mathrm{Der}_R(\textstyle\bigcup_{p \in C} \mathrm{hold}(p)) \,\rbrace .

When RR and hold\mathrm{hold} are fixed we write D(M)\mathcal{D}(M).

A family F\mathcal{F} of coalitions is up-closed (a monotone access structure) if C∈FC \in \mathcal{F} and C⊆C′C \subseteq C' imply C′∈FC' \in \mathcal{F}.

Monotonicity (dset_upclosed). Every derivability set is up-closed, for every rule set, holding relation and key.

/-! ## Section 2. Derivability sets -/

section DSetSec
variable {P α : Type}

/-- A coalition is a Boolean predicate on parties. -/
abbrev Coalition (P : Type) := P → Bool

/-- What a coalition holds: the union of its members' secrets. -/
def Know (hold : P → α → Prop) (C : Coalition P) : α → Prop :=
  fun a => ∃ p, C p = true ∧ hold p a

/-- Coalition inclusion. -/
def CSub (C C' : Coalition P) : Prop := ∀ p, C p = true → C' p = true

/-- The derivability set of a scheme `(R, hold)` for the key `M`: the family
    of coalitions that derive `M`. -/
def DSet (R : RuleSet α) (hold : P → α → Prop) (M : α) (C : Coalition P) : Prop :=
  Derivable R (Know hold C) M

/-- A family of coalitions is up-closed (a monotone access structure). -/
def UpClosed (F : Coalition P → Prop) : Prop :=
  ∀ C C', CSub C C' → F C → F C'

/-- Monotonicity.  Every derivability set is up-closed. -/
theorem dset_upclosed (R : RuleSet α) (hold : P → α → Prop) (M : α) :
    UpClosed (DSet R hold M) := by
  intro C C' h d
  exact mono_S (fun a ⟨p, hp, ha⟩ => ⟨p, h p hp, ha⟩) d

The converse holds over a finite set of parties. The canonical scheme of a family F\mathcal{F} gives each party pp one private atom sps_p. For each C∈FC \in \mathcal{F} it adds the rule {sp:p∈C}⊢M\lbrace s_p : p \in C \rbrace \vdash M, where the premises are listed in the order of a fixed list of all parties.

Realisation (canon_dset). If F\mathcal{F} is up-closed, the derivability set of its canonical scheme is exactly F\mathcal{F}.

Characterisation (access_structure_iff). Over a finite set of parties, a family of coalitions is the derivability set of some scheme if and only if it is up-closed.

Proof sketch. Suppose CC derives MM. The key is held by no party, so the last step is the rule of some C0∈FC_0 \in \mathcal{F}. Each premise sqs_q of that rule is concluded by no rule, so it must be held by CC, which gives C0⊆CC_0 \subseteq C. Up-closure then gives C∈FC \in \mathcal{F}. In the other direction, the rule for CC itself fires. ∎

/-- The canonical scheme of a family `F`: one secret atom per party, the key
    is `none`, and for every coalition in `F` a rule from the secrets of its
    members (listed via the complete party list `ps`) to the key. -/
def canonRules (ps : List P) (F : Coalition P → Prop) : RuleSet (Option P) :=
  fun r => ∃ C, F C ∧ r = ⟨(ps.filter C).map some, none⟩

/-- In the canonical scheme party `p` holds exactly the atom `some p`. -/
def canonHold (p : P) (a : Option P) : Prop := a = some p

/-- Realisation.  Over a finite party set, the canonical scheme
    of an up-closed family has exactly that family as derivability set. -/
theorem canon_dset (ps : List P) (hps : ∀ p, p ∈ ps) (F : Coalition P → Prop)
    (hF : UpClosed F) (C : Coalition P) :
    DSet (canonRules ps F) canonHold none C ↔ F C := by
  constructor
  · intro d
    have hnb : ¬ Know canonHold C none := fun ⟨p, _, h⟩ => nomatch h
    obtain ⟨r, ⟨C0, hC0, rfl⟩, _, hp⟩ := last_step d hnb
    apply hF C0 C _ hC0
    intro q hq
    have hmem : some q ∈ (ps.filter C0).map some :=
      List.mem_map.mpr ⟨q, List.mem_filter.mpr ⟨hps q, hq⟩, rfl⟩
    have hb := not_concl_base (hp _ hmem)
      (fun r ⟨C1, _, e⟩ => by subst e; intro h; exact nomatch h)
    obtain ⟨p, hp', e⟩ := hb
    cases e
    exact hp'
  · intro hC
    apply Derivable.rule ⟨(ps.filter C).map some, none⟩ ⟨C, hC, rfl⟩
    intro x hx
    obtain ⟨q, hq, rfl⟩ := List.mem_map.mp hx
    exact .base ⟨q, (List.mem_filter.mp hq).2, rfl⟩

/-- Equivalence.  Over a finite party set, a family of coalitions
    is the derivability set of some scheme iff it is up-closed. -/
theorem access_structure_iff (ps : List P) (hps : ∀ p, p ∈ ps)
    (F : Coalition P → Prop) :
    (∃ (β : Type) (R : RuleSet β) (hold : P → β → Prop) (M : β),
        ∀ C, DSet R hold M C ↔ F C) ↔ UpClosed F := by
  constructor
  · intro ⟨β, R, hold, M, H⟩ C C' h hC
    exact (H C').mp (dset_upclosed R hold M C C' h ((H C).mpr hC))
  · intro hF
    exact ⟨Option P, canonRules ps F, canonHold, none, canon_dset ps hps F hF⟩

end DSetSec

So “which coalitions can rebuild the key” always has a monotone answer, and over finitely many parties every monotone answer can be achieved. The canonical scheme has one rule per qualified coalition (one per minimal qualified coalition would already suffice), and even the minimal ones can be exponentially many. This mirrors the general construction of “Secret sharing scheme realizing general access structure” (IEEE Globecom, 1987). The next two sections give compact schemes built from formulas.

AND and OR by key combination

AND. m=KDF(k1 ∥ k2)m = \mathrm{KDF}(k_1 \,\|\, k_2), the rule kdf2(k1,k2,m)\mathrm{kdf2}(k_1, k_2, m). More generally, an ℓ\ell-ary KDF(k1∥⋯∥kℓ)\mathrm{KDF}(k_1 \| \cdots \| k_\ell) is the single rule with premise list [k1,…,kℓ][k_1, \dots, k_\ell], and its output is derivable exactly when every kjk_j is (andN_iff below).

OR. Pick mm fresh and publish mm wrapped under k1k_1 and under k2k_2, the rules wrap(k1,m)\mathrm{wrap}(k_1, m) and wrap(k2,m)\mathrm{wrap}(k_2, m).

Both need a freshness side condition. If some other rule also concluded mm, or a party held mm, then the derivability set could only grow, and the equations below could fail.

AND (and_iff, dset_and). Suppose kdf2(k1,k2,m)∈R\mathrm{kdf2}(k_1, k_2, m) \in R, every rule concluding mm has premises exactly [k1,k2][k_1, k_2], and mm is not initially known. Then mm is derivable if and only if both k1k_1 and k2k_2 are. As derivability sets: D(m)=D(k1)∩D(k2)\mathcal{D}(m) = \mathcal{D}(k_1) \cap \mathcal{D}(k_2).

OR (or_iff, dset_or). Suppose both wraps are in RR, every rule concluding mm has premises [k1][k_1] or [k2][k_2], and mm is not initially known. Then mm is derivable if and only if k1k_1 or k2k_2 is. As derivability sets: D(m)=D(k1)∪D(k2)\mathcal{D}(m) = \mathcal{D}(k_1) \cup \mathcal{D}(k_2).

/-! ## Section 3. AND / OR combination and monotone formulas -/

section Combine
variable {α : Type}

/-- AND.  If `m = KDF(k₁ ‖ k₂)` is the only rule concluding `m`
    and `m` is not initially known, then `m` is derivable iff both `k₁` and
    `k₂` are. -/
theorem and_iff {R : RuleSet α} {S : α → Prop} {k₁ k₂ m : α}
    (hr : R (kdf2 k₁ k₂ m))
    (hfresh : ∀ r, R r → r.concl = m → r.prem = [k₁, k₂]) (hS : ¬ S m) :
    Derivable R S m ↔ Derivable R S k₁ ∧ Derivable R S k₂ := by
  constructor
  · intro d
    obtain ⟨r, hr', hc, hp⟩ := last_step d hS
    have e := hfresh r hr' hc
    exact ⟨hp k₁ (by rw [e]; simp), hp k₂ (by rw [e]; simp)⟩
  · intro ⟨d₁, d₂⟩
    exact Derivable.rule (kdf2 k₁ k₂ m) hr (fun p hp => by
      simp [kdf2] at hp
      rcases hp with rfl | rfl
      · exact d₁
      · exact d₂)

/-- ℓ-ary AND.  If the only rule concluding `m` has premise list `ks`
    (one KDF over all of `ks`), and `m` is not initially known, then `m` is
    derivable iff every key in `ks` is. -/
theorem andN_iff {R : RuleSet α} {S : α → Prop} {ks : List α} {m : α}
    (hr : R ⟨ks, m⟩)
    (hfresh : ∀ r, R r → r.concl = m → r.prem = ks) (hS : ¬ S m) :
    Derivable R S m ↔ ∀ k, k ∈ ks → Derivable R S k := by
  constructor
  · intro d k hk
    obtain ⟨r, hr', hc, hp⟩ := last_step d hS
    exact hp k (by rw [hfresh r hr' hc]; exact hk)
  · intro h
    exact Derivable.rule ⟨ks, m⟩ hr h

/-- OR.  If `m` is a fresh secret whose only rules are wraps
    under `k₁` and under `k₂`, then `m` is derivable iff `k₁` or `k₂` is. -/
theorem or_iff {R : RuleSet α} {S : α → Prop} {k₁ k₂ m : α}
    (hw₁ : R (wrap k₁ m)) (hw₂ : R (wrap k₂ m))
    (hfresh : ∀ r, R r → r.concl = m → r.prem = [k₁] ∨ r.prem = [k₂])
    (hS : ¬ S m) :
    Derivable R S m ↔ Derivable R S k₁ ∨ Derivable R S k₂ := by
  constructor
  · intro d
    obtain ⟨r, hr', hc, hp⟩ := last_step d hS
    rcases hfresh r hr' hc with e | e
    · exact Or.inl (hp k₁ (by rw [e]; simp))
    · exact Or.inr (hp k₂ (by rw [e]; simp))
  · intro h
    rcases h with d | d
    · exact Derivable.rule (wrap k₁ m) hw₁ (fun p hp => by
        simp [wrap] at hp; subst hp; exact d)
    · exact Derivable.rule (wrap k₂ m) hw₂ (fun p hp => by
        simp [wrap] at hp; subst hp; exact d)

/-- AND, derivability sets: the AND-combined key's derivability
    set is the intersection of the two derivability sets. -/
theorem dset_and {P : Type} {R : RuleSet α} {hold : P → α → Prop} {k₁ k₂ m : α}
    (hr : R (kdf2 k₁ k₂ m))
    (hfresh : ∀ r, R r → r.concl = m → r.prem = [k₁, k₂])
    (hm : ∀ p, ¬ hold p m) (C : Coalition P) :
    DSet R hold m C ↔ DSet R hold k₁ C ∧ DSet R hold k₂ C :=
  and_iff hr hfresh (fun ⟨p, _, h⟩ => hm p h)

/-- OR, derivability sets: the OR-combined key's derivability
    set is the union of the two derivability sets. -/
theorem dset_or {P : Type} {R : RuleSet α} {hold : P → α → Prop} {k₁ k₂ m : α}
    (hw₁ : R (wrap k₁ m)) (hw₂ : R (wrap k₂ m))
    (hfresh : ∀ r, R r → r.concl = m → r.prem = [k₁] ∨ r.prem = [k₂])
    (hm : ∀ p, ¬ hold p m) (C : Coalition P) :
    DSet R hold m C ↔ DSet R hold k₁ C ∨ DSet R hold k₂ C :=
  or_iff hw₁ hw₂ hfresh (fun ⟨p, _, h⟩ => hm p h)

end Combine

Every monotone formula is realisable

A monotone formula over a set of factors is built from variables, ∧\wedge and ∨\vee. Its truth value is taken relative to the set of available factors. Positions in the syntax tree are paths of Booleans, with false for left and true for right.

/-- Monotone formulas over a set of factors. -/
inductive Formula (F : Type) where
  | var : F → Formula F
  | and : Formula F → Formula F → Formula F
  | or  : Formula F → Formula F → Formula F

namespace Formula
variable {F : Type}

/-- Truth of a formula when the factors satisfying `σ` are available. -/
def evalP : Formula F → (F → Prop) → Prop
  | .var f, σ => σ f
  | .and a b, σ => a.evalP σ ∧ b.evalP σ
  | .or a b, σ => a.evalP σ ∨ b.evalP σ

theorem evalP_mono (φ : Formula F) {σ τ : F → Prop} (h : ∀ f, σ f → τ f) :
    φ.evalP σ → φ.evalP τ := by
  induction φ with
  | var f => exact h f
  | and a b iha ihb => exact fun ⟨x, y⟩ => ⟨iha x, ihb y⟩
  | or a b iha ihb => exact fun x => x.elim (fun x => .inl (iha x)) (fun y => .inr (ihb y))

theorem evalP_congr (φ : Formula F) {σ τ : F → Prop} (h : ∀ f, σ f ↔ τ f) :
    φ.evalP σ ↔ φ.evalP τ :=
  ⟨evalP_mono φ (fun f => (h f).mp), evalP_mono φ (fun f => (h f).mpr)⟩

/-- Subformula at a path from the root (`false` = left, `true` = right). -/
def get : Formula F → List Bool → Option (Formula F)
  | φ, [] => some φ
  | .var _, _ :: _ => none
  | .and a _, false :: r => get a r
  | .and _ b, true :: r => get b r
  | .or a _, false :: r => get a r
  | .or _ b, true :: r => get b r

/-- Left / right child. -/
def child : Bool → Formula F → Option (Formula F)
  | _, .var _ => none
  | false, .and a _ => some a
  | true, .and _ b => some b
  | false, .or a _ => some a
  | true, .or _ b => some b

theorem get_append (φ : Formula F) (q : List Bool) (b : Bool) :
    get φ (q ++ [b]) = (get φ q).bind (child b) := by
  induction q generalizing φ with
  | nil => cases φ <;> cases b <;> simp [get, child]
  | cons c q ih => cases φ <;> cases c <;> simp [get, ih]

end Formula

Formula scheme. Let φ\varphi be a monotone formula. Each factor ff has a key fkey(f)\mathrm{fkey}(f). Each internal position qq of φ\varphi gets a gate atom νq\nu_q. The key carried by position qq is fkey(f)\mathrm{fkey}(f) if the subformula there is the variable ff, and νq\nu_q otherwise. Write q0q0 and q1q1 for the left and right children of qq (the path qq extended by false or true). The rules are:

  • for an ∧\wedge-node at qq, the rule νq=KDF(key(q0) ∥ key(q1))\nu_q = \mathrm{KDF}(\text{key}(q0) \,\|\, \text{key}(q1));
  • for an ∨\vee-node at qq, νq\nu_q is wrapped under key(q0)\text{key}(q0) and under key(q1)\text{key}(q1);
  • the master key MM is wrapped under the root key;
  • in addition, any factor-level rules RfacR_{\mathrm{fac}} over base secrets, which describe how factor keys themselves are obtained.

Write RφR_\varphi for the full rule set of the scheme. Base atoms are identified with base secrets, so a start set KK of base atoms is also a set of base secrets.

Because gate atoms are indexed by position, two identical subformulas at different places get different gate keys, and freshness holds by construction.

/-- Atoms of a formula-realised scheme: base secrets, one gate key per
    internal position of the formula, and the master key. -/
inductive Atom (B : Type) where
  | base : B → Atom B
  | node : List Bool → Atom B
  | master : Atom B

section Realise
variable {B F : Type}

/-- The key carried by the subformula at position `p`: the factor key for a
    variable, a gate key for an internal node. -/
def keyOf (fkey : F → B) : Formula F → List Bool → Atom B
  | .var f, _ => .base (fkey f)
  | .and _ _, p => .node p
  | .or _ _, p => .node p

/-- Gate rules.  AND: the gate key is `KDF(left ‖ right)`.  OR: the gate key
    is a fresh secret wrapped under the left key and under the right key. -/
def gates (fkey : F → B) : Formula F → List Bool → List (Rule (Atom B))
  | .var _, _ => []
  | .and a b, p =>
      kdf2 (keyOf fkey a (p ++ [false])) (keyOf fkey b (p ++ [true])) (.node p) ::
        (gates fkey a (p ++ [false]) ++ gates fkey b (p ++ [true]))
  | .or a b, p =>
      wrap (keyOf fkey a (p ++ [false])) (.node p) ::
      wrap (keyOf fkey b (p ++ [true])) (.node p) ::
        (gates fkey a (p ++ [false]) ++ gates fkey b (p ++ [true]))

/-- Factor-level rules over base secrets, lifted to atoms. -/
def liftR (Rf : RuleSet B) : RuleSet (Atom B) :=
  fun r => ∃ r0, Rf r0 ∧ r = ⟨r0.prem.map .base, .base r0.concl⟩

/-- The scheme realising `φ`: factor rules, gate rules, and the master key
    wrapped under the root key. -/
def scheme (Rf : RuleSet B) (fkey : F → B) (φ : Formula F) : RuleSet (Atom B) :=
  fun r => liftR Rf r ∨ r ∈ gates fkey φ [] ∨ r = wrap (keyOf fkey φ []) .master

Formula realisation (formula_scheme). Let KK be any start set that contains only base secrets. Then

M∈DerRφ(K)  ⟺  φ is true,where factor f counts as available exactly when fkey(f)∈DerRfac(K).\begin{gathered} M \in \mathrm{Der}_{R_\varphi}(K) \iff \varphi \text{ is true,} \\ \text{where factor } f \text{ counts as available exactly when } \mathrm{fkey}(f) \in \mathrm{Der}_{R_{\mathrm{fac}}}(K). \end{gathered}

Proof sketch. Soundness: define the intended truth value of every atom. A base atom is true if it is derivable by the factor rules. A gate atom νq\nu_q is true if the subformula at qq is true. MM is true if φ\varphi is. This valuation contains KK and is closed under every rule, so it contains the closure. Every gate rule sits at a unique position (mem_gates), and get_append relates a position to its children. Completeness: by induction on the subformula, each true subformula’s key is derivable, and the final wrap gives MM. ∎

/-- The rule a subformula contributes at its own position. -/
def Head (fkey : F → B) : Formula F → List Bool → Rule (Atom B) → Prop
  | .var _, _, _ => False
  | .and a b, p, r => r = kdf2 (keyOf fkey a (p ++ [false])) (keyOf fkey b (p ++ [true])) (.node p)
  | .or a b, p, r => r = wrap (keyOf fkey a (p ++ [false])) (.node p) ∨
                     r = wrap (keyOf fkey b (p ++ [true])) (.node p)

theorem mem_gates (fkey : F → B) (φ : Formula F) (p : List Bool) (r : Rule (Atom B))
    (h : r ∈ gates fkey φ p) : ∃ q ψ, φ.get q = some ψ ∧ Head fkey ψ (p ++ q) r := by
  induction φ generalizing p with
  | var f => simp [gates] at h
  | and a b iha ihb =>
    simp only [gates, List.mem_cons, List.mem_append] at h
    rcases h with h | h | h
    · exact ⟨[], .and a b, rfl, by simp [Head, h]⟩
    · obtain ⟨q, ψ, hg, hh⟩ := iha _ h
      exact ⟨false :: q, ψ, hg, by simpa using hh⟩
    · obtain ⟨q, ψ, hg, hh⟩ := ihb _ h
      exact ⟨true :: q, ψ, hg, by simpa using hh⟩
  | or a b iha ihb =>
    simp only [gates, List.mem_cons, List.mem_append] at h
    rcases h with h | h | h | h
    · exact ⟨[], .or a b, rfl, by simp [Head, h]⟩
    · exact ⟨[], .or a b, rfl, by simp [Head, h]⟩
    · obtain ⟨q, ψ, hg, hh⟩ := iha _ h
      exact ⟨false :: q, ψ, hg, by simpa using hh⟩
    · obtain ⟨q, ψ, hg, hh⟩ := ihb _ h
      exact ⟨true :: q, ψ, hg, by simpa using hh⟩

/-- The intended truth value of every atom. -/
def val (Rf : RuleSet B) (Kb : B → Prop) (fkey : F → B) (φ : Formula F) : Atom B → Prop
  | .base b => Derivable Rf Kb b
  | .node q => ∃ ψ, φ.get q = some ψ ∧ ψ.evalP (fun f => Derivable Rf Kb (fkey f))
  | .master => φ.evalP (fun f => Derivable Rf Kb (fkey f))

theorem val_keyOf {Rf : RuleSet B} {Kb : B → Prop} {fkey : F → B} {φ ψ : Formula F}
    {q : List Bool} (hg : φ.get q = some ψ) :
    val Rf Kb fkey φ (keyOf fkey ψ q) ↔ ψ.evalP (fun f => Derivable Rf Kb (fkey f)) := by
  cases ψ with
  | var f => exact Iff.rfl
  | and a b =>
    show (∃ ψ', φ.get q = some ψ' ∧ _) ↔ _
    rw [hg]; constructor
    · intro ⟨ψ', e, h⟩; cases e; exact h
    · intro h; exact ⟨_, rfl, h⟩
  | or a b =>
    show (∃ ψ', φ.get q = some ψ' ∧ _) ↔ _
    rw [hg]; constructor
    · intro ⟨ψ', e, h⟩; cases e; exact h
    · intro h; exact ⟨_, rfl, h⟩

theorem lift_derivable {Rf : RuleSet B} {fkey : F → B} {φ : Formula F}
    {K : Atom B → Prop} {b : B} (d : Derivable Rf (fun b => K (.base b)) b) :
    Derivable (scheme Rf fkey φ) K (.base b) := by
  induction d with
  | base h => exact .base h
  | rule r0 hr _ ih =>
    exact Derivable.rule (⟨r0.prem.map Atom.base, Atom.base r0.concl⟩ : Rule (Atom B)) (Or.inl ⟨r0, hr, rfl⟩)
      (fun x hx => by
        obtain ⟨p, hp, rfl⟩ := List.mem_map.mp hx
        exact ih p hp)

theorem gates_complete {Rf : RuleSet B} {fkey : F → B} {φ : Formula F}
    {K : Atom B → Prop} (ψ : Formula F) (q : List Bool)
    (hsub : ∀ r, r ∈ gates fkey ψ q → scheme Rf fkey φ r)
    (h : ψ.evalP (fun f => Derivable Rf (fun b => K (.base b)) (fkey f))) :
    Derivable (scheme Rf fkey φ) K (keyOf fkey ψ q) := by
  induction ψ generalizing q with
  | var f => exact lift_derivable h
  | and a b iha ihb =>
    have da := iha (q ++ [false])
      (fun r hr => hsub r (by simp [gates, hr])) h.1
    have db := ihb (q ++ [true])
      (fun r hr => hsub r (by simp [gates, hr])) h.2
    exact Derivable.rule (kdf2 (keyOf fkey a (q ++ [false])) (keyOf fkey b (q ++ [true])) (.node q))
      (hsub _ (by simp [gates])) (fun p hp => by
      simp [kdf2] at hp
      rcases hp with rfl | rfl
      · exact da
      · exact db)
  | or a b iha ihb =>
    rcases h with h | h
    · have da := iha (q ++ [false])
        (fun r hr => hsub r (by simp [gates, hr])) h
      exact Derivable.rule _ (hsub (wrap (keyOf fkey a (q ++ [false])) (.node q))
        (by simp [gates])) (fun p hp => by
          simp [wrap] at hp; subst hp; exact da)
    · have db := ihb (q ++ [true])
        (fun r hr => hsub r (by simp [gates, hr])) h
      exact Derivable.rule _ (hsub (wrap (keyOf fkey b (q ++ [true])) (.node q))
        (by simp [gates])) (fun p hp => by
          simp [wrap] at hp; subst hp; exact db)

/-- Realisation of monotone formulas.  Let `K` be any start set
    consisting of base secrets only.  In the scheme realising `φ` on top of
    factor rules `Rf`, the master key is derivable from `K` iff `φ` is true
    when factor `f` counts as available exactly when its key `fkey f` is
    derivable from `K` by the factor rules. -/
theorem formula_scheme (Rf : RuleSet B) (fkey : F → B) (φ : Formula F)
    (K : Atom B → Prop) (hK : ∀ a, K a → ∃ b, a = .base b) :
    Derivable (scheme Rf fkey φ) K .master ↔
      φ.evalP (fun f => Derivable Rf (fun b => K (.base b)) (fkey f)) := by
  constructor
  · intro d
    have := derivable_least (X := val Rf (fun b => K (.base b)) fkey φ)
      (fun a ha => by
        obtain ⟨b, rfl⟩ := hK a ha
        exact Derivable.base ha)
      (fun r hr hp => by
        rcases hr with ⟨r0, hr0, rfl⟩ | hr | rfl
        · exact Derivable.rule r0 hr0 (fun p hpm =>
            hp (.base p) (List.mem_map.mpr ⟨p, hpm, rfl⟩))
        · obtain ⟨q, ψ, hg, hh⟩ := mem_gates fkey φ [] r hr
          simp only [List.nil_append] at hh
          cases ψ with
          | var f => exact hh.elim
          | and a b =>
            subst hh
            have ha := (val_keyOf (ψ := a) (q := q ++ [false])
              (by rw [Formula.get_append, hg]; rfl)).mp (hp _ (by simp [kdf2]))
            have hb := (val_keyOf (ψ := b) (q := q ++ [true])
              (by rw [Formula.get_append, hg]; rfl)).mp (hp _ (by simp [kdf2]))
            exact ⟨_, hg, ha, hb⟩
          | or a b =>
            rcases hh with rfl | rfl
            · have ha := (val_keyOf (ψ := a) (q := q ++ [false])
                (by rw [Formula.get_append, hg]; rfl)).mp (hp _ (by simp [wrap]))
              exact ⟨_, hg, Or.inl ha⟩
            · have hb := (val_keyOf (ψ := b) (q := q ++ [true])
                (by rw [Formula.get_append, hg]; rfl)).mp (hp _ (by simp [wrap]))
              exact ⟨_, hg, Or.inr hb⟩
        · exact (val_keyOf (φ := φ) (ψ := φ) (q := []) (by cases φ <;> rfl)).mp (hp _ (by simp [wrap])))
      d
    exact this
  · intro h
    have dr := gates_complete (K := K) (φ := φ) φ [] (fun r hr => Or.inr (Or.inl hr)) h
    exact Derivable.rule (wrap (keyOf fkey φ []) Atom.master) (Or.inr (Or.inr rfl)) (fun p hp => by
      simp [wrap] at hp; subst hp; exact dr)

Take the factors themselves as parties, each holding its own key, with no factor rules. This gives a scheme whose derivability set is exactly the formula. If some single factor already makes the formula true, then that factor alone rebuilds the key. The statement is trivial, but it is the clean form of the lower bound: such a scheme gives no protection against compromise of that factor.

Every monotone formula is a derivability set (realise_dset). In the pure realisation of φ\varphi, a coalition of factors derives MM if and only if φ\varphi is true of the factors it contains.

A sufficient single factor is a single point of failure (single_factor_suffices). If φ\varphi is true when only ff is available, every coalition containing ff derives MM.

/-- The pure factor-level realisation: factors are the parties, factor `f`'s
    holder knows exactly the base atom `f`, and there are no factor rules. -/
def factorHold (f : F) : Atom F → Prop
  | .base g => g = f
  | _ => False

/-- Every monotone formula is a derivability set.  In the pure
    realisation of `φ`, a coalition of factors derives the master key iff `φ`
    is true of the factors it contains. -/
theorem realise_dset (φ : Formula F) (C : Coalition F) :
    DSet (scheme (fun _ => False) id φ) factorHold .master C ↔
      φ.evalP (fun f => C f = true) := by
  unfold DSet
  rw [formula_scheme _ _ _ _ (fun a ⟨p, _, h⟩ => by
    cases a with
    | base b => exact ⟨b, rfl⟩
    | node q => exact h.elim
    | master => exact h.elim)]
  apply Formula.evalP_congr
  intro f
  constructor
  · intro d
    obtain ⟨p, hp, e⟩ := not_concl_base d (fun _ h => h.elim)
    have e' : f = p := e
    subst e'; exact hp
  · intro h; exact .base ⟨f, h, rfl⟩

/-- A single sufficient factor is a single point of failure.
    If `φ` is already true when only factor `f` is available, then every
    coalition containing `f` derives the master key of the realisation. -/
theorem single_factor_suffices (φ : Formula F) (f : F)
    (h : φ.evalP (fun g => g = f)) (C : Coalition F) (hC : C f = true) :
    DSet (scheme (fun _ => False) id φ) factorHold .master C :=
  (realise_dset φ C).mpr (Formula.evalP_mono φ (fun g e => by subst e; exact hC) h)

end Realise

The same correspondence between monotone formulas and access structures underlies the secret-sharing construction of “Generalized secret sharing and monotone functions” (CRYPTO, 1988). There, AND gates split a secret additively and OR gates copy it. Here keys are combined upwards from the factors: AND hashes the child keys together, and OR makes a fresh gate key readable from either child by wrapping it under each.

Two necessity results

Two parties are easy to leave out of the analysis: the party that decides which credential the derivation service accepts as proof of an identity, and the party that supplies the code which runs on the reconstructed key. The first can, by installing one rule, stand in for the holder of the binding atom (in particular for an identity provider whose only secret is that atom) in every coalition that is qualified once given it; the second can, by emitting one ciphertext, make itself a qualified coalition by itself.

Binding atom. The binding atom gg is the atom the derivation service treats as proof of the bound identity, for example an identity-provider session for uu. A policy rule x⊢gx \vdash g says that the service now also accepts credential xx for that identity. Whoever controls the service policy can install such a rule for a credential xx it holds.

Policy installation (policy_install). If an atom aa is derivable from S∪{g}S \cup \lbrace g \rbrace, then after the rule x⊢gx \vdash g is added, aa is derivable from S∪{x}S \cup \lbrace x \rbrace.

Policy necessity (policy_dset). Let party oo hold xx, and suppose oo can install x⊢gx \vdash g. If CC together with gg derives MM, then C∪{o}C \cup \lbrace o \rbrace derives MM in the scheme with the installed rule.

A derived key is no more private than its policy (policy_alone). If gg alone derives MM, the policy controller alone derives MM.

Post-reconstruction code (code_supplier_dset). Code that runs after MM is rebuilt can, in particular, publish MM wrapped under a key kk of its supplier ss. In the scheme with that wrap, every coalition containing ss derives MM.

/-! ## Section 4. General necessity results -/

section Necessity
variable {α : Type}

/-- Installing a policy rule.  Let `g` be the atom the derivation
    service treats as proof of the bound identity.  If `t` is derivable from
    `S` together with `g`, then after a policy rule `x ⊢ g` is installed, `t`
    is derivable from `S` together with `x`. -/
theorem policy_install {R : RuleSet α} {S : α → Prop} {x g t : α}
    (d : Derivable R (fun a => S a ∨ a = g) t) :
    Derivable (fun r => R r ∨ r = kdf x g) (fun a => S a ∨ a = x) t := by
  have d' := mono_R (R' := fun r => R r ∨ r = kdf x g) (fun r h => Or.inl h) d
  refine cut ?_ d'
  intro a ha
  rcases ha with h | rfl
  · exact .base (Or.inl h)
  · exact Derivable.rule (kdf x a) (Or.inr rfl) (fun p hp => by
      simp [kdf] at hp; subst hp; exact .base (Or.inr rfl))

/-- Policy necessity, coalition form.  Let party `o` hold `x`
    and be able to install the policy rule `x ⊢ g`.  Every coalition `C`
    that would derive `M` if it were also given `g` derives `M`, once `o` is
    added, in the scheme with the installed rule. -/
theorem policy_dset {P : Type} [DecidableEq P] {R : RuleSet α}
    {hold : P → α → Prop} {M x g : α} {o : P} (ho : hold o x) (C : Coalition P)
    (d : Derivable R (fun a => Know hold C a ∨ a = g) M) :
    DSet (fun r => R r ∨ r = kdf x g) hold M (fun p => C p || decide (p = o)) := by
  refine mono_S ?_ (policy_install d)
  intro a ha
  rcases ha with ⟨p, hp, h⟩ | rfl
  · exact ⟨p, by simp [hp], h⟩
  · exact ⟨o, by simp, ho⟩

/-- A derived key is no more private than its policy.  If the
    binding atom `g` alone derives `M`, then the party controlling the policy
    derives `M` alone. -/
theorem policy_alone {P : Type} [DecidableEq P] {R : RuleSet α}
    {hold : P → α → Prop} {M x g : α} {o : P} (ho : hold o x)
    (d : Derivable R (fun a => a = g) M) :
    DSet (fun r => R r ∨ r = kdf x g) hold M (fun p => decide (p = o)) := by
  have := policy_dset (R := R) (M := M) (g := g) ho (fun _ => false)
    (mono_S (fun a h => Or.inr h) d)
  simpa using this

/-- Post-reconstruction code.  Code that runs after `M` has been
    reconstructed can publish `M` wrapped under a key `k` of the code's
    supplier.  In the scheme with that wrap, every coalition containing the
    supplier derives `M`. -/
theorem code_supplier_dset {P : Type} {R : RuleSet α} {hold : P → α → Prop}
    {M k : α} {s : P} (hs : hold s k) (C : Coalition P) (hC : C s = true) :
    DSet (fun r => R r ∨ r = wrap k M) hold M C :=
  Derivable.rule (wrap k M) (Or.inr rfl) (fun p hp => by
    simp [wrap] at hp; subst hp; exact .base ⟨s, hC, hs⟩)

end Necessity

Both results are deliberately weak in their hypotheses. They do not ask for anything malicious beyond the stated capability: installing one rule, or emitting one ciphertext. In terms of derivability sets, a policy controller that installs a rule stands in for the holder of the binding atom, and a code supplier whose code emits the wrap is a one-party qualified coalition. Both proofs are immediate (cut, and one rule application). Their content is the modelling step that turns the capability into a rule.

The threshold key-derivation service

The service has nn nodes. Node ii holds a share of a master secret msk\mathsf{msk}, and any tt shares determine it. The service never assembles msk\mathsf{msk}. Instead, each node evaluates its share at an identity uu to get a partial value parti(u)\mathsf{part}_i(u), and any tt partials at uu combine to the identity key out(u)\mathsf{out}(u). A node releases its partial only to a requester authenticated for uu, which is modelled as the rule tok(u)⊢parti(u)\mathsf{tok}(u) \vdash \mathsf{part}_i(u). The partial goes back under the requester’s ephemeral key eph(u)\mathsf{eph}(u), and that ciphertext is public.

Threshold service Thr(n,t)\mathrm{Thr}(n, t). All indices below are under nn.

rulepremisesconclusion
recontt distinct sharesmsk\mathsf{msk}
evalmsk\mathsf{msk}out(u)\mathsf{out}(u)
partialsharei\mathsf{share}_iparti(u)\mathsf{part}_i(u)
releasetok(u)\mathsf{tok}(u)parti(u)\mathsf{part}_i(u)
transporteph(u)\mathsf{eph}(u) (public wrap)parti(u)\mathsf{part}_i(u)
combinett distinct parti(u)\mathsf{part}_i(u)out(u)\mathsf{out}(u)

A start set is clean if it contains no msk\mathsf{msk}, no out\mathsf{out} and no part\mathsf{part} atom: these are computed, never stored. Bign,t(S)\mathrm{Big}_{n,t}(S) says that some tt distinct indices below nn satisfy SS.

/-! ## Section 5. The threshold key-derivation service -/

/-- Base secrets.  `share i`: share of node `i`; `part i u`: partial
    evaluation of node `i` at identity `u`; `out u`: the derived key of
    identity `u`; `msk`: the master secret (never stored); `tok u`: an
    identity-provider session for `u`; `eph u`: the client's ephemeral
    transport secret for `u`; `kD`: the passkey PRF secret; `kR`: the
    recovery code; `opc`, `ksup`: credentials of a policy operator and of a
    code supplier. -/
inductive Sec where
  | share (i : Nat) | part (i u : Nat) | out (u : Nat) | msk
  | tok (u : Nat) | eph (u : Nat) | kD | kR | opc | ksup
  deriving DecidableEq

/-- Some `t` distinct indices below `n` satisfy `S`. -/
def Big (n t : Nat) (S : Nat → Prop) : Prop :=
  ∃ L : List Nat, L.Nodup ∧ L.length = t ∧ ∀ i, i ∈ L → S i ∧ i < n

/-- The threshold service with `n` nodes and threshold `t`.
    recon:     any `t` distinct shares reconstruct `msk`;
    eval:      `msk` gives `out u` for every `u`;
    partial:   node `i` computes `part i u` from its share;
    release:   an authenticated request for `u` obtains `part i u` (the
               requester chooses its own ephemeral key);
    transport: the honest response `part i u` is public, wrapped under `eph u`;
    combine:   any `t` distinct partials at `u` give `out u`. -/
def Thr (n t : Nat) : RuleSet Sec := fun r =>
  (∃ L : List Nat, L.Nodup ∧ L.length = t ∧ (∀ i, i ∈ L → i < n) ∧
      r = ⟨L.map Sec.share, Sec.msk⟩) ∨
  (∃ u, r = kdf Sec.msk (Sec.out u)) ∨
  (∃ i u, i < n ∧ r = kdf (Sec.share i) (Sec.part i u)) ∨
  (∃ i u, i < n ∧ r = kdf (Sec.tok u) (Sec.part i u)) ∨
  (∃ i u, i < n ∧ r = wrap (Sec.eph u) (Sec.part i u)) ∨
  (∃ (L : List Nat) (u : Nat), L.Nodup ∧ L.length = t ∧ (∀ i, i ∈ L → i < n) ∧
      r = ⟨L.map (fun i => Sec.part i u), Sec.out u⟩)

/-- A start set is clean if it contains no master secret, derived key or
    partial evaluation (these are never stored). -/
def Clean (Kb : Sec → Prop) : Prop :=
  ¬ Kb .msk ∧ (∀ u, ¬ Kb (.out u)) ∧ (∀ i u, ¬ Kb (.part i u))

The analysis uses one closed valuation, as in the formula proof. It says exactly when each atom is derivable from a clean start set.

/-- Intended truth values for the threshold service. -/
def tv (n t : Nat) (Kb : Sec → Prop) : Sec → Prop
  | .share i => Kb (.share i)
  | .part i u => i < n ∧ (Kb (.share i) ∨ Kb (.tok u) ∨ Kb (.eph u))
  | .out u => Big n t (fun i => Kb (.share i)) ∨ Kb (.tok u) ∨ Kb (.eph u)
  | .msk => Big n t (fun i => Kb (.share i))
  | .tok u => Kb (.tok u)
  | .eph u => Kb (.eph u)
  | .kD => Kb .kD
  | .kR => Kb .kR
  | .opc => Kb .opc
  | .ksup => Kb .ksup

theorem thr_sound {n t : Nat} {Kb : Sec → Prop} (hc : Clean Kb) {a : Sec}
    (d : Derivable (Thr n t) Kb a) : tv n t Kb a := by
  refine derivable_least ?_ ?_ d
  · intro a ha
    cases a with
    | part i u => exact absurd ha (hc.2.2 i u)
    | out u => exact absurd ha (hc.2.1 u)
    | msk => exact absurd ha hc.1
    | _ => exact ha
  · intro r hr hp
    rcases hr with ⟨L, hn, hl, hlt, rfl⟩ | ⟨u, rfl⟩ | ⟨i, u, hi, rfl⟩ | ⟨i, u, hi, rfl⟩ |
        ⟨i, u, hi, rfl⟩ | ⟨L, u, hn, hl, hlt, rfl⟩
    · exact ⟨L, hn, hl, fun i hi => ⟨hp (.share i) (List.mem_map.mpr ⟨i, hi, rfl⟩), hlt i hi⟩⟩
    · exact Or.inl (hp .msk (by simp [kdf]))
    · exact ⟨hi, Or.inl (hp (.share i) (by simp [kdf]))⟩
    · exact ⟨hi, Or.inr (Or.inl (hp (.tok u) (by simp [kdf])))⟩
    · exact ⟨hi, Or.inr (Or.inr (hp (.eph u) (by simp [wrap])))⟩
    · show Big n t (fun i => Kb (.share i)) ∨ Kb (.tok u) ∨ Kb (.eph u)
      by_cases h : Kb (.tok u) ∨ Kb (.eph u)
      · exact Or.inr h
      · refine Or.inl ⟨L, hn, hl, fun i hi => ?_⟩
        have hpi : tv n t Kb (.part i u) := hp _ (List.mem_map.mpr ⟨i, hi, rfl⟩)
        rcases hpi with ⟨hin, hs | ht | he⟩
        · exact ⟨hs, hin⟩
        · exact absurd (Or.inl ht) h
        · exact absurd (Or.inr he) h

theorem thr_msk_of_big {n t : Nat} {Kb : Sec → Prop}
    (h : Big n t (fun i => Kb (.share i))) : Derivable (Thr n t) Kb .msk := by
  obtain ⟨L, hn, hl, hL⟩ := h
  exact Derivable.rule (⟨L.map Sec.share, Sec.msk⟩ : Rule Sec)
    (Or.inl ⟨L, hn, hl, fun i hi => (hL i hi).2, rfl⟩)
    (fun p hp => by
      obtain ⟨i, hi, rfl⟩ := List.mem_map.mp hp
      exact .base (hL i hi).1)

theorem thr_out_of_parts {n t u : Nat} {Kb : Sec → Prop} (htn : t ≤ n)
    (h : ∀ i, i < n → Derivable (Thr n t) Kb (.part i u)) :
    Derivable (Thr n t) Kb (.out u) := by
  refine Derivable.rule (⟨(List.range t).map (fun i => Sec.part i u), Sec.out u⟩ : Rule Sec)
    (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr ⟨List.range t, u, List.nodup_range t,
      List.length_range t, fun i hi => Nat.lt_of_lt_of_le (List.mem_range.mp hi) htn,
      rfl⟩))))) ?_
  intro p hp
  obtain ⟨i, hi, rfl⟩ := List.mem_map.mp hp
  exact h i (Nat.lt_of_lt_of_le (List.mem_range.mp hi) htn)

Master secret (thr_msk). From a clean start set KK, msk\mathsf{msk} is derivable if and only if KK contains tt distinct shares. Identity sessions and ephemerals never yield it.

Identity key (thr_out). If t≤nt \le n, then from a clean KK, out(u)\mathsf{out}(u) is derivable if and only if KK contains tt distinct shares, or tok(u)\mathsf{tok}(u), or eph(u)\mathsf{eph}(u).

/-- Master secret.  From a clean start set, `msk` is derivable
    iff the start set contains `t` distinct shares of nodes below `n`.
    Identity sessions and ephemeral keys never yield `msk`. -/
theorem thr_msk {n t : Nat} {Kb : Sec → Prop} (hc : Clean Kb) :
    Derivable (Thr n t) Kb .msk ↔ Big n t (fun i => Kb (.share i)) :=
  ⟨fun d => thr_sound hc d, thr_msk_of_big⟩

/-- Derived key.  With `t ≤ n`, from a clean start set the
    derived key of identity `u` is derivable iff the start set contains `t`
    distinct shares, or an identity session for `u`, or the transport
    ephemeral for `u`. -/
theorem thr_out {n t : Nat} {Kb : Sec → Prop} (hc : Clean Kb) (htn : t ≤ n) (u : Nat) :
    Derivable (Thr n t) Kb (.out u) ↔
      Big n t (fun i => Kb (.share i)) ∨ Kb (.tok u) ∨ Kb (.eph u) := by
  constructor
  · intro d; exact thr_sound hc d
  · intro h
    rcases h with hb | ht | he
    · exact Derivable.rule (kdf Sec.msk (Sec.out u)) (Or.inr (Or.inl ⟨u, rfl⟩))
        (fun p hp => by simp [kdf] at hp; subst hp; exact thr_msk_of_big hb)
    · exact thr_out_of_parts htn (fun i hi =>
        Derivable.rule (kdf (Sec.tok u) (Sec.part i u))
          (Or.inr (Or.inr (Or.inr (Or.inl ⟨i, u, hi, rfl⟩))))
          (fun p hp => by simp [kdf] at hp; subst hp; exact .base ht))
    · exact thr_out_of_parts htn (fun i hi =>
        Derivable.rule (wrap (Sec.eph u) (Sec.part i u))
          (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl ⟨i, u, hi, rfl⟩)))))
          (fun p hp => by simp [wrap] at hp; subst hp; exact .base he))

The bound for t−1t - 1 shares is a counting argument. A duplicate-free list inside a list of length less than tt has length less than tt.

tt shares suffice (thr_t_shares). Any tt distinct shares with indices below nn derive msk\mathsf{msk}.

t−1t - 1 shares do not (thr_below_threshold). Let KK be clean and t≤nt \le n, and suppose the shares in KK lie among fewer than tt indices. Then msk\mathsf{msk} is not derivable, and out(u)\mathsf{out}(u) is derivable if and only if KK contains tok(u)\mathsf{tok}(u) or eph(u)\mathsf{eph}(u).

Identity binding (thr_identity_binding). Assume 1≤t≤n1 \le t \le n. The start set {tok(u)}\lbrace \mathsf{tok}(u) \rbrace derives out(u′)\mathsf{out}(u') if and only if u′=uu' = u, and it never derives msk\mathsf{msk}.

Transport confidentiality (thr_observer). Assume t≤nt \le n. An observer who sees every public ciphertext, and holds the sessions tok(u′)\mathsf{tok}(u') and ephemerals eph(u′)\mathsf{eph}(u') of every identity u′≠uu' \ne u, the device secret kDk_D, and the shares of fewer than tt nodes, does not derive out(u)\mathsf{out}(u).

/-- A duplicate-free list inside `Ls` is no longer than `Ls`. -/
theorem nodup_len_le : ∀ (L Ls : List Nat), L.Nodup → (∀ x, x ∈ L → x ∈ Ls) →
    L.length ≤ Ls.length
  | [], _, _, _ => Nat.zero_le _
  | a :: L, Ls, hn, hs => by
    have ha : a ∈ Ls := hs a (List.mem_cons_self _ _)
    rw [List.nodup_cons] at hn
    have h1 := nodup_len_le L (Ls.erase a) hn.2 (fun x hx =>
      (List.mem_erase_of_ne (fun e => hn.1 (by subst e; exact hx))).mpr (hs x (List.mem_cons_of_mem _ hx)))
    rw [List.length_erase_of_mem ha] at h1
    have : 0 < Ls.length := List.length_pos_of_mem ha
    simp only [List.length_cons]
    omega

/-- Fewer than `t` candidate indices cannot contain `t` distinct ones. -/
theorem not_big {n t : Nat} {S : Nat → Prop} (Ls : List Nat)
    (hS : ∀ i, S i → i < n → i ∈ Ls) (hlt : Ls.length < t) : ¬ Big n t S := by
  intro ⟨L, hn, hl, hL⟩
  have := nodup_len_le L Ls hn (fun x hx => hS x (hL x hx).1 (hL x hx).2)
  omega

theorem big_congr {n t : Nat} {S T : Nat → Prop} (h : ∀ i, S i ↔ T i) :
    Big n t S ↔ Big n t T :=
  ⟨fun ⟨L, a, b, c⟩ => ⟨L, a, b, fun i hi => ⟨(h i).mp (c i hi).1, (c i hi).2⟩⟩,
   fun ⟨L, a, b, c⟩ => ⟨L, a, b, fun i hi => ⟨(h i).mpr (c i hi).1, (c i hi).2⟩⟩⟩

/-- `t` shares suffice.  Any `t` distinct shares of nodes below
    `n` derive the master secret. -/
theorem thr_t_shares (n t : Nat) (L : List Nat) (hn : L.Nodup) (hl : L.length = t)
    (hlt : ∀ i, i ∈ L → i < n) :
    Derivable (Thr n t) (fun a => ∃ i, i ∈ L ∧ a = .share i) .msk :=
  thr_msk_of_big ⟨L, hn, hl, fun i hi => ⟨⟨i, hi, rfl⟩, hlt i hi⟩⟩

/-- `t − 1` shares do not.  If the shares in a clean start set
    are among fewer than `t` indices, then `msk` is not derivable, and the
    derived key of `u` is derivable only via an identity session for `u` or
    the ephemeral for `u`. -/
theorem thr_below_threshold {n t : Nat} {Kb : Sec → Prop} (hc : Clean Kb) (htn : t ≤ n)
    (Ls : List Nat) (hS : ∀ i, Kb (.share i) → i ∈ Ls) (hlt : Ls.length < t) (u : Nat) :
    ¬ Derivable (Thr n t) Kb .msk ∧
    (Derivable (Thr n t) Kb (.out u) ↔ Kb (.tok u) ∨ Kb (.eph u)) := by
  have nb := not_big (n := n) Ls (fun i h _ => hS i h) hlt
  refine ⟨fun d => nb ((thr_msk hc).mp d), ?_⟩
  rw [thr_out hc htn]
  constructor
  · intro h; rcases h with h | h
    · exact absurd h nb
    · exact h
  · exact Or.inr

/-- Identity binding.  With `1 ≤ t ≤ n`, an identity session for
    `u` alone derives the key of `u` and of no other identity, and never the
    master secret. -/
theorem thr_identity_binding {n t : Nat} (h1 : 1 ≤ t) (htn : t ≤ n) (u u' : Nat) :
    (Derivable (Thr n t) (fun a => a = .tok u) (.out u') ↔ u' = u) ∧
    ¬ Derivable (Thr n t) (fun a => a = .tok u) .msk := by
  have hc : Clean (fun a => a = .tok u) := ⟨nofun, fun _ => nofun, fun _ _ => nofun⟩
  have below := thr_below_threshold hc htn [] (fun i h => nomatch h) (by simp; omega) u'
  refine ⟨?_, below.1⟩
  rw [below.2]
  constructor
  · intro h; rcases h with h | h
    · cases h; rfl
    · cases h
  · intro h; subst h; exact Or.inl rfl

/-- Transport confidentiality.  With `t ≤ n`, an observer who sees every
    public ciphertext and holds the sessions and ephemerals of every identity
    other than `u`, the device secret `kD`, and the shares
    of fewer than `t` nodes, still does not derive the key of `u`. -/
theorem thr_observer {n t u : Nat} (htn : t ≤ n) (Ls : List Nat) (hlt : Ls.length < t) :
    ¬ Derivable (Thr n t)
      (fun a => (∃ u', u' ≠ u ∧ (a = .tok u' ∨ a = .eph u')) ∨
        (∃ i, i ∈ Ls ∧ a = .share i) ∨ a = .kD) (.out u) := by
  have hc : Clean (fun a => (∃ u', u' ≠ u ∧ (a = .tok u' ∨ a = .eph u')) ∨
      (∃ i, i ∈ Ls ∧ a = .share i) ∨ a = .kD) :=
    ⟨by simp, fun _ => by simp, fun _ _ => by simp⟩
  have below := thr_below_threshold hc htn Ls (fun i h => by simp_all) hlt u
  intro d
  rcases below.2.mp d with h | h <;> simp at h

A concrete check with n=5n = 5 and t=3t = 3. Shares 0,2,40, 2, 4 rebuild the master secret. Shares 00 and 44 do not, and they do not give the key of identity 77 either:

example : Derivable (Thr 5 3) (fun a => ∃ i, i ∈ [0, 2, 4] ∧ a = .share i) .msk :=
  thr_t_shares 5 3 [0, 2, 4] (by decide) rfl (by decide)

example : ¬ Derivable (Thr 5 3) (fun a => a = .share 0 ∨ a = .share 4) .msk ∧
    ¬ Derivable (Thr 5 3) (fun a => a = .share 0 ∨ a = .share 4) (.out 7) := by
  have hc : Clean (fun a => a = .share 0 ∨ a = .share 4) :=
    ⟨by simp, fun _ => by simp, fun _ _ => by simp⟩
  have h := thr_below_threshold (n := 5) (t := 3) hc (by decide) [0, 4]
    (fun i h => by rcases h with h | h <;> cases h <;> simp) (by decide) 7
  exact ⟨h.1, fun d => by rcases h.2.mp d with h | h <;> simp at h⟩

The identity-key theorem also says what the service does not protect. Its derivability set for out(u)\mathsf{out}(u) is “the identity provider for uu, or any tt nodes, or whoever holds the ephemeral eph(u)\mathsf{eph}(u)”. The identity factor is therefore exactly as private as the identity provider. The ephemeral transport key is as sensitive as the output it carries, so it has to be generated per request and erased with the key.

A two-of-three construction

The three factors are:

  • II, the identity factor: the threshold service output out(u0)\mathsf{out}(u_0) for the user’s identity u0u_0.
  • DD, the device factor: the passkey PRF secret kDk_D.
  • RR, the recovery factor: the recovery code kRk_R. (In this section RR names the recovery factor, not a rule set.)

The master key is realised by the formula

(I∧D)  ∨  (I∧R)  ∨  (D∧R).(I \wedge D) \;\vee\; (I \wedge R) \;\vee\; (D \wedge R).
/-! ## Section 6. A two-of-three wallet -/

/-- Factors: identity (the threshold service output for the user's
    identity), device (passkey PRF secret), recovery code. -/
inductive Fac where
  | I | D | R
  deriving DecidableEq

/-- `(I ∧ D) ∨ (I ∧ R) ∨ (D ∧ R)`. -/
def twoOfThree : Formula Fac :=
  .or (.and (.var .I) (.var .D)) (.or (.and (.var .I) (.var .R)) (.and (.var .D) (.var .R)))

/-- No single factor suffices for the two-of-three formula. -/
theorem twoOfThree_no_single (f : Fac) : ¬ twoOfThree.evalP (fun g => g = f) := by
  cases f <;> simp [twoOfThree, Formula.evalP]

/-- Every pair of distinct factors suffices. -/
theorem twoOfThree_pairs (f g : Fac) (h : f ≠ g) :
    twoOfThree.evalP (fun x => x = f ∨ x = g) := by
  cases f <;> cases g <;> simp_all [twoOfThree, Formula.evalP]

The parties, other than the reconstructing client, hold the following:

partyholds
identity providertok(u0)\mathsf{tok}(u_0)
node iisharei\mathsf{share}_i
devicekDk_D
recovery holderkRk_R
key-store servicenothing (it keeps the public ciphertexts)
policy operatorits credential opc\mathsf{opc}
code supplierits key ksup\mathsf{ksup}

The wallet scheme is the formula scheme for this formula, with Thr(n,t)\mathrm{Thr}(n, t) as the factor-level rules.

/-- Parties.  `store` keeps the wrapped ciphertexts (all public in the
    model) and holds no secret. -/
inductive Party where
  | idp | node (i : Nat) | device | recovery | store | operator | supplier
  deriving DecidableEq

/-- Base secrets held by each party, for the user's identity `u0`. -/
def holdsB (u0 : Nat) : Party → Sec → Prop
  | .idp, b => b = .tok u0
  | .node i, b => b = .share i
  | .device, b => b = .kD
  | .recovery, b => b = .kR
  | .store, _ => False
  | .operator, b => b = .opc
  | .supplier, b => b = .ksup

def walletHold (u0 : Nat) (p : Party) : Atom Sec → Prop
  | .base b => holdsB u0 p b
  | _ => False

def walletKey (u0 : Nat) : Fac → Sec
  | .I => .out u0
  | .D => .kD
  | .R => .kR

/-- The wallet: the threshold service as factor rules, and the two-of-three
    formula realised on top of it. -/
def walletR (n t u0 : Nat) : RuleSet (Atom Sec) :=
  scheme (Thr n t) (walletKey u0) twoOfThree

/-- Which factors a coalition holds. -/
def walletσ (n t : Nat) (C : Coalition Party) : Fac → Prop
  | .I => Big n t (fun i => C (.node i) = true) ∨ C .idp = true
  | .D => C .device = true
  | .R => C .recovery = true

theorem thr_concl {n t : Nat} {r : Rule Sec} (h : Thr n t r) :
    r.concl = .msk ∨ (∃ u, r.concl = .out u) ∨ (∃ i u, r.concl = .part i u) := by
  rcases h with ⟨_, _, _, _, rfl⟩ | ⟨u, rfl⟩ | ⟨i, u, _, rfl⟩ | ⟨i, u, _, rfl⟩ |
      ⟨i, u, _, rfl⟩ | ⟨_, u, _, _, _, rfl⟩
  · exact Or.inl rfl
  · exact Or.inr (Or.inl ⟨u, rfl⟩)
  · exact Or.inr (Or.inr ⟨i, u, rfl⟩)
  · exact Or.inr (Or.inr ⟨i, u, rfl⟩)
  · exact Or.inr (Or.inr ⟨i, u, rfl⟩)
  · exact Or.inr (Or.inl ⟨u, rfl⟩)

theorem thr_leaf {n t : Nat} {Kb : Sec → Prop} {x : Sec}
    (hx : x ≠ .msk ∧ (∀ u, x ≠ .out u) ∧ (∀ i u, x ≠ .part i u)) :
    Derivable (Thr n t) Kb x ↔ Kb x := by
  constructor
  · intro d
    apply not_concl_base d
    intro r hr e
    rcases thr_concl hr with h | ⟨u, h⟩ | ⟨i, u, h⟩
    · exact hx.1 (e ▸ h)
    · exact hx.2.1 u (e ▸ h)
    · exact hx.2.2 i u (e ▸ h)
  · exact .base

Derivability set of the wallet (wallet_dset). Assume t≤nt \le n. A coalition derives the master key if and only if it holds two of the three factors. It holds DD if and only if it contains the device, and RR if and only if it contains the recovery holder. It holds II if and only if it contains the identity provider or tt distinct nodes below nn.

Proof. This is the formula theorem, with each factor’s availability computed by the threshold service theorem. No party holds an ephemeral, so that case is empty. kDk_D and kRk_R are concluded by no rule of the service, so they are available exactly when held. ∎

/-- Derivability set of the wallet.  With `t ≤ n`, a coalition
    derives the master key iff it holds two of the three factors, where it
    holds the identity factor iff it contains the identity provider or `t`
    distinct nodes below `n`. -/
theorem wallet_dset {n t : Nat} (htn : t ≤ n) (u0 : Nat) (C : Coalition Party) :
    DSet (walletR n t u0) (walletHold u0) .master C ↔ twoOfThree.evalP (walletσ n t C) := by
  unfold DSet walletR
  rw [formula_scheme _ _ _ _ (fun a ⟨p, _, h⟩ => by
    cases a with
    | base b => exact ⟨b, rfl⟩
    | node q => exact h.elim
    | master => exact h.elim)]
  have hc : Clean (fun b => Know (walletHold u0) C (.base b)) := by
    refine ⟨?_, ?_, ?_⟩
    · intro ⟨p, _, h⟩; cases p <;> simp [walletHold, holdsB] at h
    · intro u ⟨p, _, h⟩; cases p <;> simp [walletHold, holdsB] at h
    · intro i u ⟨p, _, h⟩; cases p <;> simp [walletHold, holdsB] at h
  apply Formula.evalP_congr
  intro f
  cases f with
  | I =>
    show Derivable _ _ (Sec.out u0) ↔ _
    rw [thr_out hc htn]
    have hs : ∀ i, Know (walletHold u0) C (.base (.share i)) ↔ C (.node i) = true := by
      intro i; constructor
      · intro ⟨p, hp, h⟩; cases p <;> simp_all [walletHold, holdsB]
      · intro h; exact ⟨.node i, h, rfl⟩
    have ht : Know (walletHold u0) C (.base (.tok u0)) ↔ C .idp = true := by
      constructor
      · intro ⟨p, hp, h⟩; cases p <;> simp_all [walletHold, holdsB]
      · intro h; exact ⟨.idp, h, rfl⟩
    have he : ¬ Know (walletHold u0) C (.base (.eph u0)) := by
      intro ⟨p, _, h⟩; cases p <;> simp [walletHold, holdsB] at h
    rw [big_congr hs, ht]
    show _ ↔ Big n t (fun i => C (.node i) = true) ∨ C .idp = true
    constructor
    · intro h; rcases h with h | h | h
      · exact Or.inl h
      · exact Or.inr h
      · exact absurd h he
    · intro h; rcases h with h | h
      · exact Or.inl h
      · exact Or.inr (Or.inl h)
  | D =>
    show Derivable _ _ Sec.kD ↔ C .device = true
    rw [thr_leaf (x := Sec.kD) ⟨by simp, fun _ => by simp, fun _ _ => by simp⟩]
    constructor
    · intro ⟨p, hp, h⟩; cases p <;> simp_all [walletHold, holdsB]
    · intro h; exact ⟨.device, h, rfl⟩
  | R =>
    show Derivable _ _ Sec.kR ↔ C .recovery = true
    rw [thr_leaf (x := Sec.kR) ⟨by simp, fun _ => by simp, fun _ _ => by simp⟩]
    constructor
    · intro ⟨p, hp, h⟩; cases p <;> simp_all [walletHold, holdsB]
    · intro h; exact ⟨.recovery, h, rfl⟩

Below threshold (wallet_below). Assume t≤nt \le n. If a coalition’s nodes lie among fewer than tt indices, and it contains at most one of the identity provider, the device and the recovery holder, then it does not derive the master key.

No single party (wallet_no_single). Assume 1≤t≤n1 \le t \le n. No single party derives the master key. This covers the identity provider, every node, the device, the recovery holder, the key-store service, the policy operator and the code supplier. The reconstructing client is not among the parties; see the scope section below.

Every pair (wallet_pairs). Assume t≤nt \le n. Each of the pairs (identity provider, device), (identity provider, recovery holder) and (device, recovery holder) derives the master key. So does the device together with nodes 0,…,t−10, \dots, t-1.

Policy operator (wallet_operator). Assume 1≤t≤n1 \le t \le n. In the scheme as given, the policy operator together with the device does not derive the master key. Once the operator installs the policy rule opc⊢tok(u0)\mathsf{opc} \vdash \mathsf{tok}(u_0), the two of them do.

Code supplier (wallet_supplier). Assume 1≤t≤n1 \le t \le n. In the scheme as given, the code supplier alone does not derive the master key. If the code that runs after reconstruction publishes the key wrapped under ksup\mathsf{ksup}, the supplier alone does.

The hypothesis 1≤t1 \le t is needed (wallet_t0_device). With t=0t = 0 the empty set of nodes is already a quorum, every coalition holds the identity factor, and the device alone derives the key. With t=1t = 1 a single node holds the identity factor, but that is still only one factor. The operator result is the policy-necessity theorem in this instance: in the derivability set, the policy operator counts as an identity provider.

/-- The coalition consisting of one party. -/
def single (p : Party) : Coalition Party := fun q => decide (q = p)

/-- The coalition consisting of two parties. -/
def pair (p p' : Party) : Coalition Party := fun q => decide (q = p) || decide (q = p')

/-- Fewer than t nodes and at most one personal factor.  With
    `t ≤ n`: if the nodes of a coalition are among fewer than `t` indices and
    it contains at most one of identity provider, device and recovery holder,
    it does not derive the master key. -/
theorem wallet_below {n t : Nat} (htn : t ≤ n) (u0 : Nat) (C : Coalition Party)
    (Ls : List Nat) (hS : ∀ i, C (.node i) = true → i ∈ Ls) (hlt : Ls.length < t)
    (h1 : (C .idp && C .device) = false) (h2 : (C .idp && C .recovery) = false)
    (h3 : (C .device && C .recovery) = false) :
    ¬ DSet (walletR n t u0) (walletHold u0) .master C := by
  rw [wallet_dset htn]
  have nb := not_big (n := n) Ls (fun i h _ => hS i h) hlt
  simp only [twoOfThree, Formula.evalP, walletσ]
  intro h
  rcases h with ⟨hI | hI, hD⟩ | ⟨hI | hI, hR⟩ | ⟨hD, hR⟩
  · exact nb hI
  · simp [hI, hD] at h1
  · exact nb hI
  · simp [hI, hR] at h2
  · simp [hD, hR] at h3

/-- No single party.  With `1 ≤ t ≤ n`, no single party (identity
    provider, any node, device, recovery holder, store, policy operator, code
    supplier) derives the master key of the honest wallet. -/
theorem wallet_no_single {n t : Nat} (h1 : 1 ≤ t) (htn : t ≤ n) (u0 : Nat) (p : Party) :
    ¬ DSet (walletR n t u0) (walletHold u0) .master (single p) := by
  rw [wallet_dset htn]
  cases p <;> simp [twoOfThree, Formula.evalP, walletσ, single]
  all_goals (intro h; first
    | exact not_big (n := n) [] (fun i h _ => by simp at h) (by simp; omega) h
    | skip)

/-- The bound `1 ≤ t` is needed: with `t = 0` the empty set of nodes is a
    quorum, every coalition holds the identity factor, and the device alone
    derives the master key. -/
theorem wallet_t0_device (n u0 : Nat) :
    DSet (walletR n 0 u0) (walletHold u0) .master (single .device) := by
  rw [wallet_dset (Nat.zero_le n)]
  simp only [twoOfThree, Formula.evalP, walletσ]
  exact Or.inl ⟨Or.inl ⟨[], List.nodup_nil, rfl, fun i h => by simp at h⟩, by simp [single]⟩

/-- Every pair of factors.  With `t ≤ n`, each of the coalitions
    {identity provider, device}, {identity provider, recovery holder},
    {device, recovery holder} derives the master key; so does any coalition
    of the device with `t` distinct nodes below `n`. -/
theorem wallet_pairs {n t : Nat} (htn : t ≤ n) (u0 : Nat) :
    DSet (walletR n t u0) (walletHold u0) .master (pair .idp .device) ∧
    DSet (walletR n t u0) (walletHold u0) .master (pair .idp .recovery) ∧
    DSet (walletR n t u0) (walletHold u0) .master (pair .device .recovery) ∧
    DSet (walletR n t u0) (walletHold u0) .master
      (fun q => match q with | .node i => decide (i < t) | .device => true | _ => false) := by
  refine ⟨?_, ?_, ?_, ?_⟩ <;> rw [wallet_dset htn] <;>
    simp only [twoOfThree, Formula.evalP, walletσ]
  · exact Or.inl ⟨Or.inr (by simp [pair]), by simp [pair]⟩
  · exact Or.inr (Or.inl ⟨Or.inr (by simp [pair]), by simp [pair]⟩)
  · exact Or.inr (Or.inr ⟨by simp [pair], by simp [pair]⟩)
  · refine Or.inl ⟨Or.inl ⟨List.range t, List.nodup_range t, List.length_range t,
      fun i hi => ⟨by simpa using hi, Nat.lt_of_lt_of_le (List.mem_range.mp hi) htn⟩⟩, trivial⟩

/-- Policy operator, instance.  With `1 ≤ t ≤ n`: in the honest
    wallet the coalition {policy operator, device} does not derive the master
    key; once the operator installs the policy rule binding identity `u0` to
    its own credential (`opc ⊢ tok u0`), that coalition does. -/
theorem wallet_operator {n t : Nat} (h1 : 1 ≤ t) (htn : t ≤ n) (u0 : Nat) :
    ¬ DSet (walletR n t u0) (walletHold u0) .master (pair .operator .device) ∧
    DSet (fun r => walletR n t u0 r ∨ r = kdf (Atom.base Sec.opc) (Atom.base (Sec.tok u0)))
      (walletHold u0) .master (pair .operator .device) := by
  constructor
  · apply wallet_below htn u0 _ [] (fun i h => by simp [pair] at h) (by simp; omega) <;>
      simp [pair]
  · have hd : Derivable (walletR n t u0)
        (fun a => Know (walletHold u0) (single .device) a ∨ a = .base (.tok u0)) .master := by
      refine mono_S ?_ ((wallet_pairs htn u0).1)
      intro a ⟨p, hp, h⟩
      simp [pair] at hp
      rcases hp with rfl | rfl
      · cases a with
        | base b => exact Or.inr (by simp [walletHold, holdsB] at h; rw [h])
        | node q => exact h.elim
        | master => exact h.elim
      · exact Or.inl ⟨.device, by simp [single], h⟩
    have := policy_dset (o := Party.operator) (x := Atom.base Sec.opc)
      (hold := walletHold u0) rfl (single .device) hd
    refine mono_S ?_ this
    intro a ⟨p, hp, h⟩
    refine ⟨p, ?_, h⟩
    cases p <;> simp_all [single, pair]

/-- Code supplier, instance.  With `1 ≤ t ≤ n`: in the honest
    wallet the code supplier alone does not derive the master key; if the
    code running after reconstruction publishes the key wrapped under the
    supplier's key, the supplier alone does. -/
theorem wallet_supplier {n t : Nat} (h1 : 1 ≤ t) (htn : t ≤ n) (u0 : Nat) :
    ¬ DSet (walletR n t u0) (walletHold u0) .master (single .supplier) ∧
    DSet (fun r => walletR n t u0 r ∨ r = wrap (Atom.base Sec.ksup) Atom.master)
      (walletHold u0) .master (single .supplier) :=
  ⟨wallet_no_single h1 htn u0 .supplier,
   code_supplier_dset (s := Party.supplier) (k := Atom.base Sec.ksup) rfl _ (by simp [single])⟩

Instances with five nodes and threshold three:

example : ¬ DSet (walletR 5 3 0) (walletHold 0) .master (single .idp) :=
  wallet_no_single (by decide) (by decide) 0 .idp

example : ¬ DSet (walletR 5 3 0) (walletHold 0) .master (single (.node 2)) :=
  wallet_no_single (by decide) (by decide) 0 (.node 2)

example : DSet (walletR 5 3 0) (walletHold 0) .master (pair .device .recovery) :=
  (wallet_pairs (by decide) 0).2.2.1

Pairing-equation verification

The client checks each response against the service public key before it uses the response. With a bilinear map ee, a hash HH to the first group, a generator gg of the second group (unrelated to the binding atom above), and public key pk=gk\mathsf{pk} = g^{k}, the check on a response σ\sigma for identity uu is

e(σ,g)=?e(H(u),pk).e(\sigma, g) \overset{?}{=} e(H(u), \mathsf{pk}).

This is the verification equation of “Short signatures from the Weil pairing” (ASIACRYPT, 2001). Its threshold form, with tt partials combined by interpolation in the exponent, is the subject of “Threshold signatures, multisignatures and blind signatures based on the Gap-Diffie-Hellman-group signature scheme” (PKC, 2003).

Term group model. Elements of the first group are terms H(u)kH(u)^k and elements of the target group are e(H(u),g)ke(H(u), g)^k, each indexed by an identity and a natural-number exponent. Elements of the second group are gkg^k, indexed by the exponent alone. Two elements are equal exactly when their indices are equal (exponents are not reduced modulo the group order), and the pairing multiplies exponents: e(H(u)k,gk′)=e(H(u),g)kk′e(H(u)^k, g^{k'}) = e(H(u), g)^{k k'}. In particular HH is injective.

Correctness and binding (verify_iff). In the term model, against pk=gk\mathsf{pk} = g^k the check accepts σ\sigma if and only if σ=H(u)k\sigma = H(u)^k.

Verification adds no derivation edges (public_inert, public_inert_dset). Model the check as rules that conclude only fresh output atoms (outcome bits), which no rule uses as a premise. Adding such rules to any scheme, from any start set, leaves derivability of every non-output atom unchanged, so every derivability set of every non-output atom is unchanged.

Verification and derivability side by side (verify_not_confidential). This collects three earlier results for one identity. Assume 1≤t≤n1 \le t \le n, and interpret the atom out(u)\mathsf{out}(u) as the group element H(u)kH(u)^k. Then (a) a group element passes the check for uu against gkg^k if and only if it is the interpretation of out(u)\mathsf{out}(u); (b) out(u)\mathsf{out}(u) is derivable from {tok(u)}\lbrace \mathsf{tok}(u) \rbrace alone; (c) it is not derivable by an observer who holds the sessions and ephemerals of every other identity, kDk_D, and the shares of nodes 0,…,t−20, \dots, t-2.

The formal link between the check and derivability is public_inert: the check adds no derivation edges, so the derivability set of out(u)\mathsf{out}(u), which contains every coalition holding tok(u)\mathsf{tok}(u), is the same whether or not the client checks.

/-! ## Section 7. Pairing-equation verification -/

/-- Term model of a bilinear group with an injective hash to the first
    group: `hpow u k` is `H(u)^k`, `gpow k` is `g^k`, and `gt u k` is
    `e(H(u), g)^k`. -/
inductive G1 where
  | hpow (u k : Nat)
  deriving DecidableEq

inductive G2 where
  | gpow (k : Nat)
  deriving DecidableEq

inductive GT where
  | gt (u k : Nat)
  deriving DecidableEq

/-- The pairing `e(H(u)^k, g^k') = e(H(u), g)^(k·k')`. -/
def pairing : G1 → G2 → GT
  | .hpow u k, .gpow k' => .gt u (k * k')

/-- The client's check on a response `σ` for identity `u` against the
    service public key `pk`: `e(σ, g) = e(H(u), pk)`. -/
def verify (u : Nat) (pk : G2) (σ : G1) : Bool :=
  decide (pairing σ (.gpow 1) = pairing (.hpow u 1) pk)

/-- Binding.  Against the public key `g^k`, the check accepts
    exactly `H(u)^k`: the response for the client's own identity under the
    service's secret. -/
theorem verify_iff (u k : Nat) (σ : G1) : verify u (.gpow k) σ = true ↔ σ = .hpow u k := by
  cases σ with
  | hpow u' k' => simp [verify, pairing]

/-- Verification adds no derivation edges.  Let `O` be a set of fresh
    output atoms (check outcomes).  If every added rule concludes an output
    atom, and no rule uses an output atom as a premise, then from any start
    set the added rules change nothing derivable outside `O`. -/
theorem public_inert {α : Type} {R R' : RuleSet α} {K O : α → Prop}
    (hc : ∀ r, R' r → O r.concl)
    (hp : ∀ r, (R r ∨ R' r) → ∀ p, p ∈ r.prem → ¬ O p)
    {x : α} (hx : ¬ O x) :
    Derivable (fun r => R r ∨ R' r) K x ↔ Derivable R K x := by
  constructor
  · intro d
    have h : O x ∨ Derivable R K x := by
      refine derivable_least (X := fun a => O a ∨ Derivable R K a)
        (fun a ha => Or.inr (.base ha)) ?_ d
      intro r hr ih
      rcases hr with hr' | hr'
      · exact Or.inr (Derivable.rule r hr' (fun p hm =>
          (ih p hm).resolve_left (hp r (Or.inl hr') p hm)))
      · exact Or.inl (hc r hr')
    exact h.resolve_left hx
  · exact mono_R (fun r h => Or.inl h)

/-- The same, as derivability sets: for every holding map and every
    non-output atom `x`, adding the check rules leaves the derivability set
    of `x` unchanged, coalition by coalition. -/
theorem public_inert_dset {α P : Type} {R R' : RuleSet α} {O : α → Prop}
    (hc : ∀ r, R' r → O r.concl)
    (hp : ∀ r, (R r ∨ R' r) → ∀ p, p ∈ r.prem → ¬ O p)
    (hold : P → α → Prop) {x : α} (hx : ¬ O x) (C : Coalition P) :
    DSet (fun r => R r ∨ R' r) hold x C ↔ DSet R hold x C :=
  public_inert hc hp hx

/-- Interpretation of the symbolic atoms of the service in the group model,
    for a service secret `k`: the identity key `out u` is the group element
    `H(u)^k`.  Other atoms have no group interpretation here. -/
def interp (k : Nat) : Sec → Option G1
  | .out u => some (.hpow u k)
  | _ => none

/-- Verification and derivability side by side (a collection of earlier
    results for one identity).  With `1 ≤ t ≤ n` and service
    secret `k`: a group element passes the client's check for `u` against
    `g^k` iff it is the interpretation of the atom `out u`; that atom is
    derivable from an identity session for `u` alone; and it is not derivable
    by an observer holding everything of the other identities and fewer than
    `t` shares.  The check fixes which value is accepted; who can compute it
    is fixed by the derivability set. -/
theorem verify_not_confidential {n t : Nat} (h1 : 1 ≤ t) (htn : t ≤ n) (u k : Nat) :
    (∀ σ, verify u (.gpow k) σ = true ↔ interp k (.out u) = some σ) ∧
    Derivable (Thr n t) (fun a => a = .tok u) (.out u) ∧
    ¬ Derivable (Thr n t)
      (fun a => (∃ u', u' ≠ u ∧ (a = .tok u' ∨ a = .eph u')) ∨
        (∃ i, i ∈ List.range (t - 1) ∧ a = .share i) ∨ a = .kD) (.out u) := by
  refine ⟨fun σ => ?_, (thr_identity_binding h1 htn u u).1.mpr rfl,
    thr_observer htn (List.range (t - 1)) (by simp; omega)⟩
  rw [verify_iff]
  simp only [interp]
  constructor
  · intro h; rw [h]
  · intro h; cases h; rfl

end Keyless

The binding statement is about the term abstraction. In a real prime-order bilinear group with a non-degenerate pairing, the map σ↦e(σ,g)\sigma \mapsto e(\sigma, g) is injective. So the accepted σ\sigma is unique for each (u,pk)(u, \mathsf{pk}) unconditionally: the client accepts only H(u)kH(u)^k. Three other properties are computational and outside the symbolic model:

  • keys for different identities are separated when HH is collision resistant (the term model simply assumes HH injective);
  • no one can produce H(u)kH(u)^k if the set of nodes whose share they hold, together with the nodes whose partial evaluation at uu they obtain, has fewer than tt distinct members, even given H(u′)kH(u')^k and partials of every node at every other identity u′≠uu' \ne u. This is unforgeability of the threshold short-signature scheme against an adversary that corrupts fewer than tt nodes statically (chosen before the run), under the co-CDH assumption (gap form), with HH modelled as a random oracle; adaptive corruption requires a separate analysis;
  • the key the client derives from σ\sigma through a further KDF is pseudorandom only under an assumption on that KDF.

The symbolic results say something different. The check decides which value the client accepts. Who else can compute that value is fixed entirely by the derivability set. Here that set contains every coalition that includes the identity provider for uu or tt distinct nodes, whatever the check does.

Scope of the model

  • Monotone in time. Derivability only grows, so revoking a share or a session after it has been seen removes nothing from a coalition’s knowledge. Rotation has to be modelled as new atoms and new rules, with the old derivability set still in force for anyone who held the old atoms.
  • All-or-nothing secrets. Atoms are either known or unknown. Partial leakage, guessing a low-entropy recovery code, and the probability of breaking a primitive are outside the model. Each of these needs a computational statement on top of the derivability set computed here.
  • Synchronised passkeys. The device factor is held by every authenticator the passkey credential is synchronised to, and by any service able to restore it. The two-of-three guarantees need either a device-bound credential or those holders to be disjoint from the identity provider and the recovery holder. A party that is both identity provider and such a holder has II and DD on its own.
  • Availability. The model analyses who can derive the key, not who can prevent its derivation. Wrap rules are assumed always present (the key-store service serves its ciphertexts) and the threshold service live. Blocking sets are a separate, dual analysis. Examples: the key-store service alone blocks the master key, since it withholds the wrapped ciphertexts; the identity factor is blocked by the identity provider alone or by any n−t+1n - t + 1 nodes; and, with the ciphertexts available, blocking the master key in the two-of-three construction requires blocking two of the three factors.
  • The reconstructing client. During reconstruction the client holds the factor secrets of the path it uses (two of: tok(u0)\mathsf{tok}(u_0) with eph(u0)\mathsf{eph}(u_0), the partials and out(u0)\mathsf{out}(u_0); kDk_D; kRk_R), the gate keys and MM, so it is not a party of the model. The results assume it is trusted and erases these afterwards. Here “device” means the authenticator that releases kDk_D. If an identity-provider session for u0u_0 persists on the same device, that device holds II and DD on its own.
  • Rules as capabilities. The necessity theorems take the capabilities “install a policy rule” and “emit a ciphertext” as given. Whether a deployment grants them is a property of that deployment, not of the key-derivation scheme.