# Constructing a fully homomorphic encryption scheme
with the Yoneda Lemma

Rémy Tuyéras<EMAIL_ADDRESS>
###### Abstract.

This paper redefines the foundations of asymmetric cryptography’s homomorphic
cryptosystems through the application of the Yoneda Lemma. It explicitly
illustrates that widely adopted systems, including ElGamal, RSA, Benaloh,
Regev’s LWE, and NTRUEncrypt, directly derive from the principles of the
Yoneda Lemma. This synthesis gives rise to a holistic homomorphic encryption
framework named the Yoneda Encryption Scheme. Within this scheme, encryption
is elucidated through the bijective maps of the Yoneda Lemma Isomorphism, and
decryption seamlessly follows from the naturality of these maps. This
unification suggests a conjecture for a unified model theory framework,
providing a basis for reasoning about both homomorphic and fully homomorphic
encryption (FHE) schemes. As a practical demonstration, the paper introduces
an FHE scheme capable of processing arbitrary finite sequences of encrypted
multiplications and additions without the need for additional tweaking
techniques, such as squashing or bootstrapping. This not only underscores the
practical implications of the proposed theoretical advancements but also
introduces new possibilities for leveraging model theory and forcing
techniques in cryptography to facilitate the design of FHE schemes.

##  1\. Introduction

###  1.1. Short presentation

This work proposes the unification of various asymmetric homomorphic
encryption schemes under a singular framework, establishing what we term the
Yoneda Encryption Scheme. Beyond its role in consolidating disparate
encryption methodologies, this scheme offers a versatile framework for
comparing existing homomorphic encryption schemes and devising novel ones.
This unified approach presents a promising avenue for constructing a
comprehensive theory for fully homomorphic cryptography, addressing a critical
gap in the field. Historically, the efficiency of fully homomorphic encryption
schemes has been hindered by the complexity of their foundational theories,
primarily relying on commutative group theory and attempting to reconcile
properties from commutative ring theory (as noted in [1, 7, 22]).

To tackle the challenges associated with axiomatization, our theoretical
framework draws inspiration from a category-theoretic variant of model theory
known as limit sketch theory. We illustrate how assemblies of models within a
given limit sketch can lead to the creation of novel encryption schemes.
Importantly, these schemes offer cryptographers a guiding principle for
designing cryptosystems that are not strictly reliant on commutative groups.
By harnessing the expressive power of limit sketch theory, particularly in its
domain of forcing techniques often articulated through reflective
subcategories, we clarify how our overarching framework can incorporate these
techniques to enforce specific properties within the underlying theory of a
cryptosystem.

As a practical application, we introduce an unbounded fully homomorphic
encryption scheme that operates within modules over rings of polynomials. This
scheme represents an enhancement over prior FHE implementations as it
exercises full control over noise accumulation during iterated operations.
Throughout this paper, our goal is to establish the groundwork for integrating
more sophisticated forcing techniques into cryptography, thereby unlocking
novel avenues for designing efficient fully homomorphic encryption schemes.

###  1.2. Background

Homomorphic encryption (HE) is an encryption technique that converts a message
$m$ into a ciphertext $c$ while maintaining specific arithmetic operations,
notably multiplication and addition. This feature is particularly crucial for
securing computations on untrusted servers. Fully homomorphic encryption (FHE)
further extends this capability to encompass both addition and multiplication
operations simultaneously. This advancement is significant as it enables the
execution of logical operations such as $\mathsf{AND}$ and $\mathsf{OR}$ on
encrypted data. Consequently, algorithms can be performed on untrusted remote
servers while the data remains securely encrypted. The applications of such
encryption methods are diverse, often finding utility in machine learning
computations and collaborative work conducted on cloud platforms (refer to
[22, 8] for a comprehensive overview).

At a more formal level, HE explores encryption schemes that exhibit
_malleability_ , indicating the persistence of a given operation $\square$
throughout the encryption-decryption process $(\mathsf{Enc},\mathsf{Dec})$.
This characteristic can be mathematically expressed for a generic operation
$\square$ as follows (refer to [1, 22]):

$\mathsf{Dec}(\mathsf{Enc}(m_{1})\square\mathsf{Enc}(m_{2}))=m_{1}\square
m_{2}$

To provide historical context for homomorphic encryption, extensive surveys,
as cited in [22, 1], meticulously document its evolution over time. However,
for the specific focus of this paper, our discussion will center on the
fundamental background necessary to grasp the key concepts outlined in the
current work.

HE schemes fall into three categories based on their proximity to the
definition of a fully homomorphic encryption scheme: partially homomorphic
(PHE), somewhat homomorphic (SWHE), or fully homomorphic (FHE) schemes. The
pursuit of FHE schemes, considered the pinnacle of cryptographic achievement,
reached its culmination with Gentry’s groundbreaking work in 2009 [14].
Following this pivotal breakthrough, the field of FHE schemes underwent four
distinct _generations_ of refinement [28, 5, 15, 6]. This transformative
evolution was essentially propelled by the introduction of a technique known
as _bootstrapping_ by Gentry.

To elucidate the concept of bootstrapping, let us consider an encryption
scheme comprising an encryption algorithm $\mathsf{Enc}:K_{0}\times M\to C$
and a decryption algorithm $\mathsf{Dec}:K_{1}\times C\to M$. Recall that the
encryption-decryption protocol yields the relations $\mathsf{Enc}(k^{0},m)=c$
and $\mathsf{Dec}(k^{1},c)=m$ for a public key $k^{0}$ and a private key
$k^{1}$. In the context of Gentry’s framework, we also desire an encryption
algorithm $\mathsf{Enc}$ to satisfy the following equation for a given set $S$
of pairs $(\square_{C},\square_{E})$ of algebraic operations:

$\mathsf{Enc}(k^{0},m_{1})\square_{C}\mathsf{Enc}(k^{0},m_{2})=\mathsf{Enc}(k^{0},m_{1}\square_{E}m_{2})$

However, in practice, for the encryption $\mathsf{Enc}$ to be secure, it is
imperative to introduce a controlled amount of noise $r$ into the mappings of
the encryption $\mathsf{Enc}$. As a result, utilizing operations on encrypted
data usually results in the accumulation of more noise within the encryption
process such that a long algebraic operation

$F(\mathsf{Enc}(k^{0},m_{1}),\dots,\mathsf{Enc}(k^{0},m_{n}))$

may not be of the form $\mathsf{Enc}(k^{0},F(m_{1},\dots,m_{n}))$. To achieve
full homomorphic functionality, the accumulated noise must be eradicated
through the decryption of data. However, decrypting this data directly on the
remote server poses a significant security risk, exposing sensitive
information to untrusted third parties. Gentry’s ingenious insight was to
recognize that the decryption algorithm $\mathsf{Dec}$ could be expressed as
an arithmetic operation $\square_{\mathsf{Dec}}$, formed by combinations of
operations from the set $S$.

This led to the concept that encrypted data could be shielded by an additional
layer of encryption, provided by a key pair $(q^{0},q^{1})$. This pair would
be utilized to encrypt the private key $k^{1}$ for secure transmission to the
server. Consequently, a sequence of operations $F$ operating on encrypted data
could be “refreshed” through an initial encryption using the key $q^{0}$. In
practical terms, the server would only need to compute the following operation
on encrypted information to obtain a freshly encrypted result:

$\displaystyle\mathsf{Enc}(q^{0},k^{1})\square_{\mathsf{Dec}}\mathsf{Enc}(q^{0},F(\mathsf{Enc}(k^{0},m_{1}),\dots,\mathsf{Enc}(k^{0},m_{n})))$
$\displaystyle=\mathsf{Enc}(q^{0},k^{1}\square_{\mathsf{Dec}}F(\mathsf{Enc}(k^{0},m_{1}),\dots,\mathsf{Enc}(k^{0},m_{n})))$
$\displaystyle=\mathsf{Enc}(q^{0},k^{1}\square_{\mathsf{Dec}}\mathsf{Enc}(k^{0},F(m_{1},\dots,m_{n})))$
$\displaystyle=\mathsf{Enc}(q^{0},F(m_{1},\dots,m_{n}))$

All previously published FHE schemes have incorporated bootstrapping
techniques. While these techniques enable the attainment of FHE, they also
impose significant computational burdens on these schemes. This paper
introduces a novel framework that achieves FHE without relying on Gentry’s
bootstrapping technique. The framework is derived from the Yoneda Lemma [19],
which not only provides a new foundation for FHE but also formalizes the
fundamental intuitions that have led to the development of bootstrapping
techniques.

In particular, the Yoneda Lemma establishes a profound connection between
theory and models, resembling Gentry’s proposition that the operation
$\mathsf{Dec}$ should be _realizable_ within the model used for encrypting
messages. While we apply the Yoneda Lemma at a practical level, this paper
posits that many concepts and techniques commonly used in homomorphic
encryption find their foundation in model theory, category theory, and,
ultimately, forcing techniques.

###  1.3. Motivation and roadmap

In essence, the Yonedian formalism serves as a fundamental tool for
distinguishing intrinsic elements of a cryptosystem from those introduced
through external concepts. Concepts forced into the cryptosystem, which do not
align with the underlying theory, often hinder the emergence of homomorphic
properties. Once established, the Yonedian formalism becomes instrumental in
deriving desired equations and relations that can be realized within the
underlying theory. This mirrors Gentry’s approach, where the decryption
algorithm is implemented within the algebraic structure associated with the
space of ciphertexts. Thus, by systematically deconstructing the process of
imposing specific properties on a theory, we enable the deduction of
appropriate homomorphic properties.

In the context of this paper, the Yonedian formalism significantly enhances
our comprehension of homomorphic properties within polynomial rings. Through
the lens of a category-theoretic formalism, we have identified a suitable
theory for post-quantum homomorphic encryption schemes. Notably, this
formalism emphasizes the importance of viewing rings of polynomials as
$\mathbb{Z}[X]$-modules, elucidating the relationships between the module and
its corresponding ring $\mathbb{Z}[X]$, as well as the action of the ”free”
commutative group on both the ring and the module. This clarification has led
us to identify a binary operation (Definition 5.16) based on $3$-tensors in
$\mathbb{Z}$, from which a fully homomorphic encryption scheme naturally
follows (section 5.1).

The paper is structured into three main sections. In the initial section (3),
our aim is to provide or review the necessary category-theoretical background
essential for comprehending the paper. While we shall not delve into all
formal calculations, our objective is to establish a comprehensive bridge
between readers with diverse backgrounds, whether in category theory or
cryptography. Within this first section, we revisit fundamental concepts such
as limits, cones, universal cones, limit sketches, and various versions of the
Yoneda Lemma.

The first version, articulated in Theorem 3.11, reinstates the conventional
statement applicable to categories of functors. The second version, presented
in Theorem 3.12, slightly extends the first version by incorporating colimits,
making it more applicable to a broader spectrum of cryptosystems. The third
and final version, outlined in Theorem 3.15, generalizes the Yoneda Lemma to
reflective subcategories. Although not a novel result, this version is less
frequently mentioned in the existing literature.

Throughout section 3.4 and section 3.5, we delve into various applications of
the Yoneda Lemma across different categories, preparing the reader for the
calculatory considerations employed in the subsequent sections.

Following this preliminary section, section 4 introduces the general formalism
of the paper, referred to as the Yoneda Encryption Scheme (section 4.1). This
encryption scheme serves as the foundation for describing and categorizing
common cryptosystems, including ElGamal (section 4.2), RSA (section 4.3),
Benaloh (section 4.4), NTRU (section 4.5), and LWE (section 4.6). The
intention is not only theoretical but also practical, providing readers with a
hands-on exercise in identifying scenarios where each facet of the Yoneda
Encryption Scheme can be effectively applied.

Lastly, in section 5, we leverage the insights gained from the diverse
applications of the Yoneda Encryption Scheme (discussed in section 4) to
establish a theoretical foundation for a fully homomorphic encryption system.
This system is named the Arithmetic Channel Encryption Scheme (ACES). We
define this scheme using the Yoneda formalism in section 5.1. Subsequently, in
section 5.2, we employ a slightly more general formalism to show that ACES
defines a leveled fully homomorphic encryption scheme (refer to Theorem 5.22
and Proposition 5.20). Then, in section 5.3, we add a refresh operation to our
arithmetic, which turns ACES into a proper fully homomorphic encryption scheme
(see Theorem 5.25 and Application 5.27).

To conclude, our central contribution extends beyond providing a comprehensive
theory for homomorphic encryption (HE) schemes. Notably, our key result
asserts that ACES achieves non-leveled full homomorphism without relying on
bootstrapping techniques. For those interested in exploring the practical
implications of our findings, we have developed a user-friendly Python package
supporting this theoretical paper, accessible on the following GitHub page:
https://github.com/remytuyeras/aces.

##  2\. Acknowledgment

The author would like to thank Mark Schultz for a pertinent question, which
prompted a refinement of an earlier version of the cryptosystem proposed in
section 5.

##  3\. Preparation

###  3.1. Conventions

We assume the reader’s familiarity with fundamental concepts of category
theory, including categories, functors, and natural transformations, among
other classical definitions. For a comprehensive introduction to these
concepts, we recommend consulting [19]. This section serves not only to recap
less obvious concepts but also to establish the notations and conventions
consistently employed throughout the paper.

######  Convention 3.1 (Homsets and small categories).

For every category $\mathcal{C}$, and every pair $(X,Y)$ of objects in
$\mathcal{C}$, we will denote as $\mathcal{C}(X,Y)$ the set of arrows from $X$
to $Y$. Every set of arrows of the form $\mathcal{C}(X,Y)$ will be referred to
as a _homset_. We will say that $\mathcal{C}$ is _small_ if the class of
objects of $\mathcal{C}$ is a proper set (as opposed to a class). For every
category $\mathcal{C}$ and every object $X$, we will denote as
$\mathsf{id}_{X}$ the identity arrow $X\to X$ in $\mathcal{C}$.

######  Convention 3.2 (Opposite category).

For every category $\mathcal{C}$, we will denote as
$\mathcal{C}^{\mathsf{op}}$ the category whose objects are those of
$\mathcal{C}$ and whose arrows from a given object $X$ to a given object $Y$
are the elements of the homsets $\mathcal{C}(Y,X)$. The composition of
$\mathcal{C}^{\mathsf{op}}$ is the one directly inherited from $\mathcal{C}$.

######  Convention 3.3 (Opposite functors).

The opposite operation on categories extends to functors as follows: For every
pair $(\mathcal{C},\mathcal{D})$ of categories and every functor
$F:\mathcal{C}\to\mathcal{D}$, we denote as
$F^{\mathsf{op}}:\mathcal{C}^{\mathsf{op}}\to\mathcal{D}^{\mathsf{op}}$ the
obvious functor that sends an arrow $f:Y\to X$ in $\mathcal{C}^{\mathsf{op}}$
to the arrow $F(f):F(Y)\to F(X)$ in $\mathcal{D}^{\mathsf{op}}$.

######  Convention 3.4 (Sets).

We denote as $\mathbf{Set}$ the category of sets and functions. For every non-
negative integer $n$, we will denote as $[n]$ the set of integers from $1$ to
$n$. If $n$ is zero, then the set $[n]$ is the empty set.

######  Convention 3.5 (Functors).

For every pair $(\mathcal{C},\mathcal{D})$ of categories, we will denote as
$[\mathcal{C},\mathcal{D}]$ the category whose objects are functors
$\mathcal{C}\to\mathcal{D}$ and whose arrows are the natural transformations
between functors $\mathcal{C}\to\mathcal{D}$.

######  Definition 3.6 (Constant functor).

Let $A$ be a small category. For every category $\mathcal{C}$, we will denote
as $\Delta_{A}$ the functor $\mathcal{C}\to[A,\mathcal{C}]$ the obvious
functor that sends an object $X$ in $\mathcal{C}$ to the constant function
$A\to\mathbf{1}\to\mathcal{C}$ that maps every object $a$ in $A$ to the object
$X$ in $\mathcal{C}$. For every object $X$ in $\mathcal{C}$, the functor
$\Delta_{A}(X)$ sends arrows in $A$ to identities on $X$. For every arrow
$f:X\to Y$ in $\mathcal{C}$, the natural map $\Delta_{A}(f)$ are given by
copies of the arrow $f:X\to y$ for each object $a$ in $A$.

######  Definition 3.7 (Limits and colimits).

Let $A$ be a small category and $\mathcal{C}$ be a category. The category
$\mathcal{C}$ will be said to have _limits over $A$_ if the functor
$\Delta_{A}:\mathcal{C}\to[A,\mathcal{C}]$ is equipped with a right adjoint
$\mathsf{lim}_{A}:[A,\mathcal{C}]\to\mathcal{C}$. This means that for every
object $X$ in $\mathcal{C}$ and every functor $F:A\to\mathcal{C}$, the
category $\mathcal{C}$ is equipped with a natural isomorphism as follows:

(3.1)
$[A,\mathcal{C}](\Delta_{A}(X),F)\cong\mathcal{C}(X,\mathsf{lim}_{A}(F))$

Conversely, the category $\mathcal{C}$ will be said to have _colimits over
$A$_ if the functor $\Delta_{A}:\mathcal{C}\to[A,\mathcal{C}]$ is equipped
with a left adjoint $\mathsf{col}_{A}:[A,\mathcal{C}]\to\mathcal{C}$. This
means that for every object $X$ in $\mathcal{C}$ and every functor
$F:A\to\mathcal{C}$, the category $\mathcal{C}$ is equipped with a natural
isomorphism as follows:

(3.2)
$[A,\mathcal{C}](F,\Delta_{A}(X))\cong\mathcal{C}(\mathsf{col}_{A}(F),X)$

######  Example 3.8 (Sets).

The category $\mathbf{Sets}$ has limits and colimits over all small
categories. As a result, we can show (see [19]) that for every small category
$[T,\mathbf{Set}]$ has limits and colimits over all small categories (take
these limits and colimits to be the pointwise limits and colimits).

It follows from a straightforward reformulation of the definition of limits
and colimits in $\mathbf{Set}$ and that of natural transformations that the
following isomorphism always exist.

######  Proposition 3.9.

Let $A$ be a small category and $\mathcal{C}$ be a category. If $\mathcal{C}$
has limits over $A$, then there is a natural isomorphism (in $X$ and
$F:A\to\mathcal{C}$), where the rightmost limit is defined on the functorial
mapping $a\mapsto\mathcal{C}(X,F(a))$

$\mathcal{C}(X,\mathsf{lim}_{A}(F))\cong\mathsf{lim}_{A}(\mathcal{C}(X,F(-)))$

Similarly, if $\mathcal{C}$ has colimits over $A$, then there is a natural
isomorphism (in $X$ and $F:A\to\mathcal{C}$), where the rightmost limit is
defined on the functorial mapping $a\mapsto\mathcal{C}(F(a),X)$

$\mathcal{C}(\mathsf{col}_{A}(F),X)\cong\mathsf{lim}_{A^{\mathsf{op}}}(\mathcal{C}(F^{\mathsf{op}}(-),X))$

###### Proof.

The isomorphisms of the statememt follow from the isomorphisms given in
Definition 3.7 and the straightforward correspondences given by the following
isomorphisms.

$\begin{array}[]{lll}[A,\mathcal{C}](\Delta_{A}(X),F)&\to&\mathsf{lim}_{A}(\mathcal{C}(X,F))\\\
(f_{a}:X\to F(a))_{a}&\mapsto&(f_{a}:X\to
F(a))_{a}\end{array}\quad\textrm{and}\quad\begin{array}[]{lll}[A,\mathcal{C}](F,\Delta_{A}(X))&\to&\mathsf{lim}_{A}(\mathcal{C}(F,X))\\\
(f_{a}:F(a)\to X)_{a}&\mapsto&(f_{a}:F(a)\to X)_{a}\end{array}$

As can be seen through the previous mappings, an element of
$[A,\mathcal{C}](\Delta_{A}(X),F)$ or $[A,\mathcal{C}](F,\Delta_{A}(X))$ can
be interpreted as a tuple in the limit $\mathsf{lim}_{A}(\mathcal{C}(X,F))$ or
$\mathsf{lim}_{A}(\mathcal{C}(F,X))$, respectively. ∎

######  Definition 3.10 (Full and faithful).

Let $\mathcal{C}$ and $\mathcal{D}$ be two categories.

  * 1)

A functor $F:\mathcal{C}\to\mathcal{D}$ is said to be _full_ if for every pair
$(X,Y)$ of objects in $\mathcal{C}$, the functor $F$ induces a surjective map
$\mathcal{C}(X,Y)\to\mathcal{D}(F(X),F(Y))$;

  * 2)

A functor $F:\mathcal{C}\to\mathcal{D}$ is said to be _faithful_ if for every
pair $(X,Y)$ of objects in $\mathcal{C}$, the functor $F$ induces an injective
map $\mathcal{C}(X,Y)\to\mathcal{D}(F(X),F(Y))$.

###  3.2. Yoneda lemma for functors

Consider a small category $T$. Recall that the homsets of $T$ induce a functor
$T^{\mathsf{op}}\to[T,\mathbf{Set}]$ through the nested mapping rules
$Y:a\mapsto(b\mapsto T(a,b))$ (see [19]). Intuitively, this functor serves as
an embedding of the “theory” into the category $[T,\mathbf{Set}]$, which
represents the set of models for the theory $T$. For each object $a$ in
$\mathcal{C}$, the functor $Y(a):T\mapsto\mathbf{Set}$ is said to be
_representable_ , as it is represented by the object $a$ in the small category
$T$.

######  Theorem 3.11 (Yoneda Lemma).

For every object $a$ in $T$ and every functor $F:T\mapsto\mathbf{Set}$, there
is a function

$\varphi_{a,F}:[T,\mathbf{Set}](Y(a),F)\mapsto F(a),$

natural in $a$ and $F$, that maps a natural transformation
$\theta:Y(a)\Rightarrow F$ to the element $\theta(\mathsf{id}_{a})\in F(a)$,
where $\mathsf{id}_{a}$ denotes the identity arrow in the homset $T(a,a)$. The
function $\varphi_{a,F}$ is a bijection whose inverse is defined by the
function

$F(a)\mapsto[T,\mathbf{Set}](Y(a),F)$

that maps an element $x\in F(a)$ to the natural transformation
$Y(a)\Rightarrow F$ that sends, for every object $b$ in $T$, an arrow $f\in
T(a,b)$ to the element $F(f)(x)\in F(b)$.

###### Proof.

The statement given above can be proven through a straightforward
verification. The reader can learn more about the Yoneda Lemma in [19]. ∎

By taking the functor $F$, in the statement of Theorem 3.11, to be another
representable functor, say $Y(b)$ for some object $b$ in $T$, we can show that
the functor $Y:T^{\mathsf{op}}\to[T,\mathbf{Set}]$ is _fully faithfulness_
(see [19] for instance). It follows from this property that, for every small
category $I$ and every functor $G:I\to[T,\mathbf{Set}]$, if the image $G(i)$
is a representable functor of the fome $Y(a_{i})$, then the mapping $i\mapsto
a_{i}$ induces a functor $H_{G}:I\to T^{\mathsf{op}}$ such that the following
diagram commutes.

$\textstyle{I\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{H_{G}}$$\scriptstyle{G}$$\textstyle{T^{\mathsf{op}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{Y}$$\textstyle{[T,\mathbf{Set}]}$

Below, we use the universal property of colimits to generalize the Yoneda
Lemma to colimits of representable functors. In this respect, let $I$ be a
small category. Since $[T,\mathbf{Set}]$ has colimits over $I$ (Example 3.8),
for every functor $H:I\to T^{\mathsf{op}}$, the colimit
$\mathsf{col}_{I}(Y\circ H)$ of the composite functor $Y\circ
H:I\to\mathcal{C}$ is well-defined.

######  Theorem 3.12 (Yoneda Lemma).

Take $I$ and $H:I\to T^{\mathsf{op}}$ as defined above. For every functor
$F:T\mapsto\mathbf{Set}$, there is a bijection

$\varphi_{H,F}:[T,\mathbf{Set}](\mathsf{col}_{I}(Y\circ
H),F)\mapsto\mathsf{lim}_{I^{\mathsf{op}}}(F\circ H^{\mathsf{op}}),$

natural in the variables $H$ and $F$ over the categories $[I,T^{\mathsf{op}}]$
and $[T,\mathbf{set}]$,

###### Proof.

The proof results from the composition of the natural isomorphisms given by
the Yoneda Lemma (Theorem 3.11) and that given in Proposition 3.9.
Specifically, we obtain the natural isomorphism of the statement from the
following sequence of isomorphisms:

$\displaystyle[T,\mathbf{Set}](\mathsf{col}_{I}(Y\circ H),F)$
$\displaystyle\cong\mathsf{lim}_{I^{\mathsf{op}}}([T,\mathbf{Set}](Y\circ
H^{\mathsf{op}}(-),F))$ $\displaystyle(\textrm{Proposition
\ref{prop:limit_colimits_as_limits_in_set}})$
$\displaystyle\cong\mathsf{lim}_{I^{\mathsf{op}}}(F\circ H^{\mathsf{op}})$
$\displaystyle(\textrm{Yoneda Lemma})$

The composition of the two natural isomorphisms provides the natural
isomorphism $\varphi_{H,F}$. ∎

###  3.3. Yoneda lemma for models of theories

This section extends section 3.2 to reflective subcategories of functor
categories. In practice, these subcategories will correspond to categories
whose objects are limit-preserving functors.

######  Definition 3.13 (Reflective subcategory).

Let $T$ be a small category. We will say that a category $\mathcal{L}$ is a
reflective subcategory of $[T,\mathbf{Set}]$ if it is equipped with a full
inclusion functor $U:\mathcal{L}\hookrightarrow[T,\mathbf{Set}]$ such that the
functor $U$ has a left adjoint $L:[T,\mathbf{Set}]\to\mathcal{L}$.

######  Proposition 3.14 (Colimits).

Let $T$ be a small category and let
$U:\mathcal{L}\hookrightarrow[T,\mathbf{Set}]$ be a reflective subcategory
whose left adjoint is denoted as $L$. The category $\mathcal{L}$ has colimits,
which are the images of the colimits of $[T,\mathbf{Set}]$ via the functor
$L:[T,\mathbf{Set}]\to\mathcal{L}$.

###### Proof.

The proof directly follows from the well-known property that left adjoints
preserve colimits (see [19]). Specifically, the statement follows from the
following isomorphisms, where $I$ is a small category, $X$ is an object in
$\mathcal{L}$ and $F$ is a functor $I\to\mathcal{L}$.

$\displaystyle[I,\mathcal{L}](F,\Delta_{A}(X))$
$\displaystyle\cong[I,[T,\mathbf{Set}]](U\circ F,\Delta_{A}(U(X)))$
$\displaystyle(\textrm{full sbucategory})$
$\displaystyle\cong[T,\mathbf{Set}](\mathsf{col}_{I}(U\circ F),U(X))$
$\displaystyle(\textrm{colimits})$
$\displaystyle\cong\mathcal{L}(L(\mathsf{col}_{I}(U\circ F)),X)$
$\displaystyle(\textrm{adjunction})$

We conclude from the characterization of colimits given in Definition 3.7. ∎

######  Theorem 3.15 (Yoneda Lemma).

Let $I$ and $T$ be small categories and let $H:I\to T^{\mathsf{op}}$ be a
functor. Let also $R:\mathcal{L}\hookrightarrow[T,\mathbf{Set}]$ denote a
reflective subcategory with an adjoint $L:[T,\mathbf{Set}]\to\mathcal{L}$. For
every functor $F:T\mapsto\mathbf{Set}$ in $\mathcal{L}$, there is a bijection

$\phi_{H,F}:\mathcal{L}(\mathsf{col}_{I}(L\circ Y\circ
H),F)\mapsto\mathsf{lim}_{I^{\mathsf{op}}}(U(F)\circ H^{\mathsf{op}}),$

natural in the variables $H$ and $F$ over the categories $[I,T^{\mathsf{op}}]$
and $\mathcal{L}$,

###### Proof.

The proof results from the composition of the natural isomorphisms given by
the version of the Yoneda Lemma stated in Theorem 3.12 and that resulting from
Definition 3.13. Specifically, we obtain the natural isomorphism of the
statement from the following sequence of isomorphisms:

$\displaystyle\mathcal{L}(\mathsf{col}_{I}(L\circ Y\circ H),F)$
$\displaystyle\cong\mathcal{L}(L(\mathsf{col}_{I}(U\circ L\circ Y\circ H)),F)$
$\displaystyle(\textrm{Proposition \ref{prop:colimits_ref_sub}})$
$\displaystyle\cong[T,\mathbf{Set}](\mathsf{col}_{I}(U\circ L\circ Y\circ
H),U(F))$ $\displaystyle(\textrm{Definition
\ref{def:reflective_subcategory}})$
$\displaystyle\cong[I,[T,\mathbf{Set}]](U\circ L\circ Y\circ
H,\Delta_{I}(U(F)))$ $\displaystyle(\textrm{Isomorphism
(\ref{eq:limits_colimits:colim})})$ $\displaystyle\cong[I,\mathcal{L}](L\circ
Y\circ H,\Delta_{I}(F))$ $\displaystyle(\textrm{full subcategory})$
$\displaystyle\cong[I,[T,\mathbf{Set}]](Y\circ H,\Delta_{I}(U(F)))$
$\displaystyle(\textrm{adjunction})$
$\displaystyle\cong[T,\mathbf{Set}](\mathsf{col}_{I}(Y\circ H),U(F))$
$\displaystyle(\textrm{Isomorphism (\ref{eq:limits_colimits:colim})})$
$\displaystyle\cong\mathsf{lim}_{I^{\mathsf{op}}}(U(F)\circ H^{\mathsf{op}})$
$\displaystyle(\textrm{Theorem \ref{theo:YonedaLemma2}})$

The composition of this sequence of natural isomorphisms provides the natural
isomorphism $\phi_{H,F}$. ∎

###  3.4. Limit sketches

This section defines a particular type of reflective subcategories whose
structures will be used to construct cryptosystems or recover established
ones. More precisely, these structures commonly reinstate categories of models
pertaining to a predefined theory equipped with limits. Although our
subsequent exposition leverages the general concept of limits for mathematical
convenience and to minimize unnecessary hypotheses, it is noteworthy that the
majority of our examples of reflective subcategories stem from highly specific
limits, known as products. Nevertheless, the versatility of the formalism
presented herein, which accommodates any limit, implies the potential for
further adaptation and application beyond the examples presented.

######  Definition 3.16 (Cones).

Let $A$ be a small category and $\mathcal{C}$ be a category. For every object
$X$ in $\mathcal{C}$ and every functor $F:A\to\mathcal{C}$, we will refer to a
natural transformation of the form $\Delta_{A}(X)\Rightarrow F$ as a _cone_
above $F$. Suppose that $\mathcal{C}$ has limits over $A$. Then, we will say
that the cone $\Delta_{A}(X)\Rightarrow F$ is a _universal cone_ (or a _limit
cone_) if its image through isomorphism (3.1) is an isomorphism of the form
$X\to\mathsf{lim}_{A}(F)$ in $\mathcal{C}$.

######  Remark 3.17 (Universal cone).

For every object $F$ in $[A,\mathcal{C}]$, isomorphism (3.1) allows us to
easily construct a universal cone as the inverse image of the identity on
$\mathsf{lim}_{A}(F)$ in $\mathcal{C}$, as shown below.

$\begin{array}[]{ccc}[A,\mathcal{C}](\Delta_{A}(\mathsf{lim}_{A}(F)),F)&\cong&\mathcal{C}(\mathsf{lim}_{A}(F),\mathsf{lim}_{A}(F))\\\
(\mathsf{lim}_{A}(F)\to
F(a))_{a}&\mathrel{\reflectbox{$\mapsto$}}&\mathsf{id}_{\mathsf{lim}_{A}(F)}\end{array}$

Each inverse image $\Delta_{A}(\mathsf{lim}_{A}(F))\Rightarrow F$ obtained in
this way describes a component of the unit
$\Delta_{A}\circ\mathsf{lim}_{A}\Rightarrow\mathsf{Id}$ for the adjunction
$\Delta_{A}\vdash\mathsf{lim}_{A}$ referred to in Definition 3.7.

The following proposition can be used to verify that a given cone is
universal.

######  Proposition 3.18 (Universal cones).

Let $A$ be a small category and $\mathcal{C}$ be a category. For every object
$X$ in $\mathcal{C}$ and every functor $F:A\to\mathcal{C}$, a cone
$\alpha:\Delta_{A}(X)\Rightarrow F$ is universal in $\mathcal{C}$ if, and only
if, for every cone $\beta:\Delta_{A}(Y)\Rightarrow F$ in $\mathcal{C}$, there
exists a unique morphism $f:Y\to X$ such that the following diagram commutes
in $[A,\mathcal{C}]$.

---
$\textstyle{\Delta_{A}(X)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\Delta_{A}(f)}$$\scriptstyle{\alpha}$$\textstyle{F}$$\textstyle{\Delta_{A}(Y)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\beta}$

###### Proof.

Suppose that $\alpha:\Delta_{A}(X)\Rightarrow F$ is universal and let
$a:X\to\mathsf{lim}_{A}(F)$ denote the corresponding isomorphism through
isomorphism (3.1) (Definition 3.16). If we let
$\eta_{F}:\Delta_{A}(\mathsf{lim}_{A}(F))\Rightarrow F$ denote the universal
cone obtained using the identity on $\mathsf{lim}_{A}(F)$ (see Remark 3.17),
then the naturality of isomorphism (3.1) tells us that
$\alpha=\eta_{F}\circ\Delta_{A}(a)$. Let now $Y$ be an object in
$\mathcal{C}$. Isomorphism (3.1) gives us the following sequence of
isomorphisms.

$\displaystyle[A,\mathcal{C}](Y,X)$
$\displaystyle\cong[A,\mathcal{C}](Y,\mathsf{lim}_{A}(F))$
$\displaystyle(\textrm{use }a:X\to\mathsf{lim}_{A}(F))$
$\displaystyle\cong[A,\mathcal{C}](\Delta_{A}(Y),F)$
$\displaystyle(\textrm{Isomorphism (\ref{eq:limits_colimits:lim})}$

This means that, for every cone $\beta:\Delta_{A}(Y)\Rightarrow F$, we have an
arrow $f:X\to Y$ for which the naturality of isomorphism (3.1) implies that
$\eta_{F}\circ\Delta_{A}(a\circ f)=\beta$. As a result, we have
$\alpha\circ\Delta_{A}(f)=\beta$. The arrow $f$ is unique since the previous
sequence of isomorphisms from $[A,\mathcal{C}](Y,X)$ to
$[A,\mathcal{C}](\Delta_{A}(Y),F)$ states that
$g\mapsto\alpha\circ\Delta_{A}(g)$ is a bijection.

Conversely, let us show that any cone $\alpha:\Delta_{A}(X)\Rightarrow F$ that
satisfies the property stated in the statement is universal. First, because
$\eta_{F}$ is universal (Remark 3.17), the first part of this proof shows that
there exists a (unique) morphism $f:\mathsf{lim}_{A}(F)\to X$ such that
$\alpha=\eta_{F}\circ\Delta_{A}(f)$. It also follows from the property
satisfied by $\alpha$ that there exists a (unique) morphism
$f^{\prime}:X\to\mathsf{lim}_{A}(F)$ such that
$\eta_{F}=\alpha\circ\Delta_{A}(f^{\prime})$. This gives us
$\alpha=\alpha\circ\Delta_{A}(f^{\prime}\circ f)$. By assumption on $\alpha$,
the arrow $f^{\prime}\circ f$ is unique and is hence equal to the identity on
$\mathsf{lim}_{A}(F)$. Similarly, since $\eta_{F}$ is universal, we can show
that $f\circ f^{\prime}=\mathsf{id}_{X}$ and hence $f$ is an isomorphism.
Given that $\alpha=\eta_{F}\circ\Delta_{A}(f)$, it follows from Definition
3.16 and the definition of $\eta_{F}$ that $\alpha$ is universal. ∎

In general, a full subcategory $L\hookrightarrow[T,\mathbf{Set}]$ whose
objects are functors $T\to\mathbf{Set}$ that sends certain chosen cones in $T$
to universal cones in $\mathbf{Set}$ are reflective subcategories (see [13,
18, 2, 27]).

######  Definition 3.19 (Limit sketches).

We will use the term _limit sketch_ to refer to a small category $T$ equipped
with a subset of its cones. We define a _model_ for a limit sketch $T$ as a
functor $T\mapsto\mathbf{Set}$ that sends the chosen cones of $T$ to univercal
cones in $\mathbf{Set}$. For every limit sketch $T$, we will denote the
category whose objects are models for $T$ and whose arrows are all the natural
transformations between them as $\mathbf{Mod}(T)$. This category will be
referred to as the category of models for the limit sketch (also called the
_theory_) $T$.

######  Remark 3.20.

For every limit sketch $T$, the inclusion
$\mathbf{Mod}(T)\hookrightarrow[T,\mathbf{Set}]$ defines a reflective
subcategory. As a result, Theorem 3.15 holds.

######  Example 3.21 (Magmas).

A _magma_ consists of a set $M$ and an operation $\star:M\times M\to M$. A
morphism between two magmas $(M_{1},\star_{1})$ and $(M_{2},\star_{2})$
consists of a function $m:M_{1}\to M_{1}$ such that the following diagram
commutes.

$\textstyle{M_{1}\times
M_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\star_{1}}$$\scriptstyle{m}$$\textstyle{M_{2}\times
M_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\star_{1}}$$\textstyle{M_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{m}$$\textstyle{M_{2}}$

Let us now denote as $T_{\mathsf{magma}}$ the small category generated by the
following graph.

$\begin{array}[]{c}\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
13.41669pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
13.09459pt\raise 6.73334pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.1pt\hbox{$\scriptstyle{f_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 31.80293pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx<EMAIL_ADDRESS>0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.1pt\hbox{$\scriptstyle{f_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 0.0pt\raise-29.16533pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
31.80293pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}{\hbox{\kern-7.80293pt\raise-40.49866pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}{\hbox{\kern
36.60587pt\raise-40.49866pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}\ignorespaces}}}}\ignorespaces\end{array}\begin{array}[]{c}\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
7.80293pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
15.28627pt\raise 5.58333pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.58333pt\hbox{$\scriptstyle{t}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 31.80293pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
31.80293pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}\ignorespaces}}}}\ignorespaces\end{array}$

If we equip $T_{\mathsf{magma}}$ with the cone
$f_{1},f_{2}:d_{2}\rightrightarrows d_{1}$, then for every functor
$M:T_{\mathsf{magma}}\to\mathbf{Set}$ in $\mathbf{Mod}(T_{\mathsf{magma}})$,
the universality of Cartesian products gives the following correspondence:

$M(d_{2})=M(d_{1})\times M(d_{1})$

As a result, the category of models $M$ in $\mathbf{Mod}(T_{\mathsf{magma}})$
corresponds to the category of magmas and their morphisms, such that the magma
operation is provided by function $M(t):M(d_{1})\times M(d_{1})\to M(d_{1})$.

######  Remark 3.22 (Magma of binary trees).

Recall that the Yoneda embedding provides a functor
$Y(d_{1}):T_{\mathsf{magma}}\to\mathbf{Set}$. While this functor does not
belong to the category $\mathbf{Mod}(T_{\mathsf{magma}})$, its image $L\circ
Y(d_{1})$ via the functor
$L:[T_{\mathsf{magma}},\mathbf{Set}]\to\mathbf{Mod}(T_{\mathsf{magma}})$ does.
The model $L\circ Y(d_{1})$ can be recursively constructed from the images of
the functor $Y(d_{1})$ through a transfinite colimit (see [27]). Specifically,
this transfinite construct _forces_ the presence of missing elements into the
model to turn the functor $Y(d_{1})$ into a model for the “theory”
$T_{\mathsf{magma}}$.

To appreciate what the model $L\circ Y(d_{1})$ looks like, let us identify the
elements missing from the primary set of the functor $Y(d_{1})$, specifically
$Y(d_{1})(d_{1})=T_{\mathsf{magma}}(d_{1},d_{1})$. According to the definition
of the limit sketch $T_{\mathsf{magma}}$, the sole arrow $d_{1}\to d_{1}$ in
$Y(d_{1})(d_{1})$ is the identity $\mathsf{id}_{d_{1}}$. As a result,
constructing the model $L\circ Y(d_{1})$ necessitates the formal
multiplication of $\mathsf{id}_{d_{1}}$ with itself to be part of the primary
set of the model. As outlined in [27], this element is encoded by the tuple
$(\mathsf{id}_{d_{1}},\mathsf{id}_{d_{1}},t)$, visually represented as a tree:

$\textstyle{\mathsf{id}_{d_{1}}}$$\textstyle{\mathsf{id}_{d_{1}}}$$\textstyle{\framebox{$t$}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

Iterating this formal process of generating multiplications with previously
generated elements reveals that the model $L\circ Y(d_{1})$ can be
conceptualized as the magma of binary trees with no linear branches (e.g., no
consecutive one-branch forkings):

$\textstyle{\mathsf{id}_{d_{1}}}$$\textstyle{\mathsf{id}_{d_{1}}}$$\textstyle{\framebox{$t$}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathsf{id}_{d_{1}}}$$\textstyle{\framebox{$t$}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathsf{id}_{d_{1}}}$$\textstyle{\mathsf{id}_{d_{1}}}$$\textstyle{\mathsf{id}_{d_{1}}}$$\textstyle{\mathsf{id}_{d_{1}}}$$\textstyle{\framebox{$t$}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\framebox{$t$}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\framebox{$t$}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

This magma $L\circ Y(d_{1})$, which we denote as $\mathbb{T}\mathsf{ree}$, can
be used to capture elements in any magma $M$ by utilizing the Yoneda Lemma
(Theorem 3.15), as expressed below:

$\mathbf{Mod}(T_{\mathsf{magma}})(\mathbb{T}\mathsf{ree},M)\cong M$

######  Example 3.23 (Semigroups).

A _semigroup_ consists of a magma $(M,\star)$ whose operation is associative.
This means that the magma operation must satisfies the following commutative
diagram.

$\textstyle{M\times M\times
M\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{id}_{M}\times\star}$$\scriptstyle{\star\times\mathsf{id}_{M}}$$\textstyle{M\times
M\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\star}$$\textstyle{M\times
M\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\star}$$\textstyle{M}$

We can define the small category $T_{\mathsf{sgroup}}$ as the small category
generated by the following graph structure.

$\begin{array}[]{c}\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
13.41669pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
13.09459pt\raise 6.73334pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.1pt\hbox{$\scriptstyle{f_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 31.80293pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx<EMAIL_ADDRESS>0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.1pt\hbox{$\scriptstyle{f_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 0.0pt\raise-29.16533pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
31.80293pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}{\hbox{\kern-7.80293pt\raise-40.49866pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}{\hbox{\kern
36.60587pt\raise-40.49866pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}\ignorespaces}}}}\ignorespaces\end{array}\begin{array}[]{c}\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
12.7079pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{3}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
13.44899pt\raise 5.625pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\hbox{\hbox{\kern
0.0pt\raise-0.99167pt\hbox{$\scriptstyle{g_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 31.80293pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx<EMAIL_ADDRESS>0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-0.99167pt\hbox{$\scriptstyle{g_{3}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 0.0pt\raise-29.16533pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
7.09503pt\raise-25.7425pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-0.99167pt\hbox{$\scriptstyle{g_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
31.80293pt\raise-32.52809pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
31.80293pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}{\hbox{\kern-7.80293pt\raise-40.49866pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}{\hbox{\kern
31.80293pt\raise-40.49866pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}\ignorespaces}}}}\ignorespaces\end{array}\begin{array}[]{c}\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
12.7079pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{3}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
13.44899pt\raise 5.625pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\hbox{\hbox{\kern
0.0pt\raise-0.99167pt\hbox{$\scriptstyle{g_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 31.80293pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx<EMAIL_ADDRESS>0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-0.99167pt\hbox{$\scriptstyle{g_{3}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 0.0pt\raise-29.16533pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
19.80293pt\raise-14.78758pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.035pt\hbox{$\scriptstyle{u_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
31.80293pt\raise-32.52809pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
31.80293pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}{\hbox{\kern-7.80293pt\raise-40.49866pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}{\hbox{\kern
31.80293pt\raise-40.49866pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
39.60587pt\raise-20.24933pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.1pt\hbox{$\scriptstyle{f_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
39.60587pt\raise-5.16533pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
13.09459pt\raise-33.76532pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.1pt\hbox{$\scriptstyle{f_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
7.80293pt\raise-40.49866pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces}}}}\ignorespaces\end{array}\begin{array}[]{c}\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
12.7079pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{3}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
13.44899pt\raise 5.625pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\hbox{\hbox{\kern
0.0pt\raise-0.99167pt\hbox{$\scriptstyle{g_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 31.80293pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx<EMAIL_ADDRESS>0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-0.99167pt\hbox{$\scriptstyle{g_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 0.0pt\raise-29.16533pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
19.80293pt\raise-14.78758pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.035pt\hbox{$\scriptstyle{u_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
31.80293pt\raise-32.52809pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
31.80293pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}{\hbox{\kern-7.80293pt\raise-40.49866pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}{\hbox{\kern
31.80293pt\raise-40.49866pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
39.60587pt\raise-20.24933pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.1pt\hbox{$\scriptstyle{f_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
39.60587pt\raise-5.16533pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
13.09459pt\raise-33.76532pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.1pt\hbox{$\scriptstyle{f_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
7.80293pt\raise-40.49866pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces}}}}\ignorespaces\end{array}$
$\begin{array}[]{c}\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
7.80293pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
15.28627pt\raise 5.58333pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.58333pt\hbox{$\scriptstyle{t}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 31.80293pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
31.80293pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}\ignorespaces}}}}\ignorespaces\end{array}\begin{array}[]{c}\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
12.7079pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{3}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
9.58194pt\raise 6.35666pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.81pt\hbox{$\scriptstyle{t\circ u_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 31.80293pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx<EMAIL_ADDRESS>0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-0.99167pt\hbox{$\scriptstyle{g_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 0.0pt\raise-29.16533pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
19.80293pt\raise-14.78758pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.035pt\hbox{$\scriptstyle{v_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
31.80293pt\raise-32.52809pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
31.80293pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}{\hbox{\kern-7.80293pt\raise-40.49866pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}{\hbox{\kern
31.80293pt\raise-40.49866pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
39.60587pt\raise-20.24933pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.1pt\hbox{$\scriptstyle{f_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
39.60587pt\raise-5.16533pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
13.09459pt\raise-33.76532pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.1pt\hbox{$\scriptstyle{f_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
7.80293pt\raise-40.49866pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces}}}}\ignorespaces\end{array}\begin{array}[]{c}\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
12.7079pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{3}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
9.58194pt\raise 6.35666pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.81pt\hbox{$\scriptstyle{t\circ u_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 31.80293pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx<EMAIL_ADDRESS>0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-0.99167pt\hbox{$\scriptstyle{g_{3}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 0.0pt\raise-29.16533pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
19.80293pt\raise-14.78758pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.035pt\hbox{$\scriptstyle{v_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
31.80293pt\raise-32.52809pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
31.80293pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}{\hbox{\kern-7.80293pt\raise-40.49866pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{1}}$}}}}}}}{\hbox{\kern
31.80293pt\raise-40.49866pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{d_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
39.60587pt\raise-20.24933pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.1pt\hbox{$\scriptstyle{f_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
39.60587pt\raise-5.16533pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
13.09459pt\raise-33.76532pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.1pt\hbox{$\scriptstyle{f_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
7.80293pt\raise-40.49866pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces}}}}\ignorespaces\end{array}$
$\textstyle{d_{3}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{v_{1}}$$\scriptstyle{v_{2}}$$\textstyle{d_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{t}$$\textstyle{d_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{t}$$\textstyle{d_{1}}$

If we equip $T_{\mathsf{sgroup}}$ with the cone $(f_{1},f_{2})$ and
$(g_{1},g_{2},g_{3})$, then for every functor
$M:T_{\mathsf{sgroup}}\to\mathbf{Set}$ in $\mathbf{Mod}(T_{\mathsf{sgroup}})$,
the universality of Cartesian products gives the following correspondences:

$M(d_{2})=M(d_{1})\times M(d_{1})\quad\quad\textrm{and}\quad\quad
M(d_{3})=M(d_{1})\times M(d_{1})\times M(d_{1})$

The universality of products also implies that we have the following
equations:

$M(v_{1})=\mathsf{id}_{M(d_{1})}\times M(t)\quad\quad\textrm{and}\quad\quad
M(v_{2})=M(t)\times\mathsf{id}_{M(d_{1})}$

As a result, the category of models $M$ in $\mathbf{Mod}(T_{\mathsf{sgroup}})$
corresponds to the category of semigroups and their morphisms, such that the
semigroup operation is provided by function $M(t):M(d_{1})\times M(d_{1})\to
M(d_{1})$.

######  Remark 3.24 (Semigroup of positive integers).

In a manner akin to how we obtained a generative model for magmas in Remark
3.22, we can show that the semigroup encoded by the functor $L\circ
Y(d_{1}):T_{\mathsf{sgroup}}\to\mathbf{Set}$ is isomorphic to the magma
$\mathbb{T}\mathsf{ree}$ under an associative multiplication. This can be
interpreted as the semigroup defined by the set $\mathbb{N}^{+}$ of positive
integers.

######  Example 3.25 (Monoids).

A _monoid_ is a semigroup $(M,\star)$ equipped with a neural element for the
semigroup operation. This means that it is equipped with a map
$\mathbb{1}:\mathbf{1}\to M$ picking a distinguishing element in $M$ (where
$\mathbf{1}$ is a singleton) such that the following diagrams commute.

$\textstyle{\mathbf{1}\times
M\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{pr}_{2}}$$\scriptstyle{\mathbb{1}\times\mathsf{id}_{M}}$$\textstyle{M\times
M\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\star}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces
M\times\mathbf{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{id}_{M}\times\mathbb{1}}$$\scriptstyle{\mathsf{pr}_{1}}$$\textstyle{M}$

Because a singleton such as $\mathbf{1}$ is a limit over the empty set, it is
possible to define a limit sketch $T_{\mathsf{monoid}}$ such that the category
$\mathbf{Mod}(T_{\mathsf{monoid}})$ corresponds to the category of monoids and
their morphisms.

######  Remark 3.26 (Monoid of non-negative integers).

Taking $d_{1}$ to be the object of $T_{\mathsf{monoid}}$ representing the
underlying set of the models in $\mathbf{Mod}(T_{\mathsf{monoid}})$, we can
show that the monoid generated by the model $L\circ
Y(d_{1}):T_{\mathsf{monoid}}\to\mathbf{Set}$ is the set $\mathbb{N}$ of non-
negative integers.

######  Example 3.27 (Groups).

A _group_ is a monoid $(M,\star,\mathbb{1})$ equipped with an inverse
operation $u:M\to M$ for the multiplication $\star$. This means that the
following diagram must commute.

$\textstyle{M\times
M\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{u\times\mathsf{id}_{M}}$$\textstyle{M\times
M\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\star}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces
M\times
M\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{id}_{M}\times
u}$$\textstyle{\mathbf{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathbb{1}}$$\textstyle{M}$$\textstyle{\mathbf{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathbb{1}}$

Similarly to what has been done so far with other examples of categories of
models (Examples 3.21, 3.23, 3.25), we can show that there is a limit sketch
$T_{\mathsf{group}}$ for which the category $\mathbf{Mod}(T_{\mathsf{group}})$
corresponds to the category of groups and their morphisms.

######  Remark 3.28 (Group of integers).

Taking $d_{1}$ to be the object of $T_{\mathsf{group}}$ representing the
underlying set of the models in $\mathbf{Mod}(T_{\mathsf{group}})$, we can
show that the monoid generated by the model $L\circ
Y(d_{1}):T_{\mathsf{group}}\to\mathbf{Set}$ is the set $\mathbb{Z}$ of all
integers.

######  Example 3.29 (Commutative structures).

The theories defined in 3.21, 3.23, 3.25 and 3.27 can be extended to
commutative structures by adding structural maps that recover the usual
symmetry axiom shown below, where $\gamma$ is the universal symmetry
bijection.

$\textstyle{M\times
M\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\star}$$\scriptstyle{\gamma}$$\scriptstyle{\cong}$$\textstyle{M\times
M\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\star}$$\textstyle{M\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{M}$

Below, we will denote the resulting limit sketch for commutative groups as
$T_{\mathsf{cgroup}}$.

######  Remark 3.30 (Group of integers).

Taking $d_{1}$ to be the object of $T_{\mathsf{cgroup}}$ representing the
underlying set of the models in $\mathbf{Mod}(T_{\mathsf{cgroup}})$, we can
show that the commutative group generated by the model $L\circ Y(d_{1})$ is
the set $\mathbb{Z}$ of all integers.

######  Convention 3.31 (Notation).

For every positive integer $n$, we will denote as $\mathbb{Z}_{n}$ the
commutative group whose elements are given by the set $[n-1]$ and whose group
operation is given by the addition of integers modulo $n$, namely:

$\begin{array}[]{ccl}\mathbb{Z}_{n}\times\mathbb{Z}_{n}&\to&\mathbb{Z}_{n}\\\
(x,y)&\mapsto&x+y\,(\mathsf{mod}\,n)\end{array}$

The inverse operation for this addition is the negation operation modulo $n$,
namely $x\mapsto n-x$.

###  3.5. Modules

A central application of the Yoneda Lemma in our context involves leveraging
the limit sketch of modules over a given ring. The aim of this section is to
examine the algebraic properties associated with these objects and formulate
key propositions that will be instrumental in transforming cryptosystems over
polynomials into Yoneda encryption schemes. To define module structures, we
will build upon the concepts introduced in the previous section as well as the
definition of rings (Definition 3.32).

######  Definition 3.32 (Rings).

A _ring_ is defined as a set $R$ equipped with:

  * 1)

a commutative group structure $(R,\oplus,\mathbb{0})$;

  * 2)

and a monoid structure $(R,\otimes,\mathbb{1})$,

such that the two diagrams shown below commute, where $\delta:R\to R\times R$
denotes the obvious diagonal morphism and
$\gamma:R\\!\times\\!R\\!\times\\!R\\!\times\\!R\to
R\\!\times\\!R\\!\times\\!R\\!\times\\!R$ denotes the symmetry
$(a,b,c,d)\mapsto(a,c,b,d)$:

$\textstyle{R\\!\times\\!R\\!\times\\!R\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\gamma\circ(\delta\times\mathsf{id}_{(R\times
R)})}$$\scriptstyle{\mathsf{id}_{R}\times\oplus}$$\textstyle{R\\!\times\\!R\\!\times\\!R\\!\times\\!R}$$\scriptstyle{\otimes\times\otimes}$$\textstyle{R\\!\times\\!R\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\oplus}$$\textstyle{R\\!\times\\!R\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\otimes}$$\textstyle{R}$
$\textstyle{R\\!\times\\!R\\!\times\\!R\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\gamma\circ(\mathsf{id}_{(R\times
R)}\times\delta)}$$\scriptstyle{\oplus\\!\times\\!\mathsf{id}_{R}}$$\textstyle{R\\!\times\\!R\\!\times\\!R\\!\times\\!R}$$\scriptstyle{\otimes\times\otimes}$$\textstyle{R\times
R\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\oplus}$$\textstyle{R\\!\times\\!R\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\otimes}$$\textstyle{R}$

These diagrams enforce that the monoid multiplication $\otimes$ is
distributive with respect to the group addition $\oplus$. This means that the
equations $a\otimes(b+c)=a\otimes b+a\otimes c$ and $(b+c)\otimes a=b\otimes
a+c\otimes a$ hold for every triple $(a,b,c)$ of elements in $R$.

######  Convention 3.33 (Limit sketches).

In much the same fashion as we derived limit sketches for theories
characterized by commutative diagrams in section 3.4, it is straightforward to
show that rings are precisely described by models of a limit sketches
$T_{\mathsf{ring}}$.

######  Remark 3.34 (Yoneda objects).

Let $d_{1}$ denote the object of $T_{\mathsf{ring}}$ that captures the
underlying set of the models in $\mathsf{Mod}(T_{\mathsf{ring}})$. It follows
from the distributivity axioms that the model $L\cdot
Y(d_{1}):T_{\mathsf{ring}}\to\mathbf{Set}$ is the ring of integers given by
$\mathbb{Z}[X]$.

######  Remark 3.35 (Morphisms).

A morphism of rings is defined as a natural transformation between models in
$\mathsf{Mod}(T_{\mathsf{ring}})$. The Yoneda Lemma (Theorem 3.15) gives the
isomorphism:

$\mathsf{Mod}(T_{\mathsf{ring}})(\mathbb{Z}[X],R)\cong R.$

At a fundamental level, this isomorphism means that a morphism $f$ of the form
$\mathbb{Z}[X]\to R$ is characterized by an evaluation at a specific element
$r\in R$. Indeed, since the ring $R$ contains all integer representatives,
which are derived from the unit $\mathbb{1}$, the underlying function defining
$f$ is given by the mapping $p(X)\mapsto p(r)$ where $p(X)$ is a polynomial
over integers and $p(r)$ is its evaluation at $r\in R$.

We now leave the realm of rings and mostly uses the fact that every ring
$(R,\oplus,\otimes,\mathbb{0},\mathbb{1})$ provides an underlying commutative
group $(R,\oplus,\mathbb{0})$.

######  Convention 3.36 (Powers).

For every non-negative integer $n$ and ring
$(R,\oplus,\otimes,\mathbb{0},\mathbb{1})$, we will denote the $n$-fold
Cartesian product of $R$ in $\mathbf{Mod}(T_{\mathsf{cgroup}})$ as $R^{(n)}$.
For a chosen limit structure on $\mathbf{Mod}(T_{\mathsf{cgroup}})$, this
commutative group is the limit $\mathsf{lim}_{[n]}(F)$ of the functor
$F:[n]\to\mathbf{Mod}(T_{\mathsf{cgroup}})$ picking out $n$ copies of the
commutative group $(R,\oplus,\mathbb{0})$. We can show that the underlying set
for the resulting group structure is given by an $n$-fold Cartesian product of
$R$ in $\mathbf{Set}$, and the associated addition is a componentwise
extension of the addition $\oplus$.

######  Convention 3.37 (From rings to limit sketches).

For every ring $(R,\oplus,\otimes,\mathbb{0},\mathbb{1})$, we will denote as
$T_{R}$ the small whose objects are non-negative integers and whose morphisms
$n\to m$ are given by group morphisms

$f=(f_{1},\dots,f_{m}):R^{(n)}\to R^{(m)}$

such that, for every $k\in[m]$, the Cartesian component $f_{k}:R^{(n)}\to R$
satisfies the following equation in the ring
$(R,\oplus,\otimes,\mathbb{0},\mathbb{1})$ for every$(r_{1},\dots,r_{n})\in
R^{(n)}$:

$f_{k}(r_{1},\dots,r_{n})=f_{k}(\mathbb{1},\mathbb{0},\dots,\mathbb{0})\otimes
r_{1}\oplus\dots\oplus f_{k}(\mathbb{0},\dots,\mathbb{0},\mathbb{1})\otimes
r_{n}$

It is straightforward to verify that this notion of morphisms defines a
category structure for $T_{R}$. Indeed, the morphism $f$ defined above can be
likened to a matrix product in $R$ and since matrix products in $R$ are
associative, the composition of morphisms in $T_{R}$ is also associative. In
other words, the morphisms of $T_{R}$ are linear maps of the form shown in
(3.3), where $M$ is a $(m\times n)$\- matrix in $R$ and where $e_{i}$ is the
element
$(\mathbb{0},\dots,\mathbb{0},\mathbb{1},\mathbb{0},\dots,\mathbb{0})\in
R^{(n)}$ whose $i$-th coefficient is $\mathbb{1}$.

(3.3) $f(r)=Mr=\Big{(}\bigoplus_{j=1}^{n}f_{i}(e_{j})\otimes
r_{j}\Big{)}_{i}\quad\quad M=(f_{i}(e_{j}))_{i,j})$

The category $T_{R}$ includes morphisms of the following form (where $s$
denotes any element in $R$):

$s:\left(\begin{array}[]{lll}R^{(1)}&\to&R^{(1)}\\\ r&\mapsto&s\otimes
r\end{array}\right)\quad\quad\oplus:\left(\begin{array}[]{lll}R^{(2)}&\to&R^{(1)}\\\
(r,s)&\mapsto&r\oplus
s\end{array}\right)\quad\quad\mathsf{pr}_{i}^{n}:\left(\begin{array}[]{lll}R^{(n)}&\to&R^{(1)}\\\
(r_{1},\dots,r_{n})&\mapsto&r_{i}\end{array}\right)$

We will assume that the small category $T_{R}$ is equipped with a limit sketch
structure whose cones are the collections $(\mathsf{pr}_{i}^{n}:R^{(n)}\to
R^{(1)})_{i=1}^{n}$ for every non-negative integer $n$. Note that when $n=0$,
we have $R^{(n)}=\\{0\\}$ and the resulting cone is given by the obvious
inclusion $0:\\{0\\}\hookrightarrow R$.

According to the definition of $T_{R}$, we have an isomorphism
$T_{R}(1,1)\cong R$. While this might imply that the functor
$Y(1):T_{R}\to\mathbf{Set}$ represents the ring $R$, we will in fact see that
this correspondence imbues the functor $Y(1)$ with a “module structure” over
the ring $R$ (see Definition 3.38). To expand on this, observe that the
definition of $T_{R}$ yields the following isomorphisms for every non-negative
integer $n$:

$T_{R}(1,n)\cong R^{(n)}\cong T_{R}(1,1)\times T_{R}(1,1)\times\dots\times
T_{R}(1,1)$

At an elementary level, this isomorphism asserts that the image of the cone
$(\mathsf{pr}_{i}^{n}:R^{(n)}\to R^{(1)})_{i=1}^{n}$ via the functor $k\mapsto
T_{R}(1,k)$ is a universal cone in $\mathbf{Set}$. As a result, we conclude
that the functor $Y(1):T_{R}\to\mathbf{Set}$ defines an object in
$\mathbf{Mod}(T_{R})$.

######  Definition 3.38 (Modules).

For every ring $(R,\oplus,\otimes,\mathbb{0},\mathbb{1})$, we define an _$R$
-module_ as an object in $\mathbf{Mod}(T_{R})$. It follows from Convention
3.37 that, for every $R$-module $M:T_{R}\to\mathbf{Set}$, the arrows

$s:R^{(1)}\to R^{(1)}\quad\quad\quad\oplus:R^{(2)}\to
R^{(1)}\quad\quad\quad\mathsf{pr}_{0}^{1}:R^{(0)}\to R^{(1)}$

in $T_{R}$ are sent via the functor $M$ to functions of the form

$s\odot:M(1)\to M(1)\quad\quad\quad\oplus_{M}:M(1)\times M(1)\to
M(1)\quad\quad\quad\mathbb{0}_{M}:\mathbf{1}\to M(1)$

making the following diagram commute, where $\delta:M(1)\to M(1)\times M(1)$
the obvious diagonal morphism.

$\textstyle{M(1)\times
M(1)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(r\odot)\times(s\odot)}$$\textstyle{M(1)\times
M(1)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\oplus_{M}}$$\textstyle{M(1)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\delta}$$\scriptstyle{(r\oplus
s)\odot}$$\textstyle{M(1)}$ $\textstyle{M(1)\times
M(1)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(r\odot)\times(r\odot)}$$\scriptstyle{\oplus_{M}}$$\textstyle{M(1)\times
M(1)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\oplus_{M}}$$\textstyle{M(1)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(r\odot}$$\textstyle{M(1)}$
$\textstyle{M(1)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{r\odot}$$\scriptstyle{(s\otimes
r)\odot}$$\textstyle{M(1)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{s\odot}$$\textstyle{M(1)}$
$\textstyle{\mathbf{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathbb{0}_{M}}$$\scriptstyle{\mathbb{0}_{M}}$$\textstyle{M(1)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{r\odot}$$\textstyle{M(1)}$

The four preceding diagrams encapsulate the four types of axioms typically
stipulated for $R$-modules, as conventionally defined in the literature.

######  Remark 3.39 (Yoneda objects).

The conclusions of Convention 3.37 imply that, for every ring
$(R,\oplus,\otimes,\mathbb{0},\mathbb{1})$, the functor
$Y(1):T_{R}\to\mathbf{Set}$ recovers the $R$-module structure defined the
commutative group $(R,\oplus,\mathbb{0})$. Specifically, for every element
$s\in R$, the function $Y(1)(s):R\to R$ recovers the multiplication $r\mapsto
s\otimes r$ and the function $Y(1)(\oplus):R\times R\to R$ recovers the
addition $(r,s)\mapsto r\oplus s$.

Similarly, for every non-negative integer $n$, we can show that
$Y(n):T_{R}\to\mathbf{Set}$ recovers the $R$-module defined by the power
$R^{(n)}$. Interestingly, it turns out that the object $Y(n)$ is also the
$n$-fold coproduct of the object $Y(1)$ in $\mathbf{Mod}(T_{R})$. This
statement is more formally verified through the Yoneda Lemma. Indeed, Theorem
3.15 gives us the following isomorphism for every object $M$ in
$\mathbf{Mod}(T_{R})$:

$\mathbf{Mod}(T_{R})(Y(n),M)\cong M(n)$

However, by the definition of a model in $\mathbf{Mod}(T_{R})$, the set $M(n)$
is naturally in bijection with the $n$-fold product $M(1)\times
M(1)\times\dots\times M(1)$. As a result, we have the following natural
isomorphism.

(3.4) $\mathbf{Mod}(T_{R})(Y(n),M)\cong M(1)\times M(1)\times\dots\times M(1)$

Here, some category-theoretic arguments could show that the object $Y(n)$ is
the $n$-fold coproduct of the object $Y(1)$ in $\mathbf{Mod}(T_{R})$, thereby
providing another explanation for the previous isomorphism in the context of
Theorem 3.15.

######  Remark 3.40 (Colimits in Yoneda Lemma).

Let $R$ be a ring. In Remark 3.39, we observed that the Yoneda functor
$Y(n):T_{R}\to\mathbf{Set}$ corresponds to the $n$-fold coproduct of
$Y(1):T_{R}\to\mathbf{Set}$. Consequently, it might seem like the use of
colimits in Theorem 3.15 is excessive, and its statement could be limited to
Yoneda functors of the form $Y(k)$. However, this expectation should not be
considered a general rule. For instance, for practical reasons, one might want
to confine the limit sketch $T_{R}$ to the objects $0$, $1$, $2$ and $3$.
While this restriction would be sufficient to recover the conventional
definition of $R$-modules, it would lack the objects $4$, $5$, $\dots$, $n$,
etc. As a result, it would be necessary to demonstrate that $Y(n)$ is a
coproduct of $Y(1)$ to obtain isomorphism (3.4).

##  4\. Cryptosystems and the Yoneda Lemma

###  4.1. Yoneda encryption

This section establishes a cryptosystem based on the Yoneda Lemma, as stated
in Theorem 3.15. In the upcoming sections, we will elucidate how this
overarching cryptosystem can reconstruct other cryptosystems. Below, we
consider a small category $T$ and a reflective subcategory denoted by
$U:\mathcal{L}\hookrightarrow[T,\mathbf{Set}]$ with a left adjoint
$L:[T,\mathbf{Set}]\to\mathcal{L}$.

Before we proceed to define a Yoneda cryptosystem (Definition 4.1), let us
revisit the components of conventional cryptosystems. These systems typically
involve three sets of elements:

  * -

a _plaintext space_ $M_{1}$ containing messages intended for transmission,

  * -

a _ciphertext space_ $M_{2}$ encompassing encrypted messages used for secure
communication,

  * -

and a _key space_ $K$ housing both public and private keys.

Additionally, these cryptosystems feature two $K$-indexed collections of
functions. One collection describes an encryption algorithm
$\mathsf{E}_{k}:M_{1}\to M_{2}$, responsible for transforming messages into
encrypted form using a key $k$ drawn from the set $K$. The other is a
decryption algorithm $\mathsf{D}_{k}:M_{2}\to M_{1}$, which performs the
inverse operation, decrypting the ciphertext back into the original message
using some key $k$ drawn from the set $K$. In asymmetric cryptography, the
keys used for encryption and decryption must differ.

$\textstyle{\mathsf{Bob}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{Channel}}$$\textstyle{\mathsf{Alice}}$$\textstyle{m\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{E_{k}(m)}$$\textstyle{\begin{array}[]{c}D_{k^{\prime}}(E_{k}(m))\\\
\rotatebox[origin={c}]{90.0}{$=$}\\\ m\end{array}}$

To encompass a wide range of HE schemes, Yoneda cryptosystems exhibit a
slightly greater level of generality than the conventional definition of
cryptosystems provided earlier. For further clarification on this increased
generality, please refer to Remark 4.3.

######  Definition 4.1 (Yoneda cryptosystems).

Let $(F,G)$ be a pair of objects in $\mathcal{L}$, let $(M_{1},M_{2})$ be a
pair of sets, and let $e$ be an object in $T$. We say that the tuple
$(F,G,M_{1},M_{2})$ defines a _Yoneda cryptosystem_ in $\mathcal{L}$ at the
object $e$ if it is equipped with

  * a)

a set $R$ and an $R$-indexed collection $(\mathsf{E}_{r})_{r\in R}$ of
functions $\mathsf{E}_{r}:G(e)\times M_{1}\to M_{2}$;

  * b)

and a partial function $\mathsf{D}:G(e)\times M_{2}\to M_{1}$,

such that every element $f\in F(e)$, there exists an element $f^{\prime}\in
F(e)$ for which the following equation holds for every element $r\in R$, every
morphism $h\in\mathcal{L}(F,G)$ and every element $m\in M_{1}$.

(4.1) $\mathsf{D}(h_{e}(f),\mathsf{E}_{r}(h_{e}(f^{\prime}),m))=m$

We shall refer to the resulting cryptosystem by the notation
$\mathcal{Y}(F,G,M_{1},M_{2}|R,\mathsf{E},\mathsf{D})$.

######  Convention 4.2 (Restricted Yoneda cryptosystem).

In practice, the use of Definition 4.1 does not require equation (4.1) to hold
for all morphisms $h\in\mathcal{L}(F,G)$. In fact, we will see an instance
(section 4.2) where we need to restrict equation (4.1) to a subset
$M\subseteq\mathcal{L}(F,G)$. For this reason, we will say that a Yoneda
cryptosystem is _restricted_ along a subset $M\subseteq\mathcal{L}(F,G)$ if
Definition 4.1 and, more specifically, its equation (4.1) only holds for
morphisms $h\in M$.

######  Remark 4.3 (Context).

Let us clarify the notations introduced in Definition 4.1. In this respect,
let $\mathcal{Y}(F,G,M_{1},M_{2}|R,\mathsf{E},\mathsf{D})$ be a Yoneda
cryptosystem in $\mathcal{L}$ at an object $e$ in $T$, restricted along a
subset $M\subseteq\mathcal{L}(F,G)$. Since $\mathcal{L}$ is a full subcategory
of $[T,\mathbf{Set}]$, we can evaluate any object and morphism of
$\mathcal{L}$ at the object $e$. Consequently, each morphism $h\in M$ induces
a function as follows.

$h_{e}:F(e)\to G(e)$

This is means that, for every element $f$ in $F(e)$, we can construct a
element $h_{e}(f)$ in $G(e)$. This construction is important role in the
Yoneda cryptosystem as the key space of this cryptosystem is given by the set
$G(e)$. Meanwhile, the set $F(e)$ serves as a parameter set that one can use
to construct keys through morphisms of the form $h:F\Rightarrow G$ in
$\mathcal{L}$. As a result, elements like $h_{e}(f)$ will be used in the
functions $\mathsf{E}_{r}:G(e)\times M_{1}\to M_{2}$ to encode messages in
$M_{1}$, and the function $\mathsf{D}:G(e)\times M_{2}\to M_{1}$ will be used
decrypt the resulting ciphertexts. For a given element $f\in F(e)$, the
corresponding element $f^{\prime}\in F(e)$ mentioned at the end of Definition
4.1 should be seen as a noise operation hiding important information contained
in the element $f$. This noise operation can be seen as a function

$\alpha:\left(\begin{array}[]{lll}F(e)&\to&F(e)\\\
f&\mapsto&f^{\prime}\end{array}\right).$

that makes the diagram below commute for every $r\in R$ and every $h\in M$,
where $\delta$ denotes the Cartesian diagonal function $F(e)\times F(e)\to
F(e)$ in $\mathbf{Set}$, and $\mathsf{pr}_{2}$ denotes the Cartesian
projection $F(e)\times M_{1}\to M_{1}$:

$\textstyle{F(e)\times
M_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{pr}_{2}}$$\scriptstyle{\delta\times\mathsf{id}_{M_{1}}}$$\textstyle{F(e)\times
F(e)\times
M_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h_{e}\times(h_{e}\circ\alpha)\times\mathsf{id}_{M_{1}}}$$\textstyle{G(e)\times
G(e)\times
M_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{id}_{G(e)}\times\mathsf{E}_{r}}$$\textstyle{M_{1}}$$\textstyle{G(e)\times
M_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{D}}$

In the sequel, the function $\alpha$ will not be explicitly defined, as only
the existence of an element $f^{\prime}$ for a given $f$ is required. This
justifies the introduction of Convention 4.4.

######  Convention 4.4 (Reversors).

Let $\mathcal{Y}(F,G,M_{1},M_{2}|R,\mathsf{E},\mathsf{D})$ be a Yoneda
cryptosystem in $\mathcal{L}$ at an object $e$ in $T$, restricted along a
subset $M\subseteq\mathcal{L}(F,G)$. For every element $f\in F(e)$, we define
the subset $\mathcal{R}(f)$ of $F(e)$ as follows:

$\mathcal{R}(f)=\\{f^{\prime}\in F(e)~{}|~{}\forall r\in R,\,\forall h\in
M,\,\forall m\in
M_{1}:\mathsf{D}(h_{e}(f),\mathsf{E}_{r}(h_{e}(f^{\prime}),m))=m\\}$

For every element $f\in F(e)$, an element in $\mathcal{R}(f)$ will be referred
to as a _reversor of $f$_.

In the remainder of this section, we delve into a formal examination of the
application of Yoneda cryptosystems, encompassing key generation, key
publication, encryption, and decryption steps. Each of these steps will serve
as a foundation for describing the other cryptosystems contained in this
paper.

Let us start with the key generation step, which entails configuring
parameters for the publication of the public key. This public key is intended
for use by every sending party, commonly referred to as $\mathsf{Bob}$, to
encrypt messages destined for transmission to the receiving party, usually
referred to as $\mathsf{Alice}$.

######  Generation 4.5 (Yoneda Encryption Scheme).

Let $\mathcal{Y}(F,G,M_{1},M_{2}|R,\mathsf{E},\mathsf{D})$ be a Yoneda
cryptosystem in $\mathcal{L}$ at an object $e$ in $T$, restricted along a
subset $M\subseteq\mathcal{L}(F,G)$. The key generation step for this
cryptosystem is defined as follows. $\mathsf{Alice}$ chooses:

  * -

a small category $I$ and a functor $H:I\to T^{\mathsf{op}}$;

  * -

an element $f_{0}$, called the _initializer_ , in the limit
$\mathsf{lim}_{I^{\mathsf{op}}}(F\circ H^{\mathsf{op}})$ computed in
$\mathbf{Set}$;

  * -

and an element $x$, called the _private key_ , in the set
$(\mathsf{col}_{I}(L\circ Y\circ H))(e)$, where the colimit
$\mathsf{col}_{I}(L\circ Y\circ H)$ is computed in $\mathcal{L}$ and evaluated
at the object $e$ in $T$.

At this point, the tuple $(I,F,f_{0},x)$ is solely known to $\mathsf{Alice}$.
Nevertheless, the subsequent publication step will elucidate which components
are intended to be considered public and private information.

######  Remark 4.6 (Key generation).

The setup introduced in Generation 4.5 is closely related to the statement of
Theorem 3.15. Indeed, note that any element $f_{0}$ taken in the limit
$\mathsf{lim}_{I^{\mathsf{op}}}(F\circ H^{\mathsf{op}})$ defines an element in
the image of the bijection $\phi_{H,F}$ (see Theorem 3.15).

$\phi_{H,F}:\mathcal{L}(\mathsf{col}_{I}(L\circ Y\circ
H),F)\mapsto\mathsf{lim}_{I^{\mathsf{op}}}(U(F)\circ H^{\mathsf{op}}),$

This means that the inverse image $\phi^{-1}_{H,F}(f_{0})$ of the initializer
$f_{0}$ defines a morphism $\mathsf{col}_{I}(L\circ Y\circ H)\Rightarrow F$ in
$\mathcal{L}$. We can then use this morphism to generate a function as
follows.

$\phi^{-1}_{H,F}(f_{0})_{e}:\mathsf{col}_{I}(L\circ Y\circ H)(e)\to F(e)$

We can then use this function to send the private key
$x\in\mathsf{col}_{I}(L\circ Y\circ H)(e)$ to an element
$\phi^{-1}_{H,F}(f_{0})_{e}(x)$ in the set $F(e)$.

######  Publication 4.7 (Yoneda Encryption Scheme).

Let $\mathcal{Y}(F,G,M_{1},M_{2}|R,\mathsf{E},\mathsf{D})$ be a Yoneda
cryptosystem in $\mathcal{L}$ at an object $e$ in $T$, restricted along a
subset $M\subseteq\mathcal{L}(F,G)$. Suppose that we have a key generation
$(H,f_{0},x)$ as defined in Generation 4.5. The publication step for such a
cryptosystem is as follows. $\mathsf{Alice}$ does the following:

  * -

she chooses a reversor $f^{\prime}\in\mathcal{R}(f)$ for the element
$f:=\phi^{-1}_{H,F}(f_{0})_{e}(x)$ (refer to Remark 4.6);

  * -

and she sends the tuple $(f_{0},f^{\prime})$ to $\mathsf{Bob}$. This tuple
defines the _public key_ of the cryptosystem.

At this point, the tuple $(f_{0},f^{\prime})$ along with the cryptosystem data
$(F,G,M_{1},M_{2},R,\mathsf{E},\mathsf{D},e)$ is deemed public and, therefore,
known to all parties.

The next step (Encryption 4.9) will explain how $\mathsf{Bob}$ can send a
message to $\mathsf{Alice}$ securely. Note that, at this point, only the
private key $x$ defined in Generation 4.5 is considered to be unknown to
$\mathsf{Bob}$ and any third party.

######  Remark 4.8 (Key Publication).

Let $\mathcal{Y}(F,G,M_{1},M_{2}|R,\mathsf{E},\mathsf{D})$ be a Yoneda
cryptosystem in $\mathcal{L}$ at an object $e$ in $T$, restricted along a
subset $M\subseteq\mathcal{L}(F,G)$. Suppose that we have a key generation
$(H,f_{0},x)$ as defined in Generation 4.5. The details outlined in
Publication 4.7 indicate that the Yoneda Lemma isomorphism $\phi^{-1}_{H,F}$
is intended for use in tandem with the initializer $f_{0}$ and the private key
$x$. This implies that the application of the Yoneda Lemma is relevant only to
$\mathsf{Alice}$ and essentially establishes an encryption barrier between
$\mathsf{Alice}$ and other parties.

Although $\mathsf{Bob}$ cannot directly utilize the Yoneda Lemma isomorphism
$\phi^{-1}_{H,F}$, he can leverage its image space as a proxy. For instance,
consider that the initializer $f_{0}$ is an element of the limit
$\mathsf{lim}_{I^{\mathsf{op}}}(F\circ H^{\mathsf{op}})$. Now, observe that
for every morphism $h:F\Rightarrow G$ in $\mathcal{L}$, we have a
corresponding morphism

$h_{H}:F\circ H^{\mathsf{op}}\Rightarrow G\circ H^{\mathsf{op}}.$

This morphism enables the construction of a universal function

$\mathsf{lim}_{I^{\mathsf{op}}}(h_{H})(f_{0}):\mathsf{lim}_{I^{\mathsf{op}}}(F\circ
H^{\mathsf{op}})\rightarrow\mathsf{lim}_{I^{\mathsf{op}}}(G\circ
H^{\mathsf{op}}),$

allowing $\mathsf{Bob}$ to transform the element $f_{0}$ in specific ways.
$\mathsf{Alice}$ can then simulate this transformation on an element of $F(e)$
using the naturality properties of the Yoneda Lemma.

######  Encryption 4.9 (Yoneda Encryption Scheme).

Let $\mathcal{Y}(F,G,M_{1},M_{2}|R,\mathsf{E},\mathsf{D})$ be a Yoneda
cryptosystem in $\mathcal{L}$ at an object $e$ in $T$, restricted along a
subset $M\subseteq\mathcal{L}(F,G)$. We will consider a private key $x$, as
defined in Generation 4.5, and a public key $(f_{0},f^{\prime})$, as defined
in Publication 4.7. The encryption step for such a cryptosystem unfolds as
follows. $\mathsf{Bob}$ initiates the process by selecting:

  * -

an element $r\in R$, called the _noise parameter_ ;

  * -

a morphism $h\in M$, called the _encryption token_ ;

  * -

and an element $m\in M_{1}$, identified as the _message_.

Subsequently, $\mathsf{Bob}$ transmits the following information to
$\mathsf{Alice}$:

  * -

the element $c_{1}=\mathsf{lim}_{I^{\mathsf{op}}}(h_{H})(f_{0})$ in
$\mathsf{lim}_{I^{\mathsf{op}}}(G\circ H^{\mathsf{op}})$ (refer to Remark
4.8);

  * -

and the element $c_{2}=\mathsf{E}_{r}(h_{e}(f^{\prime}),m)$ in $M_{2}$.

The tuple $(c_{1},c_{2})$ collectively constitutes the _encryption_ of the
message $m$.

The decryption step (Decryption 4.10) hinges on the intrinsic naturality
property of the Yoneda Lemma. In essence, this property empowers
$\mathsf{Alice}$ to decipher the message encrypted by $\mathsf{Bob}$ without
requiring any knowledge about the morphism $h:F\Rightarrow G$ selected by
$\mathsf{Bob}$ in Encryption 4.9.

######  Decryption 4.10 (Yoneda Encryption Scheme).

Let $\mathcal{Y}(F,G,M_{1},M_{2}|R,\mathsf{E},\mathsf{D})$ be a Yoneda
cryptosystem in $\mathcal{L}$ at an object $e$ in $T$, restricted along a
subset $M\subseteq\mathcal{L}(F,G)$. We will consider a private key $x$, as
defined in Generation 4.5, and a public key $(f_{0},f^{\prime})$, as defined
in Publication 4.7. For every encrypted message $(c_{1},c_{2})$ sent by
$\mathsf{Bob}$, as defined in Encryption 4.9, the decryption step unfolds as
follows. $\mathsf{Alice}$ computes:

  * -

the element $d=\phi_{H,G}^{-1}(c_{1})_{e}(x)$ in $G(e)$;

  * -

and the element $m^{\prime}=\mathsf{D}(d,c_{2})$ in $M_{1}$;

The element $m^{\prime}\in M_{1}$ is well-defined and corresponds to the
original message $m$ sent by $\mathsf{Bob}$, as shown in the sequence of
equations below:

$\displaystyle m^{\prime}$ $\displaystyle=\mathsf{D}(d,c_{2})$
$\displaystyle=\mathsf{D}(\phi_{H,G}^{-1}(c_{1})_{e}(x),c_{2})$
$\displaystyle(d=\phi_{H,G}^{-1}(c_{1})_{e}(x))$
$\displaystyle=\mathsf{D}(\phi_{H,G}^{-1}(\mathsf{lim}_{I^{\mathsf{op}}}(h_{H})(f_{0}))_{e}(x),c_{2})$
$\displaystyle(c_{1}=\mathsf{lim}_{I^{\mathsf{op}}}(h_{H})(f_{0}))$
$\displaystyle=\mathsf{D}((h\circ\phi_{H,F}^{-1}(f_{0}))_{e}(x),c_{2})$
$\displaystyle(\textrm{Yoneda isomorphism naturality})$
$\displaystyle=\mathsf{D}(h_{e}(\phi_{H,F}^{-1}(f_{0})_{e}(x)),c_{2})$
$\displaystyle(\textrm{Natural transformations})$
$\displaystyle=\mathsf{D}(h_{e}(f),c_{2})$
$\displaystyle(f=\phi_{H,F}^{-1}(f_{0})_{e}(x))$
$\displaystyle=\mathsf{D}(h_{e}(f),\mathsf{E}_{r}(h_{e}(f^{\prime}),m))$
$\displaystyle(c_{2}=\mathsf{E}_{r}(h_{e}(f^{\prime}),m))$ $\displaystyle=m$
$\displaystyle(f^{\prime}\in\mathcal{R}(f))$

This concludes the definition of the Yoneda Encryption Scheme. In the
following sections, we will demonstrate how this scheme can recover more
specific schemes. We will commence by exploring the ElGamal encryption scheme.

###  4.2. ElGamal encryption

The ElGamal cryptosystem, introduced by Taher Elgamal in 1985, is based on the
Diffie–Hellman key exchange protocol [1, 10]. The mathematical foundation of
this cryptosystem relies on the complexity of the discrete logarithm problem.
Throughout this section, we demonstrate how to define a Yoneda cryptosystem
that recovers the ElGamal cryptosystem.

######  Generation 4.11 (ElGamal).

The key generation step for the ElGamal cryptosystem is defined as follows.
$\mathsf{Alice}$ chooses:

  * -

a cyclic group $G$ of order $q$ with generator $g$;

  * -

a (random) private key $x\in[q-1]$

Given that the discrete logarithm problem in $G$ extends to all cyclic
subgroups of $G$, the element $g$ is not strictly required to be a generator
of the overall group structure $G$ (refer to Remark 4.12 for further
clarification).

######  Remark 4.12 (Generator).

As highlighted in Generation 4.11, the element $g$ need not be a generator of
the group $G$. This flexibility arises from the fact that solving a discrete
logarithm problem of the form $g^{x}=f$ inherently implies that the element
$y$ resides in the cyclic subgroup $\langle
g\rangle:=\\{1,g,g^{2},\dots,g^{q}\\}$. Consequently, even if $g$ is not a
generator, the cryptosystem data can effortlessly adapt to the cyclic subgroup
$\langle g\rangle$ of $G$ along with its corresponding order. Given that the
private key $x$ is intended for use as an exponent of $g$, it follows that the
private key $x$ should either be selected after the choice of $g$ or
preferably considered in the set $\mathbb{Z}$ of all integers, rather than in
the modulo set $\mathbb{Z}_{q}=[q-1]$. As demonstrated in Application 4.13,
the Yoneda cryptosystem seamlessly resolves these ambiguities.

Below, Application 4.13 clarifies how the steps outlined in Publication 4.11
can be recovered through the Yoneda cryptosystem’s generation step. To achieve
this, we need to define the reflective subcategory in which the Yoneda
cryptosystem operates and articulate the overarching encryption-decryption
protocol.

######  Application 4.13 (ElGamal as Yoneda).

Let us describe the overall setup for the Yoneda cryptosystem encoding the
ELGamal cryptosystem. First, the associated limit sketch $T$ must be the limit
sketch $T_{\mathsf{cgroup}}$ defined for commutative groups (see Example
3.29). As a result, the associated reflective subcategory is given by the
inclusion

$\mathbf{Mod}(T_{\mathsf{cgroup}})\hookrightarrow[T_{\mathsf{cgroup}},\mathbf{Set}]$

and its left adjoint $L$ (see Remark 3.20). The Yoneda cryptosystem is then
defined at the object $d_{1}$ of $T_{\mathsf{cgroup}}$ which refers to the set
of elements of the group structure. Specifically, the ElGamal cryptosystem is
expressed as a Yoneda cryptosystem of the form

$\mathcal{Y}(G,G,G(d_{1}),G(d_{1})|\mathbf{1},\mathsf{E},\mathsf{D})$

where $G$ is a cyclic group of order $q$ with generator $g$. The notation
$G(d_{1})$ refers to the underlying set of elements for the model $G$ in
$\mathbf{Mod}(T_{\mathsf{cgroup}})$. The collection of encryption algorithms
is indexed by a terminal set $\mathbf{1}=\\{\ast\\}$ and therefore consists of
a single algorithm

$\mathsf{E}_{\ast}:G(d_{1})\times G(d_{1})\to G(d_{1}),$

which is given by the mutiplication operation $(a,b)\mapsto a\cdot b$ of $G$.
The decryption algorithm

$\mathsf{D}:G(d_{1})\times G(d_{1})\to G(d_{1})$

is given by the map $(a,b)\mapsto a^{-1}\cdot b$. With such functions, we can
determine the form of the set $\mathcal{R}(f)$ for every $f\in G$, as shown
below.

$\displaystyle\mathcal{R}(f)$ $\displaystyle=\\{f^{\prime}~{}|~{}\forall
h\in\mathcal{L}(G,G),\,\forall m\in G:\,h_{d_{1}}(f)^{-1}\cdot
h_{d_{1}}(f^{\prime})\cdot m=m\\}$ $\displaystyle(\textrm{Convention
\ref{conv:reversors}})$ $\displaystyle=\\{f^{\prime}~{}|~{}\forall
h\in\mathcal{L}(G,G):\,h_{d_{1}}(f^{\prime})=h_{d_{1}}(f)\\}$
$\displaystyle(\textrm{Group structure})$ $\displaystyle=\\{f\\}$
$\displaystyle(\textrm{implied by }h=\mathsf{id}_{G})$

The fact that $\mathcal{R}(f)$ is non-empty for all $f\in G$ shows that the
Yoneda cryptosystem is well-defined. Following Generation 4.5, the key
generation step undertaken by $\mathsf{Alice}$ for this cryptosystem consists
of

  * -

a functor $H:\mathbf{1}\to T_{\mathsf{cgroup}}^{\mathsf{op}}$ picking out the
element $d_{1}$ in $T_{\mathsf{cgroup}}$;

  * -

an initializer $f_{0}$ in $\mathsf{lim}_{\mathbf{1}}(G\circ
H^{\mathsf{op}})=G(d_{1})$;

  * -

and a private key $x$ in $\mathsf{col}_{\mathbf{1}}(L\circ Y\circ
H)(d_{1})=L(Y(d_{1}))(d_{1})=\mathbb{Z}$ (see Remark 3.30).

Here, the initializer $f_{0}$ denotes some element $g^{x_{0}}$ in $G$. As
suggested in Remark 4.12, this element need not be a generator of $G$ (but it
should at least be different form the neutral element). Also note that the
private key $x$ chosen for the Yoneda cryptosystem belongs to $\mathbb{Z}$
instead of the set $[q-1]$, as required in Generation 4.11. This distinction
is inconsequential as $x$ will serve as an exponent for some element in $G$,
and can therefore be considered modulo the order $q$ of $G$.

Let us examine how the ElGamal key publication aligns with that of the Yoneda
cryptosystem (described in Application 4.13 above). First, we will present the
ElGamal key publication step in Publication 4.14 and then draw parallels with
Publication 4.7 in Application 4.15.

######  Publication 4.14 (ElGamal).

The key publication step for the ElGamal cryptosystem unfolds as follows.
$\mathsf{Alice}$ undertakes the following actions:

  * -

she computes the element $f=g^{x}$ in the group $G$;

  * -

and she sends the public key $(G,q,g,f)$ to $\mathsf{Bob}$.

Since the tuple $(G,q,g)$ has already been determined in Generation 4.11,
$\mathsf{Alice}$ essentially generates and transmits only the element $f$.

######  Application 4.15 (ElGamal as Yoneda).

The key publication step for the Yoneda cryptosystem unfolds as follows.
$\mathsf{Alice}$ does the following:

  * -

she computes the element $f=\phi_{H,G}^{-1}(f_{0})_{d_{1}}(x)$ in $G$. Since
$\phi_{H,G}^{-1}(f_{0})$ corresponds to the group homomorphism $\mathbb{Z}\to
G$ that picks out the element $f_{0}\in G(d_{1})$ at the element
$1\in\mathbb{Z}$, the element $f$ must be equal to the power $f_{0}^{x}$ in
$G$.

  * -

Since $\mathcal{R}(f)=\\{f\\}$, $\mathsf{Alice}$ must send the public key
$(f_{0},f)$ to $\mathsf{Bob}$.

As detailed in Publication 4.7, $\mathsf{Alice}$ discloses both the tuple
$(f_{0},f)$ and the accompanying cryptosystem data $(G,q)$. In essence, the
entire tuple $(G,q,f_{0},f)$ becomes public knowledge for all parties
involved.

We now address the encryption step for the ElGamal cryptosystem.

######  Encryption 4.16 (ElGamal).

The encryption step for the ElGamal cryptosystem is organized as follows.
First, $\mathsf{Bob}$ chooses the following:

  * -

an (random) element $h\in[q-1]$;

  * -

a message $m\in G$.

Then, $\mathsf{Bob}$ sends the following information to $\mathsf{Alice}$:

  * -

the element $c_{1}=g^{h}$ in the group $G$;

  * -

and the element $c_{2}=f^{h}\cdot m$ in the group $G$.

The pair $(c_{1},c_{2})$ constitutes the encryption of the message $m$.

According to Application 4.13, the set $R$ that indexes the encryption
algorithms is trivial. Consequently, the step of Encryption 4.9 where
$\mathsf{Bob}$ typically selects an element from the set $R$ is omitted in the
subsequent application. Furthermore, despite the group homomorphism chosen in
Application 4.17 being confined to a specific form, it is important to note
that the Yoneda Encryption Scheme does not impose such restrictions on the
chosen form.

######  Application 4.17 (ElGamal as Yoneda).

The encryption step for the Yoneda cryptosystem unfolds as follows.
$\mathsf{Bob}$ initiates the process by selecting:

  * -

a morphism $\tilde{h}:G\Rightarrow G$ in $\mathcal{L}$ encoded by the mapping
rule $u\mapsto u^{h}$ for some integer $h\in[q-1]$. This mapping rule does
define a group endomorphism on $G$ because $G$ is commutative;

  * -

and a message $m\in G$.

Then, $\mathsf{Bob}$ sends the following information to $\mathsf{Alice}$:

  * -

the element $c_{1}=\mathsf{lim}_{\mathbf{1}}(\tilde{h}_{H})(f_{0})=f_{0}^{h}$
in $G(d_{1})$;

  * -

and the element $c_{2}=\mathsf{E}_{\ast}(\tilde{h}_{d_{1}}(f),m)=f^{h}\cdot m$
in $G(d_{1})$.

The pair $(c_{1},c_{2})$ constitutes the encryption of the message $m$.

We conclude this section with the decryption steps. The correctness of both
the ElGamal cryptosystems and the Yoneda cryptosystems are provided by the
calculations shown in Decryption 4.10.

######  Decryption 4.18 (ElGamal).

The decryption step for the Yoneda cryptosystem unfolds as follows.
$\mathsf{Alice}$ computes:

  * -

the element $d=c_{1}^{x}$ in $G$;

  * -

the element $m^{\prime}=d^{-1}\cdot c_{2}$ in $G$.

Since we have the relations $d^{-1}=f_{0}^{-hx}$ and $c_{2}=f_{0}^{xh}\cdot
m$, the identity $m^{\prime}=m$ holds.

######  Application 4.19 (ElGamal as Yoneda).

The decryption step for the Yoneda cryptosystem unfolds as follows.
$\mathsf{Alice}$ computes:

  * -

the element $d=\phi^{-1}_{H,G}(c_{1})_{d_{1}}(x)$ in $G$. Since
$\phi_{H,G}^{-1}(c_{1})$ corresponds to the group homomorphism $\mathbb{Z}\to
G$ that picks out the element $c_{1}\in G(d_{1})$ at the element
$1\in\mathbb{Z}$, the element $d$ must be equal to the power $c_{1}^{x}$ in
$G(d_{1})$.;

  * -

the element $m^{\prime}=\mathsf{D}(d,c_{2})=d^{-1}\cdot c_{2}$ in $G(d_{1})$.

The identity $m^{\prime}=m$ follows from Decryption 4.10.

######  Remark 4.20 (Cramer–Shoup cryptosystems).

The capability to recover the ElGamal cryptosystem with elements $g$ that are
not necessarily generators has been implicitly utilized in the literature. For
example, the Cramer–Shoup cryptosystem [9] is a modification of the ElGamal
cryptosystem that leverages this flexibility along with a collision-resistant
hash function to enhance the system’s resistance to manipulation.

###  4.3. RSA encryption

The RSA encryption system, conceived in 1977 by Ron Rivest, Adi Shamir, and
Leonard Adleman, is grounded in the arithmetic of finite modulo sets
(Convention 3.31) and their cyclic subgroups [1]. The mathematical
underpinning of this cryptographic scheme relies on the difficulty of two
challenges: (1) determining the prime factorization of a given integer and (2)
identifying the logarithmic base $m$ of a power $m^{e}$ modulo a specified
integer $n$. In this section, we detail the formulation of a Yoneda
cryptosystem that reconstructs the RSA encryption scheme (starting at
Generation 4.24).

######  Convention 4.21 (Coprime).

We say that two integers $n$ and $m$ are _coprime_ if their greatest common
divisor is $1$. This means that there exists two integers $x$ and $y$ such
that the relation $nx+my=1$ holds.

######  Convention 4.22.

For every positive integer $n$, we will denote as $\mathbb{Z}_{n}^{\times}$
the subset of $\mathbb{Z}_{n}$ whose elements are coprime with $n$. It is
straightforward to show that $\mathbb{Z}_{n}^{\times}$ defines a group for the
multiplication of integers since the multiplication of two relations
$nx_{0}+m_{0}y_{0}=1$ and $nx_{1}+m_{1}y_{1}=1$ gives the following relation.

$n(nx_{1}x_{0}+x_{1}m_{0}y_{0}+m_{1}y_{1}x_{0})+m_{1}m_{0}(y_{1}y_{0})=1$

######  Definition 4.23 (Carmichael’s totient function).

For every positive integer $n$, we define the _Carmichael’s totient number_
$\lambda(n)$ as the order of the multiplicative group
$\mathbb{Z}_{n}^{\times}$. In other words, $\lambda(n)$ is defined as the
smallest positive integer $k$ such that, for every integer $x$ coprime to $n$,
the equation $x^{k}\equiv 1\,(\mathsf{mod}\,n)$ holds.

Let us now present the RSA cryptosystem. As in previous instances, we will
delineate each step of RSA alongside its counterpart in the Yoneda encryption
scheme.

######  Generation 4.24 (RSA).

The key generation step for the RSA cryptosystem is outlined as follows.
$\mathsf{Alice}$ makes the following selections:

  * -

a positive integer $n$, which should be the product of two large prime
numbers;

  * -

and an element $f_{0}$ in the multiplicative group
$\mathbb{Z}_{\lambda(n)}^{\times}$ whose inverse $f_{0}^{-1}$ in
$\mathbb{Z}_{\lambda(n)}^{\times}$ is readily known to $\mathsf{Alice}$.

In the context of the RSA cryptosystem, the inverse $f_{0}^{-1}$ is kept
private to other parties.

######  Application 4.25 (RSA as Yoneda).

Let us describe the Yoneda cryptosystem that recovers the RSA cryptosystem. To
start with, we take the associated limit sketch $T$ to be the terminal
category $\mathbf{1}=\\{\ast\\}$. As a result, the associated reflective
subcategory is given by the identity

$\mathbf{Mod}(\mathbf{1})=[\mathbf{1},\mathbf{Set}]$

where the category $[\mathbf{1},\mathbf{Set}]$ is isomorphic to
$\mathbf{Set}$. The Yoneda cryptosystem is defined at the obvious object in
$\mathbf{1}$. The RSA cryptosystem is then defined as a Yoneda cryptosystem of
the form

$\mathcal{Y}(\mathbb{Z}_{\lambda(n)}^{\times},\mathbb{Z}_{\lambda(n)}^{\times},\mathbb{Z}_{n},\mathbb{Z}_{n}|\mathbf{1},\mathsf{E},\mathsf{D})$

where $n$ is a positive integer. The collection of encryption algorithms is
indexed by a terminal set $\mathbf{1}=\\{\ast\\}$ and therefore consists of a
single algorithm given by the following function.

$\mathsf{E}_{\ast}:\left(\begin{array}[]{ccc}\mathbb{Z}_{\lambda(n)}^{\times}\times\mathbb{Z}_{n}&\to&\mathbb{Z}_{n}\\\
(g,m)&\mapsto&m^{g}\end{array}\right)$

It is important to note that although the function $\mathsf{E}{\ast}$ is
formally defined as a mapping

$\mathbb{Z}_{\lambda(n)}^{\times}\times\mathbb{Z}_{n}\to\mathbb{Z}_{n},$

the associated parameter $\lambda(n)$ exclusively pertains to
$\mathsf{Alice}$. From an external viewpoint, while other parties are aware of
the general structure of the function $\mathsf{E}{\ast}$, practically
computing the parameter $\lambda(n)$ from $n$ poses a considerable challenge.
Consequently, any sender party utilizes the encryption algorithm as a function
of the form $\mathbb{N}\times\mathbb{Z}_{n}\rightarrow\mathbb{Z}_{n}$.
Similarly, the practical knowledge required for computing the decryption
algorithm is exclusively within the grasp of $\mathsf{Alice}$. This function
is defined by the following mapping, where the term $g^{-1}$ represents the
multiplicative inverse of the element $g$ in
$\mathbb{Z}_{\lambda(n)}^{\times}$.

$\mathsf{D}:\left(\begin{array}[]{ccc}\mathbb{Z}_{\lambda(n)}^{\times}\times\mathbb{Z}_{n}&\to&\mathbb{Z}_{n}\\\
(g,c)&\mapsto&c^{g^{-1}}\end{array}\right)$

With such functions, we can determine the form of the set $\mathcal{R}(f)$ for
every $f\in\mathbb{Z}_{\lambda(n)}^{\times}$, as shown below.

$\displaystyle\mathcal{R}(f)$ $\displaystyle=\\{f^{\prime}~{}|~{}\forall
h\in\mathbf{Set}(\mathbb{Z}_{\lambda(n)}^{\times},\mathbb{Z}_{\lambda(n)}^{\times}),\,\forall
m\in\mathbb{Z}_{n}:\,\big{(}m^{h_{\ast}(f^{\prime})}\big{)}^{h_{\ast}(f)^{-1}}=m\textrm{
in }\mathbb{Z}_{n}\\}$ $\displaystyle(\textrm{Convention
\ref{conv:reversors}})$ $\displaystyle=\\{f^{\prime}~{}|~{}\forall
h\in\mathbf{Set}(\mathbb{Z}_{\lambda(n)}^{\times},\mathbb{Z}_{\lambda(n)}^{\times}):\,h_{\ast}(f^{\prime})\cdot
h_{\ast}(f)^{-1}=1\textrm{ in }\mathbb{Z}_{\lambda(n)}^{\times}\\}$
$\displaystyle(\textrm{implied by }m\in\mathbb{Z}_{n}^{\times})$
$\displaystyle=\\{f^{\prime}~{}|~{}\forall
h\in\mathbf{Set}(\mathbb{Z}_{\lambda(n)}^{\times},\mathbb{Z}_{\lambda(n)}^{\times}):\,h_{\ast}(f^{\prime})=h_{\ast}(f)\textrm{
in }\mathbb{Z}_{\lambda(n)}^{\times}\\}$ $\displaystyle(\textrm{Group
structure})$ $\displaystyle=\\{f\\}$ $\displaystyle(\textrm{implied by
}h=\mathsf{id})$

The fact that $\mathcal{R}(f)$ is non-empty for all
$f\in\mathbb{Z}_{\lambda(n)}^{\times}$ shows that the Yoneda cryptosystem is
well-defined. Following Generation 4.5, the key generation step undertaken by
$\mathsf{Alice}$ for this cryptosystem consists of

  * -

an identity functor $H:\mathbf{1}\to\mathbf{1}$;

  * -

an initializer $f_{0}$ in
$\mathsf{lim}_{\mathbf{1}}(\mathbb{Z}_{\lambda(n)}^{\times}\circ
H^{\mathsf{op}})=\mathbb{Z}_{\lambda(n)}^{\times}$ whose inverse $f_{0}^{-1}$
is readily known to $\mathsf{Alice}$;

  * -

and a private key $x$ in the singleton $\mathsf{col}_{\mathbf{1}}(Y\circ
H)(\ast)=Y(\ast)(\ast)=\\{\mathsf{id}_{\ast}\\}$.

Here, the private key $x$ must be taken to be the only element of the
singleton $\mathbf{1}(\ast,\ast)$. The security of the cryptosystem remains
unaffected since the confidential details lie in the computation of the
inverse $f_{0}^{-1}$ and the definition of the decryption algorithm. Both of
these components pose computational challenges, making them difficult to
ascertain.

We now describe the key publication steps for both RSA and its Yoneda form.

######  Publication 4.26 (RSA).

The key publication step for the RSA cryptosystem is as follows:
$\mathsf{Alice}$ transmits the element
$f_{0}\in\mathbb{Z}_{\lambda(n)}^{\times}$ to $\mathsf{Bob}$ and reveals
general information about her cryptosystem, such as the integer $n$ and the
theoretical structure of the encryption-decryption protocol.

######  Application 4.27 (RSA as Yoneda).

The key publication step for the Yoneda cryptosystem unfolds as follows.
$\mathsf{Alice}$ does the following:

  * -

she computes the element

$f=\phi_{H,\mathbb{Z}_{\lambda(n)}^{\times}}^{-1}(f_{0})_{\ast}(x).$

This element corresponds to the image of the function
$\mathbf{1}\to\mathbb{Z}_{\lambda(n)}^{\times}$ picking out the element
$f_{0}$. As a result, the element $f$ is equal to the element $f_{0}$.

  * -

Since $\mathcal{R}(f)=\\{f\\}$, $\mathsf{Alice}$ must send the public key
$(f_{0},f_{0})$ to $\mathsf{Bob}$.

As outlined in Publication 4.7, $\mathsf{Alice}$ reveals both the key $f_{0}$
and the theoretical structure of the cryptosystem data, withholding only the
computation details of the parameters intended to remain confidential.

We will now outline the encryption steps. Note that RSA encryption involves a
single ciphertext, whereas Yoneda’s encryption comprises a pair of
ciphertexts, with the first one already known to $\mathsf{Alice}$.

######  Encryption 4.28 (RSA).

The encryption step in the RSA cryptosystem unfolds as follows: $\mathsf{Bob}$
selects an element $m$ from $\mathbb{Z}_{n}$ as the message, and then
transmits the element $c=m^{f_{0}}\in\mathbb{Z}_{n}$ to $\mathsf{Alice}$.

######  Application 4.29 (RSA as Yoneda).

The encryption step for the Yoneda cryptosystem unfolds as follows.
$\mathsf{Bob}$ initiates the process by selecting:

  * -

the identity function
$h:\mathbb{Z}_{\lambda(n)}^{\times}\to\mathbb{Z}_{\lambda(n)}^{\times}$ in
$\mathbf{Set}$;

  * -

and a message $m\in\mathbb{Z}_{n}$.

Then, $\mathsf{Bob}$ sends the following information to $\mathsf{Alice}$:

  * -

the element $c_{1}=\mathsf{lim}_{\mathbf{1}}(h_{H})(f_{0})=f_{0}$ in
$\mathbb{Z}_{\lambda(n)}^{\times}$;

  * -

and the element $c_{2}=\mathsf{E}_{\ast}(h_{\ast}(f),m)=m^{f_{0}}$ in
$\mathbb{Z}_{n}$.

While the pair $(c_{1},c_{2})$ constitutes an encryption for the message $m$,
its first component $c_{1}=f_{0}$ is information already known to
$\mathsf{Alice}$. Nevertheless, this data can be utilized by $\mathsf{Bob}$ as
a certificate, ensuring that $\mathsf{Alice}$ is aware of the cryptosystem
being employed by $\mathsf{Bob}$.

Given the computational difficulty of determining $m$ for a given power
$m^{f_{0}}$ in $\mathbb{Z}_{n}$ (when $f_{0}$ is non-trivial), the ciphertexts
employed in Encryption 4.28 and Application 4.29 are deemed secure. We will
now proceed to outline the decryption steps for these ciphertexts.

######  Decryption 4.30 (RSA).

The decryption step for the RSA cryptosystem goes as follows: $\mathsf{Alice}$
calculates the value $m^{\prime}=c^{f_{0}^{-1}}$ within $\mathbb{Z}_{n}$,
where the inverse $f_{0}^{-1}$ is readily known to $\mathsf{Alice}$. Given
that $m^{\prime}$ is equivalent to the power $(m^{f_{0}})^{f_{0}^{-1}}$, we
successfully retrieve the message $m$ in $\mathbb{Z}_{n}$.

######  Application 4.31 (RSA as Yoneda).

The decryption step for the Yoneda cryptosystem unfolds as follows.
$\mathsf{Alice}$ computes:

  * -

the element

$d=\phi_{H,\mathbb{Z}_{\lambda(n)}^{\times}}^{-1}(c_{1})_{\ast}(x).$

This element corresponds to the image of function
$\mathbf{1}\to\mathbb{Z}_{\lambda(n)}^{\times}$ picking out the element
$c_{1}$. As a result, the element $d$ is equal to the element $c_{1}=f_{0}$.;

  * -

and the element
$m^{\prime}=\mathsf{D}(d,c_{2})=c_{2}^{d^{-1}}=(m^{f_{0}})^{f_{0}^{-1}}$ in
$\mathbb{Z}_{n}$;

The identity $m^{\prime}=m$ follows from Decryption 4.10.

###  4.4. Benaloh encryption

In this section, we consider the Benaloh cryptosystem as a representative
example for a well-known class of cryptosystems, including the Goldwasser-
Micali cryptosystem, the Boneh-Goh-Nissim cryptosystem and the Paillier
cryptosystem [1, 16, 3, 23]. We shall leave the translation of these
cryptosystems into Yoneda cryptosystems as an exercise to the reader. The
exposition provided for the Benaloh cryptosystem below can serve as a
reference for this purpose.

The Benaloh cryptosystem, introduced by Josh Benaloh in 1994, is grounded in
the complexity of the Higher Residuosity Problem [1]. However, the original
correctness of the cryptosystem suffered from a problem, which was correct in
2011 by Fousse, Lafourcade, and Alnuaimi [12]. Before showing how the Yoneda
Encryption Scheme can effectively recover the Benaloh cryptosystem, we will
establish a few essential notations. In particular, we will use the
terminology introduced in Convention 4.21, Convention 4.22 and Convention
4.23.

######  Convention 4.32 (Notations).

Let $n$ be a positive integer and $x$ be an element in
$\mathbb{Z}_{n}^{\times}$. For every element $y$ in $\mathbb{Z}_{n}^{\times}$
represented as a power of $x$ in $\mathbb{Z}_{n}^{\times}$, we denote by
$\mathsf{log}_{x}(y)$ the smallest exponent $m$ in $\mathbb{Z}_{n}$ for which
the equation $y=x^{m}$ holds in $\mathbb{Z}_{n}^{\times}$. The computational
steps for the function $\mathsf{log}_{x}$ are detailed in [12].

The following results identify a situation in which the computation of
discrete logarithms does not require to choose among a set of representatives.

######  Proposition 4.33 (Correctness).

Let $n$ be a positive integers and $p$ be a prime factor of $n$. We denote by
$\omega$ the generator of the cyclic group $\mathbb{Z}_{p}^{\times}$ of order
$\lambda(p)=p-1$. Let $x$ be an element in $\mathbb{Z}_{n}^{\times}$ such that
its representative in $\mathbb{Z}_{p}^{\times}$ is of the form $\omega^{k}$.
If the exponent $k$ is coprime with a factor $v$ of $p-1$, then the following
equivalence holds: for every $m\in\mathbb{Z}_{v}$, the equation $y=x^{m}$
holds in $\mathbb{Z}_{n}^{\times}$ if, and only, if $\mathsf{log}_{x}(y)=m$.

###### Proof.

To show the direct implication, let us show that if the equation $y=x^{m}$
holds in $\mathbb{Z}_{n}^{\times}$ for some $m\in\mathbb{Z}_{v}$, then $m$ is
the only exponent in $\mathbb{Z}_{n}$ for which the equation $y=x^{m}$ holds
in $\mathbb{Z}_{n}^{\times}$. Indeed, if $x^{m_{1}}=x^{m_{2}}$ in
$\mathbb{Z}_{n}^{\times}$, then $\omega^{k(m_{1}-m_{2})}=1$ in
$\mathbb{Z}_{n}^{\times}$ and hence in $\mathbb{Z}_{p}^{\times}$. Since
$\omega$ is a generator of $\mathbb{Z}_{p}^{\times}$, it follows from
Convention 4.23 that we must have $k(m_{1}-m_{2})=0$ in
$\mathbb{Z}_{\lambda(p)}$ where $\lambda(p)=p-1$. Since $v$ is a factor of
$p-1$, we also have $k(m_{1}-m_{2})=0$ in $\mathbb{Z}_{v}$. By assumption, the
integer $k$ is represented in $\mathbb{Z}_{v}^{\times}$, so we have
$m_{1}=m_{2}$ in $\mathbb{Z}_{v}$. This concludes the proof for the direct
implication. The opposite implication follows from Convention 4.32. ∎

######  Convention 4.34 (Notations).

Consider a positive integer $v$ and two prime numbers $p$ and $q$ with the
following conditions:

  * 1)

the integer $v$ divides $p-1$;

  * 2)

both integers $(p-1)/v$ and $q-1$ are coprime with the integer $v$.

These assumptions imply that $v$ divides the integer $\phi=(p-1)(q-1)$, and
$\phi/v$ is coprime with $v$. Additionally, note that since $p$ is a factor of
$n$, every element in $\mathbb{Z}_{n}^{\times}$ is represented in
$\mathbb{Z}_{p}^{\times}$. Now, if we let $n=pq$, we denote by $B^{p,q}_{v}$
the set of integers $g\in\mathbb{Z}_{n}^{\times}$ such that the representative
of $g^{\phi/v}$ in $\mathbb{Z}_{p}^{\times}$ is of the form $\omega^{k}$,
where $\omega$ is a generator of $\mathbb{Z}_{p}^{\times}$ and $k$ is coprime
with $v$. As the integer $\phi/v$ is coprime with $v$, the set $B^{p,q}_{v}$
encompasses every element of $\mathbb{Z}_{n}^{\times}$ that is a generator in
$\mathbb{Z}_{p}^{\times}$.

######  Remark 4.35 (Correctness).

Consider a positive integer $v$ and two prime numbers $p$ and $q$ such that
the integer $v$ divides $p-1$ and both integers $(p-1)/v$ and $q-1$ are
coprime with the integer $v$. It follows from Proposition 4.33 and Convention
4.34 that the following equation holds for every $f_{0}\in B^{p,q}_{v}$ and
every $m\in\mathbb{Z}_{v}$.

$\mathsf{log}_{f_{0}^{\phi/v}}(f_{0}^{m\phi/v})=m$

This means that $\mathsf{Alice}$ can decrypt ciphertexts encoded as
exponentials $f_{0}^{m\phi/v}$ by using the discrete logarithm.

The requirements detailed in the key generation for the Benaloh cryptosystem
(see Generation 4.36) are primarily motivated by Proposition 4.33 and
Convention 4.35. This is because the Benaloh cryptosystem necessitates the
computation of a discrete logarithm for decrypting its ciphertexts.

######  Generation 4.36 (Benaloh).

The key generation step for the Benaloh cryptosystem goes as follows.
$\mathsf{Alice}$ starts with the following selection:

  * -

a positive integer $v$ and two prime numbers $p$ and $q$ such that the integer
$v$ divides $p-1$ and both integers $(p-1)/v$ and $q-1$ are coprime with the
integer $v$;

  * -

and an element $f_{0}\in B^{p,q}_{v}$ where we take .

In the discussions that follow, we will use the notations $\phi=(p-1)(q-1)$
and $n=pq$.

######  Remark 4.37 (Carmichael’s totient number).

Given two prime numbers $p$ and $q$ such that $n=pq$, it is well-known that
Carmichael’s totient number $\lambda(n)$ is equal to the least common multiple
of $p-1$ and $q-1$. Letting $\phi=(p-1)(q-1)$, it follows that for every
$r\in\mathbb{Z}_{n}^{\times}$, the power $r^{\phi}$ is equal to $1$ in
$\mathbb{Z}_{n}^{\times}$.

######  Application 4.38 (Benaloh as Yoneda).

Let us describe the Yoneda cryptosystem that captures the Benaloh
cryptosystem. First, we take the associated limit sketch $T$ to be the
terminal category $\mathbf{1}=\\{\ast\\}$. As a result, the associated
reflective subcategory is given by the following identity.

$\mathbf{Mod}(\mathbf{1})=[\mathbf{1},\mathbf{Set}]$

The Yoneda cryptosystem is defined at the obvious object. The Benaloh
cryptosystem is then defined as a Yoneda cryptosystem of the form

$\mathcal{Y}(B^{p,q}_{v},B^{p,q}_{v},\mathbb{Z}_{n}^{\times},\mathbb{Z}_{v}|\mathbb{Z}_{n}^{\times},\mathsf{E},\mathsf{D})$

where $p$ and $q$ are two primes, $n$ is the product $pq$, and $v$ is a
positive integer dividing $p-1$ such that $(p-1)/v$ and $q-1$ are coprime with
$v$. Let us also denote $\phi=(p-1)(q-1)$. The collection of encryption
algorithms is indexed by the set $\mathbb{Z}_{n}^{\times}$ such that for every
$r\in\mathbb{Z}_{n}^{\times}$ we have an encryption function as follows.

$\mathsf{E}_{r}:\left(\begin{array}[]{ccc}B^{p,q}_{v}\times\mathbb{Z}_{v}&\to&\mathbb{Z}_{n}^{\times}\\\
(g,m)&\mapsto&g^{m}\cdot r^{v}\end{array}\right)$

The decryption algorithm is given by a partial function (see below). We can
use Remark 4.37 and Remark 4.35 to show that this function is well-defined at
pairs $(g,c)$ where $c$ is of the form $\mathsf{E}_{r}(g,m)$ for some elements
$r\in\mathbb{Z}_{n}^{\times}$ and $m\in\mathbb{Z}_{v}$.

$\mathsf{D}:\left(\begin{array}[]{ccc}B^{p,q}_{v}\times\mathbb{Z}_{n}^{\times}&\to&\mathbb{Z}_{v}\\\
(g,c)&\mapsto&\mathsf{log}_{g^{\phi/v}}(c^{\phi/v})\end{array}\right)$

With such functions, we can determine the form of the set $\mathcal{R}(f)$ for
every $f\in B^{p,q}_{v}$, as shown below.

$\displaystyle\mathcal{R}(f)$ $\displaystyle=\\{f^{\prime}~{}|~{}\forall
h\in\mathbf{Set}(B^{p,q}_{v},B^{p,q}_{v}),\,\forall
m\in\mathbb{Z}_{v}\,:\mathsf{log}_{h(f)^{\phi/v}}((h(f^{\prime})^{m}\cdot
r^{v})^{\phi/v})=m\\}$ $\displaystyle(\textrm{Convention
\ref{conv:reversors}})$ $\displaystyle=\\{f^{\prime}~{}|~{}\forall
h\in\mathbf{Set}(B^{p,q}_{v},B^{p,q}_{v}),\,\forall
m\in\mathbb{Z}_{v}:\,h(f^{\prime})^{m\phi/v}r^{\phi}=h(f)^{m\phi/v}\\}$
$\displaystyle(\textrm{Proposition \ref{prop:Benaloh:correctness}})$
$\displaystyle=\\{f^{\prime}~{}|~{}\forall
h\in\mathbf{Set}(B^{p,q}_{v},B^{p,q}_{v}),\,\forall
m\in\mathbb{Z}_{v}:\,h(f^{\prime})^{m\phi/v}=h(f)^{m\phi/v}\\}$
$\displaystyle(\textrm{Remark \ref{rem:Benaloh:Carmichael}})$
$\displaystyle\supseteq\\{f\\}$

The fact that $\mathcal{R}(f)$ is non-empty for all
$f\in\mathbb{Z}_{\lambda(n)}^{\times}$ shows that the Yoneda cryptosystem is
well-defined. Following Generation 4.5, the key generation step undertaken by
$\mathsf{Alice}$ for this cryptosystem consists of

  * -

an identity functor $H:\mathbf{1}\to\mathbf{1}$;

  * -

an initializer $f_{0}$ in $\mathsf{lim}_{\mathbf{1}}(B^{p,q}_{v}\circ
H^{\mathsf{op}})=B^{p,q}_{v}$;

  * -

and a private key $x$ in the singleton $\mathsf{col}_{\mathbf{1}}(Y\circ
H)(\ast)=Y(\ast)(\ast)=\\{\mathsf{id}_{\ast}\\}$.

Here, the private key $x$ is taken to be trivial, primarily due to the fact
that most of the sensitive information to be kept secret resides in the
definition of the decryption algorithm.

The publication step for the Benaloh cryptosystem is described below.

######  Publication 4.39 (Benaloh).

The key publication step for the Benaloh cryptosystem is as follows:
$\mathsf{Alice}$ sends the element $f_{0}$ to $\mathsf{Bob}$.

######  Application 4.40 (Benaloh as Yoneda).

The key publication step for the Yoneda cryptosystem unfolds as follows.
$\mathsf{Alice}$ does the following:

  * -

she computes the element

$f=\phi_{H,B^{p,q}_{v}}^{-1}(f_{0})_{\ast}(x).$

This element corresponds to the image of function $\mathbf{1}\to B^{p,q}_{v}$
picking out the element $f_{0}$. As a result, the element $f$ is equal to the
element $f_{0}$.

  * -

Since $\mathcal{R}(f)\supseteq\\{f\\}$, $\mathsf{Alice}$ can send the pair
$(f_{0},f_{0})$ as a public key to $\mathsf{Bob}$.

As outlined in Publication 4.7, $\mathsf{Alice}$ reveals both the key $f_{0}$
and the theoretical structure of the cryptosystem data, withholding only the
computation details of the parameters intended to remain confidential.

We will now outline the encryption steps. In contrast to other cryptosystems
discussed in previous sections, the associated step for the Yoneda translation
involves selecting a noise parameter (see Encryption 4.9). This noise
parameter is a crucial component in ensuring the security of the Benaloh
cryptosystem.

######  Encryption 4.41 (Benaloh).

The encryption step in the Benaloh cryptosystem goes as follows: First,
$\mathsf{Bob}$ chooses

  * -

a random element $r\in\mathbb{Z}_{n}^{\times}$;

  * -

and a message $m\in\mathbb{Z}_{v}$;

and then sends the ciphertext $c=f_{0}^{m}\cdot
r^{v}\in\mathbb{Z}_{n}^{\times}$ to $\mathsf{Alice}$.

######  Application 4.42 (Benaloh as Yoneda).

The encryption step for the Yoneda cryptosystem unfolds as follows. First,
$\mathsf{Bob}$ selects:

  * -

a noise parameter $r\in\mathbb{Z}_{n}^{\times}$;

  * -

the identity function $B^{p,q}_{v}\to B^{p,q}_{v}$.

  * -

and a message $m\in\mathbb{Z}_{v}$;

Then, $\mathsf{Bob}$ sends the following information to $\mathsf{Alice}$:

  * -

the element $c_{1}=\mathsf{lim}_{\mathbf{1}}(h_{H})(f_{0})=f_{0}$ in
$B^{p,q}_{v}$;

  * -

and the element $c_{2}=\mathsf{E}_{r}(h_{\ast}(f),m)=f_{0}^{m}\cdot r^{v}$ in
$\mathbb{Z}_{n}^{\times}$.

While the pair $(c_{1},c_{2})$ constitutes an encryption for the message $m$,
its first component $c_{1}=f_{0}$ is information already known to
$\mathsf{Alice}$. As noted before, this data can be utilized by $\mathsf{Bob}$
as a certificate, ensuring that $\mathsf{Alice}$ is aware of the cryptosystem
being employed by $\mathsf{Bob}$.

Finally, we address the decryption steps. Initially, this stage exhibited
certain ambiguities, resulting in identical decryptions for distinct messages.
However, these issues were subsequently rectified by Fousse, Lafourcade, and
Alnuaimi, as documented in [12].

######  Decryption 4.43 (Benaloh).

The decryption step for the Benaloh cryptosystem consists in making
$\mathsf{Bob}$ find the smallest integer $m^{\prime}\in\mathbb{Z}_{v}$ for
which the equation
$(f_{0}^{\phi/v})^{m^{\prime}}=c^{\phi/v}\,(\mathsf{mod}\,n)$ holds.

######  Application 4.44 (Benaloh as Yoneda).

The decryption step for the Yoneda cryptosystem unfolds as follows.
$\mathsf{Alice}$ computes:

  * -

the element

$d=\phi_{H,\mathbb{Z}_{\lambda(n)}^{\times}}^{-1}(c_{1})_{\ast}(x).$

This element corresponds to the image of function
$\mathbf{1}\to\mathbb{Z}_{\lambda(n)}^{\times}$ picking out the element
$c_{1}$. As a result, the element $d$ is equal to the element $c_{1}=f_{0}$.;

  * -

and the element
$m^{\prime}=\mathsf{D}(d,c_{2})=\mathsf{log}_{f_{0}^{\phi/v}}(c_{2}^{\phi/v})$
in $\mathbb{Z}_{v}$;

The identity $m^{\prime}=m$ follows from Decryption 4.10.

###  4.5. NTRU encryption

The NTRU cryptosystem, initially developed by Hoffstein, Pipher, and Silverman
in 1998 [17], has undergone several enhancements since its inception.