algebraic_cipher_types

#education #networksec

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$, $(a*b)c = a(b*c)$.
Identity element: There exists an element $e \in G$ such that, for every
element $a \in G$, the equation $e*a = a*e = 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*b=b*a=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: