Documentation

Provenance.Semirings.Security

The security semiring, and every Boolean algebra as an m-semiring #

The alternative security semiring S′ of Amsterdamer, Deutch and Tannen annotates a tuple with the set of clearance levels at which it may be seen: āŠ• is union, āŠ— is intersection, šŸ˜ is the empty set, šŸ™ is the whole set L of levels, the monus is set difference and Ī“ is the identity. It is š”¹^L, and nothing about it is special to sets: the construction below reads any Boolean algebra as an m-semiring, with āŠ• = āŠ”, āŠ— = āŠ“, a āŠ– b = a \ b and Ī“ = id, and S′ is that construction at Set L.

BooleanAlgebra.toSemiringWithMonus is a def and deliberately not an instance: Bool, Prop, Set α and α → Bool are all Boolean algebras in Mathlib, so a global instance would collide with the catalog's own š”¹ and š”¹[X] instances and would put a second Add, Mul and Sub on anything else Mathlib happens to make a Boolean algebra. Types that want it ask for it, as Security does below.

What the construction satisfies is every property the library states of an m-semiring at once: both idempotences, absorptivity, exclusivity, complementedness, left-distributivity of āŠ— over āŠ–, and Ī“ = id. Among m-semirings that are lattices, exclusivity is being a Boolean algebra (monus_one_isCompl, monus_one_unique_compl).

@[instance_reducible]

The commutative semiring of a Boolean algebra: join for āŠ•, meet for āŠ—. Separated from the m-semiring below so that the numerals and the natural-number cast are available while the monus part is built.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    Dependency graph
    theorem BooleanAlgebra.natCast_pos {α : Type} [BooleanAlgebra α] {n : ā„•} (hn : 0 < n) :
    ↑n = 1

    Every positive natural-number cast is šŸ™, join being idempotent.

    Dependency graph
    @[instance_reducible]

    Every Boolean algebra is an m-semiring**: join for āŠ•, meet for āŠ—, the difference for the monus, and the identity for Ī“. A def and not an instance, for the reason in this file's header.

    Equations
    • One or more equations did not get rendered due to their size.
    Instances For
      Dependency graph

      The security semiring #

      S′ L is the construction at Set L: a tuple is annotated with the set of clearance levels at which it may be seen, āŠ• collects levels, āŠ— requires them, and the monus removes them. Its own type keeps the construction's Add, Mul and Sub off Set L itself, where Mathlib's would clash.

      def Security (L : Type) :

      The alternative security semiring S′ = š”¹^L: the subsets of a set L of clearance levels.

      Equations
      Instances For
        Dependency graph
        @[instance_reducible]
        Equations
        • One or more equations did not get rendered due to their size.
        Dependency graph
        Dependency graph
        Dependency graph
        Dependency graph
        @[instance_reducible]
        Equations
        Dependency graph