# Design of Ciphers based on the Geometric Structure of the Möbius Plane

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 this paper we will show that this authentication scheme also
fulfills the requirement of completeness according to Kam and Davida [KD79]
and we will extend the application of geometric structures in cryptography by
introducing an encryption scheme in the Möbius plane. We will further examine
its properties, showing that it also fulfills the requirement of completeness
and Shannon’s requirement of perfectness in first approximation. The results
of this paper can be used to define similar encryption schemes in the circle
geometries of Laguerre and Minkowski.

Keywords: circle geometry, Möbius, cryptography, complete, perfect, optimal
key length

##  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 with the circle geometry of the Möbius
plane and analyze their properties.

Quite often the security of cryptographic algorithms is dependent on either
the fact that no efficient algorithm is known to solve a certain mathematical
problem or they use mappings that show very little structure. Examples for the
former are asymmetric algorithms like RSA or the discrete logarithm. The
latter includes e.g. symmetric algorithms like Feistel ciphers. Little
research has been done on the applicability of geometric structures in
cryptography. Gilbert, MacWilliams and Sloane showed that an authentication
scheme can be defined in the projective plane ([GMS74] and [Beu88]). In the
case that this projective plane is defined over a finite field, this
authentication scheme is perfect in the sense of Shannon, i.e. the uncertainty
of the plaintext after observing the ciphertext is equal to the a-priori
uncertainty about the plaintext [Sha49].

With the use of other incidence relationships, in this case based upon the
circle geometry of the Möbius plane, we will demonstrate that the definition
of encryption transformations is possible. The basic property of circles,
being that three points incise with a circle, 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 Möbius
plane and will be able to show that these encryption methods fulfill the
criteria of completeness in the case that the geometry is defined over a field
of characteristic 2. 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$. Encryption transformations based on Möbius are in first
approximation perfect. Strategies for key selection are introduced that
provide optimal key length for a perfect encryption method, meaning that the
size of the key does not exceed the size of the message, as long as padding is
ignored.

Acknowledgment. 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

######  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.

###### Proof.

The finiteness of the sets $M^{\prime}$ and $F^{\prime}$ follow immediately
from the finiteness of $C^{\prime}$ and from the fact that all cryptographic
transformations $f^{\prime}\in F^{\prime}$ are injective. ∎

##  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$.

Another well-known property for cryptographic schemes is the completeness
according to Kam and Davida which is defined for cryptographic schemes based
on binary strings.

######  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 Authentication Schemes

######  Definition 4.1.

Let $(M,C,A)$ be a cryptographic scheme. Let $\mu$ further be a measure on $C$
that fulfills the condition that $\mu(a(C))\ll\mu(C)$ for every $a\in A$. Then
$(M,C,A)$ is called authentication scheme, the ciphertexts $c\in C$ are called
authenticated messages and the transformations $a\in A$ are called
authentications.

######  Remark 4.2.

The authentications $a\in A$ do not necessarily need to be injective. An
authenticated message $c\in C$ is verified with a function
$\nu:C\to\\{true,false\\}$ with $\nu(c)=true$, if $c\in a(M)$ and
$\nu(c)=false$, if $c\notin a(M)$.

So an authenticated message $c\in C$ is accepted as authentic as soon as $c\in
a(M)$. This is the motivation for the condition on the authentications $a\in
A$ introduced in Definition 4.1, which ensures that only a small subset of
authenticated messages is accepted as authentic.

######  Definition 4.3.

An authentication scheme $(M,C,A)$ is called Cartesian, if any $a\in A$ is
injective and $a_{1}(M)\cap a_{2}(M)=\varnothing$ for any $a_{1},a_{2}\in A$
and $\bigcup_{a\in A}a(M)=C$.

For a Cartesian authentication scheme based on countable sets $C$ and $A$
counting can be defined as the measure $\mu$ on $C$ and $A$. Then the theorem
of Gilbert, MacWilliams and Sloane [GMS74] can be written as follows.

######  Theorem 4.4.

Let $n_{0}=\nu(A)$ be the number of authentications in a Cartesian
authentication scheme $(M,C,A)$ and let $c\in C$ be a randomly chosen
authenticated message, then the following holds:

$\nu(\\{a\in A:\exists m\in M\text{\em and }c=a(m)\\})\geq\sqrt{n_{0}}$

A proof of theorem 4.4 for an authentication scheme based on projective planes
which has been introduced in [GMS74] is given below, a general proof can be
found e.g. in [BR92].

######  Definition 4.5.

A Cartesian authentication scheme $(M,C,A)$ with $n_{0}=\nu(A)$ for which
theorem 4.4 is fulfilled sharply, is called perfect.

##  5 Authentication Schemes Based on Projective Planes

In this section we use some well-known facts about projective planes. The
corresponding proofs can be found in the literature, e.g. in [KK88] or [BR92].

######  Definition 5.1.

An incidence space $(\boldsymbol{P},\boldsymbol{L})$ of points
$\boldsymbol{P}$ and lines $\boldsymbol{L}$ and at least 3 different points in
$\boldsymbol{P}$ is called a projective plane, if each line consists of at
least 3 points and any two lines of $\boldsymbol{L}$ intersect in exactly one
point.

######  Definition 5.2.

A projective plane is finite, if its set of points is finite.

######  Remark 5.3.

All lines in a finite projective plane have the same number of points. A
projective plane with lines that consist of $q+1$ points is called a
projective plane of order $q$.

######  Definition and Theorem 5.4.

Let $(\boldsymbol{P},\boldsymbol{L})$ be a finite projective plane and
${\text{\em L}}_{0}\in\boldsymbol{L}$ be a line in
$(\boldsymbol{P},\boldsymbol{L})$. An authentication scheme $(M,C,A)$ can be
defined in $(\boldsymbol{P},\boldsymbol{L})$ as follows: $M$ is the set of all
points on ${\text{\em L}}_{0}$ and $C$ the set of all lines of
$\boldsymbol{L}\setminus{\text{\em L}}_{0}$. In order to describe the set of
authentications $A$ we define $K$ as the set of points in
$\boldsymbol{P}\setminus{\text{\em L}}_{0}$. The authentications $a\in A$ are
then defined as follows: $A:M\times K\to C$ and $a({\text{\em m}},{\text{\em
k}})=\overline{{\text{\em m}},{\text{\em k}}}$ for given ${\text{\em m}}\in M$
and ${\text{\em k}}\in K$, where m and k are considered as points of the
projective plane. An authenticated message ${\text{\em C}}\in C$ which has
been authenticated using a given ${\text{\em k}}_{0}\in K$ is verified as
true, if ${\text{\em k}}_{0}\in{\text{\em C}}$ and false otherwise. Here again
${\text{\em k}}_{0}$ is considered a point of the projective plane and C a
line in the projective plane. This authentication scheme $(M,C,A)$ is perfect
according to definition 4.5.

###### Proof.

Let $q$ be the order of $(\boldsymbol{P},\boldsymbol{L})$. Then
$(\boldsymbol{P},\boldsymbol{L})$ consists of $q^{2}+q+1$ points and as many
lines. There are $q+1$ points on each line and $q+1$ lines run through each
point in $(P,L)$. Thus $|K|=q^{2}$, $|M|=q+1$ and the number of possible
authentications for a given message ${\text{m}}\in M$ is $q$.

We distinguish between the two cases that no authenticated message is known
and that one such authenticated message ${\text{C}}\in C$ is known.

To analyze the first case we select a message m in the set of messages $M$ and
create the authenticated message ${\text{C}}\in
C=\boldsymbol{L}\setminus{\text{L}}_{0}$. Again we consider the
representations of m, C and ${\text{L}}_{0}$ as point and lines in the
projective plane. There are $q$ possible authentications, since $q$ lines
different from ${\text{L}}_{0}$ run through the point
${\text{m}}\in{\text{L}}_{0}$. Each of these $q$ lines has $q$ different
points outside ${\text{L}}_{0}$. So there are $q^{2}$ possibilities for the
point ${\text{k}}_{0}\in K$ which represents the key ${\text{k}}_{0}$ used for
the authentication. Thus the chance that C is verified as a true authenticated
message equals to $\frac{q}{q^{2}}=\frac{1}{q}$.

In the second case a message ${\text{m}}_{0}$ and its corresponding
authenticated message
${\text{C}}_{0}=\overline{{\text{m}}_{0},{\text{k}}_{0}}$ are known. Again we
are looking at the representations of ${\text{m}}_{0}$, ${\text{k}}_{0}$ and
${\text{C}}_{0}$ as points and line in the projective plane. Another
${\text{m}}\in{\text{L}}_{0}$ with ${\text{m}}\neq{\text{m}}_{0}$ and
${\text{C}}\in\boldsymbol{L}\setminus{\text{L}}_{0}$ with
${\text{C}}\neq{\text{C}}_{0}$ can be selected. The lines
$\overline{{\text{m}},{\text{k}}}$ and
$\overline{{\text{m}}_{0},{\text{k}}_{0}}$ intersect in the point
${\text{k}}\in\overline{{\text{m}}_{0},{\text{k}}_{0}}$. The probability that
${\text{k}}={\text{k}}_{0}$ is $\frac{1}{q}$. ∎

Figure 1 visualizes the authentication scheme of definition 5.4.

$L_{0}$${\text{C}}:=\overline{{\text{m}},{\text{k}}}$ km Figure 1:
Authentication in the projective plane.

######  Remark 5.5.

The points ${\text{k}}\in K$ which have been used in definition 5.4 to
construct the authenticated messages are also referred to as keys.

######  Remark 5.6.

It’s obvious that in a practical application of this perfect authentication
scheme each key can be used only once.

######  Remark 5.7.

Beutelspacher and Rosenbaum introduced a generalization of this perfect
authentication scheme in the projective space [BR92].

In this paper we continue the examination of the cryptographic properties of
the authentication scheme introduced by Gilbert and MacWilliams with following
theorem.

######  Theorem 5.8.

An authentication scheme in a finite projective plane over a filed
$\mathbf{F}$ with $\operatorname{char}\mathbf{F}=2$ as introduced in
definition 5.4 is complete in the sense of definition 3.5.

###### Proof.

We consider an authentication scheme $(M,C,A)$ in the projective plane
$(\boldsymbol{P},\boldsymbol{L})$ over the field $\mathbb{Z}_{2}^{n}$ and we
introduce homogeneous coordinates
${\text{x}}=(\mathbb{Z}_{2}^{n})^{*}\left(\begin{array}[]{c}{\text{x}}_{1}\\\
{\text{x}}_{2}\\\ {\text{x}}_{3}\end{array}\right)$ for the points in
$(\boldsymbol{P},\boldsymbol{L})$. Here and in the following the field
$\mathbf{F}^{*}$ shall denote the field $\mathbf{F}$ without its zero element.
We assume that the set of messages $M$ and the key k are in the finite and
that ${\text{m}}_{1}\neq{\text{k}}_{1}$. Otherwise the projective plane shall
be transformed accordingly.

Since $M$ is in the finite, its points can be represented as follows:

$M=\big{\\{}{\text{x}}\in\boldsymbol{P}:s{\text{x}}_{1}-{\text{x}}_{2}+t=0,s,t\in\mathbb{Z}_{2}^{n},{\text{x}}_{3}=1\big{\\}}$
(1)

There are $q=2^{n}$ points of $M$ in the finite, which are uniquely determined
by the coordinate ${\text{x}}_{1}$ in (1).

Every line of $C$ passes the point k, the key. Since k is in the finite, it
can be represented with ${\text{k}}=({\text{k}}_{1},{\text{k}}_{2},1)$. Then
the lines of $C$ are represented by following condition:

$\begin{split}u{\text{x}}_{1}-{\text{x}}_{2}+{\text{k}}_{2}-u{\text{k}}_{1}=0&\Leftrightarrow\\\
u({\text{x}}_{1}-{\text{k}}_{1})-{\text{x}}_{2}+{\text{k}}_{2}=0&,u\in\mathbb{Z}_{2}^{n},{\text{x}}_{3}=1\end{split}$
(2)

The $q=2^{n}$ lines of $C$ are in the finite. They can be uniquely identified
with the parameter $u$ in (2).

The authenticated message ${\text{C}}\in C$ is determined as that line in $C$
that passes the point m which represents the message. Thus we obtain following
condition for C:

$u({\text{x}}_{1}-{\text{k}}_{1})-s{\text{x}}_{1}-t+{\text{k}}_{2}=0$ (3)

Hence, we can refer to the authentication $a:(M,K)\to C$ as a function
$a_{\text{k}}:\mathbb{Z}_{2}^{n}\to\mathbb{Z}_{2}^{n}$ that maps the
coordinate ${\text{x}}_{1}\in\mathbb{Z}_{2}^{n}$ to the parameter
$u\in\mathbb{Z}_{2}^{n}$:

$u=a_{\text{k}}({\text{x}}_{1}):=\frac{s{\text{x}}_{1}+t-{\text{k}}_{2}}{{\text{x}}_{1}-{\text{k}}_{1}}$

We want to look at the coordinates and parameters of
$(\boldsymbol{P},\boldsymbol{L})$ as binary vectors in $\mathbb{Z}_{2}^{n}$.
Furthermore $i,j$ shall be indices with $i,j\in\\{1,2,...,n\\}$ and
$e_{i},e_{j}$ the corresponding unit vectors in $\mathbb{Z}_{2}^{n}$.

In order to show the completeness of the authentication $a$, we need to find a
point ${\text{m}}^{\prime}$ in a way that
$a({\text{m}}^{\prime},{\text{k}})={\text{C}}^{\prime}$ when
$a({\text{m}},{\text{k}})={\text{C}}$. Here ${\text{m}}^{\prime}$ is obtained
when ${\text{x}}_{1}$ is replaced by ${\text{x}}_{1}+e_{i}$ and
${\text{C}}^{\prime}$ is obtained when $u$ is replaced by $u+e_{j}$ in (3):

$(u+e_{j})({\text{x}}_{1}+e_{i}-{\text{k}}_{1})-s({\text{x}}_{1}+e_{i})-t+{\text{k}}_{2}=0$
(4)

Parameters $s,t\in\mathbb{Z}_{2}^{n}$ can be found to fulfill equations (3)
and (4).

∎

##  6 Brief Introduction of the Circle Geometry of the Möbius Plane

######  Definition 6.1.

An incidence structure $(\boldsymbol{S},\boldsymbol{X})$ with a set of points
$\boldsymbol{S}$ and a set of circles $\boldsymbol{X}$ is called Möbius plane,
if it satisfies following properties:

  * (M1)

$\forall{\text{\em a}},{\text{\em b}},{\text{\em c}}\in\boldsymbol{S}$ with
${\text{\em a}}\neq{\text{\em b}}\neq{\text{\em c}}\neq{\text{\em a}}\
{\exists}_{1}{\text{\em A}}\in\boldsymbol{X}$. Following writing convention
will be used in this context: $({\text{\em a}},{\text{\em b}},{\text{\em
c}})^{\chi}:={\text{\em A}}$.

  * (M2)

Touch axiom: $\forall{\text{\em A}}\in\boldsymbol{X},\forall{\text{\em
a}},{\text{\em b}}\in\boldsymbol{S}$ with ${\text{\em a}}\in{\text{\em A}}$
and ${\text{\em b}}\in\boldsymbol{S}\setminus{\text{\em A}}\
{\exists}_{1}{\text{\em B}}\in\boldsymbol{X}:{\text{\em a}},{\text{\em
b}}\in{\text{\em B}}$ and ${\text{\em A}}\cap{\text{\em B}}=\\{{\text{\em
a}}\\}$.

  * (M3)

$|\boldsymbol{S}|\geq 4$ and there are four points in $\boldsymbol{S}$ which
are different from each other and which do not coincide with a common circle.

By a stereographic projection of the spherical surface on the Euclidean plane,
the Möbius geometry of the spherical surface is mapped on the geometry of the
circles and lines of the Euclidean plane. If one extends the Euclidean plane
with a distant point, then the straight lines can be regarded as circles
through this point. Figure 2 illustrates this procedure.

n${\text{p}^{\prime}}$ Figure 2: Möbius plane.

In the context of this paper we will only consider Möbius planes that are
defined over separable quadratic field extensions $(\mathbf{G},\mathbf{F})$ of
finite fields $\mathbf{F}=GF(q)$. In a quadratic field extension of this kind
there is exactly one involutorial automorphism
$\overline{.\vphantom{G}}:\mathbf{G}\to\mathbf{G}$ that has the elements of
$\mathbf{F}$ as fixpoints. We obtain the Möbius plane over a separable
quadratic field extension $(\mathbf{G},\mathbf{F})$, if we close it with the
point $\infty$,
$\boldsymbol{S}:=\overline{\mathbf{G}}:=\mathbf{G}\cup\\{\infty\\}$. Möbius
planes of this form do always have an analytical representation.

######  Definition 6.2.

The derivation of a Möbius plane $(\boldsymbol{S},\boldsymbol{X})$ in a point
${\text{\em a}}\in\boldsymbol{S}$ is characterized with the pair
$(\boldsymbol{S}^{\text{\em a}},\boldsymbol{X}^{\text{\em a}})$ with
$(\boldsymbol{S}^{\text{\em a}}:=\boldsymbol{S}\setminus\\{{\text{\em a}}\\}$
and $\boldsymbol{X}^{\text{\em a}}:=\\{{\text{\em C}}\setminus\\{{\text{\em
a}}\\}:{\text{\em C}}\in\boldsymbol{X},{\text{\em a}}\in{\text{\em C}}\\}$.

Every derivation of a Möbius plane is an affine plane, as has been shown e.g.
in [KK88]. In the following we will show three different ways for an
analytical representation of a Möbius plane.

##  7 Describing the Möbius Plane Using Equations

The Euclidean plane $\mathbb{R}^{2}$ can be represented by the plane of
complex numbers $\mathbb{C}$, i.e. the analytical geometry of the pair
$(\mathbb{C},\mathbb{R})$. A circle with center ${\text{c}}\in{\mathbb{C}}$
that runs through the point
${\text{c}}+{\text{a}},{\text{a}}\in\mathbb{C}^{*}$ is defined in $\mathbb{C}$
with following equation.

$({\text{z}}-{\text{c}})\overline{({\text{z}}-{\text{c}})}={\text{a}}\cdot\overline{{\text{a}}\vphantom{()}}$
(5)

The circle has the radius $r=|{\text{a}}|$.

This model of the Euclidean geometry can be generalized by using a separable
quadratic field extension $(\mathbf{L},\mathbf{K})$ instead of the pair
$(\mathbb{C},\mathbb{R})$. Any such field extension has exactly one
automorphism $\overline{.\vphantom{L}}:\mathbf{L}\to\mathbf{L}$ that keeps the
elements of $\mathbf{K}$ unchanged. The automorphism
$\overline{.\vphantom{L}}$ is involutory. The circles of this generalized
model are presented with equation (5). To obtain the Möbius plane of the field
pair $(\mathbf{L},\mathbf{K})$, $\mathbf{L}$ needs to be closed with a distant
point $\infty$, $\overline{\mathbf{L}}:=\mathbf{L}\cup\\{\infty\\}$ and
$\overline{\mathbf{K}}:=\mathbf{K}\cup\\{\infty\\}$.

##  8 Describing the Möbius Plane by the Use of Double Ratios

It is known from the elementary function theory that circles in the Gaussian
number plane can be described using double ratios. This can be generalized
using a separable quadratic field extension $(\mathbf{L},\mathbf{K})$. The
circle through the points ${\text{a}},{\text{b}},{\text{c}}\in\mathbf{L}$
consists of the points z for which the double ratio

$\text{
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}}}}}$
(6)

is a value in $\mathbf{K}$. The coresponding Möbius plane is defined by adding
the point $\infty$, i.e.
$\boldsymbol{S}:=\overline{\mathbf{L}}:=\mathbf{L}\cup\\{\infty\\}$.

##  9 Describing the Möbius Plane using fractional linear functions

In the Möbius plane $(\boldsymbol{S},\boldsymbol{X})$ over a separable
quadratic field extension $(\mathbf{G},\mathbf{F})$ fractional linear
functions of the following form can be chosen to describe circles:

$\gamma:\begin{cases}\overline{\mathbf{F}}\to\boldsymbol{X}\\\
z\mapsto\frac{az+b}{cz+d},&ad-
bc\in\mathbf{G}^{*},z\neq\infty,z\neq-\frac{d}{c}\mbox{, if
}\frac{d}{c}\in\mathbf{F}\\\ \infty\mapsto\frac{a}{c}\\\
-\frac{d}{c}\mapsto\infty,&\mbox{if }\frac{d}{c}\in\mathbf{F}\\\ \end{cases}$
(7)

##  10 Combinatorial Aspects of the Möbius Plane

In the following we will focus on Möbius planes based on finite fields. Let
$(\boldsymbol{S},\boldsymbol{X})$ be a Möbius plane over the field
$\mathbf{F}$ with $|\mathbf{F}|=:q$. Since any derivation of the Möbius plane
in a point results in an affine plane, where every line has $q$ points, all
circles in the Möbius plane have the same number of $k:=q+1$ points. By
calling $\nu$ the number of points in $\boldsymbol{S}$ and $b$ the number of
circles in $\boldsymbol{X}$, we find the following relationships by counting
coincidences. From (M1) we know:

$\left(\begin{array}[]{r}\nu\\\ 3\\\
\end{array}\right)=b\cdot\left(\begin{array}[]{r}k\\\ 3\\\ \end{array}\right)$
(8)

Let $x$ be the number of circles that run through two different points of
$(\boldsymbol{S},\boldsymbol{X})$, because of (M1) there is:

$x(q-1)=\nu-2$ (9)

Similarly it can be shown that as many circles coincide with two different
points a and b in $(\boldsymbol{S},\boldsymbol{X})$, as there are points on
one circle. Therefore let ${\text{C}},{\text{D}}\in\boldsymbol{X}$ and
${\text{a}},{\text{b}}\in{\text{C}},{\text{C}}\cap{\text{D}}=\\{{\text{a}}\\}$.

IaIbCD Figure 3: Circles through two points of the Möbius plane.

Figure 3 shows that any circle through a and b, except the circle C itself,
intersects the circle D in a point different from a. In connection with (M1)
and (M2) this proves our assertion. Furthermore we can conclude from equation
(9) that the number of points in the Möbius plane is $\nu=q^{2}+1$. By
substituting the relations for $\nu$ and $k$ we get from equation (8) that the
number of circles in the Möbius plane $b=q(q^{2}+1)$. Since the derivation of
a Möbius plane in any point ${\text{a}}\in\boldsymbol{S}$ results in an affine
plane over the field $\mathbf{F}$ and since the affine plane has $q^{2}+q$
lines, as much circles of the Möbius plane coincide with the point a.
Furthermore there are $q$ circles different from the circle C that touch C in
the point ${\text{b}}\in{\text{C}}$. Figure 4 shows that any circle touching C
in the point b intersects with the circle D in exactly one point. Since circle
D has $q+1$ points, the assertion is correct.

IbC Figure 4: Touching circles through a point of the Möbius plane.

##  11 Encryption in the Möbius Plane

In the following we define a cipher system in a Möbius plane
$(\boldsymbol{S},\boldsymbol{X})$ over a finite field $\mathbf{F}$ with
$|\mathbf{F}|=:q$. For this purpose we define

$\left(\begin{array}[]{r}\boldsymbol{S}\\\ 3\\\
\end{array}\right):=\big{\\{}({\text{s}}_{1},{\text{s}}_{2},{\text{s}}_{3})\in\boldsymbol{S}:\big{|}\\{{\text{s}}_{1},{\text{s}}_{2},{\text{s}}_{3}\\}\big{|}=3\big{\\}}$
(10)

as the set of triples in $\boldsymbol{S}$ that consist of three different
elements.

######  Definition 11.1.

A cipher system $(M,C,F)$ is defined in the Möbius plane
$(\boldsymbol{S},\boldsymbol{X})$ as follows:

  * Messages

$M:=\left(\begin{array}[]{r}\boldsymbol{S}\\\ 3\\\ \end{array}\right)$

  * Cipher texts

$C:=\left(\begin{array}[]{r}\boldsymbol{S}\\\ 3\\\ \end{array}\right)$

  * Encryption functions

$F:M\to C$ such that, if ${\text{\em M}}:=({\text{\em m}}_{1},{\text{\em
m}}_{2},{\text{\em m}}_{3})^{\chi}$ is the circle induced by the message
$({\text{\em m}}_{1},{\text{\em m}}_{2},{\text{\em m}}_{3})$, then encryption
functions $f\in F$ are defined as $f:{\text{\em M}}\to{\text{\em M}}$ in the
following way:

    * (MC1)

$f$ is associated with the triple $({\text{\em K}}_{1},{\text{\em
K}}_{2},{\text{\em K}}_{3})\in\left(\begin{array}[]{r}\boldsymbol{X}\\\ 3\\\
\end{array}\right)$, which is called the key.

    * (MC2)

${\text{\em m}}_{i}\in{\text{\em K}}_{i}$ and $({\text{\em m}}_{1},{\text{\em
m}}_{2},{\text{\em m}}_{3})^{\chi}\cap{\text{\em K}}_{i}\cap{\text{\em
K}}_{j}=\varnothing$ for $i,j\in\\{1,2,3\\}$ and $i\neq j$.

  * Encryption

For a given message $({\text{\em m}}_{1},{\text{\em m}}_{2},{\text{\em
m}}_{3})$, an encryption function $f\in F$ and an associated key $({\text{\em
K}}_{1},{\text{\em K}}_{2},{\text{\em
K}}_{3})\in\left(\begin{array}[]{r}\boldsymbol{X}\\\ 3\\\ \end{array}\right)$
the ciphertext $({\text{\em c}}_{1},{\text{\em
c}}_{2},{\text{\em}}_{3}):=f({\text{\em m}}_{1},{\text{\em m}}_{2},{\text{\em
m}}_{3})$ is determined by

    * (MC3)

${\text{\em c}}_{i}:=\begin{cases}{\text{\em K}}_{i}\cap({\text{\em
m}}_{1},{\text{\em m}}_{2},{\text{\em m}}_{3})^{\chi}-\\{{\text{\em
m}}_{i}\\}&\mbox{if }\big{|}{\text{\em K}}_{i}\cap({\text{\em
m}}_{1},{\text{\em m}}_{2},{\text{\em m}}_{3})^{\chi}\big{|}=2\\\ {\text{\em
m}}_{i}&\mbox{if }\big{|}{\text{\em K}}_{i}\cap({\text{\em m}}_{1},{\text{\em
m}}_{2},{\text{\em m}}_{3})^{\chi}\big{|}=1\\\ \end{cases}$

  * Decryption

Applying the encryption function $f$ to the cipher text $({\text{\em
c}}_{1},{\text{\em c}}_{2},{\text{\em c}}_{3})\in C$ yields the message.

The cipher system $(M,C,F)$ is called Möbius Cipher.

Figure 5 illustrates the encryption process of the Möbius Cipher.

${\text{m}}_{1}$${\text{c}}_{1}$${\text{c}}_{3}$${\text{m}}_{3}$I${\text{c}}_{2}$I${\text{m}}_{2}$${\text{K}}_{3}$${\text{K}}_{2}$${\text{K}}_{1}$
Figure 5: Visualization of the Möbius cipher.

######  Remark 11.2.

Due to the prerequisite that the points
${\text{m}}_{1},{\text{m}}_{2},{\text{m}}_{3}$ of the message are different
from each other in pairs, it is ensured that the circle through these three
points is well defined. This allows the chosen construction of the encryption
function.

######  Remark 11.3.

The way, how the circles of the key have been chosen, ensures that the three
points of the cipher text ${\text{c}}_{1},{\text{c}}_{2},{\text{c}}_{3}$ are
also different from each other in pairs and that
$({\text{c}}_{1},{\text{c}}_{2},{\text{c}}_{3})^{\chi}=({\text{m}}_{1},{\text{m}}_{2},{\text{m}}_{3})^{\chi}$.

######  Remark 11.4.

Definition 11.1 doesn’t describe a constructive way to find suitable circles
to determine the key. Some exemplary strategies to get such key circles are
explained in [Cap94].

######  Remark 11.5.

In case the message is shorter than three points in the Möbius plane, one or
two points have to be added to make the Möbius cipher applicable. This
mechanism is called ”padding”. Both sender and receiver of encrypted messages
need to be aware about the chosen padding mechanism.

######  Remark 11.6.

If the message consists of more than three points in the Möbius plane, the
encryption with the Möbius cipher is repeated with the next three consecutive
points until the end of the message is reached. Again some padding might be
required, if there are less than three points remaining at the end of the
message. In order to achieve cryptographic security, for every new triple of
points from the message three new circles have to be chosen as key.

##  12 Cryptoanalysis of the Möbius Cipher

Quite often the security of cryptographic algorithms is dependent on either
the fact that no efficient algorithm is known to solve a certain mathematical
problem or they use mappings that show very little structure. Examples for the
former are asymmetric algorithms like RSA or the discrete logarithm. The
latter includes e.g. symmetric algorithms like Feistel ciphers. In both cases
the security of these ciphers is based on assumptions and experience, but
cannot be concluded strictly. The advantage of the Möbius cipher that has been
introduced in this paper is that it is based on well defined geometric
structures and hence its cryptographic strength can be derived from known
properties.

Before coming to the perfectness and completeness as introduced in definitions
3.3 and 3.5, we would like to discuss some other requirements for a cipher
system. An important one is that the number of potential keys needs to be
large enough to avoid successful brute force attacks. Typically $2^{128}$ is
nowadays considered to be a sufficient size for the number of possible keys.
The number field $\mathbf{F}$ over which the Möbius plane
$(\boldsymbol{S},\boldsymbol{X})$ has been defined needs to be large enough,
to fulfill this requirement. Another useful property of a cipher system is the
ratio between input and output length. If ciphertexts are longer than the
original messages, the cipher system is called expanding. Again a suitable
choice of the underlying number field $\mathbf{F}$ can reduce expansion. In
the case that ASCII characters, which have a length of 8 bit, shall be
encrypted, expansion can be kept low, if the number field $q:=|\mathbf{F}|$ is
chosen in a way that $q$ is only slightly bigger than $2^{k\cdot 8}$ and
$k\geq 16$. This choice would also fulfill the requirement mentioned above of
providing a sufficient large key space.

To examine the properties of perfectness and completeness we use a simple
strategy to select the necessary keys for the Möbius cipher $(M,C,F)$ by
choosing lines. In the Möbius plane $(\boldsymbol{S},\boldsymbol{X})$ lines
are represented by circles ${\text{C}}\in C$ that run through the point
$\infty$. This gives us following quantities for our Möbius cipher $(M,C,F)$
in the Möbius plane $(\boldsymbol{S},\boldsymbol{X})$ over the field
$\mathbf{F}$ with $|\mathbf{F}|=:q$. The messages
${\text{m}}_{1},{\text{m}}_{2},{\text{m}}_{3}$ are three points in
$(\boldsymbol{S}\setminus\\{\infty\\})=:\overset{\circ}{\boldsymbol{S}}$,
different in pairs. The key circles
${\text{K}}_{1},{\text{K}}_{2},{\text{K}}_{3}$ are determined by the three
points
${\text{k}}_{i}\in\boldsymbol{S}\setminus\\{({\text{m}}_{1},{\text{m}}_{2},{\text{m}}_{3})^{\chi},\infty\\}$,
$i\in\\{1,2,3\\}$. The following figure 6 illustrates the encryption function.

${\text{m}}_{1}$${\text{c}}_{1}$${\text{c}}_{3}$I${\text{m}}_{3}$I${\text{c}}_{2}$I${\text{m}}_{2}$${\text{K}}_{3}$${\text{K}}_{2}$${\text{K}}_{1}$
Figure 6: Möbius cipher using lines as keys.

The encryption of three points of the message requires three points as keys.
Hence the length of the key equals the length of the message. Since according
to Shannon the key length in a perfect encryption scheme is at least as big as
the length of the ciphertext, the key length of our Möbius cipher is minimal.

To examine the property of perfectness according to definition 3.3 we want to
assume that all messages in $(M,C,F)$ are equally distributed. Let
${\text{m}}_{1}\neq{\text{m}}_{2}\neq{\text{m}}_{3}\neq{\text{m}}_{1}$ be
three points of the message lying on the circle M of the Möbius plane and let
${\text{c}}_{1},{\text{c}}_{2},{\text{c}}_{3}$ be the corresponding points of
the cipher text, which also incide with the circle M. Furthermore the
probability measures $\mu$ and $\nu$ shall be defined on M as explained in
definition 3.3. In the following we want to determine the a-priori and
a-posteriori probabilities of the three points
${\text{m}}_{1},{\text{m}}_{2},{\text{m}}_{3}$ of the message independently.

Lets have a look at the encryption of ${\text{m}}_{1}$.
${\text{M}}:=({\text{m}}_{1},{\text{m}}_{2},{\text{m}_{3}})^{\chi}$ is the
circle determined by the message points. Since there are $q+1$ points on M,
the probability of the occurrence of the message point ${\text{m}}_{1}$ is
$\mu({\text{m}}_{1})=\frac{1}{q+1}$.

The number of possible keys that can be used to encrypt ${\text{m}}_{1}$ is
given by $K_{1}:=\overset{\circ}{\boldsymbol{S}}\setminus{{\text{M}}}$, hence
$|K_{1}|=q^{2}-q-1$.

The pair of points ${\text{m}}_{1},{\text{c}}_{1}$ defines a line in
$(\overset{\circ}{\boldsymbol{S}},{\boldsymbol{X}})$. If
${\text{m}}_{1}={\text{c}}_{1}$, we choose the tangent to the circle M through
the point ${\text{m}}_{1}$. Two different cases are examined to determine the
a-posteriori probabilities:

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

Every point of the tangent to the circle M through the point ${\text{c}}_{1}$
except the points ${\text{c}}_{1}$ and $\infty$ are possible key points. Hence
in this case $\big{|}\\{f\in F:({\text{m}}_{1},{\text{c}}_{1})\subset
f\\}\big{|}=q-1$.

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

For a given pair of message and ciphertext points
${\text{m}}_{1},{\text{c}}_{1}$ the key can be any point on the line defined
by ${\text{m}}_{1},{\text{c}}_{1}$, with the exception of the points
${\text{m}}_{1},{\text{c}}_{1},\infty$. Hence $\big{|}\\{f\in
F:({\text{m}}_{1},{\text{c}}_{1})\subset f\\}\big{|}=q-2$.

We can conclude that in case of ${\text{m}}_{1}={\text{c}}_{1}$ the
a-posteriori probability is
$\nu({\text{m}}_{1},{\text{c}}_{1})=\frac{q-1}{q^{2}-q-1}$ and in the case of
${\text{m}}_{1}\neq{\text{c}}_{1}$ it is
$\nu({\text{m}}_{1},{\text{c}}_{1})=\frac{q-2}{q^{2}-q-1}$. Our a-priori
probability was $\mu({\text{m}}_{1})=\frac{1}{q+1}$. So with large $q$ we can
state that in first approximation
$\mu({\text{m}}_{1})\approx\nu({\text{m}}_{1},{\text{c}}_{1})$.

Lets proceed with examining the encryption of the message point
${\text{m}}_{2}$. Due to the prerequisite that the tree message points
${\text{m}}_{1},{\text{m}}_{2},{\text{m}}_{3}$ determine a unique circle M in
the Möbius plane, we know that ${\text{m}}_{2}\neq{\text{m}}_{1}$. Hence the
a-priori probability equals $\mu({\text{m}}_{2})=\frac{1}{q}$. According to
condition (MC2) for the encryption functions of the Möbius cipher in
definition 11.1 the set $K_{2}$ of possible keys for the encryption of
${\text{m}}_{2}$ is reduced by those key points that would map
${\text{m}}_{2}$ to ${\text{m}}_{1}$ or ${\text{c}}_{1}$. Thus in case of
${\text{m}}_{1}={\text{c}}_{1}$ we get
$K_{2}:=K_{1}\setminus\\{({\text{m}}_{1},{\text{m}}_{2},\infty)^{\chi}\\}$ and
$|K_{2}|=q^{2}-2q+1$. In case of ${\text{m}}_{1}\neq{\text{c}}_{1}$ we get
$K_{2}:=K_{1}\setminus\\{({\text{m}}_{2},{\text{m}}_{1},\infty)^{\chi},({\text{m}}_{2},{\text{c}}_{1},\infty)^{\chi}\\}$
and $|K_{2}|=q^{2}-3q+3$.

To calculate the a-posteriori probabilities of the encryption of
${\text{m}}_{2}$, we have to distinguish the cases
${\text{m}}_{2}={\text{c}}_{2}$ and ${\text{m}}_{2}\neq{\text{c}}_{2}$ again:

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

Every point of the tangent through the point ${\text{c}}_{2}$ at the circle
$M$, except the points ${\text{c}}_{2}$ and $\infty$ are possible key points.
Hence $\big{|}\\{f\in F:({\text{m}}_{2},{\text{c}}_{2})\subset
f\\}\big{|}=q-1$.

  * ${\text{m}}_{1}={\text{c}}_{1}$,${\text{m}}_{2}\neq{\text{c}}_{2}$

For a given pair of message and ciphertext points
${\text{m}}_{2},{\text{c}}_{2}$ all points of the line through the points
${\text{m}}_{2},{\text{c}}_{2}$ with the exception of
${\text{m}}_{2},{\text{c}}_{2},\infty$ can be keys. Thus $\big{|}\\{f\in
F:({\text{m}}_{2},{\text{c}}_{2})\subset f\\}\big{|}=q-2$.

  * ${\text{m}}_{1}\neq{\text{c}}_{1}$,${\text{m}}_{2}={\text{c}}_{2}$

Every point of the tangent through the point ${\text{c}}_{2}$ at the circle
$M$, except the points ${\text{c}}_{2}$ and $\infty$ are possible key points.
Hence $\big{|}\\{f\in F:({\text{m}}_{2},{\text{c}}_{2})\subset
f\\}\big{|}=q-1$.

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

For a given pair of message and ciphertext points
${\text{m}}_{2},{\text{c}}_{2}$ all points of the line through the points
${\text{m}}_{2},{\text{c}}_{2}$ with the exception of
${\text{m}}_{2},{\text{c}}_{2},\infty$ can be keys. Thus $\big{|}\\{f\in
F:({\text{m}}_{2},{\text{c}}_{2})\subset f\\}\big{|}=q-2$.

The following table summarizes the a-priori and a-posteriori probabilities for
the encryption of the second message point:

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}$ | $\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}$ | $\nu({\text{m}}_{2},{\text{c}}_{2})=\frac{q-2}{q^{2}-2q+1}$
${\text{m}}_{1}\neq{\text{c}}_{1}$,${\text{m}}_{2}={\text{c}}_{2}$ | $\mu({\text{m}}_{2})=\frac{1}{q}$ | $\nu({\text{m}}_{2},{\text{c}}_{2})=\frac{q-1}{q^{2}-3q+3}$
${\text{m}}_{1}\neq{\text{c}}_{1}$,${\text{m}}_{2}\neq{\text{c}}_{2}$ | $\mu({\text{m}}_{2})=\frac{1}{q}$ | $\nu({\text{m}}_{2},{\text{c}}_{2})=\frac{q-2}{q^{2}-3q+3}$

Also the second encryption step of our Möbius cipher is in first approximation
perfect, when considering large values for $q$.

Similar considerations lead to the following results for the encryption of the
third message point ${\text{m}}_{3}$:

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}}_{3})=\frac{1}{q-1}$ | $\nu({\text{m}}_{3},{\text{c}}_{3})=\frac{q-1}{q^{2}-3q+3}$
${\text{m}}_{1}={\text{c}}_{1}$,${\text{m}}_{2}={\text{c}}_{2}$,${\text{m}}_{3}\neq{\text{c}}_{3}$ | $\mu({\text{m}}_{3})=\frac{1}{q-1}$ | $\nu({\text{m}}_{3},{\text{c}}_{3})=\frac{q-2}{q^{2}-3q+3}$
${\text{m}}_{1}={\text{c}}_{1}$,${\text{m}}_{2}\neq{\text{c}}_{2}$,${\text{m}}_{3}={\text{c}}_{3}$ | $\mu({\text{m}}_{3})=\frac{1}{q-1}$ | $\nu({\text{m}}_{3},{\text{c}}_{3})=\frac{q-1}{q^{2}-4q+5}$
${\text{m}}_{1}={\text{c}}_{1}$,${\text{m}}_{2}\neq{\text{c}}_{2}$,${\text{m}}_{3}\neq{\text{c}}_{3}$ | $\mu({\text{m}}_{3})=\frac{1}{q-1}$ | $\nu({\text{m}}_{3},{\text{c}}_{3})=\frac{q-2}{q^{2}-4q+5}$
${\text{m}}_{1}\neq{\text{c}}_{1}$,${\text{m}}_{2}={\text{c}}_{2}$,${\text{m}}_{3}={\text{c}}_{3}$ | $\mu({\text{m}}_{3})=\frac{1}{q-1}$ | $\nu({\text{m}}_{3},{\text{c}}_{3})=\frac{q-1}{q^{2}-4q+5}$
${\text{m}}_{1}\neq{\text{c}}_{1}$,${\text{m}}_{2}={\text{c}}_{2}$,${\text{m}}_{3}\neq{\text{c}}_{3}$ | $\mu({\text{m}}_{3})=\frac{1}{q-1}$ | $\nu({\text{m}}_{3},{\text{c}}_{3})=\frac{q-2}{q^{2}-4q+5}$
${\text{m}}_{1}\neq{\text{c}}_{1}$,${\text{m}}_{2}\neq{\text{c}}_{2}$,${\text{m}}_{3}={\text{c}}_{3}$ | $\mu({\text{m}}_{3})=\frac{1}{q-1}$ | $\nu({\text{m}}_{3},{\text{c}}_{3})=\frac{q-1}{q^{2}-5q+7}$
${\text{m}}_{1}\neq{\text{c}}_{1}$,${\text{m}}_{2}\neq{\text{c}}_{2}$,${\text{m}}_{3}\neq{\text{c}}_{3}$ | $\mu({\text{m}}_{3})=\frac{1}{q-1}$ | $\nu({\text{m}}_{3},{\text{c}}_{3})=\frac{q-2}{q^{2}-5q+7}$

So, also the third encryption step of the Möbius cipher is in first
approximation perfect for large values for $q$.

To show the completeness of the Möbius 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\overset{\circ}{\boldsymbol{S}}$ 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 ciphertext 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 there are two lines G and H in the Möbius plane
$(\boldsymbol{S},\boldsymbol{X})$ over the field $\mathbb{Z}_{2}^{n}$ with
${\text{m}},{\text{c}},{\text{k}}\in{\text{G}}$ and
${\text{m}}^{\prime},{\text{c}}^{\prime},{\text{k}}\in{\text{H}}$. Without
restricting generality we assume that ${\text{k}}=(0,0)$, otherwise the Möbius
plane can be transformed accordingly. Then 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}$
(11)

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}-uv&=0\end{split}$ (12)

Or:

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

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

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 be
${\text{m}}^{\prime}(x+e_{i},y)$ and ${\text{c}}^{\prime}(u+e_{j},v)$ be the
altered points. Once again it has to be shown that condition (11) is
fulfilled. In analogy to the procedure shown above we reach following
conditions:

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

Which can be simplified to:

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

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

##  13 Résumé and Outlook

We showed that geometric structures cannot only be used to define
authentication schemes but that they can also be used to design encryption
functions. A cryptographic transformation has been introduced in a Möbius
plane over a finite field that is approximately perfect in the sense of
Shannon [Sha49] and complete according to [KD79]. We think that the Möbius
cipher can be of good practical use in the area of quantum cryptography, where
a constant stream of qbits is shared as key between two parties to support
encryption. In comparison to the well known Vernam cipher [Ve26], the Möbius
cipher has the advantage of not only being approximately perfect according to
Shannon, but also complete according to Kam and Davida. The results of this
paper can easily generalized for geometric structures of the Laguerre and
Minkowski plane.

## 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.
  * [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.


\contained \MUAHomBounded{\gamma}{\ContrPwOneWay}{\leq\l}
\contained \gamma.
\]

* If $\gamma \semequiv \MUAHomBounded{\gamma}{\ContrPwOneWay}{\leq\l}$,
then $\gamma$ is equivalent to a "UCRPQ" of "contracted path-width" at
most $k$, and hence it is equivalent a "UCRPQ" of "path-width" at most $k$.

The second point can be proven similarly.

We can now prove the main theorem:

The upperbounds follow from <Ref>.
The lower-bound will be shown in <Ref>. Lastly, to prove the "ExpSpace" upper-bound
for $k=1$, we can apply the same trick as in <Ref>.

Similarly to <Ref>, we can derive from
<Ref> a characterization of "semantic path-width" at most $k$.

Assume that $\+L$ is "closed under sublanguages", and let $k \geq 1$.

For any query $\Gamma \in \UCtwoRPQ(\+L)$, the following are equivalent:

$\Gamma$ is "equivalent" to an "infinitary union" of "conjunctive queries"
of "contracted path-width" at most $k$;
$\Gamma$ has "semantic path-width" at most $k$;
$\Gamma$ is "equivalent" to a $\UCtwoRPQ(\+L)$ of "contracted path-width" at most $k$;
$\Gamma$ is "equivalent" to a $\UCtwoRPQ(\+L')$ of "path-width" at most $k$,
where $\+L'$ is the closure of $\+L$ under concatenation and inverses, "ie"
$\+L'$ is the smallest class containing $\+L$ and such that  if $K, L \in \+L'$
then $K\cdot L \in \+L'$ and $K^{-1} \in \+L'$.

Similarly, if $\Gamma \in \UCRPQ(\+L)$, then the following are equivalent:

$\Gamma$ is "equivalent" to an "infinitary union" of "conjunctive queries"
of "one-way contracted path-width" at most $k$;
$\Gamma$ has "one-way semantic path-width" at most $k$;
$\Gamma$ is "equivalent" to a $\UCRPQ(\+L)$ of "one-way contracted path-width" at most $k$;
$\Gamma$ is "equivalent" to a $\UCRPQ(\+L')$ of "path-width" at most $k$,
where $\+L'$ is the closure of $\+L$ under concatenation, "ie"
$\+L'$ is the smallest class containing $\+L$ and such that if $K, L \in \+L'$
then $K\cdot L \in \+L'$.

§.§ Evaluation of Queries of Bounded Semantic Path-Width

In this section, we show that, as a consequence of <Ref>, we have:

The class "para-NL" was introduced in <cit.> under the
name “uniform "NL" + advice”. It was renamed "para-NL" in
<cit.>. For the sake of simplicity,
instead of either of those definitions, we use the characterization of "para-NL"
proven in <cit.>.

We define ""para-NL"" as the class of parametrized languages $L \subseteq \Sigma^* \times \Nat$
for which there is a Turing machine $M$ "st"

[>=Classical TikZ Rightarrow]
$M \text{ accepts } \langle \textcolor{cRed}{x},\, \textcolor{cBlue}{k}\rangle%
\quad\text{"iff"}\quad
\langle$
[inode, cRed, right=-3.5pt of first.base east, anchor=base west](toX)$x$;
[inode, right=0pt of toX.base east, anchor=base west](comma)$,\,$;
[inode, cBlue, right=0pt of comma.base east, anchor=base west](toK)$k$;
[inode, right=-.5pt of toK.base east, anchor=base west]$\rangle \in L,$;
[cRed, below left= .3cm and .2cm of toX](fromX)input;
[cBlue, below right= .3cm and .2cm of toK](fromK)parameter;
[->, cRed] (fromX) to[out=60, in=-120] (toX.south);
[->, cBlue] (fromK) to[out=120, in=-60] (toK.south);

and, moreover, $M$ runs in non-deterministic space
$f(\textcolor{cBlue}{k}) + \+O(\log(|\textcolor{cRed}{x}|))$,
where $f\colon \Nat \to \Nat$ is a computable function.
A typical example of "para-NL" problem is the model-checking problem for first-order logic on
finite structures, when parametrized by the maximum degree of the structure

To show <Ref>, we first focus on the evaluation of queries of bounded "path-width".

For each $k \geq 1$, the "evaluation problem", restricted to "UC2RPQs" of
"path-width" at most $k$ is "NL".

Partial homomorphism computed at the fourth step of the algorithm.

Partial homomorphism computed at the fifth step of the algorithm.

Algorithm to evaluate "C2RPQs" of "path-width" at most $k$ (here $k=2$)
in non-deterministic logspace. Each subfigure represents: (i) on the left-hand side, a
"path decomposition" of a "C2RPQ", (ii) on the right-hand side, a "graph database",
and (iii) a partial "homomorphism" from the "C2RPQ" to the "database".

First part: with the "path decomposition".
First, we assume that a "tagged path decomposition" of width at most $k$ of the query of
is also provided as part of the input. Moreover, we assume "wlog" that the input is "C2RPQ"—the extension to "UC2RPQ" being straightforward. So, we are given as input:

* a database together with a tuple of nodes $G(\bar u)$,

* a "C2RPQ" $\gamma(\bar x)$, and

* a "tagged path decomposition" $\langle T, \bagmap, \tagmap \rangle$ of "width" at
most $k$ of $\gamma(\bar x)$.

The algorithm, illustrated in <Ref>, maintains a partial homomorphism
$f\colon X \pto G$
of these variables onto $G$.
We scan the "bags" of the decomposition from left to right.

* Initially—before even scanning the first "bag"—$f$ is the map with empty domain.

* Then, when scanning the $i$-th bag $b_i$,
we start by restricting $f$ to variables of $\dom(f)\cap b_i$.
Then, we extend $f$ so that it is defined on the whole "bag" $b_i$.
For every variable $y$ in $b_i \smallsetminus\dom(f)$:

* if it belongs to $\bar x$, say $y = x_i$,
we let $f(x_i) \defeq u_i$;

* otherwise, we non-deterministically guess the value of $f(y)$.

We then check, for every "atom" $x \atom{L} y$ of $\gamma(\bar x)$ which is "tagged" in
the current "bag" $b_i$ if there is a path from $f(x)$ to $f(y)$ labelled by a word of $L$ in $G$. If not, we reject.

If the algorithm manages to scan the whole bag decomposition without rejecting, it accepts.

Completeness of the algorithm is trivial. Correctness follows from the fact that if
a variable occurs in "bags" $b_i$ and $b_k$ with $i \leq k$, then it must also belong to every
"bag" $b_j$ for $j \in \lBrack i,k \rBrack$. As a consequence, a variable $x$ is assigned
exactly one value $f(x)$ during the whole process.

Concerning the space complexity:

* By construction, at the $i$-th step of the algorithm, $f$ is defined exactly on $b_i$, so on at most $k+1$ variables.
So, $f$ can be stored in space $(k+1)\log(|G|)$;

* we need a counter with $\log(|T|)$ bits to scan through the "tagged path decomposition" $\langle T, \bagmap, \tagmap \rangle$,

* each atomic check—checking if there is an $L$-labelled path from $f(x)$ to $f(y)$—can be done in non-deterministic space $c\cdot \log(|G|)$ using a straightforward adaptation of the "NL" algorithm for graph connectivity; note that these atomic checks are
independent of one another, so we can reuse this space.

Overall, the algorithm runs in non-deterministic space
$\+O(k\log(|G|) + \log(|T|)) = \+O(\log(|G|) + \log(|T|))$,
which is logarithmic in the size of the input.

Second part: without the "path decomposition".
Then, we claim that the original problem—when the "tagged tree decomposition" is not part of
the input—also lies in "NL". This is because one can compute, from $\gamma$, a
"path decomposition" in (deterministic) logarithmic space by[This result is an
adaption of a similar statement for "tree-width" <cit.>]
<cit.>. Then, a "path decomposition" can be turned into a
"tagged path decomposition" in (deterministic) logarithmic space by tagging an "atom"
$x \atom{L} y$ in the first bag containing both $x$ and $y$.
The conclusion follows since functions computable in non-deterministic logarithmic space
are closed under composition <cit.>.

We can now conclude with <Ref>, namely that the "evaluation problem" for "UC2RPQs" of
"semantic path-width" $k$ is "para-NL".

Given a "UC2RPQ"
$\Gamma(\bar x)$ of "semantic path-width" at most $k$ and a database $G(\bar u)$, we
first compute $\MUAHomBounded{\Gamma}{\ContrPwOneWay}{\leq\l}$—where $\l = \lbound{k}{\Gamma}$—, which is "equivalent" to
$\Gamma$ by <Ref>.
Then, we use <Ref> to evaluate each
$\delta(\bar x) \in \MUAHomBounded{\Gamma}{\ContrPwOneWay}{\leq\l}$ on $G(\bar u)$.
If one of the queries accepts, we accept. Otherwise, we reject.

The non-deterministic space needed by the algorithm is:

* $\+O(\l)$ bits to enumerate and store $\delta(\bar x)$, where $\l = \lbound{k}{\Gamma} $

* $\+O(\log{|G|} + \log{\size{\delta}}) \subseteq \+O(\log{|G|} + \log{|\l|} + \log{\size{\Gamma}})$ to evaluate
$\delta(\bar x)$ on $G(\bar u)$, by <Ref>
and since $\size{\delta} \leq \size{\Gamma}\cdot \l$.

Overall, we use non-deterministic space $f(\size{\Gamma}) + \+O(\log(|G|))$
where $f$ is a single exponential, which concludes the proof.

§ LOWERBOUNDS FOR DECIDING SEMANTIC TREE-WIDTH AND PATH-WIDTH

An "ExpSpace" lower-bound follows by a straightforward adaptation from the
"ExpSpace" lower-bound for the case $k=1$ <cit.>.
[Lower-bound of <Ref>]lemlowerbound

For every $k\geq 1$, the following problems are "ExpSpace"-hard, even if restricted to "Boolean CRPQs":

* the "semantic tree-width $k$ problem";

* the "one-way semantic tree-width $k$ problem";

* the "semantic path-width $k$ problem";

* the "one-way semantic path-width $k$ problem".

We say that a "C2RPQ" is ""connected"" when its underlying undirected graph is connected.
We first give a small usefull fact:

[Implicit in <cit.>]

* Let $G, G'$ be two "databases" and $\delta$ be a "connected" "Boolean" "C2RPQ".
If the disjoint sum $G+G'$ "satisfies" $\delta$, then either $G$ "satisfies" $\delta$ or
$G'$ "satisfies" $\delta$.

* Let $\gamma,\delta$ be "Boolean" "C2RPQs". If $\delta$ is "connected"
and $\gamma \contained \delta$, then there exists a "subquery" $\gamma'$ of $\gamma$,
obtained as connected component of $\gamma$, such that
$\gamma' \contained \delta$.

Notice first that if $\gamma$ and $\delta$ are "CQs" then the proof of
<Ref> follows directly from the equivalence of $\gamma \contained \delta$ (resp. $G$ "satisfies" $\gamma$) and the existence of a "homomorphism" from $\delta$ to $\gamma$ (resp. $\gamma$ to $G$).

We first prove the second point.
Write $\gamma \defeq \gamma_1 \land \hdots \land \gamma_n$ where $\gamma_1,\hdots,\gamma_n$
are connected components of $\gamma$, and assume by contradiction that
for all $i$, $\gamma_i \not\contained \delta$. Then there exists a database $G_i$
such that $G_i$ "satisfies" $\gamma_i$ but not $\delta$.
Consider the disjoint union $G = G_1 + \hdots + G_n$.

On the one hand, since the $\gamma_i$'s have disjoint variables
and $\gamma_i$ "satisfies" $G_i$ for each $i$, then $G$ "satisfies" $\gamma$.
On the other hand, $G$ cannot "satisfy" $\delta$ since $\gamma'$ is "connected"
and none of the $G_i$ "satisfies" $\delta$—otherwise, the "homomorphism"
from $\delta$ to $G$ would yield a "homomorphism" from $\delta$ to some $G_i$.
This contradicts the "containment" of $\gamma$ in $\delta$.

To prove the first point, we simply apply the second one, by letting $\gamma$
be the conjunction of the canonical "CQ" associated with $G$ and $G'$—which
is in fact the canonical "CQ" associated with $G+G'$.

We can then prove <Ref>.

Fix $k \geq 1$. We focus on "semantic tree-width", but the exact same reduction works for the other three problems. The proof contains two parts:

* first, we reduce the decision of problem of,
given two "Boolean" "CRPQs" $\gamma$ and $\gamma'$,
where $\gamma$ has "tree-width" $k$, $\gamma'$ is "connected"
and does not have "semantic tree-width" $k$,
deciding whether $\gamma \contained \gamma'$,
to the "semantic tree-width $k$ problem";

* then, we prove that the former problem is

(1): We reduce the instance $(\gamma, \gamma')$
to the instance $\gamma \land \gamma'$. We simply have to check that
$\gamma \contained \gamma'$ if and only if
$\gamma \land \gamma'$ has "semantic tree-width" $k$. The left-to-right
implication is straightforward since $\gamma \contained \gamma'$
implies that $\gamma \land \gamma' \semequiv \gamma$ and $\gamma$ was assumed to
have "tree-width" $k$.
For the converse implication, if $\gamma \land \gamma' \semequiv \delta$
where $\delta$ is a "UC2RPQ" of "tree-width" $k$ then write
$\delta = \bigvee_{i=1}^n \delta_i$ where the $\delta_i$'s are "C2RPQs"
and let $\delta_{i,1},\hdots, \delta_{i,k_i}$ be the connected components
of $\delta_i$.

Since for each $i$ we have
$\delta_i \contained \delta \semequiv \gamma \land \gamma' \contained \gamma'$, by
<Ref>, there exists $j_i$ such that
$\delta_{i,j_i} \contained \gamma'$.
Let $\delta' \defeq \bigvee_{i=1}^n \delta_{i,j_i}$ so that, by construction
$\delta' \contained \gamma'$. However, note that $\delta'$ has "tree-width" at most $k$
but $\gamma'$ was assumed not to have "semantic tree-width" $k$,
hence $\delta' \strcontained \gamma'$,
so there exists $G'$ such that:

\begin{equation}
\AP\label{eq:subquery-reduction}
G' \text{ "satisfies" } \gamma'
\quad\text{ and }\quad
G' \text{ does not "satisfy" } \delta'.
\end{equation}

We now prove that $\gamma \contained \gamma'$. Let $G$ be a
"database" "satisfying" $\gamma$. Then $G + G'$ "satisfies" $\gamma \land \gamma'$
since $G$ "satisfies" $\gamma$, $G'$ "satisfies" $\gamma'$ and $\gamma$ and $\gamma'$
have disjoint variables.
As a consequence, $G + G'$ "satisfies" $\delta$ and hence $\delta'$,
so there exists $i$ such that $G+G'$ "satisfies" $\delta_{i,j_i}$.
Since $\delta_{i,j_i}$ is "connected", either $G$ "satisfies"
$\delta_{i,j_i}$ or $G'$ "satisfies" $\delta_{i,j_i}$.
By <Ref>, the latter cannot hold,
so $G$ "satisfies" $\delta_{i,j_i}$ and hence $\gamma'$.

Therefore, we've shown that for each "database" $G$ that "satisfies"
$\gamma$, then $G$ "satisfies" $\gamma'$, i.e. $\gamma \contained \gamma'$. Overall,
$\gamma \land \gamma'$ has "semantic tree-width" $k$ if and only if
$\gamma \contained \gamma'$.

(2): It was shown in <cit.> that
the "containment" of "CRPQs" was still "ExpSpace"-hard
when restricted to inputs of the form:

[column sep=scriptsize]
γ() = ["K"]         ^?
["L_1", bend left=40] ["6pt⋮", phantom] ["L_p" below, bend right=40]        [-2.1em] = δ(),

where $K,L_1,\hdots,L_p$ are regular languages over $\A$.
We reduce it to the following problem:

[column sep=scriptsize, row sep=tiny]
[dr, "#"] [dd, "#" above left]

γ'() ["K"]     ["#" above, loop above]     ^?
["L_1", bend left=40] ["6pt⋮", phantom] ["L_p" below, bend right=40]     ["^*"]     [rr, "#" below right] [ur, "#"] [dr, "#" below left]         = δ'().

[ur, "#" below right]

where the right-hand side of $\delta'$ is a directed $(k+2)$-clique
and where $\#$ is a new symbol, i.e. $\# \not\in \A$.

We claim that $\gamma \contained \delta$ if and only if $\gamma' \contained \delta'$.
The forward implication is direct and the converse implication
simply relies on the fact that $\# \not\in \A$.
Then, observe that $\gamma'$ has "tree-width" $1 \leq k$,
and that $\delta'$ is connected but do not have "semantic tree-width"
at most $k$.

To prove the last point, consider a "UC2RPQ" $\Delta''$ that is
equivalent to $\delta'$. Pick any "expansion" $\xi'_1$ of $\delta'$.
Since $\Delta'' \contained \delta'$, there exists
an "expansion" $\xi''$ of $\Delta''$ such that there is a "homomorphism"
from $\xi'_1$ to $\xi''$. Dually, since $\delta' \contained \Delta''$,
there exists an "expansion" $\xi'_2$ of $\delta'$ such that there
is a "homomorphism" from $\xi'' \to \xi'_2$. Overall, we have
"homomorphisms" $\xi'_1 \to \xi'' \to \xi'_2$.
Since $\xi'_1$ and $\xi'_2$ are both "expansions" of $\delta'$,
they contain a $\#$-labelled directed $(k+2)$-clique,
and the $\#$-letter appears nowhere else.
Should the "homomorphism" $\xi'_1 \to \xi''$ not be injective,
$\xi''$ would contain a $\#$-labelled self-loop,
and hence, the "homomorphism" $\xi'' \to \xi'_2$ would
yield a $\#$-self loop in $\xi'_2$, which does not exist!
Hence, the "homomorphism" from $\xi'_1$ to $\xi''$
is injective on the $(k+2)$-clique.
As a result, $\xi''$ contains a $(k+2)$-clique
and has "tree-width" at least $k+1$.
We conclude that $\Delta''$ has "tree-width" at least $k+1$ by <Ref>, provided that $k \geq 2$.

Hence, we have shown that $\gamma \contained \delta$ if and only if $\gamma' \contained \delta'$
where $\gamma'$ has "tree-width" at most $k$, where $\delta'$ is "connected" and
has "semantic tree-width" at least $k+1$. Since our reduction
can be implemented in polynomial time, we conclude that the problems of
<Ref> are "ExpSpace"-hard.

Do deal with "path-width" and/or the case $k=1$,
it suffices to use the same trick as in <cit.>: for instance one can add in $\delta'$ on the $i$-th variable of the $(k+2)$-clique a self-loop labelled by a new symbol $\$_i$, and add in $\gamma'$ a self-loop labelled by $\$_i$ on the variable that
already has a $\#$-self-loop.

§ DISCUSSION

§.§ Complexity

We have studied the definability and approximation of "UC2RPQ" queries by queries of bounded "tree-width" and shown that the "maximal under-approximation" in terms of an infinitary union of "conjunctive queries" of "tree-width" $k$ can be always effectively expressed as a "UC2RPQ"
of "tree-width" $k$ (<Ref>).
However, while the "semantic tree-width $1$ problem" is shown to be -complete (which was also established in <cit.>), we have left a gap between our lower and upper-bounds in <Ref> for every $k>1$.

For $k > 1$, is the "semantic tree-width $k$ problem" -complete?

A related question is whether the "containment problem" between a "C2RPQ" and a "summary query" is in . Such this be the case, then the "semantic tree-width $k$ problem" would be in .
We also point out that since every "path-$l$ approximation" can be expressed by a polynomial "UC2RPQ" of tree-width $2k$—this is the same idea as in <cit.>—, one can produce, for every "UC2RPQ" $\Delta$ a union $\Gamma$ of poly-sized "C2RPQ" of tree-width $2k$ such that $ \MUA{\Delta}{\Tw} \contained \Gamma \contained \Delta$. This implies that the following “promise”[In reference to “promise constraint satisfaction problems”
<cit.>.] problem is decidable in : given a "UC2RPQ" $\Gamma$, answer `yes' if $\Gamma$ is of "semantic tree-width" $2k$, and answer `no' if $\Gamma$ is not of "semantic tree-width" $k$. The fact that $\MUA{\Delta}{\Tw}$ can be approximated by an exponential query of tree-width $2k+1$ can also be seen as a corollary of the proof of <cit.>.

We also do not know whether the  bound on the "semantic tree-width $k$ problem" for  has a matching lower-bound. The known lower-bound for the  "containment problem" <cit.> does not seem to be useful to be employed in a reduction in this context, since it necessitates queries of arbitrary high "tree-width".

§.§ Characterization of Tractability

Our result implies that for each $k$
the "evaluation problem" for "UC2RPQs" $\Gamma$
of "semantic tree-width" $k$ is fixed-parameter tractable—or ""FPT""—taking
the query as parameter, "ie", in time $\+O(|G|^{c} \cdot f(|\Gamma|))$
for a computable function $f$ and constant $c$, where $G$ is the "database" given as input.

While this was a known fact <cit.>, the dependence on the database was $c=2k+1$.  Our results show that the dependence can be improved to $c=k+1$, similarly to <cit.> for the case $k=1$.
It has been further argued that the "evaluation" can be done with a single-exponential $f$ <cit.>.

In a similar vein, our results show that the "evaluation problem" for "UC2RPQs"
of "semantic path-width" $k$ is "para-NL". It is unknown whether the semantic bounded width properties characterize all "FPT" and "para-NL" classes.

Does every recursively enumerable class of "CRPQs" with "para-NL" evaluation has bounded "semantic path-width"?

[Also mentionned in <cit.>]
Does every recursively enumerable class of "CRPQs" with "FPT" evaluation has bounded "semantic tree-width"?

In the case of "CQs", the answer is `yes' to <Ref> <cit.>
under standard complexity-theoretic hypotheses ($W[1] \neq $ "FPT"). For <Ref>, the answer is still `yes' <cit.> conditional to a less standard assumption[By <cit.>, if the class has bounded "semantic path-width", then the problem is in $\textsf{Path} \subseteq $ "paraNL"; by <cit.>, if the class does not have bounded "semantic path-width", then the problem is -hard.] (no $\textsf{Tree}$-hard problem is in "paraNL").

However, attempting at answering these questions for "CRPQs" is considerably more challenging. In particular, one important technical difficulty is that a class of "CRPQs" with unbounded "tree-width" may contain queries with no "expansions" which are "maximal" in the sense of "containment". That is, for every $k$, query $\gamma$ of the class of "semantic tree-width" $>k$ and "expansion" $\xi$ of "semantic tree-width" $>k$ there may be another "expansion" $\xi'$ such that $\xi' \homto \xi$ ("ie", such that $\xi \contained \xi'$).

In fact, for classes of "CRPQs" avoiding such problematic behavior, Question <ref> can be positively answered. We next show why.

Let us call a "UC2RPQ" ""finitely-redundant"" if there is no infinite chain $\xi_1(\bar x) \strcontained \xi_2(\bar x) \strcontained \dotsb$ among its "expansions". See <Ref> for a non-example.

$(i)$ A simple non-"finitely-redundant" Boolean "CRPQ". $(ii)$ For every $n$, there is a "homomorphism" from the $(n+1)$-"expansion" to the $n$-"expansion", but no "homomorphism" in the converse direction.

Observe that the classes of "CQs" and "UCQs" are "finitely-redundant", and also the class of "CRPQs" with “""no directed cycles""”, meaning no directed cycle in its underlying directed graph and no empty word $\epsilon$ in the "atom" languages.

The class of "CRPQs" with "no directed cycles" is "finitely-redundant".

By means of contradiction, let $\gamma$ have "no directed cycles" and suppose there is an infinite chain $\xi_1(\bar x) \strcontained \xi_2(\bar x) \strcontained \dotsb$ of "expansions" of $\gamma$. Hence, there must be an "atom" "expansion" which grows arbitrarily in the chain. Take $\xi_i$ such that it contains an "atom" "expansion" of size bigger than $\xi_1$. Since such "atom" "expansion" is a directed path (as we are dealing with one-way "CRPQs"), the fact that $\xi_i \homto \xi_1$ implies that there is some cycle in $\xi_1$. This is in contradiction with the hypothesis that there are "no directed cycles" in $\gamma$.

We next show that, restricted to classes of "finitely-redundant" "UC2RPQ", we can obtain a characterization of "evaluation" in "FPT".

Assuming $\wone \neq $ "FPT", for any r.e. class $\+C$ of "finitely-redundant" Boolean "UC2RPQs", the "evaluation problem" for $\+C$ is "FPT" if, and only if, $\+C$ has bounded "semantic tree-width".

Left-to-right By contrapositive, we show that if $\+C$ has unbounded "tree-width", then its "evaluation problem" is -hard via an "FPT"-reduction from the
""parameterized clique problem"". This is the problem of, given a parameter $k$ and a simple graph $G$, whether $G$ contains a $k$-clique. We do this by a simple adaptation of the proof of Grohe <cit.> for the case of "CQs".

Given an instance $\langle G,k \rangle$ of the "parameterized clique problem", the idea is to first search for a query $\gamma \in \+C$ of “sufficiently large” "semantic tree-width".

Let us call an "expansion" $\xi$ of a "UC2RPQ" to be ""maximal"" if there is no other "expansion" $\xi'$ such that $\xi \strcontained \xi'$.
The ""core"" of a "CQ" is the result of repeatedly removing any atom which results in an equivalent query. It is unique up to isomorphism (see, "eg", <cit.>), and a "CQ" has "semantic tree-width" $k$ iff its "core" has "tree-width" $k$ <cit.>.

If a "finitely-redundant" "C2RPQ" has "semantic tree-width" $\geq k$, then there is a "maximal" "expansion" thereof of "semantic tree-width" $\geq k$.

The set of all "maximal" "expansions" of queries from $\+C$ is r.e.

We enumerate all "maximal" "expansions" of $\+C$ until we find one such "expansion" $\xi$ whose "core" contains a $K \times K$ grid as a minor, for $K = {k \choose 2}$.
We know that this must happen by the Excluded Minor Theorem <cit.>, stating that there exists a function $f : \Nat \to \Nat$ such that for every $n \in \Nat$ every graph of "tree-width" at least $f(n)$ contains a $(n \times n)$-grid as a minor.
Once we get hold of such a "maximal" "expansion" $\xi$, we proceed as in <cit.> to produce, in polynomial time, a "graph database" $G_\xi$ such that:

* there is a "homomorphism" $G_\xi \homto \xi$, and

* $G_\xi$ "satisfies" $\xi$ if, and only if, $G$ has a clique of size $k$.

Now consider the "UC2RPQ" $\Gamma \in \+C$ of which $\xi$ is an expansion, and observe that if $G_\xi$ "satisfies" $\Gamma$, then we must have that $G_\xi$ also "satisfies" $\xi$, by the fact that $G_\xi \homto \xi$ and $\xi$ is "maximal". Hence, the following are equivalent:

* $G_\xi$ "satisfies" $\Gamma$,

* $G_\xi$ "satisfies" $\xi$,

* $G_\xi$ contains a $k$-clique.

This finishes the "FPT"-reduction.

Right-to-left This direction does not need any of the hypotheses (neither "finite-redundancy",  $\wone \neq $ "FPT", nor r.e.), by <Ref>.

§.§ Larger Classes

A natural and simple approach to extend the expressive power of "CRPQs" is to close the queries by transitive closure. That is, given a binary "CRPQ" $\gamma(x,y)$ we can consider "CRPQ" over the extended alphabet $\A \cup \set \gamma$, where the label $\gamma$ is interpreted as the binary relation defined by $\gamma(x,y)$. This is the principle behind ""Regular Queries"" <cit.>. The notion of "tree-width" can be easily lifted to this class, and classes of bounded "tree-width" still have a polynomial-time "evaluation problem". However, this class has not yet been studied in the context of the "semantic tree-width". It is not known if the "semantic tree-width $k$ problem" is decidable, nor whether classes of bounded "semantic tree-width" have an "FPT" "evaluation problem".

Is the "semantic tree-width $k$ problem" for "Regular Queries" decidable?

§.§ Different Notions

"CRPQs" of small "tree-width" or "path-width" enjoy a tractable "evaluation problem". However, it must be noticed that "containment" between "tree-width" $k$ or "path-width" $k$ queries is still very hard: -complete (even for $k=1$) <cit.>. The more restrictive measure of “"bridge-width"” <cit.> has been proposed as a more robust measure, which results in classes of queries which are well-behaved both for "evaluation" (since "bridge-width" $k$ implies "tree-width" $\leq k$) and for "containment" (since "containment" of bounded-"bridge-width" classes is in ).
It is not hard to see that "bridge-width" is closed under "refinements", and thus that this notion is amenable to our approach ("cf" <Ref>)

Is the problem of whether a "UC2RPQ" is equivalent to a "UC2RPQ" of "bridge-width" at most $k$ decidable?

§ POLYNOMIAL-TIME EVALUATION OF QUERIES OF BOUNDED TREE-WIDTH

A ""semi-join"" is a "CQ" of the form $q(\bar x) = R(\bar x) \land S(\bar y)$, noted $R(\bar x) \intro*\sjoin S(\bar y)$, where $\bar x$ and $\bar y$ may contain common variables and constants. ""Yannakakis algorithm"" <cit.> allows to evaluate any Boolean "acyclic"
An ""acyclic"" "CQ" over arbitrary relational structures is one which admits a "tree decomposition" whose set of "bags" are the sets of variables of its atoms (also known as “generalized hyper tree-width 1” or “$\alpha$-acyclicity” of its underlying hypergraph).
"conjunctive query" $q$ on an $n$-tuple relational database in $\+O(|q| \cdot \costjoin(n))$, where $\intro*\costjoin(n)$ is the cost of performing a "semi-join": $\+O(n \cdot \log(n))$ for Turing machines, or $\+O(n)$ for a RAM model.[
We use Random Access Machines (RAMs) with domain $\Nat$, in which we assume that the RAM's memory is initialized to 0.
For every fixed dimension $d \geq 1$  we have available an unbounded number of $d$-ary arrays $A$ such that for given $(n_1, \dotsc, n_d) \in \Nat^d$ the entry $A[n_1, \dotsc, n_d]$ at position $(n_1, \dotsc, n_d)$ can be accessed in constant time.
To compute $R(\bar x \, \bar y) \sjoin S(\bar y \, \bar z)$, where $\bar y$ are the only common variables between the atoms and $n_R$ and $n_S$ are the number of tuples in $R$ and $S$ respectively, we may assume that constants from the relations are encoded as numbers in binary, of size $\+O(\log(n_R + n_S))$.
We first encode the relation $R$ projected onto $\bar y$, as an array $A$ of the dimension of $\bar y$ in $\+O(n_R)$, by putting a `1' in $A$ for each tuple of $R$.
Then, for each tuple of $S$ we test if the $\bar y$-projection it belongs to $A$, if so we put a `2' in the array $A$, this is $\+O(n_S)$.
Finally, for each tuple of $R$ we output the tuple if its projection onto $\bar y$ has a `2' in $A$. This last step takes $\+O(n_R)$.

We reduce the "evaluation problem" for "C2RPQs" of "tree-width" $k$ to the "evaluation problem" of Boolean acyclic "CQs". First, if we receive $\Gamma (\bar x)$, $G$ and $\bar v$ as input, we replace the "free variables" $\bar x$ of $\Gamma$ with the "graph database" nodes $\bar v$ as constants, to obtain a Boolean "C2RPQ" (with constants). Let us therefore assume that $\Gamma$ is Boolean.
Take any $\gamma \in \Gamma$ and a "tagged tree decomposition" $(T, \bagmap, \tagmap)$ of "width" at most $k$ of $\gamma$.[By a "tagged tree decomposition" of $\gamma$ we mean one for the identity $\gamma \homto \gamma$.] It is easy to see that we can assume that the decomposition is of linear size in the number of "atoms" $\nbatoms{\gamma}$. For every "bag" $v$ of the decomposition containing $\bagmap(v)=\set{x_1, \dotsc, x_t}$ consider the following relation $R_v$ consisting of all tuples of "database" nodes $(v_1, \dotsc, v_t)$ such that for every "atom" $A=x_i \atom{L} x_j$ in $\tagmap^{-1}(v)$ we have that $(v_i, v_j)$ "satisfies" $A$.

It then follows that

* each $R_v$ is of size $\+O(|G|^{k+1})$,

* the "Boolean" "CQ" $q = \bigwedge_{v \in \vertex{T}} R_v(\bagmap(v))$ is "acyclic" and of size linear in $\nbatoms{\gamma}$, and

* $q$ is "equivalent" to $\gamma$.

Hence, "Yannakakis algorithm" yields a complexity of $\+O(\size{\gamma} \cdot \costjoin(|G|^{k+1}))$. That is, $\+O(\size{\gamma} \cdot |G|^{k+1} \cdot \log{|G|})$, or $\+O(\size{\gamma} \cdot |G|^{k+1})$ in a RAM model.

We are only left with the cost of computing the relation $R_v$ for any given $v \in \vertex{T}$. Let $\+A_v= \set{A_1(y_1,z_1), \dotsc, A_s(y_s,z_s)}$ be the set of all "atoms" of $\tagmap^{-1}(v)$. Let $\bagmap(v)=\set{x_1, \dotsc, x_t}$.
Compute first the relation $S_i = \set{ (u,u') \in \vertex{G}^2 : (u,u') \text{ "satisfies" } A_i(y_i,z_i)}$ for every $i$; this can be done in $\+O(|G| \cdot |L_i \times \Gpm|)$, where $L_i \times \Gpm$ is the product of the NFA for the regular language $L_i$ of $A_i$ and the expanded "database" $\Gpm$. Compute also the relation $U = \vertex{G}^t$ in $\+O(|G|^{t})$ (hence in $\+O(|G|^{k+1})$). Finally, we compute $R_v$ by performing $s$ nested "semi-joins"

\[
((U(x_1, \dotsc, x_t) \sjoin S_1(y_1,z_1)) \sjoin S_2(y_2,z_2) \dotsb )\sjoin S_s(y_s,z_s)
\]

in $\+O(s \cdot |G|^{k+1} \cdot \costjoin(|G|^{k+1}))$, that is, in $\+O(s \cdot |G|^{k+1} \cdot \log(|G|))$ or $\+O(s \cdot |G|^{k+1})$ in a RAM model. Repeating this for every "bag" we can compute all the $R_v$'s in $\+O(\size{\gamma} \cdot |G|^{k+1} \cdot \log(|G|))$ (observe that we iterate only once on each "atom", since we are using a "“tagged” decomposition@tagged tree decomposition") or $\+O(\size{\gamma} \cdot |G|^{k+1})$ in a RAM model.

§ ALTERNATIVE UPPER-BOUND FOR CONTAINMENT OF UC2RPQS

In <Ref>, in order to prove the "2ExpSpace" upper-bound to the
"semantic tree-width $k$ problem" (<Ref>), we proved an upper-bound on containment
of "UC2RPQs" (<Ref>) by relying on the notion of "bridge-width".
In this section, we give a slightly different bound, which is more elementary (in the sense that it
does not rely on "bridge-width") and still yields a "2ExpSpace" upper-bound to the "semantic
tree-width $k$ problem".

The "containment problem" $\Gamma \contained \Delta$ between two "UC2RPQs" can be solved in non-deterministic space $2^{c\cdot \size{\Gamma}} + p_{\Delta} \cdot 2^{c\cdot m_\Delta}$, where $m_\Delta$ is the size of the greatest disjunct of $\Delta$, namely $m_\Delta = \max{\{\size{\delta_\Delta} \mid \delta \in \Delta\}}$, $p_\Delta$
is the number of disjuncts of $\Delta$, and $c$ is a constant.

The proposition can be shown by close inspection of the standard "containment problem" for "UC2RPQs" <cit.>: the "containment problem" is reduced, in this instance, to checking the inclusion between NFAs of the form[$\+A_\Gamma$ and $\+A_\delta$ are denoted $A_1$ and $A_3$, respectively, in <cit.>.]

\begin{equation}
\AP\label{eq:containment-to-inclusion-regexp}
\+A_\Gamma \subseteq^? \bigcup_{\delta \in \Delta} \+A_\delta,
\end{equation}

where $A_\Gamma$ is a regular expression which is exponential in $\size{\Gamma}$,
and $\+A_\delta$ has size exponential in $\size{\delta} \leq m_\Delta$.
Should (<ref>) not hold, there must exist a counterexample of size at most

\[
2^{|\+A_\Gamma|}\times \prod_{\delta \in \Delta} 2^{|\+A_\delta|}
\]

Letting $p_\Delta$ be the number
of queries in $\Delta$, we get that the logarithm of the expression above—representing the
size of the non-deterministic space needed by the algorithm—is upper-bounded by

\[
c_0 \Bigl(|\+A_\Gamma| + \sum_{\delta \in \Delta} |\+A_\delta|\Bigr)
\mathrel{\underset{\tiny\textrm{eventually}}{\leq}}
2^{c\cdot \size{\Gamma}} + p_{\Delta} \cdot 2^{c\cdot n_\Delta},
\]

for some constants $c_0$ and $c$.

§ PATH-WIDTH IS NOT CLOSED UNDER REFINEMENTS

Let $X$ be a set of $k-1$ variables. Consider the undirected multigraph $\+G_k$ whose set of nodes is
$X \cup \{y_0, y_1, y_2, y_3\}$ with the following edge set:

* each $X \cup \{y_i\}$ ($i \in \{0,1,2,3\}$) is a clique,

* there is an edge from $y_i$ to $y_{i+1}$  for $i \in \{0,1,2\}$, and

* there is a second edge from $y_1$ to $y_2$.

By definition, this graph has "path-width" exactly $k$: it is as least $k$ since it contains
a $(k+1)$-clique—namely $X \cup \{y_i,y_{i+1}\}$—and, moreover the following sequence of bags—"cf" <Ref>—defines a path-decomposition of $\+G_k$ of "width" $k$:

\[
\langle X \cup\{y_0,y_1\},\; X \cup\{y_1,y_2\},\; X \cup\{y_2,y_3\} \rangle.
\]

Let $\+G'_k$ be the graph obtained by "refining" the second edge from $y_1$ to $y_2$, into
two edges $\langle y_1, z \rangle$ and $\langle z, y_2 \rangle$, where $z$ is a new variable.
We claim that $\+G'_k$ has path-width at least $k+1$. Indeed, let
$\langle T, \bagmap, \tagmap \rangle$ be a "path decomposition" of $\+G'_k$. Letting $n$ be the number of nodes of $T$, we let $b_i \defeq \bagmap(\text{$i$-th node of $T$}) \in \vars(\+G_k)$.

* Let $i$ be the smallest index, if it exists, "st" $X \not\subseteq b_i$,
say $x \not\in b_i$ for some $x$. Assume moreover that $z \not\in b_i$.
This means that either $x \not\in b_j$ for all $j \leq i$ or for all $j \geq i$.
Assume "wlog" that we are in the first case.
Assume that some edge $\langle u,v \rangle$ is "tagged" in a "bag" $b_j$ for some $j \leq i$.

Assume that $u$ and $v$ are distinct from $z$. Then both
$\langle u, x \rangle$ and $\langle v, x \rangle$ are edges, so
it means that $u$ and $v$, they have to be "tagged" somewhere, and so both $u$ and $v$
must belong to all "bags" $b_j, b_{j+1}, \hdots, b_i, b_{i+1}$ since $b_{i+1}$ is the first "bag" containing $x$. In particular, one can "tag" the edge $\langle u,v \rangle$ in $b_{i+1}$ instead of $b_j$.
After iterating this process, no edge is "tagged" in a "bag" $b_j$ for some $j \leq i$, and hence all of these "bags" can be removed (including $b_i$).
Hence, the "path decomposition" has the following shape: first, we have a few bags containing $z$, and then all bags must contain $X$.

* Because $\{ y_1,y_2, z \}$ is a clique, there must be a "bag" $b_i$ containing all three of them. If this "bag" is one that contains $X$ we are done: we found a bad with
$k+2$ nodes—see <Ref>.
Otherwise, we are in a situation similar to <Ref>.
Assume "wlog" that $b_i$ occurs before all "bags" containing X, the other situation being symmetric. Since $\{y_1,y_2\}\cup X$ is a clique, every "bag" between $b_i$ and the first
bag $b_j$ containing $X$ must contain $y_1$ and $y_2$.
But then, the edge $\langle y_0,y_1 \rangle$ must be tagged somewhere: it is it before
$b_j$, then, using the fact that $\{y_0,y_1\}\cup X$ is a clique, we have $\{y_0,y_1,y_2\}\cup X \subseteq b_j$, and we are done. The same argument works for the edge $\langle y_2, y_3 \rangle$. So, let $j_1,j_2$ be the indices "st" $j_i > j$, with:

\[
X \cup \{y_0,y_1\} \subseteq b_{j_1}
\quad\text{and}\quad
X \cup \{y_2,y_3\} \subseteq b_{j_2}.
\]

If $j_1 < j_2$ then $y_2$ belongs to both $b_j$ and $b_{j_2}$, so it also belongs to $b_{j_1}$, which must have size at least $k+2$. Dually if $j_1 > j_2$, then $y_1$ belongs to both $b_j$ and $b_{j_1}$, and hence it belongs to $b_{j_2}$ which must have size at least $k+2$.

In all cases, the "path decomposition" has width at least $k+1$, showing that
$\+G'_k$ has "path-width" at least[In fact it has "path-width" exactly $k+1$.] $k+1$.

§ ACKNOWLEDGMENT

The work is supported by ANR QUID, grant ANR-18-CE40-0031.