PQXDH in Lean

5.2. Shared secret computation🔗

Definition5.21
Group: Core X3DH definitions and end-to-end correctness results. (7)
Hover another entry in this group to preview it.
L∃∀Nused by 1

Alice computes four DH values from her private keys and Bob's public keys: DH1 = DH(ika, SPKb) for mutual authentication (Alice's identity), DH2 = DH(eka, IKb) for mutual authentication (Bob's identity), DH3 = DH(eka, SPKb) for forward secrecy, DH4 = DH(eka, OPKb) for replay protection (when OPK is present). When OPK is absent, DH4 defaults to 0 (the group identity).

Code for Definition5.211 definition
  • def X3DH_Alice.{u_1, u_2} {FType u_1 : Type u_1A type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. } [FieldField.{u} (K : Type u) : Type uA `Field` is a `CommRing` with multiplicative inverses for nonzero elements.
    
    An instance of `Field K` includes maps `ratCast : ℚ → K` and `qsmul : ℚ → K → K`.
    Those two fields are needed to implement the `DivisionRing K → Algebra ℚ K` instance since we need
    to control the specific definitions for some special cases of `K` (in particular `K = ℚ` itself).
    See also note [forgetful inheritance].
    
    If the field has positive characteristic `p`, our division by zero convention forces
    `ratCast (1 / p) = 1 / 0 = 0`.  FType u_1] {GType u_2 : Type u_2A type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. }
      [AddCommGroupAddCommGroup.{u} (G : Type u) : Type uAn additive commutative group is an additive group with commutative `(+)`.  GType u_2] [ModuleModule.{u, v} (R : Type u) (M : Type v) [Semiring R] [AddCommMonoid M] : Type (max u v)A module is a generalization of vector spaces to a scalar semiring.
    It consists of a scalar semiring `R` and an additive monoid of "vectors" `M`,
    connected by a "scalar multiplication" operation `r • x : M`
    (where `r : R` and `x : M`) with some natural associativity and
    distributivity axioms similar to those on a ring.  FType u_1 GType u_2] (ikₐF ekₐF : FType u_1) (IKᵦG SPKᵦG : GType u_2)
      (OPKᵦOption G : OptionOption.{u} (α : Type u) : Type uOptional values, which are either `some` around a value from the underlying type or `none`.
    
    `Option` can represent nullable types or computations that might fail. In the codomain of a function
    type, it can also represent partiality.
     GType u_2) : GType u_2 ×Prod.{u, v} (α : Type u) (β : Type v) : Type (max u v)The product type, usually written `α × β`. Product types are also called pair or tuple types.
    Elements of this type are pairs in which the first element is an `α` and the second element is a
    `β`.
    
    Products nest to the right, so `(x, y, z) : α × β × γ` is equivalent to `(x, (y, z)) : α × (β × γ)`.
    
    
    Conventions for notations in identifiers:
    
     * The recommended spelling of `×` in identifiers is `Prod`. GType u_2 ×Prod.{u, v} (α : Type u) (β : Type v) : Type (max u v)The product type, usually written `α × β`. Product types are also called pair or tuple types.
    Elements of this type are pairs in which the first element is an `α` and the second element is a
    `β`.
    
    Products nest to the right, so `(x, y, z) : α × β × γ` is equivalent to `(x, (y, z)) : α × (β × γ)`.
    
    
    Conventions for notations in identifiers:
    
     * The recommended spelling of `×` in identifiers is `Prod`. GType u_2 ×Prod.{u, v} (α : Type u) (β : Type v) : Type (max u v)The product type, usually written `α × β`. Product types are also called pair or tuple types.
    Elements of this type are pairs in which the first element is an `α` and the second element is a
    `β`.
    
    Products nest to the right, so `(x, y, z) : α × β × γ` is equivalent to `(x, (y, z)) : α × (β × γ)`.
    
    
    Conventions for notations in identifiers:
    
     * The recommended spelling of `×` in identifiers is `Prod`. GType u_2
    def X3DH_Alice.{u_1, u_2} {FType u_1 : Type u_1A type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. }
      [FieldField.{u} (K : Type u) : Type uA `Field` is a `CommRing` with multiplicative inverses for nonzero elements.
    
    An instance of `Field K` includes maps `ratCast : ℚ → K` and `qsmul : ℚ → K → K`.
    Those two fields are needed to implement the `DivisionRing K → Algebra ℚ K` instance since we need
    to control the specific definitions for some special cases of `K` (in particular `K = ℚ` itself).
    See also note [forgetful inheritance].
    
    If the field has positive characteristic `p`, our division by zero convention forces
    `ratCast (1 / p) = 1 / 0 = 0`.  FType u_1] {GType u_2 : Type u_2A type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. }
      [AddCommGroupAddCommGroup.{u} (G : Type u) : Type uAn additive commutative group is an additive group with commutative `(+)`.  GType u_2] [ModuleModule.{u, v} (R : Type u) (M : Type v) [Semiring R] [AddCommMonoid M] : Type (max u v)A module is a generalization of vector spaces to a scalar semiring.
    It consists of a scalar semiring `R` and an additive monoid of "vectors" `M`,
    connected by a "scalar multiplication" operation `r • x : M`
    (where `r : R` and `x : M`) with some natural associativity and
    distributivity axioms similar to those on a ring.  FType u_1 GType u_2]
      (ikₐF ekₐF : FType u_1) (IKᵦG SPKᵦG : GType u_2)
      (OPKᵦOption G : OptionOption.{u} (α : Type u) : Type uOptional values, which are either `some` around a value from the underlying type or `none`.
    
    `Option` can represent nullable types or computations that might fail. In the codomain of a function
    type, it can also represent partiality.
     GType u_2) : GType u_2 ×Prod.{u, v} (α : Type u) (β : Type v) : Type (max u v)The product type, usually written `α × β`. Product types are also called pair or tuple types.
    Elements of this type are pairs in which the first element is an `α` and the second element is a
    `β`.
    
    Products nest to the right, so `(x, y, z) : α × β × γ` is equivalent to `(x, (y, z)) : α × (β × γ)`.
    
    
    Conventions for notations in identifiers:
    
     * The recommended spelling of `×` in identifiers is `Prod`. GType u_2 ×Prod.{u, v} (α : Type u) (β : Type v) : Type (max u v)The product type, usually written `α × β`. Product types are also called pair or tuple types.
    Elements of this type are pairs in which the first element is an `α` and the second element is a
    `β`.
    
    Products nest to the right, so `(x, y, z) : α × β × γ` is equivalent to `(x, (y, z)) : α × (β × γ)`.
    
    
    Conventions for notations in identifiers:
    
     * The recommended spelling of `×` in identifiers is `Prod`. GType u_2 ×Prod.{u, v} (α : Type u) (β : Type v) : Type (max u v)The product type, usually written `α × β`. Product types are also called pair or tuple types.
    Elements of this type are pairs in which the first element is an `α` and the second element is a
    `β`.
    
    Products nest to the right, so `(x, y, z) : α × β × γ` is equivalent to `(x, (y, z)) : α × (β × γ)`.
    
    
    Conventions for notations in identifiers:
    
     * The recommended spelling of `×` in identifiers is `Prod`. GType u_2
    Alice's DH computations. OPKᵦ is optional; when absent, DH4 = 0. 
    complete
Definition5.22
Group: Core X3DH definitions and end-to-end correctness results. (7)
Hover another entry in this group to preview it.
L∃∀Nused by 1

Bob computes the same four DH values from his private keys and Alice's public keys. The protocol is well-formed when Alice's and Bob's tuples coincide.

Code for Definition5.221 definition
  • def X3DH_Bob.{u_1, u_2} {FType u_1 : Type u_1A type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. } [FieldField.{u} (K : Type u) : Type uA `Field` is a `CommRing` with multiplicative inverses for nonzero elements.
    
    An instance of `Field K` includes maps `ratCast : ℚ → K` and `qsmul : ℚ → K → K`.
    Those two fields are needed to implement the `DivisionRing K → Algebra ℚ K` instance since we need
    to control the specific definitions for some special cases of `K` (in particular `K = ℚ` itself).
    See also note [forgetful inheritance].
    
    If the field has positive characteristic `p`, our division by zero convention forces
    `ratCast (1 / p) = 1 / 0 = 0`.  FType u_1] {GType u_2 : Type u_2A type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. }
      [AddCommGroupAddCommGroup.{u} (G : Type u) : Type uAn additive commutative group is an additive group with commutative `(+)`.  GType u_2] [ModuleModule.{u, v} (R : Type u) (M : Type v) [Semiring R] [AddCommMonoid M] : Type (max u v)A module is a generalization of vector spaces to a scalar semiring.
    It consists of a scalar semiring `R` and an additive monoid of "vectors" `M`,
    connected by a "scalar multiplication" operation `r • x : M`
    (where `r : R` and `x : M`) with some natural associativity and
    distributivity axioms similar to those on a ring.  FType u_1 GType u_2] (ikᵦF spkᵦF : FType u_1) (opkᵦOption F : OptionOption.{u} (α : Type u) : Type uOptional values, which are either `some` around a value from the underlying type or `none`.
    
    `Option` can represent nullable types or computations that might fail. In the codomain of a function
    type, it can also represent partiality.
     FType u_1)
      (IKₐG EKₐG : GType u_2) : GType u_2 ×Prod.{u, v} (α : Type u) (β : Type v) : Type (max u v)The product type, usually written `α × β`. Product types are also called pair or tuple types.
    Elements of this type are pairs in which the first element is an `α` and the second element is a
    `β`.
    
    Products nest to the right, so `(x, y, z) : α × β × γ` is equivalent to `(x, (y, z)) : α × (β × γ)`.
    
    
    Conventions for notations in identifiers:
    
     * The recommended spelling of `×` in identifiers is `Prod`. GType u_2 ×Prod.{u, v} (α : Type u) (β : Type v) : Type (max u v)The product type, usually written `α × β`. Product types are also called pair or tuple types.
    Elements of this type are pairs in which the first element is an `α` and the second element is a
    `β`.
    
    Products nest to the right, so `(x, y, z) : α × β × γ` is equivalent to `(x, (y, z)) : α × (β × γ)`.
    
    
    Conventions for notations in identifiers:
    
     * The recommended spelling of `×` in identifiers is `Prod`. GType u_2 ×Prod.{u, v} (α : Type u) (β : Type v) : Type (max u v)The product type, usually written `α × β`. Product types are also called pair or tuple types.
    Elements of this type are pairs in which the first element is an `α` and the second element is a
    `β`.
    
    Products nest to the right, so `(x, y, z) : α × β × γ` is equivalent to `(x, (y, z)) : α × (β × γ)`.
    
    
    Conventions for notations in identifiers:
    
     * The recommended spelling of `×` in identifiers is `Prod`. GType u_2
    def X3DH_Bob.{u_1, u_2} {FType u_1 : Type u_1A type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. }
      [FieldField.{u} (K : Type u) : Type uA `Field` is a `CommRing` with multiplicative inverses for nonzero elements.
    
    An instance of `Field K` includes maps `ratCast : ℚ → K` and `qsmul : ℚ → K → K`.
    Those two fields are needed to implement the `DivisionRing K → Algebra ℚ K` instance since we need
    to control the specific definitions for some special cases of `K` (in particular `K = ℚ` itself).
    See also note [forgetful inheritance].
    
    If the field has positive characteristic `p`, our division by zero convention forces
    `ratCast (1 / p) = 1 / 0 = 0`.  FType u_1] {GType u_2 : Type u_2A type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. }
      [AddCommGroupAddCommGroup.{u} (G : Type u) : Type uAn additive commutative group is an additive group with commutative `(+)`.  GType u_2] [ModuleModule.{u, v} (R : Type u) (M : Type v) [Semiring R] [AddCommMonoid M] : Type (max u v)A module is a generalization of vector spaces to a scalar semiring.
    It consists of a scalar semiring `R` and an additive monoid of "vectors" `M`,
    connected by a "scalar multiplication" operation `r • x : M`
    (where `r : R` and `x : M`) with some natural associativity and
    distributivity axioms similar to those on a ring.  FType u_1 GType u_2]
      (ikᵦF spkᵦF : FType u_1) (opkᵦOption F : OptionOption.{u} (α : Type u) : Type uOptional values, which are either `some` around a value from the underlying type or `none`.
    
    `Option` can represent nullable types or computations that might fail. In the codomain of a function
    type, it can also represent partiality.
     FType u_1)
      (IKₐG EKₐG : GType u_2) : GType u_2 ×Prod.{u, v} (α : Type u) (β : Type v) : Type (max u v)The product type, usually written `α × β`. Product types are also called pair or tuple types.
    Elements of this type are pairs in which the first element is an `α` and the second element is a
    `β`.
    
    Products nest to the right, so `(x, y, z) : α × β × γ` is equivalent to `(x, (y, z)) : α × (β × γ)`.
    
    
    Conventions for notations in identifiers:
    
     * The recommended spelling of `×` in identifiers is `Prod`. GType u_2 ×Prod.{u, v} (α : Type u) (β : Type v) : Type (max u v)The product type, usually written `α × β`. Product types are also called pair or tuple types.
    Elements of this type are pairs in which the first element is an `α` and the second element is a
    `β`.
    
    Products nest to the right, so `(x, y, z) : α × β × γ` is equivalent to `(x, (y, z)) : α × (β × γ)`.
    
    
    Conventions for notations in identifiers:
    
     * The recommended spelling of `×` in identifiers is `Prod`. GType u_2 ×Prod.{u, v} (α : Type u) (β : Type v) : Type (max u v)The product type, usually written `α × β`. Product types are also called pair or tuple types.
    Elements of this type are pairs in which the first element is an `α` and the second element is a
    `β`.
    
    Products nest to the right, so `(x, y, z) : α × β × γ` is equivalent to `(x, (y, z)) : α × (β × γ)`.
    
    
    Conventions for notations in identifiers:
    
     * The recommended spelling of `×` in identifiers is `Prod`. GType u_2
    Bob's DH computations (mirror of Alice's). 
    complete