# Design of Ciphers based on the Geometric Structure of the Laguerre and
Minkowski Planes

Christoph Capellaro111EY EMEIA Financial Services - Cyber Security

###### Abstract

Till now geometric structures don’t play a major role in cryptography.
Gilbert, MacWilliams and Sloane [GMS74] introduced an authentication scheme in
the projective plane and showed its perfectness in the sense of Shannon
[Sha49]. In [Cap21] we introduced an encryption scheme in the Möbius plane and
showed that it fulfills Shannon’s requirement of perfectness in first
approximation and also the requirement of completeness according to Kam and
Davida [KD79]. In this paper we will apply a similar approach to define
encryption schemes in the geometries of the Laguerre plande and the Minkowski
plane. We will show that the encryption scheme in the Laguerre geometry meets
Shannon’s requirement of perfectness sharp and that the encryption scheme in
the Minkowski geometry meets this requirement in first approximation. The
Laguerre cipher also fulfills the requirement of completeness according to Kam
and Davida.

Keywords: circle geometry, Laguerre, Minkowski, cryptography, complete,
perfect

##  1 Introduction

A cryptographic transformation can be understood as an incidence relation,
whereby messages m and ciphertexts c are represented as points. The
cryptographic transformation $f$ that maps m to c is then described by a
geometric object that incises with these two points. In this paper we will
design new encryption transformations in the geometries of the Laguerre plane
and the Minkowski plane and analyze their properties.

The basic property of cycles in the Laguerre and Minkowski plane, being that
three points incise with a cycle, allow to associate one point with a message,
another point with the ciphertext and still have a degree of freedom for a
secret key. We will analyze encryption methods in the Laguerre and Minkowski
plane, namely the criteria of perfectness according to Shannon [Sha49] and the
completeness in the case that the geometry is defined over a field of
characteristic 2. Shannon’s requirement of perfectness states that basically
the result of the encryption process cannot be distinguished from a noisy
channel. Completeness according to Kam and Davida [KD79] means that, assumed
that input and output of a transformation are represented as bit vectors,
there is at least one input vector for which a change in the $i$-th bit
results in a change of the $j$-th bit of the output vector for arbitrary $i$
and $j$.

Aknowledgment. The author would like to express great gratitude to Helmut
Karzel. Without the insights in circle geometries that he shared, this paper
would not have been possible. Furthermore thank goes to Mariia Denysenko, who
with her inspiring attitude and due care of technical details supported the
completion of this paper.

##  2 Cryptographic Transformations and Cryptographic Schemes

This and the following section repeat definitions and theorems from [Cap21].
They will be required to define cryptographic schemes in the Laguerre and
Minkowski plane and to discuss their properties.

######  Definition 2.1.

Let $M$ and $C$ be sets, where $M$ is called a set of messages and $C$ a set
of ciphertexts. If there is a nonempty set of functions $F$ of the form
$F:M\to C$ with the property that every $f\in F$ is reversible, then the
elements $f\in F$ are called cryptographic transformations and $(M,C,F)$ is
called a cryptographic scheme.

######  Theorem and Definition 2.2.

A cryptographic scheme $(M,C,F)$ is called a countable infinite cryptographic
scheme, if the sets $M$, $C$ and $F$ are countable infinite. If the set of
ciphertexts $C^{\prime}$ of a cryptographic scheme
$(M^{\prime},C^{\prime},F^{\prime})$ is finite then
$(M^{\prime},C^{\prime},F^{\prime})$ is called a finite cryptographic scheme.

The proof can be found in [Cap21].

##  3 Properties of Cryptographic Schemes

######  Definition 3.1.

If $(M,C,F)$ is a cryptographic scheme, then the probability of the occurrence
of a message $m\in M$ is denoted with $\mu(m)=P(m)$ and is called a-priori
probability of the message $m$. Similarly the probability of the occurrence of
the message $m$ under the condition that $m$ is mapped to $c$ by any $f\in F$
is denoted with $\nu(m,c)=P_{c=f(m)}(m)$ and is called a-posteriori
probability of the message $m$ for a given ciphertext $c$.

######  Remark 3.2.

In the case that a cryptographic system $(M,C,F)$ is finite, relative
frequencies can be used to calculate the a-priori and a-posteriori
probabilities. Then $\mu(m)=\frac{H(m)}{|M|}$ and
$\nu(m,c)=\frac{\big{|}\\{f\in F:c=f(m)\\}\big{|}}{\sum_{m\in M}{\big{|}{f\in
F:c=f(m)}\big{|}}}$. Here $H(m)$ means the frequency of the occurrence of the
message $m$.

######  Definition 3.3.

Let $(M,C,F)$ be a cryptographic scheme for which every $c\in C$ is a possible
ciphertext and let $\mu$ and $\nu$ be its a-priori and a-posteriori
probabilities. Then $(M,C,F,\mu,\nu)$ is called perfect according to Shannon
[Sha49] as long as $\mu(m)=\nu(m,c)$ for any $m\in M$ and for any $c\in C$.

######  Remark 3.4.

If $(M,C,F)$ is finite and if $\mu(m)=\mu(m_{0})$ for any $m\in M$ then
$(M,C,F,\mu,\nu)$ is perfect as long as $\frac{1}{|M|}=\frac{\big{|}\\{f\in
F:c=f(m)\\}\big{|}}{\sum_{m\in M}{\big{|}\\{f\in F:c=f(m)\\}\big{|}}}$ for any
$m\in M$ and for any $c\in C$.

######  Definition 3.5.

Let $(M,C,F)$ be a cryptographic scheme with $M=\mathbb{Z}_{2}^{r}$ and
$C=\mathbb{Z}_{2}^{s}$. Then the cryptographic transformation $f\in F$ is
called complete according to Kam and Davida [KD79], if there is at least one
message $m_{0}=m_{0_{1}},m_{0_{2}},...,m_{0_{r}}\in M$ for every pair of
indices $i\leq r$ and $j\leq s$, where a change in the $i$-th bit of $m_{0}\in
M$ results in a change of the $j$-th bit of
$c_{0}=c_{0_{1}},c_{0_{2}},...,c_{0_{s}}=f(m_{0})\in C$. A cryptographic
scheme $(M,C,F)$ that consists exclusively of complete cryptographic
transformations is called a complete cryptographic scheme.

##  4 Brief Introduction of the Geometry of the Laguerre Plane

######  Definition 4.1.

The triple $(\boldsymbol{P},\boldsymbol{G},\boldsymbol{X})$ of points
$\boldsymbol{P}$, generators $\boldsymbol{G}$ and cycles $\boldsymbol{X})$ is
called Laguerre plane, if it satisfies following properties:

  * (L1)

$\forall{\text{\em a}}\in\boldsymbol{P}{\exists}_{1}[\,{\text{\em
a}}]\,\in\boldsymbol{G}:{\text{\em a}}\in[\,{\text{\em a}}]\,$. $[\,{\text{\em
a}}]\,$ is the generator that passes through the point a.

  * (L2)

$\forall{\text{\em a}},{\text{\em b}},{\text{\em c}}\in\boldsymbol{P}$, with
$[\,{\text{\em a}}]\,\neq[\,{\text{\em b}}]\,\neq[\,{\text{\em
c}}]\,\neq[\,{\text{\em a}}]\,\exists_{1}{\text{\em
C}}\in\boldsymbol{X}:{\text{\em a}},{\text{\em b}},{\text{\em c}}\in{\text{\em
C}}$.

  * (L3)

$\forall{\text{\em G}}\in\boldsymbol{G},\forall{\text{\em
C}}\in\boldsymbol{X}:|{\text{\em G}}\cap{\text{\em C}}|=1$.

  * (L4)

Touch axiom: $\forall{\text{\em C}}\in\boldsymbol{X},{\text{\em
a}}\in{\text{\em C}}$ and ${\text{\em
b}}\in\boldsymbol{P}\setminus\big{\\{}{\text{\em
C}}\cup[{\text{a}}]\big{\\}}{\exists}_{1}{\text{\em
D}}\in\boldsymbol{X}:{\text{\em a}},{\text{\em b}}\in{\text{\em D}}$ and
${\text{\em C}}\cap{\text{\em D}}=\\{{\text{\em a}}\\}$.

  * (L5)

$\exists{\text{\em C}}\in\boldsymbol{X}:|{\text{\em C}}|\geq 3$, there is
$|\boldsymbol{P}|>3$ and $\forall{\text{\em G}}\in\boldsymbol{G}:|{\text{\em
G}}|\geq 2$.

The Laguerre geometry can be defined as the points $\boldsymbol{P}$ on the
surface of a circular cylinder in the Euclidian space. The cycles
$\boldsymbol{X}$ of the Laguerre geometry are then the cone cuts of the
circular cylinder with all planes that are not parallel to the axis of the
cylinder. The tangents of the circular cylinder with planes touch the circular
cylinder in lines, which are the generators of the Laguerre geometry.

The Laguerre geometry of the circular cylinder can be projected into the
Euclidian plane by the use of a stereographic projection. The center of the
projection is chosen as a point of the circular cylinder, the projection plane
shall be in parallel to the axis of the cylinder and shall not contain the
projection center. If the coordinate system of the Euclidian plane is chosen
properly, the cycles of the Laguerre geometry that pass the center of the
projection are mapped to the lines in the Euclidian plane that are not
parallel to the $y$-axis. All other cycles of the cylinder are transferred to
parabolas in the Euclidian plane with axes in parallel to the $y$-axis. The
points of the Laguerre geometry that lie on the line ${\text{L}}_{0}$ passing
the center of the projection are mapped to distant points. The set of distant
points form the distant generator. Since ${\text{L}}_{0}$ is a line of the
Euclidian space, the distant generator consists of as many points as a line of
the Euclidian space. Figure 1 illustrates the stereographic projection of the
Laguerre geometry.

n${\text{p}^{\prime}}$ p Figure 1: Stereographic projection of the Laguerre
geometry.

In order to find an analytical representation of the Laguerre plane, we want
to introduce the dual numbers:

$\mathbf{D}:=\\{a+b\epsilon:a,b\in\mathbf{F}\\},\epsilon^{2}=0\\\ $

$\mathbf{D}$ is a local ring with $\mathbf{F}$ as a sub-field and
$\mathbf{F}\epsilon$ as a maximum ideal. In $\mathbf{D}$ exists an
involutorial automorphism $\overline{.\vphantom{G}}:\mathbf{D}\to\mathbf{D}$
that has the elements of $\mathbf{F}$ as fixpoints. We obtain the Laguerre
plane by closing the dual numbers with a the distant generator. We will use
the notation $\overline{\mathbf{F}}:=\mathbf{F}\cup\\{\infty\\}$ for the
closed field $\mathbf{F}$ and
$\overline{\mathbf{D}}:=\mathbf{D}\cup\\{\infty+\mathbf{F}\epsilon\\}$ for the
closure of the dual numbers.

##  5 Describing the Laguerre Plane Using Equations

With the right choice of the coordinate system, the cycles of the Laguerre
plane are represented as parables and lines in $\overline{\mathbf{D}}$. A
cycle ${\text{C}}\in\boldsymbol{X}$ is determined by the parameters
$a,b,c\in\mathbf{F}$ with $(a,b)\neq(0,0)$ and is represented by following
set:

$\big{\\{}(x,y)\in\mathbf{F}^{2}:y=ax^{2}+bx+c\big{\\}}\cup\\{\infty-a\epsilon\\}$

##  6 Describing the Laguerre Plane by the Use of Double Ratios

A cycle in the Laguerre plane that includes the points
${\text{a}},{\text{b}},{\text{c}}\in\mathbf{D}$ with
$[{\text{a}}]\,\neq[{\text{b}}]\,\neq[{\text{c}}]\,\neq[{\text{a}}]\,$ can be
represented with the following set:

$\Big{\\{}{\text{z}}\in\mathbf{D}:[{\text{z}}]\,\neq[{\text{a}}]\,\text{and}\operatorname{Dr}({\text{a}},{\text{b}},{\text{c}},{\text{z}}):=\nicefrac{{\frac{{\text{a}}-{\text{c}}}{{\text{a}}-{\text{z}}}}}{{\frac{{\text{b}}-{\text{c}}}{{\text{b}}-{\text{z}}}}}\in\mathbf{F}\Big{\\}}\cup\\{{\text{a}}\\}\cup\Big{\\{}\infty+\frac{{\text{a}}-{\text{c}}}{{\text{b}}-{\text{c}}}\epsilon\Big{\\}}$

##  7 Describing the Laguerre Plane Using Fractional Linear Functions

For the representation of the Laguerre plane with the use of fractional linear
functions we will use a representation based on the closed dual numbers
$\overline{\mathbf{D}}$ with coordinates of the field $\mathbf{F}$. Then the
cycles in the Laguerre plane are determined as the pictures of a reference
cycle, e.g. the set $\\{z\in\overline{\mathbf{F}}\\}$ regarding following
mappings $\gamma$.

$\gamma:z\mapsto\frac{{\text{a}}z+{\text{b}}}{{\text{c}}z+{\text{d}}},z\in\mathbf{F},{\text{a}},{\text{b}},{\text{c}},{\text{d}}\in\mathbf{D},{\text{a}}{\text{d}}-{\text{b}}{\text{c}}\in\mathbf{D}\setminus\mathbf{F}\epsilon\\\
\gamma(\infty)=\frac{{\text{a}}}{{\text{c}}},\gamma(-\frac{{\text{d}}}{{\text{c}}})=\infty,\,\mbox{if}\,\frac{{\text{d}}}{{\text{c}}}\in\mathbf{F}\\\
$

##  8 Combinatorial Aspects of the Laguerre Plane

In the following we will focus on a Laguerre plane
$(\boldsymbol{P},\boldsymbol{G},\boldsymbol{X})$ based on a finite field
$\mathbf{F}$ with $|\mathbf{F}|=:q$. Let be ${\text{C}}\in\boldsymbol{X}$ with
$|{\text{C}}|\geq 3$ (see (L5)), ${\text{A}},{\text{B}}\in\boldsymbol{G}$ with
${\text{A}}\neq{\text{B}}$ and
${\text{c}}\in{\text{C}}\setminus(\,{\text{A}}\cup{\text{B}})\,$. We assign
every point ${\text{a}}\in{\text{A}}$ a cycle
${\text{D}}_{\text{a}}\in\boldsymbol{X}$ with
${\text{a}}\in{\text{D}}_{\text{a}}$ in the following way: If
${\text{a}}\in{\text{C}}$, then let ${\text{D}}_{\text{a}}={\text{C}}$. If
${\text{a}}\notin{\text{C}}$, then ${\text{D}}_{\text{a}}$ shall be uniquely
defined by ${\text{D}}_{\text{a}}\cap{\text{C}}={\text{c}}$ (acc. to (L4)).
Due to properties (L3) and (L4) the mapping

$\gamma:\begin{cases}{\text{A}}\in{\text{B}}\\\
{\text{a}}\mapsto{\text{D}}_{\text{a}}\cap{\text{B}}\end{cases}$

is bijective (see figure 2).

ABCabc${\text{D}}_{\text{a}}$ Figure 2: Bijection between two generators.

Since the stereographic projection maps a generator of the Laguerre geometry
$(\boldsymbol{P},\boldsymbol{G},\boldsymbol{X})$ to a line of the affine plane
over the field $\mathbf{F}$, there are $q$ points on every generator.
Furthermore there is $|q|=|{\text{A}}|=|{\text{B}}|$ for every
${\text{A}},{\text{B}}\in\boldsymbol{G}$. With (L3) follows
$|\boldsymbol{P}|=|{\text{A}}|\cdot|{\text{C}}|$ and hence
$|{\text{C}}|=|{\text{D}}|$ for every
${\text{C}},{\text{D}}\in\boldsymbol{X}$.

Let ${\text{A}},{\text{B}},{\text{C}}$ be as defined above, and let b be a
point with ${\text{b}}\in{\text{B}}\setminus{\text{C}}$ and
${\text{E}}\in\boldsymbol{X}$ be a cycle with ${\text{b}}\in{\text{E}}$. We
assign every point ${\text{c}}\in{\text{C}}\setminus{\text{B}}$ the cycle
${\text{F}}_{\text{c}}\in\boldsymbol{X}$ with
${\text{c}}\in{\text{F}}_{\text{c}}$ and
${\text{F}}_{\text{c}}\cap{\text{E}}=\\{{\text{b}}\\}$. Basically this means
that ${\text{F}}_{\text{c}}$ touches E in b. If ${\text{c}}\in{\text{E}}$,
then let ${\text{F}}_{\text{c}}:={\text{C}}$. Figure 3 illustrates this
construction.

CABE${\text{F}}_{\text{c}}$bc Figure 3: Bijection between two generators.

According to (L4) the cycle ${\text{F}}_{\text{c}}$ is uniquely determined by
the cycle C and the points b and c. Because of (L3) the cycle
${\text{F}}_{\text{c}}$ has a common point with the generator A. Furthermore
there is
${\text{F}}_{\text{c}}\cap{\text{A}}\neq{\text{F}}_{\text{d}}\cap{\text{A}}$
for any ${\text{c}}\neq{\text{d}}$. This provides a bijection from the set of
points of ${\text{C}}\setminus\\{{\text{C}}\cap{\text{B}}\\}$ to A. Hence
$|{\text{C}}|=|{\text{A}}|+1=q+1,\forall{\text{C}}\in\boldsymbol{X}$. Together
with the results shown above we get $\boldsymbol{P}=q(q+1)$. Since a cycle is
defined by exactly three points from three different generators (L2), we get
together with (L1) as result for the number of cycles
$|\boldsymbol{X}|=q^{3}$.

##  9 Encryption in the Laguerre Plane

In [Cap94] an encryption scheme based on the Möbius plane has been introduced.
It is quite logical to transfer these results to the Laguerre plane. Again, we
will use the incidence properties, in this case in the Laguerre plane, to
create a mapping between three points representing message, cipher text and a
key. To ensure that such an incidence exists, we choose messages, cipher texts
and keys from different generators. Hence these points can never be parallel.

We want to use a Laguerre plane over a finite field ${\mathbf{F}}$ with
$|{\mathbf{F}}|\geq 3$ and hence $|\boldsymbol{G}|\geq 4$. So we select four
generators ${\text{G}}_{1},{\text{G}}_{2},{\text{G}}_{3},{\text{G}}_{4}$ of
the Laguerre plane and assign them with the different sets of a cihper system.
In this context we would like to use the notation
$({\text{a}},{\text{b}},{\text{c}})^{\circ}$ for the cycle through the three
points ${\text{a}},{\text{b}},{\text{c}}$ of the Laguerre plane which are
pairwise not parallel. Also, as a small modification to definition 2.1 we
don’t expect the transformations $F$ of the cryptographic scheme to be
reversible, but introduce a set of decryption transformations $G$ instead.

######  Definition 9.1.

A cipher system $(M,C,F,G)$ is defined in the Laguerre plane
$(\boldsymbol{P},\boldsymbol{G},\boldsymbol{X})$ as follows:

  * Messages:

$M:={\text{\em G}}_{1}$

  * Cipher texts:

$C:={\text{\em G}}_{2}$

  * Keys:

$K:={\text{\em G}}_{3}\times{\text{\em G}}_{4}$

  * Encryption functions:

$F:\begin{cases}K\times M\to C\\\ ({\text{\em k}},{\text{\em l}},{\text{\em
m}})\mapsto{\text{\em c}}:=({\text{\em k}},{\text{\em l}},{\text{\em c
}})^{\circ}\cap{\text{\em G}}_{2}\\\ \end{cases}$

  * Decryption functions:

$G:\begin{cases}K\times C\to M\\\ ({\text{\em k}},{\text{\em l}},{\text{\em
c}})\mapsto{\text{\em m}}:=({\text{\em k}},{\text{\em l}},{\text{\em
c}})^{\circ}\cap{\text{\em G}}_{1}\\\ \end{cases}$

The cipher system $(M,C,F,G)$ is called Laguerre cipher.

Due to property (L2) of the Laguerre plane there is exactly one cycle
${\text{C}}\in\boldsymbol{X}$ for any points ${\text{m}}\in M$ and
${\text{k}},{\text{l}}\in K$. Because of (L3) we know that $|{\text{C}}\cap
C|=1$. Hence the cryptographic transformation $F$ is unique. Since the
decryption function is defined analogue to the encryption function, it is also
unique.

##  10 Cryptoanalysis of the Laguerre Cipher

Let $(\boldsymbol{P},\boldsymbol{G},\boldsymbol{X})$ be a Laguerre plane over
a finite field $\mathbf{F}$. To examine the property of perfectness we want to
assume that all messages are equally distributed. The probability measures
$\mu$ and $\nu$ shall be defined as described in definition 3.3. The
probability of the occurrence of a message ${\text{m}}\in M$ is
$\mu({\text{m}})=\nicefrac{{1}}{{|\mathbf{F}|}}$, since there are
$|\mathbf{F}|$ points on a generator.

The probability $\nu({\text{m}},{\text{c}})$ that a message m belongs to a
certain ciphertext c is determined by the number of elements in the set of
cycles
${\text{K}}^{\prime}:=\\{{\text{C}}\in\boldsymbol{X}:{\text{m}},{\text{c}}\in{\text{C}}\\}$
that incide with the points ${\text{m}},{\text{c}}$ divided by the number of
elements in the set of cycles
${\text{K}}^{\prime\prime}:=\\{{\text{C}}\in\boldsymbol{X}:{\text{m}}\in{\text{C}}\\}$
that incide with m. Since a generator ${\text{G}}^{\prime}$ with
${\text{m}},{\text{c}}\notin{\text{G}}^{\prime}$ has a unique common point
with every cycle from ${\text{K}}^{\prime}$ and since ${\text{G}}^{\prime}$
has $|\mathbf{F}|$ points, we get $|{\text{K}}^{\prime}|=|\mathbf{F}|$. The
corresponding considerations about the number of cycles that pass m lead to
$|{\text{K}}^{\prime\prime}|=|\mathbf{F}|^{2}$. This leads to a probability
for the occurrence of a message of
$\mu({\text{m}})=\nicefrac{{1}}{{|\mathbf{F}|}}$ equaling the probability
$\nu({\text{m}},{\text{c}})=\nicefrac{{|\mathbf{F}|}}{{|\mathbf{F}|^{2}}}$
that the message m belongs to a certain ciphertext c. Hence the Laguerre
cipher fulfills the requirement of perfectness according to Shannon.

To examine the property of completeness according to Kam and Davida we define
a Laguerre cipher as introduced in definition 9.1 in a Laguerre plane
$(\boldsymbol{P},\boldsymbol{G},\boldsymbol{X})$ over a finite field
$\mathbf{F}:=\mathbb{Z}_{2}^{n}$. The points in $\boldsymbol{P}$ have
following coordinates:

$\begin{split}{\text{m}}&=m_{1}+m_{2}\epsilon\\\
{\text{c}}&=c_{1}+c_{2}\epsilon\\\ {\text{k}}&=k_{1}+k_{2}\epsilon\\\
{\text{l}}&=l_{1}+l_{2}\epsilon\\\ \end{split}$

We choose the generators of $(\boldsymbol{P},\boldsymbol{G},\boldsymbol{X})$
such that ${\text{m}}_{1}+\mathbf{F}\epsilon={\text{E}}_{1}$ and
${\text{c}}_{1}+\mathbf{F}\epsilon={\text{E}}_{2}$. Let also
${\text{E}}_{1},{\text{E}}_{2}$ be in the finite. Otherwise the Laguerre plane
can be transformed accordingly. Since the Laguerre cipher introduced in
definition 9.1 uses only points from ${\text{E}}_{1}$ as messages and only
points from ${\text{E}}_{2}$ as ciphertexts, the cryptographic function
$f:({\text{m}},{\text{k}},{\text{l}})\mapsto{\text{c}}$ effectively maps the
2nd coordinate $m_{2}$ of m to the 2nd coordinate $c_{2}$ of c. We can
describe these coordinages as binary vectors of length $n$.

To show the property of completeness we select two indices $i,j\in{1,2,...,n}$
and define $e_{i}$ and $e_{j}$ as the respective unit vectors in
$\mathbb{Z}_{2}^{n}$. For two points k and l on the generators
${\text{E}}_{3}$ and ${\text{E}}_{4}$ we have to find a m and c that hold
following conditions:

$({\text{k}},{\text{l}},{\text{m}})^{\circ}\cap{\text{E}}_{2}=\\{{\text{c}}\\}$
(1)

$\begin{split}({\text{k}},{\text{l}},{\text{m}}^{\prime})^{\circ}\cap{\text{E}}_{2}&=\\{{\text{c}}^{\prime}\\}\\\
{\text{m}}^{\prime}&=m_{1}+(m_{2}+e_{i})\epsilon\\\
{\text{c}}^{\prime}&=c_{1}+(c_{2}+e_{j})\epsilon\end{split}$ (2)

When we use double ratios to describe cycles in the Laguerre plane, the
equations (1) and (2) can be presented as follows:

$\begin{split}\operatorname{Dr}({\text{k}},{\text{l}},{\text{m}},{\text{c}})&\in\mathbf{F}\\\
\operatorname{Dr}({\text{k}},{\text{l}},{\text{m}^{\prime}},{\text{c}^{\prime}})&\in\mathbf{F}\end{split}$

or

$\begin{split}\frac{{\text{k}}-{\text{m}}}{{\text{k}}-{\text{c}}}&=c\cdot\frac{{\text{l}}-{\text{m}}}{{\text{l}}-{\text{c}}},c\in\mathbf{F}\\\
\frac{{\text{k}}-{\text{m}}^{\prime}}{{\text{k}}-{\text{c}}^{\prime}}&=d\cdot\frac{{\text{l}}-{\text{m}}^{\prime}}{{\text{l}}-{\text{c}}^{\prime}},d\in\mathbf{F}\end{split}$

This leads to the following conditions for $m_{2}$, $c_{2}$, $c$ and $d$:

$\displaystyle(k_{1}-m_{1})(l_{1}-c_{1})$
$\displaystyle=c\cdot(k_{1}-c_{1})(l_{1}-m_{1})$
$\displaystyle(k_{1}-m_{1})(l_{2}-c_{2})+(k_{2}-m_{2})(l_{1}-c_{1})$
$\displaystyle=c\cdot\big{(}(k_{1}-c_{1})(l_{2}-m_{2})+(k_{2}-c_{2})(l_{1}-m_{1})\big{)}$
$\displaystyle(k_{1}-m_{1})(l_{1}-c_{1})$
$\displaystyle=d\cdot(k_{1}-c_{1})(l_{1}-m_{1})$
$\displaystyle(k_{1}-m_{1})(l_{2}-c_{2}-e_{j})$
$\displaystyle+(k_{2}-m_{2}-e_{i})(l_{1}-c_{1})=$
$\displaystyle=k\cdot\big{(}(k_{1}-c_{1})(l_{2}-m_{2}-e_{i})$
$\displaystyle+(k_{2}-c_{2}-e_{j})(l_{1}-m_{1}-e_{i})\big{)}$

Values can be chosen for ${\text{m}}_{2}$, ${\text{c}}_{2}$, $c$ and $d$ to
solve this systen of linear equations.

##  11 Brief Introduction of the Geometry of the Minkowski Plane

Another circle geometry is given with the Minkowski plane. Examples are
hyperboloids in the three-dimensional projective space $\boldsymbol{P}$ over a
commutative field $\mathbf{F}$. A hyperboloid can be represented as the set of
points ${\text{p}}\in\boldsymbol{P}$, with
${\text{p}}:=\mathbf{F}^{*}(x_{1},x_{2},x_{3},x_{4})^{\top}$ and
$(x_{1},x_{2},x_{3},x_{4})\in\big{(}\mathbf{F}^{4}\big{)}^{*}$ that satisfy
the quadratic equation $x_{1}x_{4}-x_{2}x_{3}=0$. In comparison to the
circular cylinder of the Laguerre plane the hyperboloid of the Minkowski plane
has two distinguished classes of straight lines $\boldsymbol{G}_{1}$ and
$\boldsymbol{G}_{2}$ as generators. Two generators that are different from
each other don’t intersect, when they belong to the same class of generators,
and they share exactly one common point, when they belong to different
classes. The generator ${\text{G}}_{i}\in\boldsymbol{G}_{i},i=1,2$ that
contains the point p is denoted with $[{\text{p}}]_{i}$. Two points
${\text{p}}_{1}$ and ${\text{p}}_{2}$ are called connectable, when
$\left[{\text{p}_{1}}\right]_{i}\neq\left[{\text{p}_{2}}\right]_{i}$ for
$i=1,2$, otherwise they are called parallel. The set of cycles of the
Minkowski plane is determined by the figures that result from intersections
with the planes of the three-dimensional projective space $\boldsymbol{P}$
that are no tangential planes of the hyperboloid. The following definition
summarizes the properties of the Minkowski plane [KK88].

######  Definition 11.1.

The sets of points $\boldsymbol{H}$, generators
$\boldsymbol{G}_{1}\cup\boldsymbol{G}_{2}$ and cycles $\boldsymbol{X}$
constitute the Minkowski plane
$(\boldsymbol{H},\boldsymbol{G}_{1}\cup\boldsymbol{G}_{2},\boldsymbol{X})$, if
following properties are met:

  * (N1)

$\forall{\text{\em p}}\in\boldsymbol{H}{\exists}_{2}{\text{\em
G}}_{i}:{\text{\em G}}_{i}\in\boldsymbol{G}_{i},[{\text{\em
p}}]_{i}={\text{G}}_{i},i\in\\{1,2\\}$

  * (N2)

$\forall{\text{\em G}}_{1}\in\boldsymbol{G}_{1},\forall{\text{\em
G}}_{2}\in\boldsymbol{G}_{2}\exists_{1}{\text{\em
p}}\in\boldsymbol{H}:p\in{\text{\em G}}_{i},i=1,2$

  * (N3)

$\forall{\text{\em G}}\in\boldsymbol{G}_{1}\cup\boldsymbol{G}_{2}:|G|\geq 2$

  * (N4)

$\forall{\text{\em
G}}\in\boldsymbol{G}_{1}\cup\boldsymbol{G}_{2},\forall{\text{\em
C}}\in\boldsymbol{X}:|{\text{\em G}}\cap{\text{\em C}}|=1$

  * (N5)

For three pairwise connectable points ${\text{\em p}}_{1},{\text{\em
p}}_{2},{\text{\em p}}_{3}\in\boldsymbol{H}$ exists exactly one ${\text{\em
C}}\in\boldsymbol{X}$ with ${\text{\em p}}_{1},{\text{\em p}}_{2},{\text{\em
p}}_{3}\in{\text{\em C}}$.

  * (R)

Rectangle axiom: For ${\text{\em A}},{\text{\em B}},{\text{\em
C}}\in\boldsymbol{X}$ the set $\Big{\\{}\big{[}[{\text{\em
a}}]_{1}\cap{\text{\em B}}\big{]}_{2}\cap\big{[}[{\text{\em
a}}]_{2}\cap{\text{\em C}}\big{]}_{1}:{\text{\em a}}\in{\text{\em
A}}\Big{\\}}$ is a cycle in $\boldsymbol{X}$.

  * (T)

Touch axiom: $\forall{\text{\em A}}\in\boldsymbol{X},{\text{\em
a}}\in{\text{\em A}},{\text{\em b}}\in\boldsymbol{H}\setminus\big{(}{\text{\em
A}}\cup[a]_{1}\cup[a]_{2}\big{)}{\exists}_{1}{\text{\em
B}}\in\boldsymbol{X}:{\text{\em b}}\in{\text{\em B}},{\text{\em
A}}\cap{\text{\em B}}=\\{{\text{\em a}}\\}$

  * (S)

Symmetry axiom: If ${\text{\em C}},{\text{\em D}}\in\boldsymbol{X}$ are two
cycles and, if the point ${\text{\em p}}\in{\text{\em C}}\setminus{\text{\em
D}}$ fulfills the condition $\big{[}[{\text{\em p}}]_{1}\cap{\text{\em
D}}\big{]}_{2}\cap\big{[}[{\text{\em p}}]_{2}\cap{\text{\em
D}}\big{]}_{1}\in{\text{\em C}}$ then $\big{[}[{\text{\em
x}}]_{1}\cap{\text{\em D}}\big{]}_{2}\cap\big{[}[{\text{\em
x}}]_{2}\cap{\text{\em D}}\big{]}_{1}\in{\text{\em C}}$ holds for any
${\text{\em x}}\in{\text{\em C}}$.

The hyperboloid $\boldsymbol{H}$ can be projected into the Euclidean plane
$\mathbb{R}^{2}$ by means of a central projection. Therefore a point
${\text{n}}\in\boldsymbol{H}$ is chosen as the center of the projection and a
plane P of the projective space with ${\text{n}}\notin{\text{P}}$ as
projection plane. If ${\text{T}}_{\text{n}}$ is the tangential plane in the
point n, we consider
$\overset{\circ}{\text{E}}:={\text{E}}\setminus{\text{T}}_{\text{n}}$. The
generators of $\boldsymbol{H}$ are mapped to two sets of parallel lines in
$\overset{\circ}{\text{E}}$. The cycles ${\text{C}}\in\boldsymbol{X}$ that do
not pass the point n are transformed to hyperbolas with the images of the
generators in $\boldsymbol{H}$ as asymptotes. The cycles in $\boldsymbol{X}$
that pass the projection center n are mapped to the lines of
$\overset{\circ}{\text{E}}$ that are different from the images of the two sets
of generators. Figure 4 visualizes this projection.

n${\text{p}^{\prime}}$p Figure 4: Stereographic projection of the Minkowski
geometry.

Let $\mathbf{F}$ be the field of the coordinates of the three-dimensional
projective space $\boldsymbol{P}$. The points of this projective space can be
written as 2x2-matrices ${\text{M}}_{22}$ over the field $\mathbf{F}$. The set
of points can be written as
$\boldsymbol{P}:=\\{\mathbf{F}^{*}{\text{x}}:{\text{x}}\in{\text{M}}_{22}\\}$.
The subset
$\boldsymbol{H}:=\\{\mathbf{F}^{*}{\text{x}}:\operatorname{det}{\text{x}}=0\\}$
defines a hyperboloid in $\boldsymbol{P}$.

For every point $\mathbf{F}^{*}{\text{a}}\in\boldsymbol{P}$ we define
$(\mathbf{F}^{*}{\text{a}})^{\perp}:=\\{\mathbf{F}^{*}{\text{x}}\in\boldsymbol{P}:\operatorname{det}({\text{x}}+{\text{a}})=\operatorname{det}{\text{x}}+\operatorname{det}{\text{a}}\\}$
as the polar plane of the point $\mathbf{F}^{*}{\text{a}}$ regarding the
quadric $\boldsymbol{H}$. The plane $(\mathbf{F}^{*}{\text{a}})^{\perp}$ is a
tangential plane of $\boldsymbol{H}$ only, if
$\operatorname{det}{\text{a}}=0$. Since every plane of the projective space is
a polar plane for some point in the projective space, the sets
$(\mathbf{F}^{*}{\text{a}})^{\perp}\cap\boldsymbol{H}$ with
$\operatorname{det}a\neq 0$ determine all sections of $\boldsymbol{H}$ with
planes that are not tangential.

Concluding, the Minkowski plane
$(\boldsymbol{H},\boldsymbol{G}_{1}\cup\boldsymbol{G}_{1},\boldsymbol{X})$
over the commutative field $\mathbf{F}$ can be represented with following
coordinates:

$\begin{split}\boldsymbol{H}&=\big{\\{}\mathbf{F}^{*}{\text{x}}:\operatorname{det}{\text{x}}=0\big{\\}}\\\
\boldsymbol{G}_{1}&=\left\\{\left\\{\mathbf{F}^{*}\left(\begin{array}[]{cc}g_{1}x_{1}&g_{2}x_{1}\\\
g_{1}x_{2}&g_{2}x_{2}\end{array}\right):(x_{1},x_{2})\in{\mathbf{F}^{2}}^{*}\right\\}:(g_{1},g_{2})\in{\mathbf{F}^{2}}^{*}\right\\}\\\
\boldsymbol{G}_{2}&=\left\\{\left\\{\mathbf{F}^{*}\left(\begin{array}[]{cc}x_{1}g_{1}&x_{2}g_{1}\\\
x_{1}g_{2}&x_{2}g_{2}\end{array}\right):(x_{1},x_{2})\in{\mathbf{F}^{2}}^{*}\right\\}:(g_{1},g_{2})\in{\mathbf{F}^{2}}^{*}\right\\}\\\
\boldsymbol{X}&=\big{\\{}(\mathbf{F}^{*}{\text{a}})^{\perp}\cap\boldsymbol{H}:{\text{a}}\in{\text{M}}_{22},\operatorname{det}{\text{a}}\neq
0\big{\\}}\end{split}$

##  12 Describing the Minkowski Plane using Equations

The set Q defines a one-sheeted hyperboloid in the three-dimensional real
projective space $\boldsymbol{P}$.

${\text{Q}}:=\big{\\{}(x,y,z,t)\in\boldsymbol{P}:x^{2}-y^{2}+z^{2}-t^{2}=0\big{\\}}$

The stereographic projection $\sigma$ with projection center
${\text{n}}=\mathbf{F}^{*}(0,0,1,1)$ maps Q to the plane ${\text{P}}:z=0$. The
generators of the Minkowski plane are mapped to two crossing bundles of
parallel lines. If ${\text{T}}_{\text{n}}$ is the tangent plane to the
hyperboloid Q through the point n, then ${\text{T}}_{\text{n}}$ and Q
intersect in two lines that meet in the point n. These two lines have no image
in the plane P. By this reason the projection $\sigma$ is analytically
continued by identifying the image of these two lines with the two distant
generators of the Minkowski plane.

The cycles of the Minkowski plane can be described in the plane P by replacing
the Euclidean metric that is defined by the quadratic form $x^{2}+y^{2}$ with
the indefinite form $x^{2}-y^{2}$. If a suitable coordinate system is chosen
for P, a cycle C can be described in the finit as the following set of points:

${\text{C}}=\big{\\{}(x,y)\in\mathbb{R}^{2}:(x-a)(y-b)=c,a,b,c\in\mathbb{R}\big{\\}}$
(3)

Here the cycles of the Minkowski plane are of the shape of hyperbolas with
asymptotes which are parallel to the lines $y=c$ and $x=c$ with
$c\in\mathbb{R}$.

This model of the Minkowski plane can be generalized by using a field
$\mathbf{F}$ instead of the real numbers $\mathbb{R}$. In this case the cycles
of the Minkowski plane fulfill following condition:

${\text{C}}=\big{\\{}(x,y)\in\mathbf{F}^{2}:(x-a)(y-b)=c,a,b,c\in\mathbf{F}\big{\\}}$
(4)

##  13 Combinatorial Aspects of the Minkowski Plane

We consider a Minkowski plane based on a finite field $\mathbf{F}$ with
$|\mathbf{F}|=:q$ elements. From the analytical representation of the
Minkowski plane introduced in section 11 follows for the set of generators
$\overline{\boldsymbol{G}_{1}}\cup\overline{\boldsymbol{G}_{2}}$ that
$|\overline{\boldsymbol{G}_{i}}|=q+1$ for $i=1,2$. With (N2) follows for the
number of points in the Minkowski plane $|\boldsymbol{H}|=(q+1)^{2}$.
Furthermore we gain the number of cycles $|\boldsymbol{X}|=(q+1)q(q-1)$ from
properties (N1), (N2), (N4) and (N5).

##  14 Encryption based on the Minkowski Plane

The encryption scheme introduced in [Cap21] for the Möbius plane can be
transferred to the Minkowski plane
$(\boldsymbol{H},\boldsymbol{G}_{1}\cup\boldsymbol{G}_{2},\boldsymbol{X})$.
Messages and cipher texts can be identified with the set of triples of points
in $\boldsymbol{H}$. Here we have to consider the case that the point m
representing the message and the point k representing the key are parallel.
Then these two points are not connectable. In this case the cipher text can be
determined using following construction: Lets consider that
$\left[{\text{m}}\right]_{1}=\left[{\text{k}}\right]_{1}$, then we define the
associated ciphertext with $c:={\text{M}}\cap\left[{\text{k}}\right]_{2}$,
where M is determined by the three messages
${\text{m}},{\text{n}},{\text{o}}$. According to (N4) there is always such a
point of intersection (see figure 5). The corresponding practice can be
applied in case of $\left[{\text{m}}\right]_{2}=\left[{\text{k}}\right]_{2}$.

$\left[{\text{k}}\right]_{1}$$\left[{\text{k}}\right]_{2}$Ckmc Figure 5:
Encryption in the Minkowski plane with parallel key.

With these preparations we can define a ciphersystem in the Minkowski plane.
Therefore a point $\infty$ shall be distinguished in
$(\boldsymbol{H},\boldsymbol{G}_{1}\cup\boldsymbol{G}_{2},\boldsymbol{X})$.
Then we consider the derivation of the Minkowski plane in that point:

$\begin{split}\boldsymbol{H}^{\infty}&:=\boldsymbol{H}\setminus\big{(}\left[\infty\right]_{1}\cup\left[\infty\right]_{2}\big{)}\\\
\boldsymbol{X}^{\infty}&:=\Big{\\{}{\text{C}}\setminus\\{\infty\\}:{\text{C}}\in\boldsymbol{X}(\infty),\boldsymbol{X}(\infty):=\big{\\{}{\text{C}\in\boldsymbol{X}:\infty\in{\text{C}}}\big{\\}}\Big{\\}}\\\
\boldsymbol{G}_{1}^{\infty}&:=\Big{\\{}{\text{G}}\setminus\left[\infty\right]_{2}:{\text{G}}\in\boldsymbol{G}_{1}\setminus\big{\\{}\left[\infty\right]_{1}\big{\\}}\Big{\\}}\\\
\boldsymbol{G}_{2}^{\infty}&:=\Big{\\{}{\text{G}}\setminus\left[\infty\right]_{1}:{\text{G}}\in\boldsymbol{G}_{2}\setminus\big{\\{}\left[\infty\right]_{2}\big{\\}}\Big{\\}}\\\
\end{split}$

Then
$(\boldsymbol{H}^{\infty},\boldsymbol{G}_{1}^{\infty}\cup\boldsymbol{G}_{2}^{\infty}\cup\boldsymbol{X}^{\infty})$
is an affine plane. For two given points
${\text{a}},{\text{b}}\in\boldsymbol{H}^{\infty}$ with
${\text{a}}\neq{\text{b}}$ we denote $\overline{{\text{a}},{\text{b}}}$ as the
straight line uniquely determined by these two points. Furthermore the sets of
degenerated, ordinary and all hyperbolas in the affine plane shall be defined
as follows:

$\begin{split}[{\text{x}}]&:=\left[{\text{x}}\right]_{1}\cup\left[{\text{x}}\right]_{2}\forall{\text{x}}\in\boldsymbol{H}^{\infty}\\\
\big{[}\boldsymbol{H}^{\infty}\big{]}&:=\big{\\{}[{\text{x}}]\setminus[\infty]:{\text{x}\in\boldsymbol{H}^{\infty}}\big{\\}}\\\
\boldsymbol{X}_{\infty}&:=\big{\\{}{\text{X}}\setminus[\infty]:{\text{X}}\in\boldsymbol{X}\setminus\boldsymbol{X}(\infty)\big{\\}}\\\
\overline{\boldsymbol{X}}&:=\boldsymbol{X}_{\infty}\cup\big{[}\boldsymbol{H}^{\infty}\big{]}\\\
\end{split}$

With this preparation we can define a cipher system in the Minkowski plane.
For this cipher we will use straight lines as keys, however the following
definition can be generalized in a way that cycles of the Minkowski plane are
used as keys [Cap94].

######  Definition 14.1.

Let
$(\boldsymbol{H}^{\infty},\boldsymbol{G}_{1}^{\infty}\cup\boldsymbol{G}_{2}^{\infty}\cup\boldsymbol{X}^{\infty})$
be the derivation of the Minkowski plane
$(\boldsymbol{H},\boldsymbol{G}_{1}\cup\boldsymbol{G}_{2},\boldsymbol{X})$ in
the point $\infty$ and let ${\text{\em m}}_{1},{\text{\em m}}_{2},{\text{\em
m}}_{3}\in\boldsymbol{H}^{\infty}$ be three different points of the affine
plane that cannot be connected with one straight line. Then we want to make
following definitions:

  * Messages:

$\left(\begin{array}[]{c}\boldsymbol{H}^{\infty}\\\ 3\\\ \end{array}\right)$
shall denote the set of triples of points in $\boldsymbol{H}^{\infty}$. Then
the set of messages can be defined as follows:

$M:=\left\\{({\text{\em m}}_{1},{\text{\em m}}_{2},{\text{\em
m}}_{3})\in\left(\begin{array}[]{c}\boldsymbol{H}^{\infty}\\\ 3\\\
\end{array}\right):\begin{array}[]{l}\left[{\text{\em
m}}_{1}\right]\neq\left[{\text{\em m}}_{2}\right]\neq\left[{\text{\em
m}}_{3}\right]\neq\left[{\text{\em m}}_{1}\right]\\\ \nexists{\text{\em
L}}\in\boldsymbol{X}^{\infty}:\\{{\text{\em m}}_{1},{\text{\em
m}}_{2},{\text{\em m}}_{3}\\}\in{\text{\em L}}\\\ \end{array}\right\\}$

  * Cipher texts:

$C:=M$

  * Keys:

$K:=\big{\\{}({\text{\em k}}_{1},{\text{\em k}}_{2},{\text{\em
k}}_{3})\in\left(\boldsymbol{H}^{\infty}\right)^{3}\big{\\}}$ with following
properties:

    * ${\text{\em k}}_{i}\notin({\text{\em m}}_{1},{\text{\em m}}_{2},{\text{\em m}}_{3})^{\circ}$ and

    * $({\text{\em m}}_{1},{\text{\em m}}_{2},{\text{\em m}}_{3})^{\circ}\cap\overline{{\text{\em m}}_{i},{\text{\em k}}_{i}}\cap\overline{{\text{\em m}}_{j},{\text{\em k}}_{j}}=\varnothing$ for $i,j\in\\{1,2,3\\}$ and $i\neq j$

  * Encryption Funtion:

$F:K\times M\to C$

  * Encryption:

${\text{\em c}}_{i}:=\begin{cases}\overline{{\text{\em m}}_{i},{\text{\em
k}}_{i}}\cap({\text{\em m}}_{1},{\text{\em m}}_{2},{\text{\em
m}}_{3})^{\circ}\setminus\\{{\text{\em
m}}_{i}\\},&{\text{i}f}\big{|}\overline{{\text{\em m}}_{i},{\text{\em
k}}_{i}}\cap({\text{\em m}}_{1},{\text{\em m}}_{2},{\text{\em
m}}_{3})^{\circ}\big{|}=2\\\ &{\text{a}nd}\left[{\text{\em
m}}_{i}\right]\cap\left[{\text{\em k}}_{i}\right]\leq 2\\\ {\text{\em
m}}_{i},&{\text{i}f}\big{|}\overline{{\text{\em m}}_{i},{\text{\em
k}}_{i}}\cap({\text{\em m}}_{1},{\text{\em m}}_{2},{\text{\em
m}}_{3})^{\circ}\big{|}=1\\\ &{\text{a}nd}\left[{\text{\em
m}}_{i}\right]\cap\left[{\text{\em k}}_{i}\right]\leq 2\\\ \left[{\text{\em
k}}_{i}\right]_{2}\cap({\text{\em m}}_{1},{\text{\em m}}_{2},{\text{\em
m}}_{3})^{\circ},&{\text{i}f}\left[{\text{\em
m}}_{i}\right]_{1}=\left[{\text{\em k}}_{i}\right]_{1}\\\ \left[{\text{\em
k}}_{i}\right]_{1}\cap({\text{\em m}}_{1},{\text{\em m}}_{2},{\text{\em
m}}_{3})^{\circ},&{\text{i}f}\left[{\text{\em
m}}_{i}\right]_{2}=\left[{\text{\em k}}_{i}\right]_{2}\\\ \end{cases}$

  * Decryption Funtion:

$G:K\times C\to M$

  * Decryption:

${\text{\em m}}_{i}:=\begin{cases}\overline{{\text{\em c}}_{i},{\text{\em
k}}_{i}}\cap({\text{\em c}}_{1},{\text{\em c}}_{2},{\text{\em
c}}_{3})^{\circ}\setminus\\{{\text{\em
c}}_{i}\\},&{\text{i}f}\big{|}\overline{{\text{\em c}}_{i},{\text{\em
k}}_{i}}\cap({\text{\em c}}_{1},{\text{\em c}}_{2},{\text{\em
c}}_{3})^{\circ}\big{|}=2\\\ &{\text{a}nd}\left[{\text{\em
c}}_{i}\right]\cap\left[{\text{\em k}}_{i}\right]\leq 2\\\ {\text{\em
c}}_{i},&{\text{i}f}\big{|}\overline{{\text{\em c}}_{i},{\text{\em
k}}_{i}}\cap({\text{\em c}}_{1},{\text{\em c}}_{2},{\text{\em
c}}_{3})^{\circ}\big{|}=1\\\ &{\text{a}nd}\left[{\text{\em
c}}_{i}\right]\cap\left[{\text{\em k}}_{i}\right]\leq 2\\\ \left[{\text{\em
k}}_{i}\right]_{2}\cap({\text{\em c}}_{1},{\text{\em c}}_{2},{\text{\em
c}}_{3})^{\circ},&{\text{i}f}\left[{\text{\em
c}}_{i}\right]_{1}=\left[{\text{\em k}}_{i}\right]_{1}\\\ \left[{\text{\em
k}}_{i}\right]_{1}\cap({\text{\em c}}_{1},{\text{\em c}}_{2},{\text{\em
c}}_{3})^{\circ},&{\text{i}f}\left[{\text{\em
c}}_{i}\right]_{2}=\left[{\text{\em k}}_{i}\right]_{2}\\\ \end{cases}$

This cipher system is called Minkowski cipher.

##  15 Cryptoanalysis of the Minkowski Cipher

To analyze the property of perfectness according to definition 3.3 for the
Minkowski cipher, we consider the Minkowski plane
$(\boldsymbol{H},\boldsymbol{G}_{1}\cup\boldsymbol{G}_{2},\boldsymbol{X})$
over a finite field $\mathbf{F}$ with $q:=|\mathbf{F}|$ elements. When we
select a point $\infty\in\boldsymbol{X}$, we get an affine plane
$(\boldsymbol{H}^{\infty},\boldsymbol{G}_{1}^{\infty}\cup\boldsymbol{G}_{2}^{\infty}\cup\boldsymbol{X}^{\infty})$
as the derivation of the Minkowski plane in the point $\infty$. Let
$({\text{m}}_{1},{\text{m}}_{2},{\text{m}}_{3})\in M$ be a message from the
set of messages as defined in definition 14.1. Then there exists exactly one
cycle
$({\text{m}}_{1},{\text{m}}_{2},{\text{m}}_{3})^{\circ}\in\boldsymbol{X}_{\infty}$.

To show the perfectness of the Minkowski cipher, we look at the encryption of
the message points ${\text{m}}_{1},{\text{m}}_{2},{\text{m}}_{3}$ that all lie
on the same cycle C of the Minkowski plane. Probability measures $\mu$ and
$\nu$ as introduced in definition 3.1 shall be defined. We will further assume
that all messages occur with the same probability. The number of possible keys
that can be used to encrypt ${\text{m}}_{i}$ to ${\text{c}}_{i}$ is determined
by the conditions for the set of keys $K$ as defined in definition 14.1.

We look at the encryption of the message point ${\text{m}}_{1}$. The message
$({\text{m}}_{1},{\text{m}}_{2},{\text{m}}_{3})$ determines the hyperbola
${\text{H}}:=({\text{m}}_{1},{\text{m}}_{2},{\text{m}}_{3})^{\circ}\in\boldsymbol{X}_{\infty}$.
The message point ${\text{m}}_{1}$ can be one of the $q-1$ points of the
hyperbola H. Hence the probability for the occurrence of ${\text{m}}_{1}$ is
$\mu({\text{m}}_{1})=\nicefrac{{1}}{{(q-1)}}$.

The set $K_{1}$ of keys of the Minkowski cipher that can be used to encrypt
${\text{m}}_{1}$ is described by the set of all points in the affine plane
that are not on the hyperbola H, i.e.
$\boldsymbol{X}_{\infty}\setminus{\text{H}}$. Hence
$|{\text{K}}_{1}|=q^{2}-(q-1)$. To find the number of keys that can encrypt
the message ${\text{m}}_{1}$ to the cipher text ${\text{c}}_{1}$ we have to
distinguish two cases.

  * ${\text{m}}_{1}={\text{c}}_{1}$

Every point of the tangent to the hyperbola H through the point
${\text{c}}_{1}$ except the point ${\text{c}}_{1}$ itself is a possible key.
Hence $\big{|}\\{f\in F:({\text{m}}_{1},{\text{c}}_{1})\subset
f\\}\big{|}=q-1$.

  * ${\text{m}}_{1}\neq{\text{c}}_{1}$

All points of the line $\overline{\vphantom{l}{\text{\em m}}_{1},{\text{\em
c}}_{1}}$ except ${\text{m}}_{1}$ and ${\text{c}}_{1}$ and the points
$\left[{\text{m}}_{1}\right]_{1}\cap\left[{\text{c}}_{1}\right]_{2}$ and
$\left[{\text{m}}_{1}\right]_{2}\cap\left[{\text{c}}_{1}\right]_{1}$ are
possible keys. Hence $\big{|}\\{f\in F:({\text{m}}_{1},{\text{c}}_{1})\subset
f\\}\big{|}=q$.

Altogether we found in the case ${\text{m}}_{1}={\text{c}}_{1}$ the
a-posteriori probability
$\nu({\text{m}}_{1},{\text{c}}_{1})=\frac{q-1}{q^{2}-q+1}$ and in the case
${\text{m}}_{1}\neq{\text{c}}_{1}$ the a-posteriori probability
$\nu({\text{m}}_{1},{\text{c}}_{1})=\frac{q}{q^{2}-q+1}$. As the a-priori
probability for the encryption of ${\text{m}}_{1}$ holds
$\mu({\text{m}}_{1})=\frac{1}{q-1}$ we can conclude that the encryption of the
first message point ${\text{m}}_{1}$ is perfect in first approximation for
large $q$.

We continue with the analysis of the encryption of the message point
${\text{m}}_{2}$. Since the three message points
${\text{m}}_{1},{\text{m}}_{2},{\text{m}}_{3}$ determine a unique cycle in
$\boldsymbol{X}_{\infty}$, we know that ${\text{m}}_{2}\neq{\text{m}}_{1}$.
Hence we obtain an a-priori probability of
$\mu({\text{m}}_{2})=\nicefrac{{1}}{{(q-2)}}$. Due to the condition given for
the selection of keys in definition 14.1, the set of keys $K_{2}$ for the
encryption of ${\text{m}}_{2}$ is reduced about those keys that would map
${\text{m}}_{2}$ to ${\text{m}}_{1}$ or ${\text{c}}_{1}$. Again the two cases
${\text{m}}_{1}={\text{c}}_{1}$ and ${\text{m}}_{1}\neq{\text{c}}_{1}$ need to
be distinguished. In case of ${\text{m}}_{1}={\text{c}}_{1}$ there is
$K_{2}=K_{1}\setminus\left\\{\overline{\vphantom{l}{\text{\em
m}}_{1},{\text{\em m}}_{2}}\right\\}$ and hence
$|K_{2}|=q^{2}-q+1-q=(q-1)^{2}$. In case of ${\text{m}}_{1}\neq{\text{c}}_{1}$
we gain $K_{2}=K_{1}\setminus\left\\{\overline{\vphantom{l}{\text{\em
m}}_{1},{\text{\em m}}_{2}},\overline{\vphantom{l}{\text{\em
m}}_{2},{\text{\em c}}_{1}}\right\\}$ leading to
$|K_{2}|=q^{2}-q+1-q-q=q^{2}-3q+1$.

For the determination of the a-posteriori probabilities for the encryption of
${\text{m}}_{2}$ the cases ${\text{m}}_{2}={\text{c}}_{2}$ and
${\text{m}}_{2}\neq{\text{c}}_{2}$ have to be distinguished:

  * ${\text{m}}_{2}={\text{c}}_{2}$:

Every point of the tangent to the hyperbola H through the point
${\text{c}}_{2}$ is a possible key. Hence $\big{|}\big{\\{}f\in
F:({\text{m}}_{2},{\text{c}}_{2}\subset f)\big{\\}}\big{|}=q-1$.

  * ${\text{m}}_{2}\neq{\text{c}}_{2}$:

Any point of the line through ${\text{m}}_{2}$ and ${\text{c}}_{2}$ except the
two points ${\text{m}}_{2}$ and ${\text{c}}_{2}$ themselves and the points
$\left[{\text{m}}_{2}\right]_{1}\cap\left[{\text{c}}_{2}\right]_{2}$ and
$\left[{\text{m}}_{2}\right]_{2}\cap\left[{\text{c}}_{2}\right]_{1}$ are
possible keys. Hence $\big{|}\big{\\{}f\in
F:({\text{m}}_{2},{\text{c}}_{2}\subset f)\big{\\}}\big{|}=q$.

The following table summarizes the resulting a-priori and a-posteriori
probabilities for the encryption of ${\text{m}}_{2}$:

Case | A-priori probability | A-posteriori probability
---|---|---
${\text{m}}_{1}={\text{c}}_{1}$,${\text{m}}_{2}={\text{c}}_{2}$ | $\mu({\text{m}}_{2})=\frac{1}{q-2}$ | $\nu({\text{m}}_{2},{\text{c}}_{2})=\frac{1}{q-1}$
${\text{m}}_{1}={\text{c}}_{1}$,${\text{m}}_{2}\neq{\text{c}}_{2}$ | $\mu({\text{m}}_{2})=\frac{1}{q-2}$ | $\nu({\text{m}}_{2},{\text{c}}_{2})=\frac{q}{(q-1)^{2}}$
${\text{m}}_{1}\neq{\text{c}}_{1}$,${\text{m}}_{2}={\text{c}}_{2}$ | $\mu({\text{m}}_{2})=\frac{1}{q-2}$ | $\nu({\text{m}}_{2},{\text{c}}_{2})=\frac{q-1}{q^{2}-3q+1}$
${\text{m}}_{1}\neq{\text{c}}_{1}$,${\text{m}}_{2}\neq{\text{c}}_{2}$ | $\mu({\text{m}}_{2})=\frac{1}{q-2}$ | $\nu({\text{m}}_{2},{\text{c}}_{2})=\frac{q}{q^{2}-3q+1}$

Hence the encryption of the message point ${\text{m}}_{2}$ is also
approximately perfect for large $q$.

The a-priori probability for the encryption of ${\text{m}}_{3}$ is
$\mu({\text{m}}_{3})=\nicefrac{{1}}{{(q-3)}}$. The following table shows also
the a-posteriori probabilities:

Case | A-priori probability | A-posteriori probability
---|---|---
${\text{m}}_{1}={\text{c}}_{1}$,${\text{m}}_{2}={\text{c}}_{2}$,${\text{m}}_{3}={\text{c}}_{3}$ | $\mu({\text{m}}_{2})=\frac{1}{q-3}$ | $\nu({\text{m}}_{3},{\text{c}}_{3})=\frac{q-1}{q^{2}-3q+1}$
${\text{m}}_{1}={\text{c}}_{1}$,${\text{m}}_{2}={\text{c}}_{2}$,${\text{m}}_{3}\neq{\text{c}}_{3}$ | $\mu({\text{m}}_{2})=\frac{1}{q-3}$ | $\nu({\text{m}}_{3},{\text{c}}_{3})=\frac{q}{q^{2}-3q+1}$
${\text{m}}_{1}={\text{c}}_{1}$,${\text{m}}_{2}\neq{\text{c}}_{2}$,${\text{m}}_{3}={\text{c}}_{3}$ | $\mu({\text{m}}_{2})=\frac{1}{q-3}$ | $\nu({\text{m}}_{3},{\text{c}}_{3})=\frac{q-1}{q^{2}-4q+1}$
${\text{m}}_{1}={\text{c}}_{1}$,${\text{m}}_{2}\neq{\text{c}}_{2}$,${\text{m}}_{3}\neq{\text{c}}_{3}$ | $\mu({\text{m}}_{2})=\frac{1}{q-3}$ | $\nu({\text{m}}_{3},{\text{c}}_{3})=\frac{q}{q^{2}-4q+1}$
${\text{m}}_{1}\neq{\text{c}}_{1}$,${\text{m}}_{2}={\text{c}}_{2}$,${\text{m}}_{3}={\text{c}}_{3}$ | $\mu({\text{m}}_{2})=\frac{1}{q-3}$ | $\nu({\text{m}}_{3},{\text{c}}_{3})=\frac{q-1}{q^{2}-4q+1}$
${\text{m}}_{1}\neq{\text{c}}_{1}$,${\text{m}}_{2}={\text{c}}_{2}$,${\text{m}}_{3}\neq{\text{c}}_{3}$ | $\mu({\text{m}}_{2})=\frac{1}{q-3}$ | $\nu({\text{m}}_{3},{\text{c}}_{3})=\frac{q}{q^{2}-4q+1}$
${\text{m}}_{1}\neq{\text{c}}_{1}$,${\text{m}}_{2}\neq{\text{c}}_{2}$,${\text{m}}_{3}={\text{c}}_{3}$ | $\mu({\text{m}}_{2})=\frac{1}{q-3}$ | $\nu({\text{m}}_{3},{\text{c}}_{3})=\frac{q-1}{q^{2}-5q+1}$
${\text{m}}_{1}\neq{\text{c}}_{1}$,${\text{m}}_{2}\neq{\text{c}}_{2}$,${\text{m}}_{3}\neq{\text{c}}_{3}$ | $\mu({\text{m}}_{2})=\frac{1}{q-3}$ | $\nu({\text{m}}_{3},{\text{c}}_{3})=\frac{q}{q^{2}-5q+1}$

Also the last encryption step is approximately perfect for large $q$.

To show the completeness of the Minkowski cipher in the sense of definition
3.5, we will look at the special case of a number field $\mathbf{F}$ with
$\operatorname{char}\mathbf{F}=2$. The points
${\text{p}}\in\boldsymbol{H}^{\infty}$ can then be described in the form
${\text{p}}(x,y)$ and $x\in\mathbb{Z}_{2}^{n}$, $y\in\mathbb{Z}_{2}^{n}$. A
message of $2n$ bits length can be understood as the point ${\text{p}}(x,y)$
with coordinates $x$ and $y$. The $i$-th bit of the message shall be the
$i$-th position in the representation of the point ${\text{p}}(x,y)$, which
would be the $i$-th component of the vector $x$ for $i=1,...,n$ and the
$(i-n)$-th component of the vector $y$ for $i=n+1,...,2n$.

Let m be a message point and c be the corresponding cipher text point when
using the key point k. The encryption is complete in the sense of definition
3.5, if there is a representation of m where a change in position $j$ of c is
caused by a change in position $i$ of m, $i,j\in\\{1,2,...,2n\\}$.

Two cases have to be considered. The indices $i$ and $j$ may affect the same
coordinate of both m and c. Without restricting generality we assume the
$x$-coordinate. Alternatively, the first index $i$ may affect one coordinate,
say the $x$-coordinate of m, the second index $j$ may then affect the
$y$-coordinate of c.

We have a look at the second case first. Let ${\text{m}}(x,y)$ and
${\text{c}}(u,v)$ be the message and ciphertext points and their coordinates.
Furthermore, let $e_{i}$, $i\in\\{1,...,n\\}$ be the unit vectors in
$\mathbb{Z}_{2}^{n}$. We transform the index $j$ to $j\rightarrow j-n$. Then
${\text{m}}^{\prime}(x+e_{i},y)$ and ${\text{c}}^{\prime}(u,v+e_{j})$ are the
message and ciphertext points with changes in positions $i$ and $j$.

It has to be shown that for any key k it is possible to find two points
${\text{m}},{\text{c}}$ as message and cipher text in a way that the
encryption function $f\in F$ holds $f({\text{k}},{\text{m}})={\text{c}}$ and
$f({\text{k}},{\text{m}}^{\prime})={\text{c}}^{\prime}$. Due to the definition
of the encryption function in definition 14.1 the cases
$[{\text{m}}]\cap[{\text{k}}]\leq 2$, $[{\text{m}}]_{1}=[{\text{k}}]_{1}$ and
$[{\text{m}}]_{2}=[{\text{k}}]_{2}$ need to be distinguished. Without
restricting generality we will assume that ${\text{k}}=(0,0)$, otherwise the
Minkowski plane can be transformed accordingly.

  * ${[{\text{m}}]}\cap{[{\text{k}}]}\leq 2$

Due to the way, the keys of the Minkowski cipher have been chosen in
definition 14.1, we have to find two lines ${\text{K}},{\text{K}}^{\prime}$ in
$\boldsymbol{G}_{1}^{\infty}\cup\boldsymbol{G}_{2}^{\infty}\cup\boldsymbol{X}^{\infty}$
over the field $\mathbb{Z}_{2}^{n}$ with
${\text{m}},{\text{c}},{\text{k}}\in{\text{K}}$ and
${\text{m}}^{\prime},{\text{c}}^{\prime},{\text{k}}\in{\text{K}}^{\prime}$.

Our assertion is equal to

$\begin{split}\operatorname{det}({\text{m}},{\text{c}})&=0\\\
\operatorname{det}({\text{m}}^{\prime},{\text{c}}^{\prime})&=0\end{split}$ (5)

Substituting the coordinates for
${\text{m}},{\text{m}}^{\prime},{\text{c}},{\text{c}}^{\prime}$ results in:

$\begin{split}xv-uy&=0\\\ xv+xe_{j}+ve_{i}+e_{i}e_{j}-uy&=0\end{split}$ (6)

Or:

$\begin{split}xv-uy&=0\\\ xe_{j}+ve_{i}+e_{i}e_{j}&=0\end{split}$ (7)

It is easy to provide coordinates for ${\text{m}}(x,y)$ and ${\text{c}}(u,v)$
that satisfy these equations.

  * ${[{\text{m}}]}_{1}={[{\text{k}}]}_{1}$

According to the construction of the encryption function in definition 14.1
the cipher text points ${\text{c}},{\text{c}}^{\prime}$ are both on the line
$[{\text{k}}]_{2}$. So the conditions in equation (5) are met.

  * ${[{\text{m}}]}_{2}={[{\text{k}}]}_{2}$

It follows that c is on $[{\text{k}}]_{1}$. So the first condition of equation
(5) is met. To fulfill also the seconde one, we have to find a line
${\text{K}}^{\prime}$ with
${\text{m}}^{\prime},{\text{c}}^{\prime},{\text{k}}\in{\text{K}}^{\prime}$.
Again values can be found for m and c so that following equation is fulfilled:

$\operatorname{det}({\text{m}}^{\prime},{\text{c}}^{\prime})=0$ (8)

This concludes the examination of the case that the indices $i$ and $j$ affect
different coordinates of m and c.

To show the first case we again assume that the two points ${\text{m}}(x,y)$
and ${\text{c}}(u,v)$ and their coordinates as given. Let now
${\text{m}}^{\prime}(x+e_{i},y)$ and ${\text{c}}^{\prime}(u+e_{j},v)$ be the
altered points. Again the three different ways of encryption need to be
distinguished:

  * ${[{\text{m}}]}\cap{[{\text{k}}]}\leq 2$

Once again it has to be shown that condition (5) is fulfilled. In analogy to
the procedure shown above we reach following conditions:

$\begin{split}xv-uy&=0\\\ xv+e_{i}v-yu-ye_{j}&=0\end{split}$ (9)

Which can be simplified to:

$\begin{split}xv-uy&=0\\\ e_{i}v-ye_{j}&=0\end{split}$ (10)

Again it is easy to find suitable points m and c to meet these conditions for
all possible $i,j$.

  * ${[{\text{m}}]}_{1}={[{\text{k}}]}_{1}$

In this case the message has the coordinates ${\text{m}}(x,0)$. From
definition 14.1 of the Minkowski cipher follows that the cipher text has the
coordinates ${\text{c}}(0,v)$. Hence the condition (5) leads to the following:

$\begin{split}xv&=0\\\ xv+e_{i}v&=0\end{split}$ (11)

Since both $x$ and $v$ cannot be $0$ due to the requirements for the keys of
the Minkowski cipher in definition 14.1, equation (11) has no legitimate
solution.

  * ${[{\text{m}}]}_{2}={[{\text{k}}]}_{2}$

In this case the message has the coordinates ${\text{m}}(0,y)$. From
definition 14.1 of the Minkowski cipher follows that the cipher text has the
coordinates ${\text{c}}(u,0)$. Hence the condition (5) leads to the following:

$(0+e_{i})0-y(u+e_{j})=0$ (12)

Since $y\neq 0$ and $u\neq-e_{j}$, as ${\text{c}}^{\prime}\neq{\text{k}}$ due
to the requirements for the keys of the Minkowski cipher in definition 14.1,
equation (12) has no legitimate solution.

As a summary we showed that the Minkowski cipher with the encryption functions
introduced in definition 14.1 is not complete in accordance with definition
3.5.

##  16 Resume and Outlook

We introduced encryption functions on the geometric structures of the Laguerre
and the Minkowski geometry and showed that the former fulfills both the
requirements of perfectness in the sense of Shannon [Sha49] and completeness
according to [KD79]. The latter is also perfect in first approximation but
doesn’t have the property of compleness, at least when using the encryption
functions as defined in this paper. Further research can be done in the
Minkowski geometry to find improved encryption functions. One way would be to
apply a similar approach to that one used in the Laguerre geometry, i.e.
select generators as sets of possible messages and ciphertexts.

## References

  * [Beu88] A. Beutelspacher, Enciphered Geometry, Some Applications of Geometry in Cryptography, Annals of Discrete Mathematics 37 (1988) 59-68, Elsevier Science Publishers B.V. (North-Holland).
  * [BR92] A. Beutelspacher, U. Rosenbaum, Projektive Geometrie, Vieweg, Braunschweig, Wiesbaden, 1992.
  * [Cap94] C. Capellaro, Anwendungen endlicher Kreisgeometrien in der Kryptologie, Mathematisches Institut der Technischen Universität München, 1994.
  * [Cap21] C. Capellaro, Design of Ciphers based on the Geometric Structure of the Möbius Plane, arXiv:2102.10321 [cs.CR].
  * [GMS74] E. N. Gilbert, F. J. MacWilliams and N. J. A. Sloane, Codes Which Detect Deception, Bell Sys. Tech. J., 53 (1974), 405-424.
  * [KD79] J. B. Kam, G. I. Davida, Structures Design of Substitution-Permutation Encryption Networks, IEEE Trans. Computers, 28 (1979), 747-753.
  * [KK88] H. Karzel, H.-J. Kroll, Geschichte der Geometrie seit Hilbert, Wissenschaftliche Buchgesellschaft Darmstadt, 1988.
  * [Sha49] C. E. Shannon, Communication Theory of Secrecy Systems, Bell Sys. Tech. J., 28 (1949), 656-715.
  * [Ve26] G. S. Vernam, Cipher printing telegraph systems for secret wire and radio telegraphic communications, J. AIEE, 45, 1926, 109-115.