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 \mapsto 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 $ab=ba=e$, where$e$ is the identity element.

A monoid $(S,*)$ relaxes the requirement of a group by removing the requirements 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} \mapsto 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 a$.

• $s’ : c_A S \mapsto S$ satisfies $s’(s(a,k))=a$ and $s(s’(j),k)=c_A a$ for any $a \in S$ and $k \in 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) \mapsto c_A S$ that is given by the following axioms:

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