A storage node holds records in which some fields are sealed: the node stores a ciphertext and never the plaintext. The node still does work over those records. It evaluates authorization rules, runs queries, decides whether to accept writes, issues receipts, and charges for the work in some unit of gas. Every one of those outputs is a potential channel. A rule that branches on a sealed field leaks a bit through its decision. A query that filters on one leaks through the rows it returns. A meter that counts the bytes of a plaintext leaks its length, and a meter that counts loop iterations leaks whatever the loop bound depended on.
This article states the goal as a non-interference property over everything the node computes or reports, including the usage it charges. It then puts together a design from known parts (a type system, opaque ciphertext values, a metering semantics, typed declassification, a hash chain of receipts and a signed membership log) and proves that the combination meets the goal. Concrete counterexamples show that the typing hypotheses (on rules and on stored values), the declassification policy, the public text of operations and the public lengths cannot be dropped. All statements are checked in Lean 4 with the core library only. The code blocks below concatenate, in reading order, into one file that compiles with Lean 4.16 with no sorry and no declared axioms.
The goal
The node sees each value through a view: a clear value is seen as itself, and a sealed value is seen as its ciphertext handle and its length, without the plaintext. A declassification policy marks fields whose plaintext the node is allowed to use.
Goal (metered non-interference relative to ). Fix a collection whose authorization rule is well-typed. Take two stores and two sequences of operations that are well-typed for the collection’s schema, that have the same shape and the same views everywhere, and that agree on the plaintext of every field marks. Then the node produces, step by step, the same accept/reject decisions, the same result rows, the same usage vectors, the same receipts and the same price under every price function of usage.
With empty, the premise says only that the two states differ in sealed plaintexts and in nothing else. Then every output is the same: what the node reports depends on sealed content only through ciphertext handles and lengths.
Handles are symbolic in the model. A sealed value carries its handle and its plaintext as independent components, so the two worlds of the goal may hold the same handle over different plaintexts. Under one fixed key this is impossible, since decryption is a function of the ciphertext. The two worlds should therefore be read as possibly using different keys, or the handle as a name for a ciphertext rather than its bits. Turning this symbolic statement into a computational one is the subject of “Cryptographically Sound Implementations for Typed Information-Flow Security” (POPL 2008), and it is not attempted here.
Two caveats are part of the statement and not afterthoughts.
- The view is public by definition. The theorem says that outputs are a function of views and declassified plaintexts. That the view in turn reveals nothing about the plaintext is a property of the encryption scheme (indistinguishability under chosen-plaintext attack) and is outside the model. With deterministic encryption, equal plaintexts give equal ciphertexts, so ciphertext identity, which is in the view, reveals plaintext equality.
- Length is in the view. A ciphertext’s length is generally a function of the plaintext’s length. The model treats the length as public and says so. Padding every value of a field to one length is the case in which the length carries no information, and a concrete example below shows that the theorem fails if lengths are left out of the view.
Components
Each part below is known. What this article adds is their combination toward this goal and a machine-checked proof that the result meets it.
- Non-interference as the security property. “Security Policies and Security Models” (IEEE Symposium on Security and Privacy, 1982), in the information-flow setting of “A Lattice Model of Secure Information Flow” (Communications of the ACM, 1976).
- Enforcement by typing. “A Sound Type System for Secure Flow Analysis” (Journal of Computer Security, 1996). Here there are two levels, clear and sealed, and the sealed level is a type of its own rather than a label on other types.
- Ciphertexts as opaque values compared by identity. “Cryptographically-Masked Flows” (SAS 2006; Theoretical Computer Science, 2008) treats encryption inside an information-flow type system, with ciphertexts released as public values and equality on them taken into account.
- Proof by a logical relation. The relation-indexed-by-type method of “Types, Abstraction and Parametric Polymorphism” (IFIP Congress, 1983), used for dependency and secrecy in “A Core Calculus of Dependency” (POPL 1999).
- Cost as an observable. Resource and timing channels in language-based security, as in “Transforming Out Timing Leaks” (POPL 2000) and “Language-Based Control and Mitigation of Timing Channels” (PLDI 2012). Here the observable is not physical time but the charged usage vector.
- Declassification as an explicit, typed operation. “A Model for Delimited Information Release” (ISSS 2003) and the survey “Declassification: Dimensions and Principles” (Journal of Computer Security, 2009). The policy here says what may be released, field by field.
- Receipts as a hash chain. “How to Time-Stamp a Digital Document” (Journal of Cryptology, 1991). The binding proof computes a collision from the two chains, as in the iterated-hash argument of “A Design Principle for Hash Functions” (CRYPTO 1989).
- Unforgeability as an extracted forgery. Existential unforgeability under chosen-message attack, from “A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks” (SIAM Journal on Computing, 1988).
Architecture
A collection fixes a schema (the type of each field), a policy , a width, an authorization rule allow, and a gate. The rule is an expression of the language and sees the request record and one stored record. The gate sees the wire form of a write, that is, the views of the request and of the new record. It may, for instance, verify a signature over the ciphertexts. The theorems below allow any gate that is a function of views, and they say nothing about what a gate guarantees. The node runs three operations.
- query evaluates
allowand a predicate on every stored record and returns the views of the chosen fields of the records on which both hold. - insert accepts a record iff the gate passes and
allowholds, and charges for the rule and for the bytes written. - delete removes the records on which
allowand the predicate hold and returns their views.
Each operation produces an output: a decision bit, a list of rows (lists of views), and a usage vector of steps and bytes. Receipts are a hash chain over outputs, and gas is any function of the usage vector.
- typed ruleallow, predicate
eval sz ρ e : Val × Usage - gatewire form of a write
List View → List View → Bool - outputdecision, rows, usage
Out - receipt, gashash chain, price
H rc o, price o.usage
Three design choices carry the proof.
Sealedis a type with no operations that inspect it. A sealed value can be read from a field, moved through a conditional, stored, compared to another sealed value by ciphertext identity, and asked for its length. Equality on values is typed only at clear types.- Conditions are booleans, and booleans are clear. A conditional may carry sealed values in its branches, but its choice of branch never depends on sealed content.
- The meter prices a value from its view. Reading a field charges one step and
szof the field’s view, for an arbitrary functionsz. Since the length is in the view, a meter that counts ciphertext bytes is covered.
Definitions
Values, views and types
A sealed value carries a ciphertext handle ct, a length len and the plaintext pt. The evaluator holds all three, which makes the model honest: the plaintext is physically present, and only the typing discipline keeps it out of the outputs.
namespace MNI
inductive Ty where
| nat | bool | sealed
deriving DecidableEq, Repr
/-- A sealed value carries a ciphertext handle `ct`, a length `len` and the plaintext `pt`.
The evaluator holds all three; typing decides which it may use. -/
inductive Val where
| nat (n : Nat)
| bool (b : Bool)
| sealed (ct len pt : Nat)
deriving DecidableEq, Repr
/-- What the node may observe of a value: everything but the plaintext. -/
inductive View where
| nat (n : Nat)
| bool (b : Bool)
| sealed (ct len : Nat)
deriving DecidableEq, Repr
def Val.view : Val → View
| .nat n => .nat n
| .bool b => .bool b
| .sealed c l _ => .sealed c l
inductive Val.HasTy : Val → Ty → Prop
| nat (n : Nat) : Val.HasTy (.nat n) .nat
| bool (b : Bool) : Val.HasTy (.bool b) .bool
| sealed (c l p : Nat) : Val.HasTy (.sealed c l p) .sealed
Environments and low equivalence
An environment gives a value for every field of the request and of the stored record. Low equivalence relative to is equal views everywhere and equal values on the fields marks.
Low equivalence. iff for every source and index , , and implies .
inductive Src where
| req | doc
deriving DecidableEq, Repr
abbrev Env := Src → Nat → Val
abbrev Schema := Src → Nat → Ty
abbrev Policy := Src → Nat → Bool
def EnvOk (Γ : Schema) (ρ : Env) : Prop := ∀ s i, (ρ s i).HasTy (Γ s i)
/-- Low equivalence relative to a declassification policy `D`: equal views everywhere,
equal values on declassified fields. -/
def LowEnv (D : Policy) (ρ₁ ρ₂ : Env) : Prop :=
∀ s i, (ρ₁ s i).view = (ρ₂ s i).view ∧ (D s i = true → ρ₁ s i = ρ₂ s i)
Expressions and typing
The grammar has constants, field reads, addition, equality, conjunction, negation, a conditional, ciphertext identity ctEq, public length len, and two ways to read a plaintext. declass s i reads the plaintext of field of source . peek a reads the plaintext of any expression. peek is in the grammar only so that the tightness example can show what typing prevents: it has no typing rule.
Typing. with . The rules that matter are these.
inductive Expr where
| nat (n : Nat)
| bool (b : Bool)
| field (s : Src) (i : Nat)
| add (a b : Expr)
| eq (a b : Expr)
| and (a b : Expr)
| not (a : Expr)
| ite (c a b : Expr)
| ctEq (a b : Expr)
| len (a : Expr)
| declass (s : Src) (i : Nat)
| peek (a : Expr)
deriving Repr
/-- The typing judgment. `peek` has no rule. -/
inductive Typed (Γ : Schema) (D : Policy) : Expr → Ty → Prop
| nat (n : Nat) : Typed Γ D (.nat n) .nat
| bool (b : Bool) : Typed Γ D (.bool b) .bool
| field (s : Src) (i : Nat) : Typed Γ D (.field s i) (Γ s i)
| add {a b : Expr} : Typed Γ D a .nat → Typed Γ D b .nat → Typed Γ D (.add a b) .nat
| eq {a b : Expr} {τ : Ty} : Typed Γ D a τ → Typed Γ D b τ → τ ≠ .sealed →
Typed Γ D (.eq a b) .bool
| and {a b : Expr} : Typed Γ D a .bool → Typed Γ D b .bool → Typed Γ D (.and a b) .bool
| not {a : Expr} : Typed Γ D a .bool → Typed Γ D (.not a) .bool
| ite {c a b : Expr} {τ : Ty} : Typed Γ D c .bool → Typed Γ D a τ → Typed Γ D b τ →
Typed Γ D (.ite c a b) τ
| ctEq {a b : Expr} : Typed Γ D a .sealed → Typed Γ D b .sealed → Typed Γ D (.ctEq a b) .bool
| len {a : Expr} : Typed Γ D a .sealed → Typed Γ D (.len a) .nat
| declass {s : Src} {i : Nat} : Γ s i = .sealed → D s i = true → Typed Γ D (.declass s i) .nat
Metered evaluation
Evaluation returns a value and a usage vector . Every node costs one step. A field read also charges bytes. ctEq and len look only at the views of their arguments. Ill-typed combinations fall back to a default value. The fallbacks are never reached by typed expressions in environments well-typed for the schema, but they keep eval total.
structure Usage where
steps : Nat
bytes : Nat
deriving DecidableEq, Repr
instance : Add Usage := ⟨fun u w => ⟨u.steps + w.steps, u.bytes + w.bytes⟩⟩
def Usage.tick : Usage := ⟨1, 0⟩
def addV : Val → Val → Val
| .nat m, .nat n => .nat (m + n)
| _, _ => .nat 0
def andV : Val → Val → Val
| .bool a, .bool b => .bool (a && b)
| _, _ => .bool false
def notV : Val → Val
| .bool a => .bool (!a)
| _ => .bool false
def ctEqV : View → View → Val
| .sealed c _, .sealed c' _ => .bool (decide (c = c'))
| _, _ => .bool false
def lenV : View → Val
| .sealed _ l => .nat l
| _ => .nat 0
def openV : Val → Val
| .sealed _ _ p => .nat p
| _ => .nat 0
/-- Metered evaluation; `sz` prices the bytes of a value from its view. -/
def eval (sz : View → Nat) (ρ : Env) : Expr → Val × Usage
| .nat n => (.nat n, .tick)
| .bool b => (.bool b, .tick)
| .field s i => (ρ s i, ⟨1, sz (ρ s i).view⟩)
| .add a b => (addV (eval sz ρ a).1 (eval sz ρ b).1,
(eval sz ρ a).2 + (eval sz ρ b).2 + .tick)
| .eq a b => (.bool (decide ((eval sz ρ a).1 = (eval sz ρ b).1)),
(eval sz ρ a).2 + (eval sz ρ b).2 + .tick)
| .and a b => (andV (eval sz ρ a).1 (eval sz ρ b).1,
(eval sz ρ a).2 + (eval sz ρ b).2 + .tick)
| .not a => (notV (eval sz ρ a).1, (eval sz ρ a).2 + .tick)
| .ite c a b =>
match (eval sz ρ c).1 with
| .bool true => ((eval sz ρ a).1, (eval sz ρ c).2 + (eval sz ρ a).2 + .tick)
| _ => ((eval sz ρ b).1, (eval sz ρ c).2 + (eval sz ρ b).2 + .tick)
| .ctEq a b => (ctEqV (eval sz ρ a).1.view (eval sz ρ b).1.view,
(eval sz ρ a).2 + (eval sz ρ b).2 + .tick)
| .len a => (lenV (eval sz ρ a).1.view, (eval sz ρ a).2 + .tick)
| .declass s i => (openV (ρ s i), ⟨1, sz (openV (ρ s i)).view⟩)
| .peek a => (openV (eval sz ρ a).1, (eval sz ρ a).2 + .tick)
The logical relation
Relation at type . iff , and .
At a clear type the view determines the value, so is equality on values of type . At the sealed type it relates any two sealed values with the same handle and length, whatever their plaintexts.
/-- The logical relation at type τ: both values have type τ and the same view. -/
def Rel (τ : Ty) (v w : Val) : Prop := v.HasTy τ ∧ w.HasTy τ ∧ v.view = w.view
Records, collections and the node
A record maps field indices to values. A collection’s rule must have type bool, and its gate is any function of the views of a write. The output of a step is a decision, a list of rows of views, and a usage vector.
abbrev Record := Nat → Val
def env (q d : Record) : Env := fun s => match s with
| .req => q
| .doc => d
def RecOk (Γ : Schema) (s : Src) (r : Record) : Prop := ∀ i, (r i).HasTy (Γ s i)
def LowRec (D : Policy) (s : Src) (r₁ r₂ : Record) : Prop :=
∀ i, (r₁ i).view = (r₂ i).view ∧ (D s i = true → r₁ i = r₂ i)
def recView (w : Nat) (r : Record) : List View := (List.range w).map (fun i => (r i).view)
/-- A collection: its schema, declassification policy, width, authorization rule, and an
admission check on the wire form of a write (for instance a signature verification). -/
structure Coll where
Γ : Schema
D : Policy
width : Nat
allow : Expr
gate : List View → List View → Bool
def CollOk (C : Coll) : Prop := Typed C.Γ C.D C.allow .bool
structure Out where
decision : Bool
rows : List (List View)
usage : Usage
deriving DecidableEq, Repr
def isTrue (v : Val) : Bool := decide (v = .bool true)
scan walks the store, evaluates the rule and the predicate on each record, returns the projected views of the selected records and keeps the others. Query keeps the whole store, delete keeps the unselected records, and insert prepends the record if it is accepted.
def scan (C : Coll) (sz : View → Nat) (q : Record) (pred : Expr) (proj : List Nat) :
List Record → List Record × List (List View) × Usage
| [] => ([], [], ⟨0, 0⟩)
| d :: ds =>
if isTrue (eval sz (env q d) C.allow).1 && isTrue (eval sz (env q d) pred).1 then
((scan C sz q pred proj ds).1,
proj.map (fun i => (d i).view) :: (scan C sz q pred proj ds).2.1,
(eval sz (env q d) C.allow).2 + (eval sz (env q d) pred).2 + (scan C sz q pred proj ds).2.2)
else
(d :: (scan C sz q pred proj ds).1,
(scan C sz q pred proj ds).2.1,
(eval sz (env q d) C.allow).2 + (eval sz (env q d) pred).2 + (scan C sz q pred proj ds).2.2)
inductive Op where
| query (q : Record) (pred : Expr) (proj : List Nat)
| insert (q r : Record)
| delete (q : Record) (pred : Expr)
def writeBytes (sz : View → Nat) (vs : List View) : Nat := (vs.map sz).foldr (· + ·) 0
def step (C : Coll) (sz : View → Nat) (st : List Record) : Op → Out × List Record
| .query q pred proj =>
(⟨true, (scan C sz q pred proj st).2.1, (scan C sz q pred proj st).2.2⟩, st)
| .insert q r =>
let ok := C.gate (recView C.width q) (recView C.width r) &&
isTrue (eval sz (env q r) C.allow).1
(⟨ok, [], (eval sz (env q r) C.allow).2 + ⟨1, writeBytes sz (recView C.width r)⟩⟩,
if ok then r :: st else st)
| .delete q pred =>
let s := scan C sz q pred (List.range C.width) st
(⟨true, s.2.1, s.2.2⟩, s.1)
Well-formedness and low equivalence lift to stores and operations. Two operations are low-equivalent if they are the same kind of operation with the same predicate and projection, on low-equivalent records. The text of a query is therefore public. A secret query parameter is passed as a sealed field of the request.
def StOk (Γ : Schema) (st : List Record) : Prop := ∀ r ∈ st, RecOk Γ .doc r
inductive LowSt (D : Policy) : List Record → List Record → Prop
| nil : LowSt D [] []
| cons {r₁ r₂ : Record} {l₁ l₂ : List Record} :
LowRec D .doc r₁ r₂ → LowSt D l₁ l₂ → LowSt D (r₁ :: l₁) (r₂ :: l₂)
inductive OpOk (C : Coll) : Op → Prop
| query {q : Record} {pred : Expr} {proj : List Nat} :
RecOk C.Γ .req q → Typed C.Γ C.D pred .bool → OpOk C (.query q pred proj)
| insert {q r : Record} : RecOk C.Γ .req q → RecOk C.Γ .doc r → OpOk C (.insert q r)
| delete {q : Record} {pred : Expr} :
RecOk C.Γ .req q → Typed C.Γ C.D pred .bool → OpOk C (.delete q pred)
inductive OpLow (C : Coll) : Op → Op → Prop
| query {q₁ q₂ : Record} {pred : Expr} {proj : List Nat} :
LowRec C.D .req q₁ q₂ → OpLow C (.query q₁ pred proj) (.query q₂ pred proj)
| insert {q₁ q₂ r₁ r₂ : Record} :
LowRec C.D .req q₁ q₂ → LowRec C.D .doc r₁ r₂ → OpLow C (.insert q₁ r₁) (.insert q₂ r₂)
| delete {q₁ q₂ : Record} {pred : Expr} :
LowRec C.D .req q₁ q₂ → OpLow C (.delete q₁ pred) (.delete q₂ pred)
Runs, receipts and the empty policy
A run maps a store and a list of operations to the list of outputs. A receipt is , chained over the outputs. is an arbitrary function, so nothing about it is assumed until the binding theorem, where its collision resistance enters as a hypothesis.
def outs (C : Coll) (sz : View → Nat) : List Record → List Op → List Out
| _, [] => []
| st, op :: ops => (step C sz st op).1 :: outs C sz (step C sz st op).2 ops
/-- The receipt chain: each receipt binds the previous one and the step's output. -/
def receipts (H : Nat → Out → Nat) : Nat → List Out → List Nat
| _, [] => []
| rc, o :: os => H rc o :: receipts H (H rc o) os
def chainHead (H : Nat → Out → Nat) : Nat → List Out → Nat
| rc, [] => rc
| rc, o :: os => chainHead H (H rc o) os
inductive OpsLow (C : Coll) : List Op → List Op → Prop
| nil : OpsLow C [] []
| cons {o₁ o₂ : Op} {l₁ l₂ : List Op} :
OpOk C o₁ → OpOk C o₂ → OpLow C o₁ o₂ → OpsLow C l₁ l₂ → OpsLow C (o₁ :: l₁) (o₂ :: l₂)
The empty policy declassifies nothing. PlainOnly says that two records have the same view everywhere, that is, they differ at most in sealed plaintexts.
def noDeclass : Policy := fun _ _ => false
/-- Two records differ only in sealed plaintexts. -/
def PlainOnly (r₁ r₂ : Record) : Prop := ∀ i, (r₁ i).view = (r₂ i).view
Collision extraction, profiles and signed membership
A collision of is two different inputs with the same output. For any compressing collisions exist, so “a collision exists” is not a usable conclusion. Collision resistance enters instead through extraction: extract walks two chains side by side and returns a pair of distinct inputs with equal hashes, taken from the chains given to it. A theorem that concludes “the claim holds, or extract returns a collision” says that anyone who breaks the claim has computed a collision.
/-- Walk two chains in step; return a pair of distinct inputs from the two chains whose
hashes agree, preferring the latest position. -/
def extract (H : Nat → Out → Nat) :
Nat → List Out → Nat → List Out → Option ((Nat × Out) × (Nat × Out))
| r₁, o₁ :: t₁, r₂, o₂ :: t₂ =>
match extract H (H r₁ o₁) t₁ (H r₂ o₂) t₂ with
| some c => some c
| none =>
if (r₁, o₁) ≠ (r₂, o₂) ∧ H r₁ o₁ = H r₂ o₂ then some ((r₁, o₁), (r₂, o₂)) else none
| _, _, _, _ => none
Each collection declares a profile: whether membership changes are authenticated, and the scheme of each field. Secrecy with a non-plaintext scheme requires authenticity. The declaration check is exactly that implication. Receipts need no declaration of their own: they are a function of the outputs, and the run theorem below covers them for every collection.
inductive Scheme where
| plaintext | encrypted
deriving DecidableEq, Repr
structure Profile where
authentic : Bool
schemes : List Scheme
def Profile.needsAuth (p : Profile) : Bool := p.schemes.any (fun s => s != .plaintext)
/-- The declaration check. -/
def Profile.ok (p : Profile) : Bool := !p.needsAuth || p.authentic
Why should secrecy require authenticity? The plaintext of a sealed field is readable by whoever holds the keys of the epoch in which it was written. Those are the members of an audience, and new members are added by join requests, each claiming to come from an existing member. If join requests are not authenticated, anyone can claim to be a member and add themselves. Their future reads are then exactly what secrecy was meant to prevent. Authenticity in a profile therefore means that join requests carry signatures that the node verifies.
I model a signature scheme by a verification function and by the set of messages the holders of legitimate keys actually signed. A join request is forged if its signature verifies on a message its claimed signer did not sign. Unforgeability then enters, as collision resistance does, through a specific forged request that the theorem points at, never as a bare existential over all keys and messages. The legitimate audience is the closure of the initial members under “a member signed this newcomer in”.
/-- A signature scheme over keys, messages and signatures; `signed k m` records what the
holder of `k` signed. -/
structure Sig where
verify : Nat → Nat → Nat → Bool
signed : Nat → Nat → Bool
/-- A request to add `new` to an audience, claimed to come from `claimed`. -/
structure Join where
claimed : Nat
new : Nat
sig : Nat
/-- A forged request: its signature verifies, but the claimed signer never signed the newcomer. -/
def Sig.Forged (S : Sig) (j : Join) : Prop :=
S.verify j.claimed j.new j.sig = true ∧ S.signed j.claimed j.new = false
def joinStep (authentic : Bool) (S : Sig) (aud : List Nat) (j : Join) : List Nat :=
if decide (j.claimed ∈ aud) && (!authentic || S.verify j.claimed j.new j.sig) then
j.new :: aud else aud
/-- Who may legitimately be in the audience: the initial members and those a member signed in. -/
inductive Reach (S : Sig) (aud₀ : List Nat) : Nat → Prop
| init {k : Nat} : k ∈ aud₀ → Reach S aud₀ k
| add {k n : Nat} : Reach S aud₀ k → S.signed k n = true → Reach S aud₀ n
The secrecy property of a profile is stated over its audience. If the profile has a sealed field, the readers of sealed plaintexts are the audience members. The property says that after any list of join requests, every member is legitimate, unless one of those requests is a forgery against a legitimate member’s key. A profile with no sealed field satisfies it vacuously: there is nothing to read.
/-- Secrecy of a profile: if it has a sealed field, every member of the audience after `js` is
legitimate, unless some request in `js` is forged against a legitimate member's key. -/
def Secure (p : Profile) (S : Sig) (aud₀ : List Nat) (js : List Join) : Prop :=
Scheme.encrypted ∈ p.schemes →
∀ x ∈ js.foldl (joinStep p.authentic S) aud₀,
Reach S aud₀ x ∨ ∃ j ∈ js, Reach S aud₀ j.claimed ∧ S.Forged j
A database passes when every collection passes.
def dbOk (ps : List Profile) : Bool := ps.all Profile.ok
Theorems
The fundamental lemma
At a clear type, two values of that type with the same view are equal. The six operator results have the types the rules give them.
/-- At a clear type the view is the value. -/
theorem Val.eq_of_view {v w : Val} {τ : Ty} (hv : v.HasTy τ) (hw : w.HasTy τ)
(hτ : τ ≠ .sealed) (h : v.view = w.view) : v = w := by
cases hv <;> cases hw <;> simp_all [Val.view]
theorem addV_ty (v w : Val) : (addV v w).HasTy .nat := by
cases v <;> cases w <;> exact .nat _
theorem andV_ty (v w : Val) : (andV v w).HasTy .bool := by
cases v <;> cases w <;> exact .bool _
theorem notV_ty (v : Val) : (notV v).HasTy .bool := by
cases v <;> exact .bool _
theorem ctEqV_ty (v w : View) : (ctEqV v w).HasTy .bool := by
cases v <;> cases w <;> exact .bool _
theorem lenV_ty (v : View) : (lenV v).HasTy .nat := by
cases v <;> exact .nat _
theorem openV_ty (v : Val) : (openV v).HasTy .nat := by
cases v <;> exact .nat _
Fundamental lemma. For every metering function , if are well-typed for , and , then and have values related by and equal usage vectors. If moreover , the two evaluations are equal.
Proof. Induction on the typing derivation.
- Constants are trivial.
- Field reads return values with equal views by low equivalence. The charge is a function of the view.
- Addition, conjunction, negation and equality have operands of clear type. By the induction hypothesis the operands are related at a clear type, so they are equal, and the results and usages are equal.
- The conditional has a boolean condition, which is therefore equal on both sides. Both runs take the same branch, and the induction hypothesis for that branch gives the relation at (possibly ) and equal usage.
ctEqandlenread only views, which are equal by the induction hypothesis.- Declassify is typed only if holds, and low equivalence then gives equal values at that field.
For the last claim, a relation at a clear type is equality. ∎
/-- Fundamental lemma: a typed expression maps low-equivalent environments to related values
and to the same usage vector. -/
theorem eval_rel (sz : View → Nat) {Γ : Schema} {D : Policy} {ρ₁ ρ₂ : Env}
(h₁ : EnvOk Γ ρ₁) (h₂ : EnvOk Γ ρ₂) (hL : LowEnv D ρ₁ ρ₂)
{e : Expr} {τ : Ty} (ht : Typed Γ D e τ) :
Rel τ (eval sz ρ₁ e).1 (eval sz ρ₂ e).1 ∧ (eval sz ρ₁ e).2 = (eval sz ρ₂ e).2 := by
induction ht with
| nat n => exact ⟨⟨.nat n, .nat n, rfl⟩, rfl⟩
| bool b => exact ⟨⟨.bool b, .bool b, rfl⟩, rfl⟩
| field s i => exact ⟨⟨h₁ s i, h₂ s i, (hL s i).1⟩, by simp [eval, (hL s i).1]⟩
| add _ _ iha ihb =>
obtain ⟨⟨a1, a2, av⟩, au⟩ := iha
obtain ⟨⟨b1, b2, bv⟩, bu⟩ := ihb
have ea := Val.eq_of_view a1 a2 (by decide) av
have eb := Val.eq_of_view b1 b2 (by decide) bv
simp only [eval]
rw [ea, eb, au, bu]
exact ⟨⟨addV_ty _ _, addV_ty _ _, rfl⟩, rfl⟩
| eq _ _ hτ iha ihb =>
obtain ⟨⟨a1, a2, av⟩, au⟩ := iha
obtain ⟨⟨b1, b2, bv⟩, bu⟩ := ihb
have ea := Val.eq_of_view a1 a2 hτ av
have eb := Val.eq_of_view b1 b2 hτ bv
simp only [eval]
rw [ea, eb, au, bu]
exact ⟨⟨.bool _, .bool _, rfl⟩, rfl⟩
| and _ _ iha ihb =>
obtain ⟨⟨a1, a2, av⟩, au⟩ := iha
obtain ⟨⟨b1, b2, bv⟩, bu⟩ := ihb
have ea := Val.eq_of_view a1 a2 (by decide) av
have eb := Val.eq_of_view b1 b2 (by decide) bv
simp only [eval]
rw [ea, eb, au, bu]
exact ⟨⟨andV_ty _ _, andV_ty _ _, rfl⟩, rfl⟩
| not _ iha =>
obtain ⟨⟨a1, a2, av⟩, au⟩ := iha
have ea := Val.eq_of_view a1 a2 (by decide) av
simp only [eval]
rw [ea, au]
exact ⟨⟨notV_ty _, notV_ty _, rfl⟩, rfl⟩
| ite _ _ _ ihc iha ihb =>
obtain ⟨⟨c1, c2, cv⟩, cu⟩ := ihc
have ec := Val.eq_of_view c1 c2 (by decide) cv
simp only [eval]
rw [ec, cu]
split
· exact ⟨iha.1, by rw [iha.2]⟩
· exact ⟨ihb.1, by rw [ihb.2]⟩
| ctEq _ _ iha ihb =>
obtain ⟨⟨_, _, av⟩, au⟩ := iha
obtain ⟨⟨_, _, bv⟩, bu⟩ := ihb
simp only [eval]
rw [av, bv, au, bu]
exact ⟨⟨ctEqV_ty _ _, ctEqV_ty _ _, rfl⟩, rfl⟩
| len _ iha =>
obtain ⟨⟨_, _, av⟩, au⟩ := iha
simp only [eval]
rw [av, au]
exact ⟨⟨lenV_ty _, lenV_ty _, rfl⟩, rfl⟩
| @declass s i _ hd =>
have e := (hL s i).2 hd
simp only [eval]
rw [e]
exact ⟨⟨openV_ty _, openV_ty _, rfl⟩, rfl⟩
/-- At a clear type the whole result (value and usage) is the same. -/
theorem eval_clear (sz : View → Nat) {Γ : Schema} {D : Policy} {ρ₁ ρ₂ : Env}
(h₁ : EnvOk Γ ρ₁) (h₂ : EnvOk Γ ρ₂) (hL : LowEnv D ρ₁ ρ₂)
{e : Expr} {τ : Ty} (ht : Typed Γ D e τ) (hτ : τ ≠ .sealed) :
eval sz ρ₁ e = eval sz ρ₂ e := by
obtain ⟨⟨v1, v2, vv⟩, u⟩ := eval_rel sz h₁ h₂ hL ht
exact Prod.ext (Val.eq_of_view v1 v2 hτ vv) u
The conditional case is the reason sealed values can be moved but not inspected. No typing rule turns a sealed value into a boolean. Equality is excluded at the sealed type, and ctEq compares handles, which are in the view.
One step of the node and whole runs
Records and environments inherit low equivalence, and projected views of low-equivalent records are equal.
theorem env_ok {Γ : Schema} {q d : Record} (hq : RecOk Γ .req q) (hd : RecOk Γ .doc d) :
EnvOk Γ (env q d) := by
intro s i; cases s
· exact hq i
· exact hd i
theorem env_low {D : Policy} {q₁ q₂ d₁ d₂ : Record} (hq : LowRec D .req q₁ q₂)
(hd : LowRec D .doc d₁ d₂) : LowEnv D (env q₁ d₁) (env q₂ d₂) := by
intro s i; cases s
· exact hq i
· exact hd i
theorem recView_low {D : Policy} {s : Src} {r₁ r₂ : Record} (w : Nat) (h : LowRec D s r₁ r₂) :
recView w r₁ = recView w r₂ := by
have : (fun i => (r₁ i).view) = (fun i => (r₂ i).view) := funext fun i => (h i).1
simp only [recView, this]
theorem proj_low {D : Policy} {s : Src} {r₁ r₂ : Record} (proj : List Nat)
(h : LowRec D s r₁ r₂) :
proj.map (fun i => (r₁ i).view) = proj.map (fun i => (r₂ i).view) := by
have : (fun i => (r₁ i).view) = (fun i => (r₂ i).view) := funext fun i => (h i).1
rw [this]
Step non-interference. Let the collection’s rule have type bool, and let the gate be any function of views. Take two well-typed, low-equivalent stores and two well-typed, low-equivalent operations. Then the two steps give the same output (decision, rows, usage), and the new stores are again well-typed and low-equivalent.
Proof. For query and delete, induct on the low-equivalence of the stores. At each record the rule and the predicate have type bool, so by the fundamental lemma they give the same values and usage on both sides. The same records are selected, their projected views are equal, and the unselected records pair up into low-equivalent stores. For insert, the gate gets equal views, the rule gives the same value and usage, and the bytes written are a function of the record’s views. The accepted record is low-equivalent to its counterpart, so the new stores are too. ∎
theorem scan_ni (C : Coll) (sz : View → Nat) (hC : CollOk C) {q₁ q₂ : Record} {pred : Expr}
(proj : List Nat) (hq₁ : RecOk C.Γ .req q₁) (hq₂ : RecOk C.Γ .req q₂)
(hq : LowRec C.D .req q₁ q₂) (hp : Typed C.Γ C.D pred .bool) :
∀ {st₁ st₂ : List Record}, StOk C.Γ st₁ → StOk C.Γ st₂ → LowSt C.D st₁ st₂ →
(scan C sz q₁ pred proj st₁).2 = (scan C sz q₂ pred proj st₂).2 ∧
LowSt C.D (scan C sz q₁ pred proj st₁).1 (scan C sz q₂ pred proj st₂).1 ∧
StOk C.Γ (scan C sz q₁ pred proj st₁).1 ∧ StOk C.Γ (scan C sz q₂ pred proj st₂).1 := by
intro st₁ st₂ hs₁ hs₂ hl
induction hl with
| nil => exact ⟨rfl, .nil, by simp [scan, StOk], by simp [scan, StOk]⟩
| @cons d₁ d₂ l₁ l₂ hd _ ih =>
have hd₁ : RecOk C.Γ .doc d₁ := hs₁ d₁ (List.mem_cons_self _ _)
have hd₂ : RecOk C.Γ .doc d₂ := hs₂ d₂ (List.mem_cons_self _ _)
have ht₁ : StOk C.Γ l₁ := fun r hr => hs₁ r (List.mem_cons_of_mem _ hr)
have ht₂ : StOk C.Γ l₂ := fun r hr => hs₂ r (List.mem_cons_of_mem _ hr)
obtain ⟨e2, el, ok1, ok2⟩ := ih ht₁ ht₂
have eo₁ := env_ok hq₁ hd₁
have eo₂ := env_ok hq₂ hd₂
have elw := env_low hq hd
have ea := eval_clear sz eo₁ eo₂ elw hC (by decide)
have ep := eval_clear sz eo₁ eo₂ elw hp (by decide)
have epr := proj_low proj hd
simp only [scan]
rw [ea, ep, epr]
split
· refine ⟨?_, el, ok1, ok2⟩
simp only [Prod.mk.injEq]
exact ⟨congrArg (fun x => _ :: x) (congrArg Prod.fst e2),
congrArg (fun x => _ + x) (congrArg Prod.snd e2)⟩
· refine ⟨?_, .cons hd el, ?_, ?_⟩
· simp only [Prod.mk.injEq]
exact ⟨congrArg Prod.fst e2, congrArg (fun x => _ + x) (congrArg Prod.snd e2)⟩
· intro r hr
cases List.mem_cons.mp hr with
| inl h => exact h ▸ hd₁
| inr h => exact ok1 r h
· intro r hr
cases List.mem_cons.mp hr with
| inl h => exact h ▸ hd₂
| inr h => exact ok2 r h
/-- One step: identical output (decision, rows, usage), low-equivalent and well-typed states. -/
theorem step_ni (C : Coll) (sz : View → Nat) (hC : CollOk C) {st₁ st₂ : List Record}
{op₁ op₂ : Op} (hs₁ : StOk C.Γ st₁) (hs₂ : StOk C.Γ st₂) (hl : LowSt C.D st₁ st₂)
(ho₁ : OpOk C op₁) (ho₂ : OpOk C op₂) (ho : OpLow C op₁ op₂) :
(step C sz st₁ op₁).1 = (step C sz st₂ op₂).1 ∧
LowSt C.D (step C sz st₁ op₁).2 (step C sz st₂ op₂).2 ∧
StOk C.Γ (step C sz st₁ op₁).2 ∧ StOk C.Γ (step C sz st₂ op₂).2 := by
cases ho with
| query hq =>
cases ho₁ with
| query hq₁ hp =>
cases ho₂ with
| query hq₂ _ =>
obtain ⟨e, _, _, _⟩ := scan_ni C sz hC _ hq₁ hq₂ hq hp hs₁ hs₂ hl
simp only [step]
exact ⟨by rw [e], hl, hs₁, hs₂⟩
| insert hq hr =>
rename_i q₁ q₂ r₁ r₂
cases ho₁ with
| insert hq₁ hr₁ =>
cases ho₂ with
| insert hq₂ hr₂ =>
have ea := eval_clear sz (env_ok hq₁ hr₁) (env_ok hq₂ hr₂) (env_low hq hr) hC (by decide)
have vq := recView_low C.width hq
have vr := recView_low C.width hr
simp only [step]
rw [ea, vq, vr]
refine ⟨rfl, ?_, ?_, ?_⟩
· split
· exact .cons hr hl
· exact hl
· split
· intro x hx
cases List.mem_cons.mp hx with
| inl h => exact h ▸ hr₁
| inr h => exact hs₁ x h
· exact hs₁
· split
· intro x hx
cases List.mem_cons.mp hx with
| inl h => exact h ▸ hr₂
| inr h => exact hs₂ x h
· exact hs₂
| delete hq =>
cases ho₁ with
| delete hq₁ hp =>
cases ho₂ with
| delete hq₂ _ =>
obtain ⟨e, el, ok1, ok2⟩ := scan_ni C sz hC (List.range C.width) hq₁ hq₂ hq hp hs₁ hs₂ hl
simp only [step]
exact ⟨by rw [e], el, ok1, ok2⟩
Metered non-interference for runs. Under the hypotheses of step non-interference for every pair of operations, for every metering function, hash function , initial receipt and price function, two runs give equal output lists, equal receipt lists, equal chain heads and equal charges for every operation.
Proof. Induction on the operation lists, using step non-interference and the preserved invariants at each step. Receipts and prices are functions of the outputs. ∎
theorem outs_ni (C : Coll) (sz : View → Nat) (hC : CollOk C) {ops₁ ops₂ : List Op}
(ho : OpsLow C ops₁ ops₂) :
∀ {st₁ st₂ : List Record}, StOk C.Γ st₁ → StOk C.Γ st₂ → LowSt C.D st₁ st₂ →
outs C sz st₁ ops₁ = outs C sz st₂ ops₂ := by
induction ho with
| nil => intros; rfl
| cons h₁ h₂ h _ ih =>
intro st₁ st₂ hs₁ hs₂ hl
obtain ⟨e, el, ok1, ok2⟩ := step_ni C sz hC hs₁ hs₂ hl h₁ h₂ h
simp only [outs]
rw [e, ih ok1 ok2 el]
/-- Metered non-interference for runs: identical outputs, receipts and chain heads, and
identical gas under every price function of the usage vector. -/
theorem run_ni (C : Coll) (sz : View → Nat) (hC : CollOk C) (H : Nat → Out → Nat)
(rc : Nat) (price : Usage → Nat) {ops₁ ops₂ : List Op} (ho : OpsLow C ops₁ ops₂)
{st₁ st₂ : List Record} (hs₁ : StOk C.Γ st₁) (hs₂ : StOk C.Γ st₂) (hl : LowSt C.D st₁ st₂) :
outs C sz st₁ ops₁ = outs C sz st₂ ops₂ ∧
receipts H rc (outs C sz st₁ ops₁) = receipts H rc (outs C sz st₂ ops₂) ∧
chainHead H rc (outs C sz st₁ ops₁) = chainHead H rc (outs C sz st₂ ops₂) ∧
(outs C sz st₁ ops₁).map (fun o => price o.usage) =
(outs C sz st₂ ops₂).map (fun o => price o.usage) := by
have e := outs_ni C sz hC ho hs₁ hs₂ hl
exact ⟨e, by rw [e], by rw [e], by rw [e]⟩
No declassification: plaintexts do not matter
Sealed plaintexts are invisible. Records that differ only in sealed plaintexts are low-equivalent under the empty policy, and under the empty policy declass has no typing derivation at all. Hence, for a collection with the empty policy and a well-typed rule, two well-typed stores and two well-typed operation lists that differ only in sealed plaintexts, record by record, give identical results, decisions, receipts and usage.
Proof. Lift “differ only in sealed plaintexts” pointwise to low equivalence of stores and operations under the empty policy, and apply the run theorem. ∎
theorem lowRec_noDeclass {s : Src} {r₁ r₂ : Record} (h : PlainOnly r₁ r₂) :
LowRec noDeclass s r₁ r₂ := fun i => ⟨h i, fun hf => by simp [noDeclass] at hf⟩
theorem declass_untypable {Γ : Schema} {s : Src} {i : Nat} {τ : Ty} :
¬ Typed Γ noDeclass (.declass s i) τ := by
intro h; cases h with
| declass _ hd => simp [noDeclass] at hd
/-- Stores that differ only in sealed plaintexts, record by record. -/
inductive StPlain : List Record → List Record → Prop
| nil : StPlain [] []
| cons {r₁ r₂ : Record} {l₁ l₂ : List Record} :
PlainOnly r₁ r₂ → StPlain l₁ l₂ → StPlain (r₁ :: l₁) (r₂ :: l₂)
/-- Operations with the same text whose records differ only in sealed plaintexts. -/
inductive OpPlain : Op → Op → Prop
| query {q₁ q₂ : Record} {pred : Expr} {proj : List Nat} :
PlainOnly q₁ q₂ → OpPlain (.query q₁ pred proj) (.query q₂ pred proj)
| insert {q₁ q₂ r₁ r₂ : Record} :
PlainOnly q₁ q₂ → PlainOnly r₁ r₂ → OpPlain (.insert q₁ r₁) (.insert q₂ r₂)
| delete {q₁ q₂ : Record} {pred : Expr} :
PlainOnly q₁ q₂ → OpPlain (.delete q₁ pred) (.delete q₂ pred)
inductive OpsPlain (C : Coll) : List Op → List Op → Prop
| nil : OpsPlain C [] []
| cons {o₁ o₂ : Op} {l₁ l₂ : List Op} :
OpOk C o₁ → OpOk C o₂ → OpPlain o₁ o₂ → OpsPlain C l₁ l₂ →
OpsPlain C (o₁ :: l₁) (o₂ :: l₂)
theorem plain_low {C : Coll} (hD : C.D = noDeclass) {s : Src} {r₁ r₂ : Record}
(h : PlainOnly r₁ r₂) : LowRec C.D s r₁ r₂ := by
rw [hD]; exact lowRec_noDeclass h
theorem stPlain_low {C : Coll} (hD : C.D = noDeclass) {l₁ l₂ : List Record}
(h : StPlain l₁ l₂) : LowSt C.D l₁ l₂ := by
induction h with
| nil => exact .nil
| cons hr _ ih => exact .cons (plain_low hD hr) ih
theorem opsPlain_low {C : Coll} (hD : C.D = noDeclass) {l₁ l₂ : List Op}
(h : OpsPlain C l₁ l₂) : OpsLow C l₁ l₂ := by
induction h with
| nil => exact .nil
| cons h₁ h₂ ho _ ih =>
refine .cons h₁ h₂ ?_ ih
cases ho with
| query hq => exact .query (plain_low hD hq)
| insert hq hr => exact .insert (plain_low hD hq) (plain_low hD hr)
| delete hq => exact .delete (plain_low hD hq)
/-- Sealed plaintexts are invisible: identical outputs, receipts, chain heads and gas. -/
theorem sealed_invisible (C : Coll) (sz : View → Nat) (hC : CollOk C) (hD : C.D = noDeclass)
(H : Nat → Out → Nat) (rc : Nat) (price : Usage → Nat) {ops₁ ops₂ : List Op}
(ho : OpsPlain C ops₁ ops₂) {st₁ st₂ : List Record} (hs₁ : StOk C.Γ st₁)
(hs₂ : StOk C.Γ st₂) (hl : StPlain st₁ st₂) :
outs C sz st₁ ops₁ = outs C sz st₂ ops₂ ∧
receipts H rc (outs C sz st₁ ops₁) = receipts H rc (outs C sz st₂ ops₂) ∧
chainHead H rc (outs C sz st₁ ops₁) = chainHead H rc (outs C sz st₂ ops₂) ∧
(outs C sz st₁ ops₁).map (fun o => price o.usage) =
(outs C sz st₂ ops₂).map (fun o => price o.usage) :=
run_ni C sz hC H rc price (opsPlain_low hD ho) hs₁ hs₂ (stPlain_low hD hl)
Each hypothesis is needed
Concrete counterexamples, each a closed evaluation checked by decide, show that the statement becomes false when one of the typing, policy, operation-text or length hypotheses is dropped. One general lemma covers padding. The environments , , put a sealed value in every field.
- Typing of expressions. and have the same handle 7 and length 64 and plaintexts 1 and 2. They are well-typed and low-equivalent under the empty policy. The expression
peek (field doc 0), which has no typing derivation, returns 1 in one and 2 in the other. - Typing of stored values. Under the schema that types every field
nat, the expressioneq (field req 0) (field doc 0)is well-typed. In and in an environment that holds plaintext 2 in thedocfields, every field still has the same view, so the two are low-equivalent, but neither is well-typed for that schema. The equality compares whole values, plaintexts included, and returnstruein one andfalsein the other. - Relativity to . With the policy that marks
doc 0, the expressiondeclass doc 0is typed and tells from . Declassification is a real channel, which is why the theorem is relative to . - Public operation text. On one store, two queries that differ only in their predicate return different rows. This is why low-equivalent operations must have the same predicate and projection, and why a secret parameter belongs in a sealed request field.
- Length in the view. is with length 128 instead of 64. A view that drops the length makes and low-equivalent under the empty policy, but the well-typed expression
len (field doc 0)returns 64 in one and 128 in the other, and with the meter that charges a sealed value its length a field read is charged differently. If lengths were treated as secret, the theorem would be false. - Padding (general lemma). With a fixed length , two sealed values with the same handle have the same view whatever their plaintexts. Padding is the special case in which public lengths carry no information about the plaintext.
def Γ₀ : Schema := fun _ _ => .sealed
def ρA : Env := fun _ _ => .sealed 7 64 1
def ρB : Env := fun _ _ => .sealed 7 64 2
theorem ρA_ok : EnvOk Γ₀ ρA := fun _ _ => .sealed _ _ _
theorem ρB_ok : EnvOk Γ₀ ρB := fun _ _ => .sealed _ _ _
theorem ρAB_low : LowEnv noDeclass ρA ρB :=
fun _ _ => ⟨rfl, fun hf => by simp [noDeclass] at hf⟩
theorem peek_untypable {Γ : Schema} {D : Policy} {a : Expr} {τ : Ty} :
¬ Typed Γ D (.peek a) τ := by
intro h; cases h
/-- Without typing (here `peek`), the result reads the plaintext. -/
theorem peek_leaks :
(eval (fun _ => 0) ρA (.peek (.field .doc 0))).1 ≠
(eval (fun _ => 0) ρB (.peek (.field .doc 0))).1 := by decide
/-- Declassification is a real channel: typed under a policy declassifying `doc 0`, the
result differs between environments low-equivalent under `noDeclass`. -/
def D₀ : Policy := fun s i => decide (s = .doc ∧ i = 0)
theorem declass_typed : Typed Γ₀ D₀ (.declass .doc 0) .nat := .declass rfl (by decide)
theorem declass_channel :
(eval (fun _ => 0) ρA (.declass .doc 0)).1 ≠ (eval (fun _ => 0) ρB (.declass .doc 0)).1 := by
decide
/-- Stored values must be well-typed: a `nat` schema over fields that hold sealed values. -/
def Γnat : Schema := fun _ _ => .nat
def ρD : Env := fun s _ => match s with
| .req => .sealed 7 64 1
| .doc => .sealed 7 64 2
theorem ρAD_low : LowEnv noDeclass ρA ρD := by
intro s _; cases s <;> exact ⟨rfl, fun hf => by simp [noDeclass] at hf⟩
theorem ρA_illtyped : ¬ EnvOk Γnat ρA := by
intro h; have h0 := h .doc 0; cases h0
theorem eq_typed : Typed Γnat noDeclass (.eq (.field .req 0) (.field .doc 0)) .bool :=
.eq (.field _ _) (.field _ _) (by decide)
theorem illtyped_leaks :
(eval (fun _ => 0) ρA (.eq (.field .req 0) (.field .doc 0))).1 ≠
(eval (fun _ => 0) ρD (.eq (.field .req 0) (.field .doc 0))).1 := by decide
/-- The text of an operation is public: different predicates, different rows on one store. -/
def C₀ : Coll := ⟨Γ₀, noDeclass, 1, .bool true, fun _ _ => true⟩
def r₀ : Record := fun _ => .sealed 7 64 1
theorem pred_public :
(step C₀ (fun _ => 0) [r₀] (.query r₀ (.bool true) [0])).1 ≠
(step C₀ (fun _ => 0) [r₀] (.query r₀ (.bool false) [0])).1 := by decide
/-- Lengths must be public. A view without lengths, and the low equivalence it induces. -/
def viewNoLen : Val → View
| .sealed c _ _ => .sealed c 0
| v => v.view
def LowEnvNoLen (D : Policy) (ρ₁ ρ₂ : Env) : Prop :=
∀ s i, viewNoLen (ρ₁ s i) = viewNoLen (ρ₂ s i) ∧ (D s i = true → ρ₁ s i = ρ₂ s i)
def ρC : Env := fun _ _ => .sealed 7 128 1
theorem ρAC_lowNoLen : LowEnvNoLen noDeclass ρA ρC :=
fun _ _ => ⟨rfl, fun hf => by simp [noDeclass] at hf⟩
theorem ρC_ok : EnvOk Γ₀ ρC := fun _ _ => .sealed _ _ _
theorem len_typed : Typed Γ₀ noDeclass (.len (.field .doc 0)) .nat := .len (.field _ _)
/-- Under the length-blind relation, a typed expression still tells ρA from ρC. -/
theorem length_leaks :
(eval (fun _ => 0) ρA (.len (.field .doc 0))).1 ≠
(eval (fun _ => 0) ρC (.len (.field .doc 0))).1 := by decide
/-- And a meter that charges ciphertext bytes charges the two field reads differently. -/
theorem length_charged :
(eval (fun v => match v with | .sealed _ l => l | _ => 0) ρA (.field .doc 0)).2 ≠
(eval (fun v => match v with | .sealed _ l => l | _ => 0) ρC (.field .doc 0)).2 := by
decide
/-- Padding to a fixed length `L` makes the length condition hold for all plaintexts. -/
theorem padded_view (c L p p' : Nat) : (Val.sealed c L p).view = (Val.sealed c L p').view := rfl
Verifiability: receipts bind the outputs
Chain binding. For any , if two output lists of equal length have the same chain head from initial receipts , then and the lists are equal, or extract applied to the two chains returns a pair of inputs with and . Moreover, whatever extract returns is such a collision.
Proof. The second claim is an induction that only follows the definition: a pair is returned only after its two conditions have been checked. For the first, induct on the first list. Equal heads after one more output give, by the induction hypothesis on the tails, either a pair returned from the tails, which extract passes on, or equal tails with equal intermediate receipts . In the latter case extract on the identical tails returns nothing. If the claim follows. Otherwise extract returns this pair, which is a collision. ∎
The collision is computed from the two given chains and is one of their pairs , so a verifier who is shown two runs with equal heads and equal lengths either learns that they agree or holds a collision of . The equal-length hypothesis cannot be dropped. Without it, makes the empty list from and the one-element list from agree, and no collision is involved. A verifier therefore needs the number of operations as well as the head. Since the run theorem gives the same output list in both worlds, the receipts reveal nothing about sealed plaintexts, and the binding argument applies to that list as to any other.
/-- Whatever `extract` returns is a collision of `H`. -/
theorem extract_sound (H : Nat → Out → Nat) :
∀ (os₁ os₂ : List Out) (r₁ r₂ : Nat) (a b : Nat × Out),
extract H r₁ os₁ r₂ os₂ = some (a, b) → a ≠ b ∧ H a.1 a.2 = H b.1 b.2 := by
intro os₁
induction os₁ with
| nil => intro os₂ r₁ r₂ a b h; simp [extract] at h
| cons o₁ t₁ ih =>
intro os₂ r₁ r₂ a b h
cases os₂ with
| nil => simp [extract] at h
| cons o₂ t₂ =>
simp only [extract] at h
split at h
· rename_i c hc
cases h
exact ih t₂ _ _ a b hc
· split at h
· rename_i hcond
cases h
exact hcond
· cases h
/-- On two identical chains `extract` returns nothing. -/
theorem extract_self (H : Nat → Out → Nat) :
∀ (os : List Out) (r : Nat), extract H r os r os = none := by
intro os
induction os with
| nil => intro r; rfl
| cons o t ih =>
intro r
simp only [extract, ih]
simp
/-- Chain binding: equal heads over equal lengths give equal chains, or `extract` returns a
collision taken from the two chains. -/
theorem chain_binding (H : Nat → Out → Nat) :
∀ (os₁ os₂ : List Out) (r₁ r₂ : Nat), os₁.length = os₂.length →
chainHead H r₁ os₁ = chainHead H r₂ os₂ →
(r₁ = r₂ ∧ os₁ = os₂) ∨
∃ a b, extract H r₁ os₁ r₂ os₂ = some (a, b) ∧ a ≠ b ∧ H a.1 a.2 = H b.1 b.2 := by
intro os₁
induction os₁ with
| nil =>
intro os₂ r₁ r₂ hlen h
cases os₂ with
| nil => exact .inl ⟨h, rfl⟩
| cons _ _ => simp at hlen
| cons o₁ t₁ ih =>
intro os₂ r₁ r₂ hlen h
cases os₂ with
| nil => simp at hlen
| cons o₂ t₂ =>
simp only [List.length_cons, Nat.add_right_cancel_iff] at hlen
simp only [chainHead] at h
cases ih t₂ _ _ hlen h with
| inr hc =>
obtain ⟨a, b, he, hab⟩ := hc
refine .inr ⟨a, b, ?_, hab⟩
simp only [extract, he]
| inl hh =>
obtain ⟨hH, ht⟩ := hh
subst ht
by_cases hp : (r₁, o₁) = (r₂, o₂)
· have h1 : r₁ = r₂ := congrArg Prod.fst hp
have h2 : o₁ = o₂ := congrArg Prod.snd hp
exact .inl ⟨h1, by rw [h2]⟩
· refine .inr ⟨(r₁, o₁), (r₂, o₂), ?_, hp, hH⟩
simp only [extract, hH, extract_self]
simp [hp, hH]
Composition: secrecy needs authenticity
The declaration check is sound: a passing profile with a sealed field authenticates joins.
theorem check_sound (p : Profile) (h : p.ok = true) (hn : p.needsAuth = true) :
p.authentic = true := by
simp [Profile.ok, hn] at h; exact h
/-- A profile needs authenticity exactly when it has a sealed field. -/
theorem needsAuth_iff (p : Profile) : p.needsAuth = true ↔ Scheme.encrypted ∈ p.schemes := by
simp only [Profile.needsAuth, List.any_eq_true]
constructor
· intro ⟨s, hs, hne⟩
cases s with
| plaintext => simp at hne
| encrypted => exact hs
· intro h; exact ⟨.encrypted, h, by decide⟩
Audience closure. Under authenticated joins, every member of the audience reached from by a list of join requests is in the legitimate audience of , or some request is forged against a key whose holder is a legitimate member.
Proof. Induction on the list of joins, with the invariant “every member is legitimate, or a request already processed is forged against a legitimate member’s key”. An accepted join has a claimed member in the audience and a verifying signature on the newcomer. By the invariant the claimed member is legitimate, or a forged request has already been found. If the claimed member signed the newcomer in, the newcomer is legitimate. If not, the join itself is forged, and its claimed signer is legitimate. ∎
The forged request is one of the requests the node actually received, and its key belongs to a legitimate member. This is the shape of existential unforgeability: an adversary who breaks closure has produced, from the given requests, a forgery against an honest key.
theorem audience_sound (S : Sig) (aud₀ : List Nat) :
∀ (js pre : List Join) (aud : List Nat),
(∀ x ∈ aud, Reach S aud₀ x ∨ ∃ j ∈ pre, Reach S aud₀ j.claimed ∧ S.Forged j) →
∀ x ∈ js.foldl (joinStep true S) aud,
Reach S aud₀ x ∨ ∃ j ∈ pre ++ js, Reach S aud₀ j.claimed ∧ S.Forged j := by
intro js
induction js with
| nil => intro pre aud h; simpa using h
| cons j js ih =>
intro pre aud h x hx
have := ih (pre ++ [j]) (joinStep true S aud j) ?_ x hx
· simpa using this
intro y hy
have weaken : (∃ j' ∈ pre, Reach S aud₀ j'.claimed ∧ S.Forged j') →
∃ j' ∈ pre ++ [j], Reach S aud₀ j'.claimed ∧ S.Forged j' := by
intro ⟨j', hm, hr⟩; exact ⟨j', List.mem_append_left _ hm, hr⟩
simp only [joinStep, Bool.not_true, Bool.false_or] at hy
split at hy
· rename_i hc
simp only [Bool.and_eq_true, decide_eq_true_eq] at hc
cases List.mem_cons.mp hy with
| inr hm => exact (h y hm).imp id weaken
| inl he =>
subst he
cases h j.claimed hc.1 with
| inr hf => exact .inr (weaken hf)
| inl hr =>
cases hs : S.signed j.claimed j.new with
| true => exact .inl (.add hr hs)
| false => exact .inr ⟨j, by simp, hr, hc.2, hs⟩
· exact (h y hy).imp id weaken
/-- Every member reached by authenticated joins is legitimate, unless one of the given requests
is forged against a legitimate member's key. -/
theorem audience_closed (S : Sig) (aud₀ : List Nat) (js : List Join) :
∀ x ∈ js.foldl (joinStep true S) aud₀,
Reach S aud₀ x ∨ ∃ j ∈ js, Reach S aud₀ j.claimed ∧ S.Forged j := by
intro x hx
have := audience_sound S aud₀ js [] aud₀ (fun _ hy => .inl (.init hy)) x hx
simpa using this
The check is sufficient. Every profile that passes the check is secure, for every signature scheme, initial audience and list of join requests. In particular a profile with no sealed field is secure even without authentication.
Proof. If the profile has a sealed field, it needs authenticity, so the check forces authenticated joins, and audience closure is the claim. If it has none, the property is vacuous. ∎
theorem secure_of_ok (p : Profile) (h : p.ok = true) (S : Sig) (aud₀ : List Nat)
(js : List Join) : Secure p S aud₀ js := by
intro he
rw [check_sound p h ((needsAuth_iff p).mpr he)]
exact audience_closed S aud₀ js
theorem plaintext_secure (p : Profile) (h : ∀ s ∈ p.schemes, s = .plaintext) (S : Sig)
(aud₀ : List Nat) (js : List Join) : Secure p S aud₀ js := by
intro he
exact absurd (h _ he) (by decide)
The check is necessary. For every profile the check refuses, there are a signature scheme, an initial audience and one join request, none of them forged, after which the outsider 99 reads sealed fields: the profile is not secure.
The scheme used verifies nothing and records nothing as signed, so no request is forged. A refused profile has a sealed field, so its audience is the set of readers of sealed plaintexts. An unauthenticated join ignores verification, so the claim to come from member 1 is enough to put 99 in it. Here the sealed field matters: a refused profile is exactly one with a sealed field and no authentication, and plaintext_secure shows that the same unauthenticated join breaks nothing when no field is sealed.
/-- Nothing ever verifies and nothing was signed. -/
def S₀ : Sig := ⟨fun _ _ _ => false, fun _ _ => false⟩
theorem S₀_unforgeable (j : Join) : ¬ S₀.Forged j := by
intro ⟨h, _⟩; simp [S₀] at h
theorem not_reach_99 : ¬ Reach S₀ [1] 99 := by
intro h
cases h with
| init hm => simp at hm
| add _ hs => simp [S₀] at hs
/-- The check is necessary: every profile it refuses is insecure, with no forged request. -/
theorem check_necessary (p : Profile) (h : p.ok = false) :
Scheme.encrypted ∈ p.schemes ∧ p.authentic = false ∧
(∀ j ∈ [Join.mk 1 99 0], ¬ S₀.Forged j) ∧ ¬ Secure p S₀ [1] [Join.mk 1 99 0] := by
have h' : p.needsAuth = true ∧ p.authentic = false := by
simp only [Profile.ok, Bool.or_eq_false_iff, Bool.not_eq_false'] at h; exact h
have he := (needsAuth_iff p).mp h'.1
refine ⟨he, h'.2, fun j _ => S₀_unforgeable j, ?_⟩
intro hs
have hm : 99 ∈ [Join.mk 1 99 0].foldl (joinStep p.authentic S₀) [1] := by
rw [h'.2]; decide
cases hs he 99 hm with
| inl hr => exact not_reach_99 hr
| inr hf =>
obtain ⟨j, _, _, hj⟩ := hf
exact S₀_unforgeable j hj
Per-collection composition. If every collection’s profile passes the check, every collection is secure for every signature scheme, initial audience and list of join requests, and every collection with a sealed field authenticates its joins.
theorem dbOk_sound (ps : List Profile) (h : dbOk ps = true) :
∀ p ∈ ps, p.needsAuth = true → p.authentic = true := by
intro p hp hn
simp only [dbOk, List.all_eq_true] at h
exact check_sound p (h p hp) hn
theorem dbOk_secure (ps : List Profile) (h : dbOk ps = true) :
∀ p ∈ ps, ∀ (S : Sig) (aud₀ : List Nat) (js : List Join), Secure p S aud₀ js := by
intro p hp
simp only [dbOk, List.all_eq_true] at h
exact secure_of_ok p (h p hp)
end MNI
The three properties compose for a structural reason as well. The node-side non-interference theorem holds for every gate that is a function of views, so a gate that checks signatures over ciphertexts does not affect it. The receipt chain is a function of outputs, so keeping receipts does not affect it either. Authenticity of joins, verifiability of receipts and secrecy can thus be chosen per collection. The only constraint between them is the one the check enforces. secure_of_ok and check_necessary show that, for secrecy in the audience sense defined above, this constraint is sufficient and necessary.
Limits and assumptions
- The view is public. The theorems show that outputs depend only on views and on declassified plaintexts. That a ciphertext reveals nothing about its plaintext is the encryption scheme’s indistinguishability assumption (“Probabilistic Encryption”, Journal of Computer and System Sciences, 1984), and the model does not prove it. With a deterministic scheme, ciphertext identity reveals equality of plaintexts.
- Lengths are public by choice. Lengths are part of the view. Padding to a fixed length is the case covered by
padded_view.length_leaksshows that with a view that omits lengths the statement is false, for a well-typed expression and well-typed environments. - Usage, not time. The observable is the charged vector of steps and bytes, and gas is any function of it. Wall-clock time, memory access patterns and cache behaviour of an implementation are outside the model.
- Public operation shapes. The kind of each operation, its predicate, its projection, the number of operations and the size of the store are the same in both worlds. Secret parameters belong in sealed request fields.
- Audience as a premise. The link from secrecy to authenticity is modelled as control of the audience, meaning who can join the group that receives future epoch keys. The step “the audience bounds who can read plaintexts” is a modelling premise, not a theorem about key schedules. Removal of members and the advance of epochs on removal are not modelled.
- Authenticity means signed joins. In the profile, authenticity is the verification of signatures on join requests. A write gate may also check signatures, and non-interference holds for any such gate, but no theorem here states what a gate guarantees about the origin of writes.
- Receipts bind but do not prove inclusion. Verifiability here is only the binding of the receipt chain. Inclusion proofs for individual records against a committed state are not modelled.
- A small language. The language has no loops or folds, and a run concerns one collection. Composition across collections is the per-collection check, not a theorem about a joint run over several collections. Loops and folds, and the cost bounds they would need, are not covered.
#print axioms reports propext and Quot.sound for run_ni, sealed_invisible, audience_closed, secure_of_ok, check_necessary, dbOk_sound and dbOk_secure, only propext for extract_sound, propext, Quot.sound and Classical.choice (through core simplification lemmas and case analysis) for chain_binding, and no axioms at all for peek_leaks, illtyped_leaks, pred_public, length_leaks and length_charged.
Prior work
Information-flow control and non-interference: “A Lattice Model of Secure Information Flow” (Communications of the ACM, 1976), “Security Policies and Security Models” (IEEE Symposium on Security and Privacy, 1982), “A Sound Type System for Secure Flow Analysis” (Journal of Computer Security, 1996), and the survey “Language-Based Information-Flow Security” (IEEE Journal on Selected Areas in Communications, 2003). Logical relations and dependency: “Types, Abstraction and Parametric Polymorphism” (IFIP Congress, 1983), “The SLam Calculus: Programming with Secrecy and Integrity” (POPL 1998) and “A Core Calculus of Dependency” (POPL 1999). Encryption inside information-flow type systems: “Cryptographically-Masked Flows” (SAS 2006; Theoretical Computer Science, 2008) and “Cryptographically Sound Implementations for Typed Information-Flow Security” (POPL 2008). Declassification: “A Model for Delimited Information Release” (ISSS 2003), “Robust Declassification” (IEEE CSFW 2001) and “Declassification: Dimensions and Principles” (Journal of Computer Security, 2009). Cost and timing channels: “Transforming Out Timing Leaks” (POPL 2000) and “Language-Based Control and Mitigation of Timing Channels” (PLDI 2012). Queries over encrypted data and what they leak: “Protecting Confidentiality with Encrypted Query Processing” (SOSP 2011), “Deterministic and Efficiently Searchable Encryption” (CRYPTO 2007), “Inference Attacks on Property-Preserving Encrypted Databases” (ACM CCS 2015) and “Generic Attacks on Secure Outsourced Databases” (ACM CCS 2016), the last of which uses only access patterns and result sizes. Hash chains and signatures: “How to Time-Stamp a Digital Document” (Journal of Cryptology, 1991), “A Design Principle for Hash Functions” (CRYPTO 1989), “A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks” (SIAM Journal on Computing, 1988), and, for why confidentiality without integrity fails against active adversaries, “Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm” (ASIACRYPT 2000).