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:
- 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.
- Combining keys with a KDF realises AND, and wrapping one key under several realises OR, so every monotone formula over factors is realisable.
- 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.
- An exact analysis of the threshold service, and a two-of-three construction built on it.
- 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 says that anyone who knows all the premises can compute the conclusion . For a set of rules and a start set , is the least set that contains and is closed under .
Three kinds of rule are used throughout:
- is , a one-way derivation.
- is , that is .
- is . It stands for a ciphertext of under that anyone may read, so knowing gives .
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 , a holding relation (which atoms each party holds) and a key . A coalition is a set of parties, and it knows the union of its members’ atoms. The derivability set of the scheme is
When and are fixed we write .
A family of coalitions is up-closed (a monotone access structure) if and imply .
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 gives each party one private atom . For each it adds the rule , where the premises are listed in the order of a fixed list of all parties.
Realisation (canon_dset). If is up-closed, the derivability set of its canonical scheme is exactly .
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 derives . The key is held by no party, so the last step is the rule of some . Each premise of that rule is concluded by no rule, so it must be held by , which gives . Up-closure then gives . In the other direction, the rule for 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. , the rule . More generally, an -ary is the single rule with premise list , and its output is derivable exactly when every is (andN_iff below).
OR. Pick fresh and publish wrapped under and under , the rules and .
Both need a freshness side condition. If some other rule also concluded , or a party held , then the derivability set could only grow, and the equations below could fail.
AND (and_iff, dset_and). Suppose , every rule concluding has premises exactly , and is not initially known. Then is derivable if and only if both and are. As derivability sets: .
OR (or_iff, dset_or). Suppose both wraps are in , every rule concluding has premises or , and is not initially known. Then is derivable if and only if or is. As derivability sets: .
/-! ## 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, and . 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 be a monotone formula. Each factor has a key . Each internal position of gets a gate atom . The key carried by position is if the subformula there is the variable , and otherwise. Write and for the left and right children of (the path extended by false or true). The rules are:
- for an -node at , the rule ;
- for an -node at , is wrapped under and under ;
- the master key is wrapped under the root key;
- in addition, any factor-level rules over base secrets, which describe how factor keys themselves are obtained.
Write for the full rule set of the scheme. Base atoms are identified with base secrets, so a start set 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 be any start set that contains only base secrets. Then
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 is true if the subformula at is true. is true if is. This valuation contains 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 . ∎
/-- 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 , a coalition of factors derives if and only if is true of the factors it contains.
A sufficient single factor is a single point of failure (single_factor_suffices). If is true when only is available, every coalition containing derives .
/-- 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 is the atom the derivation service treats as proof of the bound identity, for example an identity-provider session for . A policy rule says that the service now also accepts credential for that identity. Whoever controls the service policy can install such a rule for a credential it holds.
Policy installation (policy_install). If an atom is derivable from , then after the rule is added, is derivable from .
Policy necessity (policy_dset). Let party hold , and suppose can install . If together with derives , then derives in the scheme with the installed rule.
A derived key is no more private than its policy (policy_alone). If alone derives , the policy controller alone derives .
Post-reconstruction code (code_supplier_dset). Code that runs after is rebuilt can, in particular, publish wrapped under a key of its supplier . In the scheme with that wrap, every coalition containing derives .
/-! ## 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 nodes. Node holds a share of a master secret , and any shares determine it. The service never assembles . Instead, each node evaluates its share at an identity to get a partial value , and any partials at combine to the identity key . A node releases its partial only to a requester authenticated for , which is modelled as the rule . The partial goes back under the requester’s ephemeral key , and that ciphertext is public.
Threshold service . All indices below are under .
| rule | premises | conclusion |
|---|---|---|
| recon | distinct shares | |
| eval | ||
| partial | ||
| release | ||
| transport | (public wrap) | |
| combine | distinct |
A start set is clean if it contains no , no and no atom: these are computed, never stored. says that some distinct indices below satisfy .
/-! ## 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 , is derivable if and only if contains distinct shares. Identity sessions and ephemerals never yield it.
Identity key (thr_out). If , then from a clean , is derivable if and only if contains distinct shares, or , or .
/-- 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 shares is a counting argument. A duplicate-free list inside a list of length less than has length less than .
shares suffice (thr_t_shares). Any distinct shares with indices below derive .
shares do not (thr_below_threshold). Let be clean and , and suppose the shares in lie among fewer than indices. Then is not derivable, and is derivable if and only if contains or .
Identity binding (thr_identity_binding). Assume . The start set derives if and only if , and it never derives .
Transport confidentiality (thr_observer). Assume . An observer who sees every public ciphertext, and holds the sessions and ephemerals of every identity , the device secret , and the shares of fewer than nodes, does not derive .
/-- 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 and . Shares rebuild the master secret. Shares and do not, and they do not give the key of identity 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 is “the identity provider for , or any nodes, or whoever holds the ephemeral ”. 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:
- , the identity factor: the threshold service output for the user’s identity .
- , the device factor: the passkey PRF secret .
- , the recovery factor: the recovery code . (In this section names the recovery factor, not a rule set.)
The master key is realised by the formula
/-! ## 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:
| party | holds |
|---|---|
| identity provider | |
| node | |
| device | |
| recovery holder | |
| key-store service | nothing (it keeps the public ciphertexts) |
| policy operator | its credential |
| code supplier | its key |
The wallet scheme is the formula scheme for this formula, with 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 . A coalition derives the master key if and only if it holds two of the three factors. It holds if and only if it contains the device, and if and only if it contains the recovery holder. It holds if and only if it contains the identity provider or distinct nodes below .
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. and 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 . If a coalition’s nodes lie among fewer than 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 . 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 . 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 .
Policy operator (wallet_operator). Assume . 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 , the two of them do.
Code supplier (wallet_supplier). Assume . 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 , the supplier alone does.
The hypothesis is needed (wallet_t0_device). With the empty set of nodes is already a quorum, every coalition holds the identity factor, and the device alone derives the key. With 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 , a hash to the first group, a generator of the second group (unrelated to the binding atom above), and public key , the check on a response for identity is
This is the verification equation of “Short signatures from the Weil pairing” (ASIACRYPT, 2001). Its threshold form, with 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 and elements of the target group are , each indexed by an identity and a natural-number exponent. Elements of the second group are , 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: . In particular is injective.
Correctness and binding (verify_iff). In the term model, against the check accepts if and only if .
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 , and interpret the atom as the group element . Then (a) a group element passes the check for against if and only if it is the interpretation of ; (b) is derivable from alone; (c) it is not derivable by an observer who holds the sessions and ephemerals of every other identity, , and the shares of nodes .
The formal link between the check and derivability is public_inert: the check adds no derivation edges, so the derivability set of , which contains every coalition holding , 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 is injective. So the accepted is unique for each unconditionally: the client accepts only . Three other properties are computational and outside the symbolic model:
- keys for different identities are separated when is collision resistant (the term model simply assumes injective);
- no one can produce if the set of nodes whose share they hold, together with the nodes whose partial evaluation at they obtain, has fewer than distinct members, even given and partials of every node at every other identity . This is unforgeability of the threshold short-signature scheme against an adversary that corrupts fewer than nodes statically (chosen before the run), under the co-CDH assumption (gap form), with modelled as a random oracle; adaptive corruption requires a separate analysis;
- the key the client derives from 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 or 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 and 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 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: with , the partials and ; ; ), the gate keys and , 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 . If an identity-provider session for persists on the same device, that device holds and 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.