algebraic_cipher_types

Source: Dev.to

Algebraic Cipher Types

Before we can define the cipher functor, we need to define the algebraic structures that we will be working with. The cipher functor defines a way to lift a monoid into a cipher monoid.

Groups and Monoids

A group is a set, $G$, together with an operation $* : G \times G \to G$ that combines any two elements $a$ and $b$ to form another element $a*b$. To qualify as a group, the set and operation, $(G, *)$, must satisfy four requirements known as the group axioms:

• Closure: For all $a,b \in G$, the result of the operation, $a*b$, is also in $G$.
• Associativity: For all $a,b,c \in G$, $(ab)c = a(bc)$.
• Identity element: There exists an element $e \in G$ such that, for every element $a \in G$, the equation $ea = ae = a$ holds. Such an element is unique, and thus one speaks of the identity element.
• Inverse element: For each $a \in G$, there exists an element $a’ \in G$ such that $a*a’ = a’*a = e$, where $e$ is the identity element.

A monoid $(S,*)$ relaxes the requirement of a group by removing the requirement of an inverse element.

Cipher Functor

In the cipher functor, we lift a monoid $(S,)$ to $c_A(S,)$, which is defined in the following way:

• $A$ is a subset of $S$.
• $s : S \times \mathbb{N} \to c_A S$ maps $S$ to representations of $S$ in $c_A S$, i.e., $s(a,k)$ maps element $a \in S$ to the $k$‑th representation of $a$ in $c_A S$.
• $s’ : c_A S \to S$ satisfies $s’(s(a,k)) = a$ and $s(s’(j),k) = c_A a$ for any $a \in S$ and $k \in \mathbb{N}$.

Typically, $s$ is generated by some other function parameterized by a secret and a fixed bit length for each representation.

$c_A(S,*,e)$ has an operation $(c_A *) : (c_A S, c_A S) \to c_A S$ that is given by the following axiom:

• Associativity: For all $x,y,z \in A$,
  $s’((c_A x * c_A y) * c_A z) = s’(c_A x * (c_A y * c_A z))$.