$\mathrm{CE}_{\mathcal{F}}=\sup_{g\in\mathcal{G}}\bigg{|}\operatorname{\mathbb{E}}_{P_{X}}\bigg{(}\sum_{y\in\mathcal{Y}}\big{(}\operatorname{\mathbb{P}}(Y=y|P_{X})-P_{X}(\\{y\\})\big{)}g_{y}\big{(}P_{X}\big{)}\bigg{)}\bigg{|}=\mathrm{CCE}_{\mathcal{G}}.$

Thus both definitions are equivalent for classification models but the
structure of the employed function classes differs. The definition of
$\mathrm{CCE}$ is based on vector-valued functions on the probability simplex
whereas the formulation presented in this paper uses real-valued function on
the product space of the probability simplex and the targets.

An interesting theoretical aspect of this difference is that in the case of
$\mathrm{KCE}$ we consider real-valued kernels on
$\mathcal{P}\times\mathcal{Y}$ instead of matrix-valued kernels on
$\mathcal{P}$, as shown by the following comparison. By
$e_{i}\in\mathbb{R}^{d}$ we denote the $i$th unit vector, and for a prediction
$p\in\mathcal{P}$ its representation $v_{p}\in\mathbb{R}^{d}$ in the
probability simplex is defined as

${(v_{p})}_{y}=p\big{(}\\{y\\}\big{)}$

for all targets $y\in\mathcal{Y}$.

Let
$k\colon(\mathcal{P}\times\mathcal{Y})\times(\mathcal{P}\times\mathcal{Y})\to\mathbb{R}$.
We define the matrix-valued function
$K\colon\mathcal{P}\times\mathcal{P}\to\mathbb{R}^{d\times d}$ by

$\big{[}K(p,p^{\prime})\big{]}_{y,y^{\prime}}=k\big{(}(p,y),(p^{\prime},y^{\prime})\big{)}$

for all $y,y^{\prime}\in\mathcal{Y}$ and $p,p^{\prime}\in\mathcal{P}$. From
the positive definiteness of kernel $k$ it follows that $K$ is a matrix-valued
kernel (Micchelli & Pontil, 2005, Definition 2). We obtain

$\begin{split}\mathrm{SKCE}_{k}={}&\operatorname{\mathbb{E}}_{P_{X},Y,P_{X^{\prime}},Y^{\prime}}\big{[}K(P_{X},P_{X^{\prime}})\big{]}_{Y,Y^{\prime}}-2\operatorname{\mathbb{E}}_{P_{X},Y,P_{X^{\prime}},Z_{X^{\prime}}}\big{[}K(P_{X},P_{X^{\prime}})\big{]}_{Y,Z_{X^{\prime}}}\\\
&+\operatorname{\mathbb{E}}_{P_{X},Z_{X},P_{X^{\prime}},Z_{X^{\prime}}}\big{[}K(P_{X},P_{X^{\prime}})\big{]}_{Z_{X},Z_{X^{\prime}}}\\\
={}&\operatorname{\mathbb{E}}_{P_{X},Y,P_{X^{\prime}},Y^{\prime}}e_{Y}^{\mathsf{T}}K(P_{X},P_{X^{\prime}})e_{Y^{\prime}}-2\operatorname{\mathbb{E}}_{P_{X},Y,P_{X^{\prime}},Y^{\prime}}e_{Y}^{\mathsf{T}}K(P_{X},P_{X^{\prime}})v_{P_{X^{\prime}}}\\\
&+\operatorname{\mathbb{E}}_{P_{X},Y,P_{X^{\prime}},Y^{\prime}}v_{P_{X}}^{\mathsf{T}}K(P_{X},P_{X^{\prime}})v_{P_{X^{\prime}}}\\\
={}&\operatorname{\mathbb{E}}_{P_{X},Y,P_{X^{\prime}},Y^{\prime}}{(e_{Y}-v_{P_{X}})}^{\mathsf{T}}K(P_{X},P_{X^{\prime}})(e_{Y^{\prime}}-v_{P_{X^{\prime}}}),\end{split}$

which is exactly the result by Widmann et al. (2019) for matrix-valued
kernels.

As a concrete example, Widmann et al. (2019) used a matrix-valued kernel of
the form $(p,p^{\prime})\mapsto\exp{(-\gamma\|p-p^{\prime}\|)}\mathbf{I}_{d}$
in their experiments. In our formulation this corresponds to the real-valued
tensor product kernel
$\big{(}(p,y),(p^{\prime},y^{\prime})\big{)}\mapsto\exp{(-\gamma\|p-p^{\prime}\|)}\delta_{y,y^{\prime}}$.

##  Appendix F Temperature scaling

Since many modern neural network models for classification have been
demonstrated to be uncalibrated (Guo et al., 2017), it is of high practical
interest being able to improve calibration of predictive models. Generally,
one distinguishes between calibration techniques that are applied during
training and post-hoc calibration methods that try to calibrate an existing
model after training.

Temperature scaling (Guo et al., 2017) is a simple calibration method for
classification models with only one scalar parameter. Due to its simplicity it
can trade off calibration of different classes (Kull et al., 2019), but
conveniently it does not change the most-confident prediction and hence does
not affect the accuracy of classification models with respect to the 0-1 loss.

In regression, common post-hoc calibration methods are based on quantile
binning and hence insufficient for our framework. Song et al. (2019) proposed
a calibration method for regression models with real-valued targets, based on
a special case of Definition 1. This calibration method was shown to perform
well empirically but is computationally expensive and requires users to choose
hyperparameters for a Gaussian process model and its variational inference. As
a simpler alternative, we generalize temperature scaling to arbitrary
predictive models in the following way.

###### Definition F.1

Let $P_{x}$ be the output of a probabilistic predictive model $P$ for feature
$x$. If $P_{x}$ has probability density function $p_{x}$ with respect to a
reference measure $\mu$, then temperature scaling with respect to $\mu$ with
temperature $T>0$ yields a new output $Q_{x}$ whose probability density
function $q_{x}$ with respect to $\mu$ satisfies

$q_{x}\propto p_{x}^{1/T}.$

The notion for classification models given by Guo et al. (2017) can be
recovered by choosing the counting measure on the classes as reference
measure.

For some exponential families on $\mathbb{R}^{d}$ we obtain particularly
simple transformations with respect to the Lebesgue measure $\lambda^{d}$ that
keep the type of predicted distribution and its mean invariant. Hence in
contrast to other calibration methods, for these models temperature scaling
yields analytically tractable distributions and does not negatively impact the
accuracy of the models with respect to the mean squared error and the mean
absolute error.

For instance, temperature scaling of multivariate power exponential
distributions (Gómez et al., 1998) in $\mathbb{R}^{d}$, of which multivariate
normal distributions are a special case, with respect to $\lambda^{d}$
corresponds to multiplication of their scale parameter with $T^{1/\beta}$,
where $\beta$ is the so-called kurtosis parameter (Gómez-Sánchez-Manzano et
al., 2008). For normal distributions, this corresponds to multiplication of
the covariance matrix with $T$.

Similarly, temperature scaling of Beta and Dirichlet distributions with
respect to reference measure

$\mu(\mathrm{d}x)\coloneqq
x^{-1}(1-x)^{-1}\mathbbm{1}_{(0,1)}(x)\lambda^{1}(\mathrm{d}x)$

and

$\mu(\mathrm{d}x)\coloneqq\bigg{(}\prod_{i=1}^{d}x_{i}^{-1}\bigg{)}\mathbbm{1}_{(0,1)^{d}}(x)\lambda^{d}(\mathrm{d}x),$

respectively, corresponds to division of the canonical parameters of these
distributions by $T$ without affecting the predicted mean value.

All in all, we see that temperature scaling for general predictive models
preserves some of the nice properties for classification models. For some
exponential families such as normal distributions reference measure $\mu$ can
be chosen such that temperature scaling is a simple transformation of the
parameters of the predicted distributions (and hence leaves the considered
model class invariant) that does not affect accuracy of these models with
respect to the mean squared error and the mean absolute error.

##  Appendix G Expected calibration error for countably infinite discrete
target spaces

In literature, $\mathrm{ECE}_{d}$ and $\mathrm{MCE}_{d}$ are defined for
binary and multi-class classification problems (Vaicenavicius et al., 2019;
Guo et al., 2017; Naeini et al., 2015). For common distance measures on the
probability simplex such as the total variation distance and the squared
Euclidean distance, $\mathrm{ECE}_{d}$ and $\mathrm{MCE}_{d}$ can be
formulated as a calibration error in the framework of Widmann et al. (2019),
which is a special case of the framework proposed in this paper for binary and
multi-class classification problems.

In contrast to previous approaches, our framework handles countably infinite
discrete target spaces as well. For every problem with countably infinitely
many targets, such as, e.g., Poisson regression, there exists an equivalent
regression problem on the set of natural numbers. Hence without loss of
generality we assume $\mathcal{Y}=\mathbb{N}$. Denote the space of probability
distributions on $\mathbb{N}$, the infinite dimensional probability simplex,
with $\Delta^{\infty}$. Clearly, $\Delta^{\infty}$ can be viewed as a subspace
of the sequence space $\ell^{1}$ that consists of all sequences
$x=(x_{n})_{n\in\mathbb{N}}$ with $x_{n}\geq 0$ for all $n\in\mathbb{N}$ and
$\|x\|_{1}=1$.

######  Theorem G.1.

Let $1<p<\infty$ with Hölder conjugate $q$. If

$\mathcal{F}\coloneqq\\{f\colon\Delta^{\infty}\times\mathbb{N}\to\mathbb{R}\mid\operatorname{\mathbb{E}}_{P_{X}}\|\big{(}f(P_{X},n)\big{)}_{n\in\mathbb{N}}\|_{p}^{p}\leq
1\\},$

then

$\mathrm{CE}^{q}_{\mathcal{F}}=\operatorname{\mathbb{E}}_{P_{X}}\|\operatorname{\mathbb{P}}(Y|P_{X})-P_{X}\|_{q}^{q}.$

Let $\mu$ be the law of $P_{X}$. If
$\mathcal{F}\coloneqq\\{f\colon\Delta^{\infty}\times\mathbb{N}\to\mathbb{R}\mid\operatorname{\mathbb{E}}_{P_{X}}\|(f(P_{X},n))_{n\in\mathbb{N}}\|_{1}\leq
1\\}$, then

$\mathrm{CE}_{\mathcal{F}}=\mu\text{-}\operatorname*{ess\,sup}_{\xi\in\Delta^{\infty}}\sup_{y\in\mathbb{N}}|\operatorname{\mathbb{P}}(Y=y|P_{X}=\xi)-\xi(\\{y\\})|.$

Moreover, if
$\mathcal{F}=\\{f\colon\Delta^{\infty}\times\mathbb{N}\to\mathbb{R}\mid\mu\text{-}\operatorname*{ess\,sup}_{\xi\in\Delta^{\infty}}\sup_{y\in\mathbb{N}}|f(\xi,y)|\leq
1\\}$, then

$\mathrm{CE}_{\mathcal{F}}=\operatorname{\mathbb{E}}_{P_{X}}\|\operatorname{\mathbb{P}}(Y|P_{X})-P_{X}\|_{1}.$

###### Proof.

Let $1\leq p\leq\infty$, and let $\mu$ be the law of $P_{X}$ and $\nu$ be the
counting measure on $\mathbb{N}$. Since both $\mu$ and $\nu$ are
$\sigma$-finite measures, the product measure $\mu\otimes\nu$ is uniquely
determined and $\sigma$-finite as well. Using these definitions, we can
reformulate $\mathcal{F}$ as

$\mathcal{F}=\\{f\in
L^{p}(\Delta^{\infty}\times\mathbb{N};\mu\otimes\nu)\mid\|f\|_{p;\mu\otimes\nu}\leq
1\\}.$

Define the function $\delta\colon\Delta^{\infty}\times\mathbb{N}\to\mathbb{R}$
$(\mu\otimes\nu)$-almost surely by

$\delta(\xi,y)\coloneqq\operatorname{\mathbb{P}}(Y=y\,|\,P_{X}=\xi)-\xi(\\{y\\}).$

Note that $\delta$ is well-defined since we assume that all singletons on
$\Delta^{\infty}$ are $\mu$-measurable. Moreover, $\delta\in
L^{q}(\Delta^{\infty}\times\mathbb{N};\mu\otimes\nu)$, which follows from
$(\xi,y)\mapsto\operatorname{\mathbb{P}}(Y=y\,|\,P_{X}=\xi)$ and
$(\xi,y)\mapsto\xi(\\{y\\})$ being functions in
$L^{q}(\Delta^{\infty}\times\mathbb{N};\mu\otimes\nu)$.

Since $\mu\otimes\nu$ is a $\sigma$-finite measure, the extremal equality of
Hölder’s inequality implies that

$\begin{split}\mathrm{CE}_{\mathcal{F}}&=\sup_{f\in\mathcal{F}}\operatorname{\mathbb{E}}_{P_{X},Y}f(P_{X},Y)-\operatorname{\mathbb{E}}_{P_{X},Z_{X}}f(P_{X},Z_{X})\\\
&=\sup_{f\in\mathcal{F}}\bigg{|}\operatorname{\mathbb{E}}_{P_{X},Y}f(P_{X},Y)-\operatorname{\mathbb{E}}_{P_{X},Z_{X}}f(P_{X},Z_{X})\bigg{|}\\\
&=\sup_{f\in\mathcal{F}}\bigg{|}\int_{\Delta^{\infty}\times\mathbb{N}}f(\xi,y)\delta(\xi,y)\,(\mu\otimes\nu)(\mathrm{d}(\xi,y))\bigg{|}\\\
&=\|\delta\|_{q;\mu\otimes\nu}.\end{split}$

Note that the second equality follows from the symmetry of the function spaces
$\mathcal{F}$: for every $f\in\mathcal{F}$, also $-f\in\mathcal{F}$.

Hence for $1<p\leq\infty$, we obtain

$\begin{split}\mathrm{CE}_{\mathcal{F}}^{q}&=\int_{\Delta^{\infty}\times\mathbb{N}}|\delta(\xi,y)|^{q}\,(\mu\otimes\nu)(\mathrm{d}(\xi,y))\\\
&=\operatorname{\mathbb{E}}_{P_{X}}\|(\delta(P_{X},y))_{y\in\mathbb{N}}\|_{q}^{q}=\operatorname{\mathbb{E}}_{P_{X}}\|\operatorname{\mathbb{P}}(Y|P_{X})-P_{X}\|_{q}^{q}.\end{split}$

For $p=1$, we get

$\begin{split}\mathrm{CE}_{\mathcal{F}}=\mu\text{-}\operatorname*{ess\,sup}_{\xi\in\Delta^{\infty}}\sup_{y\in\mathbb{N}}|\delta(\xi,y)|=\mu\text{-}\operatorname*{ess\,sup}_{\xi\in\Delta^{\infty}}\sup_{y\in\mathbb{N}}|\operatorname{\mathbb{P}}(Y=y|P_{X}=\xi)-\xi(\\{y\\})|,\end{split}$

which concludes the proof. ∎

We see that our framework deals with countably infinite discrete target spaces
seamlessly whereas the previously proposed framework by Widmann et al. (2019)
is not applicable to such spaces. It is mathematically pleasing to see that
for countably infinite discrete targets the calibration errors obtained in
Theorem G.1 within our framework coincide with the natural generalization of
$\mathrm{ECE}_{d}$ and $\mathrm{MCE}_{d}$ given in Section B.2.


Subsequent research, such as works by Steinfeld and Stehlé [25] and López-Alt
_et al._ [20], has contributed to enhancing the security and efficiency of
NTRU, resulting into what is now called the NTRUEncrypt system. In this
section, we illustrate how this framework translates into the structure
derived from the Yoneda Lemma.

######  Convention 4.45 (Polynomials).

Given a polynomial $p(X)$ in $R[X]$, we use the notation $R[X]/p(X)$ to
represent the ring of polynomial representatives in $R[X]$ modulo $p(X)$. In
simpler terms, the set $R[X]/p(X)$ consists of polynomials $f(X)$ with degrees
less than or equal to $p(X)$. The operations defined for this ring involve the
addition and multiplication of polynomials, followed by the computation of
their remainder for the Euclidean division by the polynomial $p(X)$.

######  Convention 4.46 (Notations).

For every ring $R$ with unit $\mathbb{1}$ (Definition 3.32) and every positive
integer $N$, we will denote the quotient ring $R[X]/(X^{N}-\mathbb{1})$ of
$R[X]$ by the polynomial $X^{N}-\mathbb{1}$ as $R[X]_{N}$.

######  Convention 4.47 (Inverses).

Let $p$ be a prime number and $N$ be a positive integer. We denote as
$I_{p}^{N}$ the set of polynomials $g$ in $\mathbb{Z}[X]$ such that the
mapping of $g$ to the ring $\mathbb{Z}_{p}[X]_{N}$ has an inverse for the
multiplication, namely there exists a (unique) polynomial $g^{\prime}$ in
$\mathbb{Z}_{p}[X]_{N}$ for which the relation $g^{\prime}\cdot g=1$ holds in
$\mathbb{Z}_{p}[X]_{N}$. For every $g\in I_{p}^{N}$, we will denote as
$\mathsf{inv}_{p}(g)$ the multiplicative inverse of $g$ in
$\mathbb{Z}_{p}[X]_{N}$.

######  Definition 4.48 (Keys).

For every positive integer $N$ and every pair $(p,q)$ of prime numbers, we
denote by $Q_{p,q}^{N}$ the set of pairs $(g_{0},g_{1})$ where $g_{0}$ and
$g_{1}$ are two polynomials in $\mathbb{Z}_{3}[X]_{N}$ such that

  * 1)

the polynomial $g_{0}$ is in $I_{p}^{N}$ and $I_{q}^{N}$,

  * 2)

and for every pair $(r,m)$ of elements in $\mathbb{Z}_{3}[X]_{N}$, the
polynomial expression

$g_{1}(X)\cdot r(X)\cdot p+g_{0}(X)\cdot m(X)$

computed in $\mathbb{Z}[X]_{N}$ has all its coefficients within the interval
$[-q/2,q/2]$.

######  Remark 4.49 (Correctness).

We will see that the NTRU cryptosystem relies on the computation of an
expression of the following form for some pair $(g_{0},g_{1})\in Q_{p,q}^{N}$.

$g_{0}\cdot(\mathsf{inv}_{q}(g_{0})\cdot g_{1}\cdot r\cdot p+m)$

According to Definition 4.48, this expression provides a polynomial whose
representative in $\mathbb{Z}_{q}[X]_{N}$ is given by the polynomial
$g_{1}rp+g_{0}m$ computed in $\mathbb{Z}[X]_{N}$.

######  Generation 4.50 (NTRUEncrypt).

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

  * -

a positive integer $N$;

  * -

two prime numbers $p$ and $q$;

  * -

a pair $(g_{0},g_{1})\in Q_{p,q}^{N}$.

The previous selection will later allow $\mathsf{Alice}$ to construct a
product of the form $\mathsf{inv}_{q}(g_{0})\cdot g_{1}\cdot p$, which she
will use as a public key.

######  Application 4.51 (NTRUEncrypt as Yoneda).

Let us describe the overall setup for the Yoneda cryptosystem encoding the
NTRUEncrypt systen. 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 NTRUEncrypt
scheme is then defined as a Yoneda encryption scheme of the form

$\mathcal{Y}(\mathbb{Z}_{q}[X]_{N},\mathbb{Z}_{q}[X]_{N},\mathbb{Z}_{p}[X]_{N},\mathbb{Z}_{q}[X]_{N}|\mathbb{Z}_{3}[X]_{N},\mathsf{E},\mathsf{D})$

where $p$ and $q$ are two primes. The collection of encryption algorithms is
indexed by the set $\mathbb{Z}_{3}[X]_{N}$ such that for every polynomial
$r\in\mathbb{Z}_{3}[X]_{N}$ we have an encryption function as follows.

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

The decryption algorithm is given by the following function, which is defined
for a fixed pair $(g_{0},g_{1})\in Q_{p,q}^{N}$. The modulo operation by $q$
used in the decryption below is assumed to output the only representative in
$\mathbb{Z}_{q}[X]_{N}$ whose coefficients are in the interval $[-q/2,q/2]$.

$\mathsf{D}:\left(\begin{array}[]{ccc}\mathbb{Z}_{q}[X]_{N}\times\mathbb{Z}_{q}[X]_{N}&\to&\mathbb{Z}_{p}[X]_{N}\\\
(g,c)&\mapsto&\mathsf{inv}_{p}(g_{0})\cdot\Big{(}g_{0}\cdot
c\,(\mathsf{mod}\,q)\Big{)}\end{array}\right)$

With such functions, we can determine the form of the set $\mathcal{R}(f)$ for
every element $f\in\mathbb{Z}_{q}[X]_{N}$, as shown below.

$\displaystyle\mathcal{R}(f)$
$\displaystyle=\left\\{f^{\prime}~{}\left|~{}\begin{array}[]{l}\forall
h\in\mathbf{Set}(\mathbb{Z}_{q}[X]_{N},\mathbb{Z}_{q}[X]_{N}),\,\forall
m\in\mathbb{Z}_{p}[X]_{N}\,:\\\
\mathsf{inv}_{p}(g_{0})\Big{(}g_{0}(h(f^{\prime})r+m)\,(\mathsf{mod}\,q)\Big{)}=m\end{array}\right.\right\\}$
$\displaystyle(\textrm{Convention \ref{conv:reversors}})$
$\displaystyle=\left\\{f^{\prime}~{}\left|~{}\begin{array}[]{l}\forall
h\in\mathbf{Set}(\mathbb{Z}_{q}[X]_{N},\mathbb{Z}_{q}[X]_{N}),\,\forall
m\in\mathbb{Z}_{p}[X]_{N},\,\exists k\in\mathbb{Z}[X]\,:\\\
g_{0}(h(f^{\prime})r+m)-kq\textrm{ with coefficients in }[-q/2,q/2]\\\
\textrm{and }m-\mathsf{inv}_{p}(g_{0})kq=m\textrm{ in
}\mathbb{Z}_{p}[X]_{N}\end{array}\right.\right\\}$
$\displaystyle=\left\\{h(f^{\prime})~{}\left|~{}\begin{array}[]{l}\forall
h\in\mathbf{Set}(\mathbb{Z}_{q}[X]_{N},\mathbb{Z}_{q}[X]_{N}),\,\forall
m\in\mathbb{Z}_{p}[X]_{N},\,\exists k\in\mathbb{Z}[X]\,:\\\
f_{0}h(f^{\prime})r+f_{0}m-kq\textrm{ with coefficients in }[-q/2,q/2]\\\
\textrm{and }kq=0\textrm{ in
}\mathbb{Z}_{p}[X]_{N}\end{array}\right.\right\\}$
$\displaystyle\supseteq\\{\mathsf{inv}_{q}(g_{0})\cdot g_{1}\cdot p\textrm{
computed in }\mathbb{Z}_{q}[X]_{N}\\}$ $\displaystyle(\textrm{Definition
}\ref{def:NTRU:Q})$

The fact that $\mathcal{R}(f)$ is non-empty for all
$f\in\mathbb{Z}_{q}[X]_{N}$ 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}_{q}[X]_{N}\circ
H^{\mathsf{op}})=\mathbb{Z}_{q}[X]_{N}$;

  * -

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. Also note that the initializer always
satsifies the inclusion
$\mathcal{R}(f_{0})\supseteq\\{\mathsf{inv}_{q}(g_{0})\cdot g_{1}\cdot p\\}$
where $(g_{0},g_{1})\in Q_{p,q}^{N}$ was fixed when defining the decryption
algorithm above.

Let us now describe the publication steps. Interestingly, the NTRU
cryptosystem is the first cryptosystem presented so far whose associated
reversors do not seem to depend on the initializer. This feature is probably
one of the main characteristics of NTRUEncrypt compared to other HE schemes.

######  Publication 4.52 (NTRUEncrypt).

The key publication step for the NTRU cryptosystem is as follows:
$\mathsf{Alice}$ sends the compute the polynomial
$f^{\prime}=\mathsf{inv}_{q}(g_{0})\cdot g_{1}\cdot p$ in
$\mathbb{Z}_{q}[X]_{N}$ and send it to $\mathsf{Bob}$.

######  Application 4.53 (NTRUEncrypt 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}_{q}[X]_{N}}^{-1}(f_{0})_{\ast}(x).$

This element corresponds to the image of function
$\mathbf{1}\to\mathbb{Z}_{q}[X]_{N}$ picking out the element $f_{0}$. As a
result, the element $f$ is equal to the element $f_{0}$.

  * -

Since $\mathcal{R}(f)\supseteq\\{\mathsf{inv}_{q}(g_{0})\cdot g_{1}\cdot
p\\}$, $\mathsf{Alice}$ can take $f^{\prime}=\mathsf{inv}_{q}(g_{0})\cdot
g_{1}\cdot p$ and send the pair $(f_{0},f^{\prime})$ as a public key to
$\mathsf{Bob}$.

Note that the element $f_{0}$ sent by $\mathsf{Alice}$ has no influence on the
encryption-decryption protocole and should just be seen as a formal
certificate, which will later be resent by $\mathsf{Bob}$ as a confirmation to
$\mathsf{Alice}$.

We now verify that the NTRU cryptosystem and its Yoneda translation have
corresponding encryption protocols. As mentioned above, the Yoneda formalism
adds a formal certificate that can be used between $\mathsf{Alice}$ and a
sending party to agree on a parameters to use for the communication.

######  Encryption 4.54 (NTRUEncrypt).

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

  * -

a random element $r\in\mathbb{Z}_{3}[X]_{N}$;

  * -

and a message $m\in\mathbb{Z}_{p}[X]_{N}$;

and then sends the ciphertext $c=f^{\prime}\cdot r+m$, computed in
$\mathbb{Z}_{q}[X]_{N}$, to $\mathsf{Alice}$.

######  Application 4.55 (NTRUEncrypt as Yoneda).

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

  * -

a noise parameter $r\in\mathbb{Z}_{3}[X]_{N}$;

  * -

the identity function $h:\mathbb{Z}_{q}[X]_{N}\to\mathbb{Z}_{q}[X]_{N}$.

  * -

and a message $m\in\mathbb{Z}_{p}[X]_{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}_{q}[X]_{N}$;

  * -

and the element $c_{2}=\mathsf{E}_{r}(h_{\ast}(f^{\prime}),m)=f^{\prime}\cdot
r+m$ in $\mathbb{Z}_{q}[X]_{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}$. 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}$.

Now, we proceed to outline the decryption step for the NTRU cryptosystem. A
vital prerequisite for the success of this step is to guarantee the non-
emptiness of the set $Q_{p,q}^{N}$ introduced in Definition 4.48. This
condition relies on the careful selection of parameters $p$, $q$, and $N$.

######  Decryption 4.56 (NTRUEncrypt).

The decryption step for the NTRU cryptosystem requires $\mathsf{Bob}$ to:

  * -

compute the representative $m_{0}$ of $g_{0}\cdot c$ in
$\mathbb{Z}_{q}[X]_{N}$ that has all its coefficients in $[-q/2,q/2]$ ;

  * -

and then to compute the element $m^{\prime}=\mathsf{inv}_{p}(g_{0})\cdot
m_{0}$ in $\mathbb{Z}_{p}[X]_{N}$.

It follows from Definition 4.48 and the fact that $(g_{0},g_{1})\in
Q_{p.q}^{N}$ that the element $m^{\prime}$ is equal to the message $m$ in
$\mathbb{Z}_{p}[X]_{N}$.

######  Application 4.57 (NTRUEncrypt as Yoneda).

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

  * -

the element

$d=\phi_{H,\mathbb{Z}_{q}[X]_{N}}^{-1}(c_{1})_{\ast}(x).$

This element corresponds to the image of function
$\mathbf{1}\to\mathbb{Z}_{q}[X]_{N}$ 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{inv}_{p}(g_{0})\Big{(}g_{0}(f^{\prime}r+m)\,(\mathsf{mod}\,q)\Big{)}$
in $\mathbb{Z}_{p}[X]_{N}$;

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

###  4.6. LWE-based cryptosystems

Learning with Error (LWE) serves as the fundamental basis for most, if not
all, post-quantum cryptography and stands as the cornerstone for fully
homomorphic encryption schemes. The inherent complexity of LWE is grounded in
the difficulty of lattice-based problems. Oded Regev introduced the LWE
problem in 2009, presenting a cryptosystem reliant on the problem’s hardness
on the torus [24]. Regev’s cryptosystem has since sparked inspiration for a
diverse array of similar encryption schemes [5]. Since its inception, the LWE
problem has undergone various formulations, particularly expanding to rings of
polynomials, leading to the RLWE problem [26, 21, 4, 11, 7, 28, 6]. The
general version of LWE is articulated below, utilizing some terminology
introduced in Convention 4.45.

######  Convention 4.58 (Quotient rings as modules).

For every ring $R$ and every polynomial $u$ in $R$, we will denote the
quotient ring $R[X]/u(X)$ as $R[X]_{u}$. Unless specified otherwise, a ring of
the form $R[X]_{u}$ will be seen as a $\mathbb{Z}[X]$-module whose action
$\mathbb{Z}[X]\times R[X]_{u}\to R[X]_{u}$ is given by the multiplication of
polynomials up to the canonical morphism $\mathbb{Z}[X]\hookrightarrow R[X]\to
R[X]_{u}$.

In this section, we use the notation introduced in Convention 3.36.

######  Definition 4.59 (GLWE).

Consider four positive integers $p$, $q$, $n$, $N$. For a given polynomial
$u(X)$ in $\mathbb{Z}[X]$, the _General LWE problem_ entails finding
$\mathbf{s}\in\mathbb{Z}_{q}[X]_{u}^{(n)}$ given the following data:

  * 1)

a polynomial $m\in\mathbb{Z}_{p}[X]_{u}$;

  * 2)

for every $i\in[N]$, a vector $\mathbf{a}_{i}\in\mathbb{Z}_{q}[X]_{u}^{(n)}$;

  * 3)

for every $i\in[N]$, a vector $b_{i}\in\mathbb{Z}_{q}[X]_{u}$ such that

$b_{i}=\langle\mathbf{a}_{i},\mathbf{s}\rangle+e_{i}$

where $e_{i}$ is chosen in $\mathbb{Z}_{q}[X]_{u}$ according to some
distribution $\chi$, and $\langle\mathbf{a}_{i},\mathbf{s}\rangle$ denotes the
scalar product in $\mathbb{Z}_{q}[X]_{u}^{(n)}$, namely the sum
$\sum_{j=1}^{n}a_{i,j}s_{j}$ where $\mathbf{a}_{i}=(a_{i,1},\dots,a_{i,n})$
and $\mathbf{s}=(s_{1},\dots,s_{n})$.

For additional details on the definition of $\chi$, refer to [24] and other
cited references such as [26, 4].

The Yoneda encryption scheme takes on two forms within FWE-based systems. If
the cryptosystem discloses the data $\mathbf{a}_{i}$ used in the statement of
LWE for its public key, the associated limit sketch $T$ under the Yoneda
translation is non-trivial. On the other hand, if this data is not disclosed,
the limit sketch is forced to be a terminal category. For instance,
cryptosystems outlined in [24, 4, 11, 6] are instances of Yoneda encryption
schemes with non-terminal limit sketches. In contrast, those elucidated in [5,
7] are described by Yoneda encryption schemes featuring terminal limit
sketches.

In this section, we exclusively explore schemes with non-terminal limit
sketches. Readers can apply the insights developed throughout this article to
understand other cryptosystems with terminal limit sketches [5, 7, 1]. Below,
we offer a synthesis of the cryptosystems presented in [24, 4, 11, 6],
consolidating them into a single Yoneda encryption scheme. It is important to
note that our approach aims to provide a comprehensive overview of the various
features of the cryptosystems discussed in those works. However, a more
specific refinement of the Yoneda framework may be necessary for a thorough
recovery of the individual cryptosystems detailed therein.

We will now provide a broad overview of LWE-based cryptosystems and their
transformation into Yoneda cryptosystems. Our focus will be on prominent
schemes, including BGV, FV, and CKKS [4, 11, 6], alongside the original
cryptosystem introduced by Regev in [24].

######  Generation 4.60 (LWE-based).

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

  * -

four positive integers $p$, $q$, $n$, $N$;

  * -

a polynomial $u(X)$ in $\mathbb{Z}[X]$;

  * -

a vector $\mathbf{s}=(s_{1},\dots,s_{n})\in\mathbb{Z}_{q}[X]_{u}^{(n)}$;

######  Convention 4.61.

For every real number, we will denote as:

  * -

$\lfloor x\rfloor$ the greatest integer less than or equal to $x$;

  * -

$\lceil x\rceil$ the smallest integer greater than or equal to $x$;

  * -

$\lfloor x\rceil$ the integer that is the closest to $x$;

######  Application 4.62 (LWE-based as Yoneda).

Let us describe the overall setup for the Yoneda cryptosystem encoding the
LWE-based cryptosystems described in [24, 4, 11, 6]. First, the associated
limit sketch $T$ must be the limit sketch $T_{\mathbb{Z}[X]}$ defined for
modules over the ring $\mathbb{Z}[X]$ (Convention 3.37). As a result, the
associated reflective subcategory is given by the inclusion

$\mathbf{Mod}(T_{\mathbb{Z}[X]})\hookrightarrow[T_{\mathbb{Z}[X]},\mathbf{Set}]$

and its left adjoint $L$. The Yoneda cryptosystems will all be defined at the
object $1$ of $T_{\mathbb{Z}[X]}$ (see Convention 3.37). Specifically, the
LWE-based cryptosystems that we investigate here are all expressed as Yoneda
cryptosystems of the form

$\mathcal{Y}(\mathbb{Z}_{q}[X]_{u}^{(N)},\mathbb{Z}_{q}[X]_{u},\mathbb{Z}_{p}[X]_{u},\mathbb{Z}_{q}[X]_{u}|\mathbb{Z}_{q}[X]_{u},\mathsf{E},\mathsf{D})$

where $u$ is some polynomial in $\mathbb{Z}[X]$ and where $p$, $q$ and $N$ are
positive integers. It is straightforward to see that the objects
$\mathbb{Z}_{q}[X]_{u}^{(N)}$ and $\mathbb{Z}_{q}[X]_{u}$ define
$\mathbb{Z}[X]$-module for the obvious multiplication of polynomials (see
Convention 4.58).

The collection of encryption algorithms is indexed by the set
$\mathbb{Z}_{q}[X]_{u}$ such that for every polynomial
$r\in\mathbb{Z}_{q}[X]_{u}$ we have an encryption function of the following
form, where $\delta_{0}$ and $\delta_{1}$ are some integers known to all
parties.

$\mathsf{E}_{r}:\left(\begin{array}[]{ccc}\mathbb{Z}_{q}[X]_{u}\times\mathbb{Z}_{p}[X]_{u}&\to&\mathbb{Z}_{q}[X]_{u}\\\
(g,m)&\mapsto&\delta_{0}\cdot m+\delta_{1}\cdot r+g\end{array}\right)$

The decryption algorithm can vary slightly across different cryptosystems, yet
it consistently takes the form shown below. Specifically, the decryption
function incorporates a comparison operation $\mathsf{C}$ that gauges the
relationship between its input and some given reference. The general form of
$\mathsf{D}$ is as follows.

$\mathsf{D}:\left(\begin{array}[]{ccc}\mathbb{Z}_{q}[X]_{u}\times\mathbb{Z}_{q}[X]_{u}&\to&\mathbb{Z}_{p}[X]_{u}\\\
(g,c)&\mapsto&\mathsf{C}(c-g)\end{array}\right)$

For example:

  * 1)

In Regev’s cryptosystem [24], with $\delta_{0}=1$, $\delta_{1}=0$ and
$u(X)=X-1$ such that $\mathbb{Z}_{q}[X]_{u}\cong\mathbb{Z}_{q}$, the function
$\mathsf{C}:\mathbb{Z}_{q}\to\mathbb{Z}_{p}$ returns $0$ if its input is
closer to $0$ than to $\lfloor p/2\rfloor$, and $1$ otherwise.

  * 2)

In the BGV cryptosystem [4], with $\delta_{0}=1$ and $\delta_{1}=p$, the
function $\mathsf{C}:\mathbb{Z}_{q}[X]_{u}\to\mathbb{Z}_{p}[X]_{u}$ is defined
by the mapping $t\mapsto t\,(\mathsf{mod}\,p)$.

  * 3)

In the FV cryptosystem [11], with $\delta_{0}=\lfloor q/p\rfloor$ and
$\delta_{1}=1$, the function
$\mathsf{C}:\mathbb{Z}_{q}[X]_{u}\to\mathbb{Z}_{p}[X]_{u}$ is defined by the
mapping
$t\mapsto\lfloor\big{(}(pt\,(\mathsf{mod}\,q)\big{)}/q\rceil\,(\mathsf{mod}\,p)$.

  * 4)

In the CKKS cryptosystem [6], with $\delta_{0}=1$ and $\delta_{1}=1$, the
function $\mathsf{C}:\mathbb{Z}_{q}[X]_{u}\to\mathbb{Z}_{p}[X]_{u}$ is defined
by the mapping $t\mapsto t\,(\mathsf{mod}\,p)$.

With such functions, we can determine the form of the set $\mathcal{R}(f)$
(Convention 4.4) for every $f\in\mathbb{Z}_{q}[X]_{u}^{(N)}$, as shown below.

$\mathcal{R}(f)=\\{f^{\prime}~{}|~{}\forall
h\in\mathcal{L}(\mathbb{Z}_{q}[X]_{u}^{(N)},\mathbb{Z}_{q}[X]_{u}),\,\forall
m\in\mathbb{Z}_{p}[X]_{u}:\,\mathsf{C}(\delta_{0}\cdot m+\delta_{1}\cdot
r+h(f^{\prime})-h(f))=m\\}$

For the sake of simplicity, we will assume that the set $\mathcal{R}(f)$ is
non-empty for all $f\in\mathbb{Z}_{q}[X]_{u}$. Following Generation 4.5, the
key generation step undertaken by $\mathsf{Alice}$ for LWE-based cryptosystem
consists of

  * -

a non-empty discrete category $I=[n]$ containing $n$ objects (and their
identities) and a functor

$H:\left(\begin{array}[]{lll}I&\to&T_{\mathbb{Z}[X]}^{\mathsf{op}}\\\
k&\mapsto&1\end{array}\right)$

picking out the object $1$ in the limit sketch $T_{\mathbb{Z}[X]}$;

  * -

an initializer $f_{0}$ taken in the following set:

$\mathsf{lim}_{I^{\mathsf{op}}}(\mathbb{Z}_{q}[X]_{u}^{(N)}\circ
H^{\mathsf{op}})=\mathbb{Z}_{q}[X]_{u}^{(N\times n)}$

  * -

and a private key $x$ taken in the following $\mathbb{Z}[X]$-module:

$\mathsf{col}_{I}(L\circ Y\circ H)(1)=\Big{(}\coprod^{n}Y(1)\Big{)}(1)\cong
Y(n)(1)\cong\mathbb{Z}[X]^{(n)}$

Later, we will use the notations $f_{0}=(f_{0,i,j})_{i,j}$ and $x=(x_{j})_{j}$
to refer to the components of the elements $f_{0}$ and $x$ in
$\mathbb{Z}_{q}[X]_{u}$ and $\mathbb{Z}[X]$, respectively. For convenience, we
will also denote $f_{0,i}:=(f_{0,i,j})_{i,j}$ foir every fixed index
$i\in[N]$.

The publication steps outlined below involve a parameter $\delta_{1}$, as
described in Application 4.62. In general, we can assume that $\delta_{1}$ is
a carefully chosen integer that can be eliminated during the decryption
process.

######  Publication 4.63 (LWE-based).

The key publication step for LWE-based cryptosystems is defined as follows.
$\mathsf{Alice}$ does the following:

  * -

she chooses $N$ random polynomials $\mathbf{a}_{1},\dots,\mathbf{a}_{N}$ in
$\mathbb{Z}_{q}[X]_{u}^{(n)}$;

  * -

she chooses $N$ polynomials $e_{1},\dots,e_{N}$ in $\mathbb{Z}_{q}[X]_{u}$
according to some distribution $\chi$;

  * -

and she sends the following tuple to $\mathsf{Bob}$:

$\Big{(}(\mathbf{a}_{k})_{k\in[N]},(\langle\mathbf{a}_{k},\mathbf{s}\rangle+\delta_{1}\cdot
e_{k})_{k\in[N]}\Big{)}$

From now on, we will use the notations $\mathbf{a}_{k}=(a_{k,j})_{j}$ to refer
to the components $a_{k,j}$ of the element $\mathbf{a}_{k}$ in
$\mathbb{Z}_{q}[X]_{u}$ for every $k\in[N]$.

######  Application 4.64 (LWE-based 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}_{q}[X]_{u}^{(N)}}^{-1}(f_{0})_{1}(x)$

This element corresponds to the image of the element $x\in\mathbb{Z}[X]^{(n)}$
via the morphism

$\phi_{H,\mathbb{Z}_{q}[X]_{u}^{(N)}}^{-1}(f_{0}):\mathbb{Z}[X]^{(n)}\to\mathbb{Z}_{q}[X]_{u}^{(N)}$

that sends every element $y$ in $\mathbb{Z}[X]^{(n)}$ to the matrix product of
$f_{0}$ with $y$. As a result, the element $f$ is equal to the matrix product
$f_{0}x$.

  * -

Since Regev’s cryptosystem as well FV, CKKS and BGV are designed such that we
have inclusions of the form

$\mathcal{R}(f)\supseteq\\{f+\delta_{1}\cdot e\\}$

for some well-chosen vectors $e\in\mathbb{Z}_{q}[X]_{u}^{(N)}$,
$\mathsf{Alice}$ can send a pair of the form $(f_{0},f+\delta_{1}\cdot e)$ to
$\mathsf{Bob}$;

For convenience, we will denote the pair sent by $\mathsf{Alice}$ to
$\mathsf{Bob}$ as a tuple $(f,f^{\prime})$.

An interesting characteristic of LWE-based cryptosystems is the presence of
encryption token morphisms (refer to Definition 4.9) with distinct sources and
domains. In practical terms, this translates to the encryption algorithm
concealing information through matrix products. The encryption step described
below also introduces a parameter $\delta_{0}$ in the encryption process. This
parameter follows the same requirements as those described in Application
4.62.

######  Encryption 4.65 (LWE-based).

The encryption step for LWE-based cryptosystems goes defined as follows.
First, $\mathsf{Bob}$ selects

  * -

an element $r$ in $\mathbb{Z}_{q}[X]_{u}$;

  * -

an element $\mathbf{b}=(b_{1},\dots,b_{N})$ in $\mathbb{Z}_{q}[X]_{u}^{(N)}$;

  * -

an element $m$ in $\mathbb{Z}_{p}[X]_{u}$

and then sends the following information to $\mathsf{Alice}$:

  * -

the element $c_{1}=\sum_{k=1}^{N}b_{k}\cdot\mathbf{a}_{k}$ in
$\mathbb{Z}_{q}[X]_{u}^{(n)}$;

  * -

the element $c_{2}=\delta_{0}\cdot m+\delta_{1}\cdot
r+\sum_{k=1}^{N}b_{k}\cdot(\langle\mathbf{a}_{k},\mathbf{s}\rangle+\delta_{1}\cdot
e_{k})$ in $\mathbb{Z}_{q}[X]_{u}$;

For example:

  * 1)

In Regev’s cryptosystem [24], we have the vector $\mathbf{b}$ belongs to
$\\{0,1\\}^{N}$;

  * 2)

In the BGV cryptosystem [4], the FV cryptosystem [11] and CKKS cryptosystem
[6], the vector $\mathbf{a}_{N}$ is implicitly assumed to be equal to the
constant polynomial such that the polynomial $b_{N}$ can be used as a
additional noise parameter, as shown below.

$\left\\{\begin{array}[]{ll}c_{1}&=(\sum_{k=1}^{N-1}b_{k}\cdot\mathbf{a}_{k})+\delta_{1}\cdot
r^{\prime}\\\ c_{2}&=\delta_{0}\cdot m+\delta_{1}\cdot r+\delta_{1}\cdot
r^{\prime\prime}+\sum_{k=1}^{N-1}b_{k}\cdot(\langle\mathbf{a}_{k},\mathbf{s}\rangle+\delta_{1}\cdot
e_{k})\\\ \end{array}\right.$

For detailed information on the decryption process of these encryptions,
please consult the respective references. Typically, the decryption protocols
align with those derived from their corresponding Yoneda encryption schemes,
utilizing the decryption function
$\mathsf{D}:\mathbb{Z}_{q}[X]_{u}\times\mathbb{Z}_{q}[X]_{u}\to\mathbb{Z}_{p}[X]_{u}$.

As previously mentioned, the encryption step in Yoneda encryption schemes
employs a non-trivial encryption token that calculates scalar products of
polynomials.

######  Application 4.66 (LWE-based as Yoneda).

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

  * -

a noise parameter $r\in\mathbb{Z}_{q}[X]_{u}$;

  * -

a morphism of the following form in $\mathbf{Mod}(T_{\mathbb{Z}[X]})$.

$h:\mathbb{Z}_{q}[X]_{u}^{(N)}\to\mathbb{Z}_{q}[X]_{u}$

Such a morphism can be described as a linear map $y\mapsto b^{T}y$ where $b$
is a fixed element in $\mathbb{Z}_{q}[X]_{u}^{(N)}$. We will use the notation
$b=(b_{k})_{k}$ to refer to the components $b_{k}$ of $b$ in
$\mathbb{Z}_{q}[X]_{u}$;

  * -

and a message $m\in\mathbb{Z}_{p}[X]_{u}$;

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

  * -

the element $c_{1}=\mathsf{lim}_{I^{\mathsf{op}}}(h_{H})(f_{0})=f_{0}^{T}b$ in
$\mathbb{Z}_{q}[X]^{(n)}$ where $f_{0}^{T}b$ denotes the matrix product of the
transpose of $f_{0}$ with $b$;

  * -

and the element $c_{2}=\mathsf{E}_{r}(h_{1}(f^{\prime}),m)=\delta_{0}\cdot
m+\delta_{1}\cdot r+b^{T}(f_{0}x+\delta_{1}\cdot e)$ in
$\mathbb{Z}_{q}[X]_{N}$.

We omit the decryption steps for the collection of previously explored LWE-
based cryptosystems and directly address decryption within the Yoneda
encryption framework. As is customary, the Yoneda decryption process retrieves
that which is employed in the corresponding cryptosystem.

######  Application 4.67 (LWE-based as Yoneda).

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

  * -

the element

$d=\phi_{H,\mathbb{Z}_{q}[X]_{u}}^{-1}(c_{1})_{1}(x).$

This element corresponds to the image of the element $x\in\mathbb{Z}[X]^{(n)}$
via the morphism

$\phi_{H,\mathbb{Z}_{q}[X]_{u}}^{-1}(f_{0}):\mathbb{Z}[X]^{(n)}\to\mathbb{Z}_{q}[X]_{u}$

that sends every element $y$ in $\mathbb{Z}[X]^{(n)}$ to the scalar product of
$c_{1}$ with $y$. As a result, the element $f$ is equal to the matrix product
$c_{1}^{T}x$.

  * -

and the element $m^{\prime}=\mathsf{D}(d,c_{2})=\mathsf{C}(c_{2}-c_{1}^{T}x)$
in $\mathbb{Z}_{p}[X]_{N}$.

In the general case, the following identity holds:

$m^{\prime}=\mathsf{C}\Big{(}\delta_{0}\cdot
m+\delta_{1}\cdot(r+b^{T}e)\Big{)}$

Theoretically, the equality $m^{\prime}=m$ is guaranteed by the calculations
of Decryption 4.10.

##  5\. Applications

This segment is divided into three key components. First, we formulate an
encryption scheme employing the Yoneda Encryption Scheme. Then, we demonstrate
the fulfillment of the homomorphism property by this scheme, thereby
establishing its classification as a leveled FHE scheme. Lastly, upon the
comprehensive introduction of FHE operations, we delineate a refreshing
operation designed to transform this leveled FHE scheme into an unbounded FHE
scheme.

###  5.1. From Yoneda Lemma to leveled FHE schemes

This section leverages the intuitions developed in previous sections,
highlighting the unifying power of the Yoneda Lemma. We apply these insights
to construct a novel cryptosystem referred to as the _Arithmetic Channel
Encryption Scheme_ (ACES). Notably, this construction eliminates the need for
bootstrapping techniques, as we will demonstrate in the following sections.

The following definition introduces the very important concept of arithmetic
channels. The construction of these objects will be central to generating an
instance of ACES.

######  Definition 5.1 (Arithmetic channels).

An _arithmetic channel_ consists of a tuple $\mathsf{C}=(p,q,\omega,u)$ where:

  * 1)

$p$, $q$ and $\omega$ are positive integers such that $p<q$;

  * 2)

$u$ is a polynomial in $\mathbb{Z}[X]$ such that $u(\omega)=q$;

For such a structure $\mathsf{C}$, we will denote as
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}$ the function
$\mathbb{Z}_{q}[X]_{u}\to\mathbb{Z}_{q}$ that sends every polynomial $v$ in
$\mathbb{Z}_{q}[X]_{u}$ to the evaluation $v(\omega)$ in $\mathbb{Z}_{q}$.
Note that the operation
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}$ must be computed as
follows: first, the representative $v$ is embedded in $\mathbb{N}[X]$ and then
its evaluation $v(\omega)$ in $\mathbb{N}$ is computed modulo $q$.

The homomorphic properties ingrained in ACES find their basis in the result
outlined in Proposition 5.2 below. This result subtly exploits the important
interplay between formal polynomials and polynomial functions, a connection
implicitly invoked through the utilization of rings quotiented by polynomials.
From a broad viewpoint, this concept aligns with the foundational approach
adopted by NTRUEncrypt, where the design of a public key hinges on the notion
of an invertible polynomial.

######  Proposition 5.2.

Let $\mathsf{C}=(p,q,\omega,u)$ be an arithmetic channel. For every pair
$(v_{1},v_{2})$ of polynomials in $\mathbb{Z}_{q}[X]_{u}$, the following
equations hold in the ring $\mathbb{Z}_{q}$.

$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(v_{1}\cdot
v_{2})=\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(v_{1})\cdot\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(v_{2})\quad\quad\quad\quad\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(v_{1}+v_{2})=\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(v_{1})+\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(v_{2})$

Since $\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(1)=1$ and
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(0)=0$, it follows
that $\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}$ defines a ring
morphism $\mathbb{Z}_{q}[X]_{u}\to\mathbb{Z}_{q}$.

###### Proof.

Suppose that the symbol $\square$ denotes either an addition or a
multiplication in $\mathbb{Z}[X]$. This means that the operation $\square$
commutes with the evaluation of polynomials in $\mathbb{Z}$. Let
$r\in\mathbb{N}[X]$ denote the representative of $v_{1}\square v_{2}$ in
$\mathbb{Z}_{q}[X]_{u}$. This means that there exist polynomials $s$ and $t$
such that the equation

$r(X)=v_{1}(X)\square v_{2}(X)+u(X)s(X)+qt(X)$

holds in $\mathbb{Z}[X]$. This gives us the following equations:

$\displaystyle\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(v_{1}\square
v_{2})$
$\displaystyle=\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(r)$
$\displaystyle=r(\omega)$ $\displaystyle=v_{1}(\omega)\square
v_{2}(\omega)+u(\omega)s(\omega)+qt(\omega)$
$\displaystyle=\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(v_{1})\square\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(v_{2})+q(s(\omega)+t(\omega))$

The previous sequence of equations shows that the relation
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(v_{1}\square
v_{2})=\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(v_{1})\square\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(v_{2})$
holds in $\mathbb{Z}_{q}$. This equation proves the statement. ∎

The morphism presented in Proposition 5.2 enables us to further explore the
intricate relationship between formal polynomials and polynomial functions.
The following development draws upon a well-established connection in
algebraic geometry, revealing the interplay between ideals and a zero locus.

######  Convention 5.3 (Leveled ideal).

Let $p$ be a positive integer. For every positive integer $k$, we will denote
as $\chi(k)$ the set $\\{0,p,\dots,kp\\}$ consiting of all multiples of $p$,
from 0 to $kp$. We will denote as $\chi$ the collection of set $\chi(k)$ over
all positive integers $k$.

######  Proposition 5.4.

Let $p$ be a positive integer. The following properties hold:

  * 1)

if $a\in\chi(k_{a})$ and $b\in\chi(k_{b})$, then the addition $a+b$ in
$\mathbb{Z}$ is also in $\chi(k_{a}+k_{b})$;

  * 1)

if $a\in\\{0,1,\dots,k_{a}p\\}$ and $b\in\chi(k_{b})$, then the multiplication
$a\cdot b$ in $\mathbb{Z}$ is also in $\chi(k_{a}k_{b}p)$;

###### Proof.

Directly follows from Porposition 5.3. ∎

######  Definition 5.5 (Vanishing ideal).

For every arithmetic channel $\mathsf{C}=(p,q,\omega,u)$ and every positive
integer $k$, we define the _vanishing ideal_ $\mathcal{I}_{k}(\mathsf{C})$ of
$\mathsf{C}$ as the inverse image of the set $\chi(k)$ via
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}:\mathbb{Z}_{q}[X]_{u}\to\mathbb{Z}_{q}$.
This means that the following equation holds:

$\mathcal{I}_{k}(\mathsf{C})=\\{e\in\mathbb{Z}_{q}[X]_{u}~{}|~{}\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e)\in\chi(k)\\}$

Since we have $u(\omega)=q$, any polynomial of the from
$\sum_{i=1}^{d}a_{i}(X-\omega)^{i}+u(X)s(X)+j\cdot p$, where $j\in[k]$, is an
element of $\mathcal{I}_{k}(\mathsf{C})$.

######  Proposition 5.6 (Leveled ideal).

Let $\mathsf{C}=(p,q,\omega,u)$ be an arithmetic channel. The collection
$(\mathcal{I}_{k}(\mathsf{C}))_{k}$ satisfies the following properties for
every pair $(k_{1},k_{2})$ of positive integers:

  * 1)

for every $e_{1}\in\mathcal{I}_{k_{1}}(\mathsf{C})$ and every
$e_{2}\in\mathcal{I}_{k_{2}}(\mathsf{C})$, the following implication holds.

$k_{1}+k_{2}<q/p\quad\quad\Rightarrow\quad\quad
e_{1}+e_{2}\in\mathcal{I}_{k_{1}+k_{2}}(\mathsf{C})$

  * 2)

for every $e_{1}\in\mathbb{Z}_{q}[X]_{u}$ such that
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{1})\in\\{0,1,\dots,k_{1}p\\}$
and every $e\in\mathcal{I}_{k_{2}}(\mathsf{C})$, the following implication
holds.

$k_{1}k_{2}p<q/p\quad\quad\Rightarrow\quad\quad e_{1}\cdot
e_{2}\in\mathcal{I}_{k_{1}k_{2}p}(\mathsf{C})$

###### Proof.

The proof uses Proposition 5.2 and Proposition 5.5. Let us show item 1). If we
have $e_{1}\in\mathcal{I}_{k_{1}}(\mathsf{C})$ and
$e_{2}\in\mathcal{I}_{k_{2}}(\mathsf{C})$ such that $k_{1}+k_{2}<q/p$, then
the following addition, computed in $\mathbb{Z}$, is less than $q$.

$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{1})+\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{2})$

This implies that
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{1})+\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{2})$
is its own representative in $\mathbb{Z}_{q}$ and Proposition 5.2 implies that
the following equation holds.

$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{1})+\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{2})=\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{1}+e_{2})$

Proposition 5.5 then gives the relation
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{1}+e_{2})\in\chi(k_{1}+k_{2})$.
Similarly, let us show item 2). If we have $e_{1}\in\mathbb{Z}_{q}[X]_{u}$
such that
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{1})\in\\{0,1,\dots,k_{1}p\\}$
and $e\in\mathcal{I}_{k_{2}}(\mathsf{C})$ such that $k_{1}k_{2}p<q/p$, then
the following multiplication, computed in $\mathbb{Z}$, is less than $q$.

$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{1})\cdot\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{2})$

This implies that
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{1})\cdot\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{2})$
is its own representative in $\mathbb{Z}_{q}$ and Proposition 5.2 implies that
the following equation holds.

$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{1})\cdot\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{2})=\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{1}\cdot
e_{2})$

Proposition 5.5 then gives the relation
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e_{1}+e_{2})\in\chi(k_{1}k_{2}q)$.
∎

######  Definition 5.7.

For every arithmetic channel $\mathsf{C}=(p,q,\omega,u)$, we denote as
$\mathcal{E}(\mathsf{C})$ the set of functions
$r:\mathbb{Z}_{q}\to\mathbb{Z}_{q}[X]_{u}$ such that for every integer $m$ in
$\mathbb{Z}_{q}$, the equation
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(r(m))=m$ holds in
$\mathbb{Z}_{q}$. Note that any function $\mathbb{Z}_{q}\to\mathbb{Z}_{q}[X]$
of the from

$m\mapsto m+\sum_{k=1}^{d}a_{k,m}(X-\omega)^{k}+u(X)s_{m}(X)$

where $a_{k,m}\in\mathbb{Z}_{q}$ and $s_{m}(X)\in\mathbb{Z}_{q}[X]$ is in
$\mathcal{E}(\mathsf{C})$.

Readers familiar with the subject may recognize the upcoming result as an
affine adaptation of the Zariski correspondence between points and ideals in
algebraic geometry. As demonstrated in Proposition 5.8 and later emphasized in
Proposition 5.20, a significant portion of our subsequent developments
involves leveraging the affine nature of polynomials. This inherent affineness
guarantees that the encrypted outputs of ACES remain indistinguishable from
noisy results.

######  Proposition 5.8.

Let $\mathsf{C}=(p,q,\omega,u)$ be an arithmetic channel. For every pair
$(r_{1},r_{2})$ of elements in $\mathcal{E}(\mathsf{C})$ and every pair
$(m_{1},m_{2})$ of elements in $\mathbb{Z}_{q}$, the following holds:

  * 1)

there exists $r_{3}\in\mathcal{E}(\mathsf{C})$ such that $r_{1}(m_{1})\cdot
r_{2}(m_{2})=r_{3}(m_{1}\cdot m_{2})$ in $\mathbb{Z}_{q}[X]_{u}$;

  * 1)

there exists $r_{4}\in\mathcal{E}(\mathsf{C})$ such that
$r_{1}(m_{1})+r_{2}(m_{2})=r_{4}(m_{1}+m_{2})$ in $\mathbb{Z}_{q}[X]_{u}$;

###### Proof.

It is straightforward to construct two polynomials $Q_{1}(X)$ and $Q_{2}(X)$
in $\mathbb{Z}_{q}[X]_{u}$ for which the following equations hold.

$r_{1}(m_{1})=m_{1}+Q_{1}(X)\quad\quad\quad\quad r_{2}(m_{2})=m_{2}+Q_{2}(X)$

Since $r_{1}$ and $r_{2}$ are elements of $\mathcal{E}(\mathsf{C})$, it
follows that $Q_{1}(\omega)=0$ and $Q_{2}(\omega)=0$. Now, if we take
$r_{3}(m)=m+m_{1}Q_{2}(X)+m_{2}Q_{1}(X)+Q_{1}(X)Q_{2}(X)$ and
$r_{4}(m)=m+Q_{2}(X)+Q_{1}(X)$ for every every element $m$ in
$\mathbb{Z}_{q}$, then we can show that $r_{3}(m)(\omega)=m$ and
$r_{4}(m)(\omega)=m$. This means that $r_{3}$ and $r_{4}$ belong to
$\mathcal{E}(\mathsf{C})$. In addition, we can check that the following
equations hold:

$\begin{array}[]{lll}r_{1}(m_{1})\cdot
r_{2}(m_{2})&=m_{1}m_{2}++m_{1}Q_{2}(X)+m_{2}Q_{1}(X)+Q_{1}(X)Q_{2}(X)&=r_{3}(m_{1}m_{2})\\\
r_{1}(m_{1})+r_{2}(m_{2})&=m_{1}+m_{2}+Q_{2}(X)+Q_{1}(X)&=r_{3}(m_{1}+m_{2})\\\
\end{array}$

This finishes the proof of the statement. ∎

In the remainder of this section, we extends the notations of Convention 3.36
to the set $\mathcal{I}_{k}(\mathsf{C})$. Specifically, for every arithmetic
channel $\mathcal{C}=(p,q,\omega,u)$ and every positive integer $k$, we will
denote as $\mathcal{I}_{k}(\mathsf{C})^{(N)}$ the subset of
$\mathbb{Z}_{q}[X]_{u}^{(N)}$ whose elements
$(f_{1},\dots,f_{N})\in\mathbb{Z}_{q}[X]_{u}^{(N)}$ are such that their
components $f_{k}$ are in the set $\mathcal{I}_{k}(\mathsf{C})$.

######  Generation 5.9 (ACES).

Let us describe the overall setup for ACES. First, the associated limit sketch
$T$ must be the limit sketch $T_{\mathbb{Z}[X]}$ defined for modules over the
ring $\mathbb{Z}[X]$ (Convention 3.37). As a result, the associated reflective
subcategory is given by the inclusion

$\mathbf{Mod}(T_{\mathbb{Z}[X]})\hookrightarrow[T_{\mathbb{Z}[X]},\mathbf{Set}]$

and its left adjoint $L$. The cryptosystem is defined at the object $1$ of
$T_{\mathbb{Z}[X]}$ (see Convention 3.37) and is expressed as a Yoneda
cryptosystem of the form

$\mathcal{Y}(\mathbb{Z}_{q}[X]_{u}^{(N)},\mathbb{Z}_{q}[X]_{u},\mathbb{Z}_{p},\mathbb{Z}_{q}[X]_{u}|\mathcal{E}(\mathsf{C}),\mathsf{E},\mathsf{D})$

where $N$ is a positive integer and $(p,q,\omega,u)$ defines an arithmetic
channel $\mathsf{C}$. We also require that the inequality $p^{2}N\leq q$
holds. In addition, we restrict the cryptosystem to the following set of
morphisms (see Convention 4.2).

$M=\left\\{h\in\mathcal{L}(\mathbb{Z}_{q}[X]_{u}^{(N)},\mathbb{Z}_{q}[X]_{u})~{}\left|~{}\begin{array}[]{l}\textrm{
where }h:y\mapsto b^{T}y\\\ \textrm{ with
}b=(b_{j})_{j\in[N]}\in\mathbb{Z}_{q}[X]_{u}^{(N)}\end{array}\textrm{ and
}\forall
i\in[N]\,:\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(b_{i})\in\\{0,1,\dots,p\\}\right.\right\\}$

The collection of encryption algorithms is indexed by the set
$\mathcal{E}(\mathsf{C})$ such that for every function
$r\in\mathcal{E}(\mathsf{C})$ we have an encryption function of the following
form.

$\mathsf{E}_{r}:\left(\begin{array}[]{ccc}\mathbb{Z}_{q}[X]_{u}\times\mathbb{Z}_{p}&\to&\mathbb{Z}_{q}[X]_{u}\\\
(g,m)&\mapsto&r(m)+g\end{array}\right)$

The decryption algorithm is given by the following function, where we consider
the integer
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(c-g)\in\\{0,1,\dots,q\\}$
modulo $p$.

$\mathsf{D}:\left(\begin{array}[]{ccc}\mathbb{Z}_{q}[X]_{u}\times\mathbb{Z}_{q}[X]_{u}&\to&\mathbb{Z}_{p}\\\
(g,c)&\mapsto&\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(c-g)\,(\mathsf{mod}\,p)\end{array}\right)$

With such functions, we can determine the form of the set $\mathcal{R}(f)$
(Convention 4.4) for every $f\in\mathbb{Z}_{q}[X]_{u}^{(N)}$, as shown below

$\displaystyle\mathcal{R}(f)$ $\displaystyle=\\{f^{\prime}~{}|~{}\forall h\in
M,\,\forall
m\in\mathbb{Z}_{p}:\,\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(r(m)+h(f^{\prime})-h(f))\,(\mathsf{mod}\,p)=m\\}$
$\displaystyle=\\{f^{\prime}~{}|~{}\forall h\in M,\,\forall
m\in\mathbb{Z}_{p}:\,\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(r(m)+h(f^{\prime})-h(f))\equiv
m\,(\mathsf{mod}\,p)\\}$

Let us simply the specification of the set $\mathcal{R}(f)$ with some detailed
explanation. First, we have the following expansion in the commutative group
$\mathbb{Z}_{q}$.

$\displaystyle\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}\big{(}r(m)+h(f^{\prime})-h(f)\big{)}$
$\displaystyle=\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}\big{(}r(m)\big{)}+\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}\big{(}h(f^{\prime})-h(f)\big{)}$
$\displaystyle(\textrm{Proposition \ref{prop:channel-homomorphism}})$
$\displaystyle=m+\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}\big{(}h(f^{\prime})-h(f)\big{)}$
$\displaystyle(\textrm{Definition \ref{def:arith-channel:E:errors}})$

Given that $m\in\mathbb{Z}_{p}$, the previous development give us the
following equivalence:

$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}\big{(}r(m)+h(f^{\prime})-h(f)\big{)}\equiv
m\,(\mathsf{mod}\,p)\quad\quad\Leftrightarrow\quad\quad\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}\big{(}h(f^{\prime})-h(f)\big{)}\equiv
0\,(\mathsf{mod}\,p)$

Since the element
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(h(f^{\prime})-h(f))$
is in $\mathbb{Z}_{q}$, the previous relation is equivalent to the following
relation.

$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(h(f^{\prime})-h(f))\in\chi(\lfloor
q/p\rfloor)$

By Definition 5.5, this means that we have the following reduced form for
$\mathcal{R}(f)$:

$\displaystyle\mathcal{R}(f)$ $\displaystyle=\\{f^{\prime}~{}|~{}\forall h\in
M:\,h(f^{\prime})-h(f)\in\mathcal{I}_{\lfloor q/p\rfloor}(\mathsf{C})\\}$
$\displaystyle(\textrm{Definition \ref{def:vanishing-ideal}})$
$\displaystyle\supseteq\\{f^{\prime}=(f^{\prime}_{1},\dots,f_{N})~{}|~{}\,f^{\prime}_{i}-f_{i}\in\mathcal{I}_{\lfloor\lfloor
q/p\rfloor/pN\rfloor}(\mathsf{C})\\}$ $\displaystyle(\textrm{Def. of $M$ and
Prop. \ref{prop:level-ideal:vanishing-ideal}})$
$\displaystyle\supseteq\\{f^{\prime}=(f^{\prime}_{1},\dots,f_{N})~{}|~{}\,f^{\prime}_{i}-f_{i}\in\mathcal{I}_{1}(\mathsf{C})\\}$
$\displaystyle(\textrm{Since $p^{2}N\leq q$})$
$\displaystyle=f+\mathcal{I}_{1}(\mathsf{C})^{(N)}$

The fact that $\mathcal{R}(f)$ is non-empty for all
$f\in\mathbb{Z}_{q}[X]_{u}^{(N)}$ shows that the Yoneda cryptosystem is well-
defined (if restricted along $M$). Following Generation 4.5, the key
generation step undertaken by $\mathsf{Alice}$ for this cryptosystem consists
of

  * -

a non-empty discrete category $I=[n]$ containing $n$ objects (and their
identities) and a functor

$H:\left(\begin{array}[]{lll}I&\to&T_{\mathbb{Z}[X]}^{\mathsf{op}}\\\
k&\mapsto&1\end{array}\right)$

picking out the object $1$ in the limit sketch $T_{\mathbb{Z}[X]}$;

  * -

an initializer $f_{0}$ taken in the following set:

$\mathsf{lim}_{I^{\mathsf{op}}}(\mathbb{Z}_{q}[X]_{u}^{(N)}\circ
H^{\mathsf{op}})=\mathbb{Z}_{q}[X]_{u}^{(N\times n)}$

  * -

and a private key $x$ taken in the following $\mathbb{Z}[X]$-module:

$\mathsf{col}_{I}(L\circ Y\circ H)(1)=\Big{(}\coprod^{n}Y(1)\Big{)}(1)\cong
Y(n)(1)\cong\mathbb{Z}[X]^{(n)}$

Later, we will use the notations $f_{0}=(f_{0,i,j})_{i,j}$ and $x=(x_{j})_{j}$
to refer to the components of the elements $f_{0}$ and $x$ in
$\mathbb{Z}_{q}[X]_{u}$ and $\mathbb{Z}[X]$, respectively. For convenience, we
will also denote $f_{0,i}:=(f_{0,i,j})_{i,j}$ foir every fixed index
$i\in[N]$.

######  Publication 5.10 (ACES).

The key publication step for ACES goes as follows. $\mathsf{Alice}$ does the
following:

  * -

she computes the element

$f=\phi_{H,\mathbb{Z}_{q}[X]_{u}^{(N)}}^{-1}(f_{0})_{1}(x)$

This element corresponds to the image of the element $x\in\mathbb{Z}[X]^{(n)}$
via the morphism

$\phi_{H,\mathbb{Z}_{q}[X]_{u}^{(N)}}^{-1}(f_{0}):\mathbb{Z}[X]^{(n)}\to\mathbb{Z}_{q}[X]_{u}^{(N)}$

that sends every element $y$ in $\mathbb{Z}[X]^{(n)}$ to the matrix product of
$f_{0}$ with $y$. As a result, the element $f$ is equal to the matrix product
$f_{0}x$.

  * -

Since $\mathcal{R}(f)\supseteq f+\mathcal{I}_{1}(\mathsf{C})^{(N)}$,
$\mathsf{Alice}$ can send a pair of the form $(f_{0},f+e)$, where
$e\in\mathcal{I}_{1}(\mathsf{C})^{(N)}$, to $\mathsf{Bob}$;

For convenience, we will denote the pair sent by $\mathsf{Alice}$ to
$\mathsf{Bob}$ as a tuple $(f,f^{\prime})$.

######  Encryption 5.11 (ACES).

The encryption step for ACES is defined as follows. First, $\mathsf{Bob}$
selects:

  * -

a noise parameter $r\in\mathcal{E}(\mathsf{C})$;

  * -

a morphism $h\in M$ of the following type.

$h:\mathbb{Z}_{q}[X]_{u}^{(N)}\to\mathbb{Z}_{q}[X]_{u}$

Such a morphism is described as a linear map $y\mapsto b^{T}y$ where $b$ is a
fixed element in $\mathbb{Z}_{q}[X]_{u}^{(N)}$ and, if we denote
$b=(b_{j})_{j}$, every component $b_{i}$ in $\mathbb{Z}_{q}[X]_{u}$ satisfies
the relation
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(b_{i})\in\\{0,1,\dots,p\\}$;

  * -

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

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

  * -

the element $c_{1}=\mathsf{lim}_{I^{\mathsf{op}}}(h_{H})(f_{0})=f_{0}^{T}b$ in
$\mathbb{Z}_{q}[X]^{(n)}$ where $f_{0}^{T}b$ denotes the matrix product of the
transpose of $f_{0}$ with $b$;

  * -

and the element
$c_{2}=\mathsf{E}_{r}(h_{1}(f^{\prime}),m)=r(m)+b^{T}(f_{0}x+e)$ in
$\mathbb{Z}_{q}[X]_{N}$.

The following remark justifies the use of two noisy components $r$ and $e$ on
the ciphertext constructed in Encryption 5.11. Note that this type of
construction aligns with the strategies used in cryptographic systems such as
BGV, FV, and CKKS. However, one difference between these cryptosystems and
ACES is that, in the case of ACES, the two noisy components act on the
ciphertext containing the message.

######  Remark 5.12 (Evaluation as an attack).

Let us analyze the encryption protocol of ACES and its relationship with
previously encountered cryptosystems. Consider a ciphertext $(c_{1},c_{2})$,
as defined in Encryption 5.11. An attempt to breach this ciphertext involves
evaluating its polynomial at the element $\omega$, followed by two distinct
strategies:

  * 1)

either we evaluate the ciphertext in $\mathbb{Z}_{q}$ and we obtain the
following equations:

$c_{1}(\omega)=(f_{0}(\omega))^{T}b(\omega)\quad\quad\quad\quad
c_{2}(\omega)=m+(b(\omega))^{T}f_{0}(\omega)+b^{T}(\omega)e(\omega)$

  * 2)

or we evaluate the ciphertext in $\mathbb{Z}_{p}$ and we obtain the following
equations:

$c_{1}(\omega)=(f_{0}(\omega))^{T}b(\omega)\quad\quad\quad\quad
c_{2}(\omega)=r(m)(\omega)+(b(\omega))^{T}f_{0}(\omega)$

Given the condition $p<q$, the message $m$ is hidden by either the element
$b^{T}(\omega)e(\omega)$ – a multiple of $p$ in $\mathbb{Z}_{q}$ – or the
element $r(m)(\omega)$ – an element of the form $m+qk$ in $\mathbb{Z}_{p}$.
Note that if we denote the gcd of $p$ and $q$ as $\delta$, then the previous
attacks can also be extended to $\mathbb{Z}_{\delta}$, giving the following
information.

$c_{1}(\omega)=(f_{0}(\omega))^{T}b(\omega)\quad\quad\quad\quad
c_{2}(\omega)=m-\delta\lfloor m/\delta\rfloor+(b(\omega))^{T}f_{0}(\omega)$

By taking $\delta=1$, we can make sure that the attacker is not able to learn
information about the message $m$.

######  Decryption 5.13 (ACES).

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

  * -

the element

$d=\phi_{H,\mathbb{Z}_{q}[X]_{u}}^{-1}(c_{1})_{1}(x).$

This element corresponds to the image of the element $x\in\mathbb{Z}[X]^{(n)}$
via the morphism

$\phi_{H,\mathbb{Z}_{q}[X]_{u}}^{-1}(f_{0}):\mathbb{Z}[X]^{(n)}\to\mathbb{Z}_{q}[X]_{u}$

that sends every element $y$ in $\mathbb{Z}[X]^{(n)}$ to the scalar product of
$c_{1}$ with $y$. As a result, the element $f$ is equal to the matrix product
$c_{1}^{T}x$.

  * -

and the element
$m^{\prime}=\mathsf{D}(d,c_{2})=\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(c_{2}-c_{1}^{T}x)$
in $\mathbb{Z}_{q}[X]_{N}$.

The equality $m^{\prime}=m$ is guaranteed by the calculations of Decryption
4.10.

###  5.2. Homomorphic properties

This section addresses the homomorphic properties of the cryptosystem defined
in section 5.1. Specifically, it exhibits homomorphic properties for addition
and multiplication with full control of the noise level.

To uphold these homomorphic properties, an additional piece of information
needs to be disclosed during the publication step of the cryptosystem.
Importantly, this extra information is not anticipated to compromise the
security of the cryptosystem.

######  Definition 5.14.

Let $\mathsf{C}=(p,q,\omega,u)$ be an arithmetic channel, let $n$ be a
positive integer, and let $x=(x_{1},\dots,x_{n})$ be an element in the
$\mathbb{Z}[X]$-module $\mathbb{Z}[X]^{(n)}$. We denote as
$\mathcal{H}(x|\mathsf{C})$ the set of 3-tensors $\lambda=(\lambda_{i,j}^{k})$
in $\mathbb{Z}_{q}$ for which the following equation holds in the ring
$\mathbb{Z}_{q}[X]_{u}$ for every pair $(i,j)$ of elements in $[n]$.

$x_{i}\cdot x_{j}=\sum_{k=1}^{n}\lambda_{i,j}^{k}\cdot x_{k}$

As suggested by Generation 5.15, the set defined in Definition 5.14 originates
from the observation that $\mathbb{Z}[X]$-modules possess three degrees of
freedom: the dimension of the ring of integer, which acts of the formal
monomial $X$, the dimension given by polynomials in $\mathbb{Z}[X]$, and the
dimension offered by the module structure111This leveled structure is
implicitely suggested by our construction in Convention 3.37, where we (1)
start with a ring structure $R$, (2) then send it to a commutative group
structure, and (3) induce its associated modules using a functors
$T_{R}\to\mathbf{Set}$. This distinguishes it from the cryptosystems explored
in section 4, which were typically dependent on what could be considered as
two degrees of freedom, often encoded by generators and their exponents (e.g.,
ElGamal, RSA, Benaloh) or encoded by rings and their ideals (NTRU and LWE-
based cryptosystems). In essence, the reader may perceive this freedom in
dimensionality as the factor that renders ACES fully homomorphic.

######  Generation 5.15.

Let $\mathsf{C}=(p,q,\omega,u)$ be an arithmetic channel, let $n$ be a
positive integer, and let $x=(x_{1},\dots,x_{n})$ be an element in the
$\mathbb{Z}[X]$-module $\mathbb{Z}[X]^{(n)}$. Suppose that the polynomial $u$
is of degree $d$. This implies that, for every pair $(i,j)$ in $[n]$, the
polynomial $x_{i}x_{j}$ in $\mathbb{Z}_{q}[X]_{u}$ can be regarded as a vector
$(a_{i,j}^{1},\dots,a_{i,j}^{d})$ with coefficients in $\mathbb{Z}_{q}$.

$x_{i}x_{j}=a_{i,j}^{1}X^{0}+a_{i,j}^{2}X^{1}+\dots+\dots,a_{i,j}^{d}X^{d-1}$

Similarly, if we denote the vector representing the polynomial
$x_{k}\in\mathbb{Z}_{q}[X]_{u}$ as $(b_{k}^{1},\dots,b_{k}^{d})$, then the
element $\lambda$ in $\mathcal{H}(x|\mathsf{C})$ is characterized by the
following matrix equation in $\mathbb{Z}_{q}$ for every pair $(i,j)$ in $[n]$.

$\left(\begin{array}[]{c}a_{i,j}^{1}\\\ \vdots\\\
a_{i,j}^{d}\end{array}\right)=\left(\begin{array}[]{ccc}b_{1}^{1}&\dots&b_{n}^{1}\\\
\vdots&\dots&\vdots\\\ b_{n}^{d}&\dots&b_{n}^{d}\\\
\end{array}\right)\cdot\left(\begin{array}[]{c}\lambda_{i,j}^{1}\\\ \vdots\\\
\lambda_{i,j}^{n}\end{array}\right)$

In other words, the set $\mathcal{H}(x|\mathsf{C})$ is non-empty whenever the
matrix induced by the element $x$ is invertible. In this scenario, we can
provide an algorithm that generates an element of $\mathcal{H}(x|\mathsf{C})$.

######  Definition 5.16.

Let $\mathsf{C}=(p,q,\omega,u)$ be an arithmetic channel, let $n$ be a
positive integer, and let $x=(x_{1},\dots,x_{n})$ be an element in the
$\mathbb{Z}[X]$-module $\mathbb{Z}[X]^{(n)}$. For every element
$\lambda=(\lambda_{i,j}^{k})$ in $\mathcal{H}(x|\mathsf{C})$ and every pair
$(v_{1},v_{2})$ of elements in the $\mathbb{Z}[X]$-module
$\mathbb{Z}_{q}[X]_{u}^{(n)}$, we denote as $v_{1}\boxtimes_{\lambda}v_{2}$
the element of $\mathbb{Z}_{q}[X]_{u}^{(n)}$ encoded by the following tuple.

$v_{1}\boxtimes_{\lambda}v_{2}:=\Big{(}\sum_{i,j}\lambda_{i,j}^{k}v_{1,i}v_{2,j}\Big{)}_{k\in[n]}$

######  Proposition 5.17.

Let $\mathsf{C}=(p,q,\omega,u)$ be an arithmetic channel, let $n$ be a
positive integer, and let $x=(x_{1},\dots,x_{n})$ be an element in the
$\mathbb{Z}[X]$-module $\mathbb{Z}[X]^{(n)}$. For every element
$\lambda=(\lambda_{i,j}^{k})$ in $\mathcal{H}(x|\mathsf{C})$ and every pair
$(v_{1},v_{2})$ of elements in the $\mathbb{Z}[X]$-module
$\mathbb{Z}_{q}[X]_{u}^{(n)}$, the following equation holds in
$\mathbb{Z}_{q}[X]_{u}$.

$(v_{1}^{T}x)\cdot(v_{2}^{T}x)=(v_{1}\boxtimes_{\lambda}v_{2})^{T}x$

###### Proof.

The proof is a straightforward calculation using the different concepts
introduced in Definition 5.14 and Definition 5.16. Specifically, we have:

$\displaystyle(v_{1}^{T}x)\cdot(v_{2}^{T}x)$
$\displaystyle=(\sum_{i}v_{1,i}x_{i})\cdot(\sum_{j}v_{2,j}x_{j})$
$\displaystyle=\sum_{i,j}v_{1,i}x_{i}v_{2,j}x_{j}$
$\displaystyle=\sum_{i,j}v_{1,i}v_{2,j}(\sum_{k=1}^{n}\lambda_{i,j}^{k}\cdot
x_{k})$
$\displaystyle=\sum_{k=1}^{n}\Big{(}\sum_{i,j}\lambda_{i,j}^{k}v_{1,i}v_{2,j}\Big{)}\cdot
x_{k}$ $\displaystyle=(v_{1}\boxtimes_{\lambda}v_{2})^{T}x$

This proves the proposition. ∎

######  Definition 5.18 (Encryption space).

Let $\mathsf{C}=(p,q,\omega,u)$ be an arithmetic channel, let $n$ be a
positive integer and let $x$ be an element in $\mathbb{Z}[X]^{(n)}$. For every
element $m\in\mathbb{Z}_{p}$ and every positive integer $k$, we define the
$k$-th _$\mathsf{C}$ -encryption space_ $\mathcal{S}^{x}_{\mathsf{C},k}(m)$ at
the element $m$ as the set containing the pairs

$(c,c^{\prime})\in\mathbb{Z}_{q}[X]_{u}^{(n)}\times\mathbb{Z}_{q}[X]_{u}$

for which there exist $r\in\mathcal{E}(\mathsf{C})$ and
$e\in\mathcal{I}_{k}(C)$ such that the equation $c^{\prime}=r(m)+c^{T}x+e$
holds in $\mathbb{Z}_{q}[X]_{u}$.

######  Remark 5.19 (ACES).

For the encrytion $(c_{1},c_{2})$ of any message $m\in\mathbb{Z}_{q}$ via the
encryption scheme presented in section 5.1 belongs to the
$\mathsf{C}$-encryption space $\mathcal{S}^{x}_{\mathsf{C},Np}(m)$ for the
corresponding arithmetic channel $\mathsf{C}=(p,q,\omega,u)$ and positive
integer $N$. Indeed, as defined thereof. As explained in Encryption 5.11, we
have the equations

$c_{1}=f_{0}^{T}b\quad\quad\quad c_{2}=r(m)+b^{T}(f_{0}x+e)$

where $e\in\mathcal{I}(\mathsf{C})^{(N)}$ and the vector
$b=(b_{1},\dots,b_{N})$ in $\mathbb{Z}_{q}[X]_{u}^{(N)}$ is such that
$\textrm{\textlbrackdbl}C\textrm{\textrbrackdbl}(b_{i})\in\\{0,1,\dots,p\\}$
for every $i\in[N]$. Since we have the equation

$\textrm{\textlbrackdbl}C\textrm{\textrbrackdbl}(b^{T}e)=\sum_{i=1}^{N}\textrm{\textlbrackdbl}C\textrm{\textrbrackdbl}(b_{i}\cdot
e_{i})=\sum_{i=1}^{N}\textrm{\textlbrackdbl}C\textrm{\textrbrackdbl}(b_{i})\cdot\textrm{\textlbrackdbl}C\textrm{\textrbrackdbl}(e_{i})$

it follows from Proposition 5.4 that the element is in $\chi(Np)$.

######  Proposition 5.20 (Decryption).

Let $\mathsf{C}=(p,q,\omega,u)$ be an arithmetic channel, let $n$ be a
positive integer, and let $x$ be an element in $\mathbb{Z}[X]^{(n)}$. Consider
the following decryption function, which was introduced in Generation 5.9.

$\mathsf{D}:\left(\begin{array}[]{ccc}\mathbb{Z}_{q}[X]_{u}\times\mathbb{Z}_{q}[X]_{u}&\to&\mathbb{Z}_{q}\\\
(g,c)&\mapsto&\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(c-g)\,(\mathsf{mod}\,p)\end{array}\right)$

For every element $m\in\mathbb{Z}_{q}$ and every positive integer $k$, the
following implication holds.

$(c,c^{\prime})\in\mathcal{S}^{x}_{\mathsf{C},k}(m)\quad\quad\Rightarrow\quad\quad\mathsf{D}(c^{T}x,c^{\prime})=m$

###### Proof.

This kind of calculation has already been explored in detail throughout
section 5.1. First, recall that we have the relation
$\mathsf{D}(c^{T}x,c^{\prime})=\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(c^{\prime}-c^{T}x)\,(\mathsf{mod}\,p)$.
Then, the development in $\mathbb{Z}_{q}$ unfolds as follows:

$\displaystyle\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(c^{\prime}-c^{T}x)$
$\displaystyle=\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(r(m)+e)$
$\displaystyle(\textrm{Definition \ref{def:encryption-space:general}})$
$\displaystyle=\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(r(m))+\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e)$
$\displaystyle(\textrm{Proposition \ref{prop:channel-homomorphism}})$
$\displaystyle=m+\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e)$
$\displaystyle(\textrm{Definition \ref{def:arith-channel:E:errors}})$

Given that $m\in\mathbb{Z}_{p}$ and
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e)\in\\{0,p,2p,\dots,kp\\}$
(Definition 5.5) that the following equations hold:

$\mathsf{D}(c^{T}x,c^{\prime})=\Big{(}m+\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e)\Big{)}\,(\mathsf{mod}\,p)=m$

Note that the rightmost equation comes from the equality
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e)\,(\mathsf{mod}\,p)=0$,
since $e$ belongs to $\mathcal{I}(\mathsf{C})$. ∎

######  Definition 5.21 (Algebraic operations).

Let $\mathsf{C}=(p,q,\omega,u)$ be an arithmetic channel, let $n$ be a
positive integer, and let $x$ be an element in $\mathbb{Z}[X]^{(n)}$. Also,
let us consider an $n$-vector $x$ in the $\mathbb{Z}[X]$-module
$\mathbb{Z}[X]^{(n)}$ and an element $\lambda\in\mathcal{H}(x|\mathsf{C})$.
For every pair $(m_{1},m_{2})$ of elements in $\mathbb{Z}_{q}$ and every pair
$(k_{1},k_{2})$ of positive integers, we define two operations $\oplus$ and
$\otimes_{\lambda}$ of the form

$\mathcal{S}^{x}_{\mathsf{C},k_{1}}(m_{1})\times\mathcal{S}^{x}_{\mathsf{C},k_{2}}(m_{2})\to\mathbb{Z}_{q}[X]_{u}^{(n)}\times\mathbb{Z}_{q}[X]_{u}$

such that the following equations hold for every
$(c_{1},c^{\prime}_{1})\in\mathcal{S}^{x}_{\mathsf{C},k_{1}}(m_{1})$ and
$(c_{2},c^{\prime}_{2})\in\mathcal{S}^{x}_{\mathsf{C},k_{2}}(m_{2})$.

$\begin{array}[]{ll}(c_{1},c^{\prime}_{1})\oplus(c_{2},c^{\prime}_{2})&=(c_{1}+c_{2},c_{1}^{\prime}+c_{2}^{\prime})\\\
(c_{1},c^{\prime}_{1})\otimes_{\lambda}(c_{2},c^{\prime}_{2})&=(c_{2}^{\prime}\cdot
c_{1}+c_{1}^{\prime}\cdot
c_{2}-c_{1}\boxtimes_{\lambda}c_{2},c_{1}^{\prime}c_{2}^{\prime})\end{array}$

Note that the expression $c_{2}^{\prime}\cdot c_{1}+c_{1}^{\prime}\cdot c_{2}$
should be seen as a linear combination of the vector $c_{1}$ and $c_{2}$ such
that $c_{2}^{\prime}$ and $c_{1}^{\prime}$ are scalar coefficients in
$\mathbb{Z}_{q}[X]_{u}$. The previous two equations fully determine the
mapping rules associated with the operations $\oplus$ and $\otimes_{\lambda}$.

######  Theorem 5.22 (Leveled FHE).

Let $\mathsf{C}=(p,q,\omega,u)$ be an arithmetic channel, let $n$ be a
positive integer, and let $x$ be an element in $\mathbb{Z}[X]^{(n)}$. Also,
let us consider an $n$-vector $x$ in the $\mathbb{Z}[X]$-module
$\mathbb{Z}[X]^{(n)}$ and an element $\lambda\in\mathcal{H}(x|\mathsf{C})$.
For every pair $(m_{1},m_{2})$ of elements in $\mathbb{Z}_{q}$, every pair
$(k_{1},k_{2})$ of positive integers, and every pair of ciphertexts
$(c_{1},c^{\prime}_{1})\in\mathcal{S}^{x}_{\mathsf{C},k_{1}}(m_{1})$ and
$(c_{2},c^{\prime}_{2})\in\mathcal{S}^{x}_{\mathsf{C},k_{2}}(m_{2})$, the
following implications hold:

$\begin{array}[]{lll}k_{1}+k_{2}<q/p&\Rightarrow(c_{1},c^{\prime}_{1})\oplus(c_{2},c^{\prime}_{2})&\in\mathcal{S}^{x}_{\mathsf{C},k_{1}+k_{2}}(m_{1}+m_{2})\\\
k_{1}k_{2}p<q/p&\Rightarrow(c_{1},c^{\prime}_{1})\otimes_{\lambda}(c_{2},c^{\prime}_{2})&\in\mathcal{S}^{x}_{\mathsf{C},k_{1}k_{2}p}(m_{1}m_{2})\end{array}$

###### Proof.

The proof is a straightforward application of Definition 5.21 and Proposition
5.6. Let us suppose that the inequality $k_{1}+k_{2}<q/p$ holds and we have
the following encoding for the two elements
$(c_{1},c^{\prime}_{1})\in\mathcal{S}^{x}_{\mathsf{C},k_{1}}(m_{1})$ and
$(c_{2},c^{\prime}_{2})\in\mathcal{S}^{x}_{\mathsf{C},k_{2}}(m_{2})$:

$(c_{1},c_{1}^{\prime})=(c_{1},r_{1}(m_{1})+c_{1}^{T}x+e_{1})\quad(c_{2},c_{2}^{\prime})=(c_{1},r_{2}(m_{2})+c_{2}^{T}x+e_{2})$

Let us denote $e_{3}=e_{1}+e_{2}$. Since $k_{1}+k_{2}<q/p$, with
$e_{1}\in\mathcal{I}_{k_{1}}(\mathsf{C})$ and
$e_{2}\in\mathcal{I}_{k_{2}}(\mathsf{C})$, Proposition 5.6 implies that
$e_{3}\in\mathcal{I}_{k_{1}+k_{2}}(\mathsf{C})$. We can use the previous
formulas to show that there exists $r\in\mathcal{E}(\mathsf{C})$ for which the
following equations hold:

$\displaystyle(c_{1},c^{\prime}_{1})\oplus(c_{2},c^{\prime}_{2})$
$\displaystyle=(c_{1}+c_{2},r_{1}(m_{1})+r_{2}(m_{2})+(c_{1}+c_{2})^{T}x+e_{1}+e_{2})$
$\displaystyle(\textrm{linearity})$
$\displaystyle=(c_{1}+c_{2},r(m_{1}+m_{2})+(c_{1}+c_{2})^{T}x+e_{3})$
$\displaystyle(\textrm{Proposition \ref{prop:homomorphic-
properties:E:errors}})$

According to Definition 5.18, the previous equations show that
$(c_{1},c^{\prime}_{1})\oplus(c_{2},c^{\prime}_{2})$ is in
$\mathcal{S}^{x}_{\mathsf{C},k_{1}+k_{2}}(m_{1}+m_{2})$.

To show the property satisfied by the operation $\otimes_{\lambda}$, we will
proceed in two steps. First, suppose that $k_{1}k_{2}p<q/p$ and consider the
element $e_{3}=e_{2}r_{1}(m_{1})+e_{1}r_{2}(m_{2})+e_{1}e_{2}$. Since we have
$e_{1}\in\mathcal{I}_{k_{1}}(\mathsf{C})$ and
$e_{2}\in\mathcal{I}_{k_{2}}(\mathsf{C})$, Proposition 5.6 implies that
$e_{3}\in\mathcal{I}_{k_{1}k_{2}p}(\mathsf{C})$. We can use the element
$e_{3}$ to show that there exists $r\in\mathcal{E}(\mathsf{C})$ for which the
following equations hold:

$\displaystyle(r_{1}(m_{1})+e_{1})(r_{2}(m_{2})+e_{2})$
$\displaystyle=r_{1}(m_{1})r_{2}(m_{2})+e_{3}$
$\displaystyle=r(m_{1}m_{2})+e_{3}$ $\displaystyle(\textrm{Proposition
\ref{prop:homomorphic-properties:E:errors}})$

Alternatively, we also have the following identities:

$\displaystyle(r_{1}(m_{1})-e_{1})(r_{2}(m_{2})-e_{2})$
$\displaystyle=(c^{\prime}_{1}-c_{1}^{T}x)(c^{\prime}_{2}-c_{2}^{T}x)$
$\displaystyle=c^{\prime}_{1}c^{\prime}_{2}-\big{(}c^{\prime}_{2}\cdot
c_{1}+c^{\prime}_{1}\cdot c_{2}\big{)}^{T}x+(c_{1}^{T}x)(c_{2}^{T}x)$
$\displaystyle=c^{\prime}_{1}c^{\prime}_{2}-\big{(}c^{\prime}_{2}\cdot
c_{1}+c^{\prime}_{1}\cdot
c_{2}\big{)}^{T}x+\big{(}c_{1}\boxtimes_{\lambda}c_{2}\big{)}^{T}x$
$\displaystyle(\textrm{Proposition \ref{prop:boxtimes_lambda:product}})$
$\displaystyle=c^{\prime}_{1}c^{\prime}_{2}-\big{(}c^{\prime}_{2}\cdot
c_{1}+c^{\prime}_{1}\cdot c_{2}-c_{1}\boxtimes_{\lambda}c_{2}\big{)}^{T}x$
$\displaystyle(\textrm{linearity})$

Our two previous developement give us the following equation:

$c^{\prime}_{1}c^{\prime}_{2}=r(m_{1}m_{2})+\big{(}c^{\prime}_{2}\cdot
c_{1}+c^{\prime}_{1}\cdot
c_{2}-c_{1}\boxtimes_{\lambda}c_{2}\big{)}^{T}x+e_{3}$

According to Definition 5.18, this equation shows that
$(c_{1},c^{\prime}_{1})\otimes_{\lambda}(c_{2},c^{\prime}_{2})$ is in
$\mathcal{S}^{x}_{\mathsf{C},k_{1}k_{2}p}(m_{1}m_{2})$. ∎

In summary of this section, the assertions made in Theorem 5.22 and
Proposition 5.20 affirm that the encryption scheme introduced in section 5.1
qualifies as a leveled fully homomorphic encryption scheme. This holds true
under the condition that $\mathsf{Alice}$ publishes an element of the set
$\mathcal{H}(x|\mathsf{C})$, where $x$ represents the private key, as
constructed in Generation 5.15.

###  5.3. From leveled FHE schemes to proper FHE schemes

This section introduces a refresh operation designed to decrease the
encryption level linked to a ciphertext. Following the definition of this
operation, we proceed to establish an FHE protocol between a user and a
server.

######  Definition 5.23.

Let $\mathsf{C}=(p,q,\omega,u)$ be an arithmetic channel, let $n$ be a
positive integer, and let $x$ be an element in $\mathbb{Z}[X]^{(n)}$. For
every $m\in\mathbb{Z}_{q}$, every pair $(k,k_{0})$ of positive integers such
that $k_{0}\leq k$, we define the function

$\mathsf{refr}_{k,k_{0}}:\mathcal{S}^{x}_{\mathsf{C},k}(m)\to\mathbb{Z}_{q}[X]_{u}^{(n)}\times\mathbb{Z}_{q}[X]_{u}$

such that for every $(c,c^{\prime})\in\mathcal{S}^{x}_{\mathsf{C},k}(m)$, we
have $\mathsf{refr}_{k,k_{0}}((c,c^{\prime}))=(c,c^{\prime}-k_{0}pX^{0})$ in
$\mathbb{Z}_{q}[X]_{u}^{(n)}\times\mathbb{Z}_{q}[X]_{u}$.

######  Definition 5.24 (Level).

Let $\mathsf{C}=(p,q,\omega,u)$ be an arithmetic channel, let $n$ be a
positive integer, and let $x$ be an element in $\mathbb{Z}[X]^{(n)}$. For
every positive integer and every element $e\in\mathcal{I}_{k}(\mathsf{C})$, we
define the _level_ $\mathsf{lvl}(e)$ of $e$ as the positive integer
$k^{\prime}\leq k$ for which the equation
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e)=k^{\prime}p$
holds. As a result, the level of $e$ can also be defined as the smallest
positive integer $k^{\prime}$ for which
$e\in\mathcal{I}_{k^{\prime}}(\mathsf{C})$. By extension, for every encryption
$(c,c^{\prime})\in\mathcal{S}^{x}_{\mathsf{C},k}(m)$, we define the _level_
$\mathsf{lvl}((c,c^{\prime}))$ of the encryption $(c,c^{\prime})$ as the
positive integer $k^{\prime}\leq k$ for which the equation
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(c^{\prime}-c^{T}x)-m=k^{\prime}p$
holds. Similarly, we deduce that the level of $(c,c^{\prime})$ can be defined
as the smallest positive integer $k^{\prime}$ for which
$(c,c^{\prime})\in\mathcal{S}^{x}_{\mathsf{C},k^{\prime}}(m)$.

######  Theorem 5.25 (Proper FHE).

Let $\mathsf{C}=(p,q,\omega,u)$ be an arithmetic channel, let $n$ be a
positive integer, and let $x$ be an element in $\mathbb{Z}[X]^{(n)}$. For
every element $m\in\mathbb{Z}_{q}$, every pair $(k,k_{0})$ of positive
integers such that $k_{0}\leq k<q/p$, and every encryption
$(c,c^{\prime})\in\mathcal{S}^{x}_{\mathsf{C},k}(m)$, the element
$\mathsf{refr}_{k,k_{0}}((c,c^{\prime}))$ belongs to the encryption space
$\mathcal{S}^{x}_{\mathsf{C},k-k_{0}}(m)$ whenever the inequality
$k_{0}\leq\mathsf{lvl}((c,c^{\prime}))$ holds.

###### Proof.

By Definition 5.23, the identity
$\mathsf{refr}_{k,k_{0}}((c,c^{\prime}))=(c,c^{\prime}-k_{0}pX^{0})$ holds. In
particular, if we denote $e^{\prime}=e-k_{0}pX^{0}$, we have the following
development.

$c^{\prime}-k_{0}pX^{0}=r(m)+c^{T}x+e-k_{0}pX^{0}=r(m)+c^{T}x+e^{\prime}$

Let us show that $e^{\prime}$ belongs to $\mathcal{I}_{k-k_{0}}(\mathsf{C})$.
To do so, let us first notice that the subtraction
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e)-\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(k_{0}pX^{0})$
computed in $\mathbb{Z}$ is less than or equal to the integer $(k-k_{0})p$.
Since the inequalities $\mathsf{lvl}(e)-k_{0}\geq 0$ and

$0\leq(k-k_{0})p<kp<q$

hold, we can assert that the element
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e-k_{0}pX^{0})$ is
represented by the subtraction
$\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(e)-\textrm{\textlbrackdbl}\mathsf{C}\textrm{\textrbrackdbl}(k_{0}pX^{0})$
in $\mathbb{Z}_{q}$ (because of Proposition 5.2). As a result, the element
$\mathsf{refr}_{k,k_{0}}((c,c^{\prime}))$ is in the $\mathsf{C}$-encryption
space $\mathcal{S}^{x}_{\mathsf{C},k-k_{0}}(m)$. ∎

######  Remark 5.26 (Arithmetic).

Theorem 5.22 implies that levels follow the arithmetic of ciphertexts.
Specifically, for every arithmetic channel $\mathsf{C}=(p,q,\omega,u)$, if two
ciphertexts in a $\mathsf{C}$-encryption space have levels $k_{1}$ and
$k_{2}$, then their addition is of level $k_{1}+k_{2}$ and their
multiplication is of level $k_{1}k_{2}p$. This means that every algorithm on
ciphertexts made of additions and multiplications has an equivalent on levels
of ciphertexts. Specifically, this equivalent algorithm is obtained by
replacing the addition with the map $(k_{1},k_{2})\mapsto k_{1}+k_{2}$ and the
multiplication with the map $(k_{1},k_{2})\mapsto k_{1}k_{2}p$.

######  Application 5.27 (FHE protocol).

Let $\mathsf{C}=(p,q,\omega,u)$ be an arithmetic channel. Suppose that we have
three parties $\mathsf{Alice}$ (user side), $\mathsf{Bob}$ (user side) and
$\mathsf{Carol}$ (server side). The situation is as follows:

  * 1)

$\mathsf{Alice}$ and $\mathsf{Bob}$ want to collaborate using the server
resources owned by carol $\mathsf{Carol}$;

  * 2)

$\mathsf{Alice}$ owns data $m_{1},m_{2},\dots,m_{d}$ to be uploaded onto
$\mathsf{Carol}$’s server;

  * 3)

$\mathsf{Bob}$ owns an algorithm $F:(x_{1},\dots,x_{d})\mapsto
F(x_{1},\dots,x_{d})$ to be used on $\mathsf{Alice}$’s data;

  * 4)

$\mathsf{Alice}$ encrypts her data $m_{1},m_{2},\dots,m_{d}$ as
$c_{1},c_{2},\dots,c_{d}$ using the encryption scheme described in section 5.1
and chooses an integer $0\leq k_{i}\leq\mathsf{lvl}(c_{i})$ for each
encryption $c_{i}$. Then, $\mathsf{Alice}$ sends the encrypted data
$c_{1},c_{2},\dots,c_{d}$ to $\mathsf{Carol}$ and keeps each $k_{i}$ secret;

  * 4)

$\mathsf{Bob}$ sends his algorithm (made of additions and multiplications) to
$\mathsf{Alice}$ and $\mathsf{Carol}$.

$\textstyle{\mathsf{Alice}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{c,F_{i},k^{\prime}_{i}}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\mathsf{Bob}}$$\scriptstyle{F}$$\scriptstyle{F}$$\textstyle{\mathsf{Carol}}$

After this, $\mathsf{Alice}$ decompose $\mathsf{Bob}$’s algorithm into smaller
sequences of operations $F_{1},F_{2},\dots,F_{K}$ such that each $F_{i}$ is
compatible with the leveled FHE framework of Theorem 5.22. Then,
$\mathsf{Alice}$ translates the additions and multiplications of each
$F_{1},F_{2},\dots,F_{K}$ into corresponding algorithms
$G_{1},G_{2},\dots,G_{K}$ that can be applied on levels (as explained in
Remark 5.26). Next, $\mathsf{Alice}$ applies each algorithm $G_{i}$ on their
corresponding portion of the sequence $k_{1},k_{2},\dots,k_{d}$ and obtains
integers $k_{1}^{\prime},k_{2}^{\prime},\dots,k_{K}^{\prime}$. After these
operations, $\mathsf{Alice}$ sends the following data to $\mathsf{Carol}$:

$(F_{1},F_{2},\dots,F_{K})\quad\quad\quad(k_{1}^{\prime},k_{2}^{\prime},\dots,k_{K}^{\prime})$

  * 5)

$\mathsf{Carol}$ computes each algorithm $F_{i}$ on its corresponding portion
of the encrypted data and refreshes the resulting encrypted $c_{i}^{\prime}$
output using the operation
$\mathsf{refr}_{\mathsf{lvl}(c_{i}^{\prime}),k_{i}^{\prime}}$.

  * 6)

Once all the operations in $F$ have been processed on encrypted data,
$\mathsf{Carol}$ sends the resulting ciphertexts back to $\mathsf{Alice}$, who
may decide to share the decryption with $\mathsf{Bob}$.

In practice, it is advisable for $\mathsf{Alice}$ to select integers $k_{i}$
in a manner that ensures the success of refreshing operations. One approach to
achieve this is by establishing an agreement with $\mathsf{Bob}$ on a specific
class of algorithms that are permitted for application on the encrypted data.

To conclude, the statements of Theorem 5.22 and Proposition 5.20 and Theorem
5.25 show that the encryption scheme defined in section 5.1 defines a proper
fully homomorphic encryption schemes.

###  5.4. Security

The security of the cryptosystem outlined in section 5.1 is contingent upon
the computational complexity of the RLWE problem (see [26]). Specifically, the
challenge lies in the difficulty of deducing the secret key $x$, as defined in
Generation 5.9, solely from the knowledge of the public key $(f,f^{\prime})$
provided in Publication 5.10. Additionally, we assume that the publication of
a $3$-tensor $\lambda$ in the set $\mathcal{H}(\mathsf{C}|x)$ (defined in
Definition 5.14) does not provide enough information about the components of
$x$ to compromise the secure full homomorphic property of ACES.

###  5.5. Implementation

The cryptosystem described in section 5.1 has an existing Python
implementation tailored for the parameter values $\omega=1$ and $N=1$. While
this implementation features a user-friendly suite of functions, it is
important to note that it is not optimized for real-world applications. Its
design is geared towards facilitating research and experimentation. The code
for this package can be accessed on GitHub through the following link:
https://github.com/remytuyeras/aces.

## References

  * [1] Abbas Acar, Hidayet Aksu, A. Selcuk Uluagac, and Mauro Conti.  A survey on homomorphic encryption schemes: Theory and implementation.  ACM Comput. Surv., 51(4), jul 2018.
  * [2] J. Adamek and J. Rosicky.  Locally Presentable and Accessible Categories.  London Mathematical Society Lecture Note Series. Cambridge University Press, 1994.
  * [3] Dan Boneh, Eu-Jin Goh, and Kobbi Nissim.  Evaluating 2-dnf formulas on ciphertexts.  In Joe Kilian, editor, Theory of Cryptography, pages 325–341, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
  * [4] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan.  (leveled) fully homomorphic encryption without bootstrapping.  In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, page 309–325, New York, NY, USA, 2012. Association for Computing Machinery.
  * [5] Zvika Brakerski and Vinod Vaikuntanathan.  Efficient fully homomorphic encryption from (standard) lwe.  Cryptology ePrint Archive, Paper 2011/344, 2011.  https://eprint.iacr.org/2011/344.
  * [6] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song.  Homomorphic encryption for arithmetic of approximate numbers.  Cryptology ePrint Archive, Paper 2016/421, 2016.  https://eprint.iacr.org/2016/421.
  * [7] Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène.  Tfhe: Fast fully homomorphic encryption over the torus.  2018\.  https://eprint.iacr.org/2018/421.
  * [8] Ilaria Chillotti, Marc Joye, and Pascal Paillier.  New challenges for fully homomorphic encryption.  In 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada, 2020.
  * [9] Ronald Cramer and Victor Shoup.  A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack.  In Hugo Krawczyk, editor, Advances in Cryptology — CRYPTO ’98, pages 13–25, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg.
  * [10] T. Elgamal.  A public key cryptosystem and a signature scheme based on discrete logarithms.  IEEE Transactions on Information Theory, 31(4):469–472, 1985.
  * [11] Junfeng Fan and Frederik Vercauteren.  Somewhat practical fully homomorphic encryption.  Cryptology ePrint Archive, Paper 2012/144, 2012.  https://eprint.iacr.org/2012/144.
  * [12] Laurent Fousse, Pascal Lafourcade, and Mohamed Alnuaimi.  Benaloh’s dense probabilistic encryption revisited.  In Abderrahmane Nitaj and David Pointcheval, editors, Progress in Cryptology – AFRICACRYPT 2011, pages 348–362, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
  * [13] P.J. Freyd and G.M. Kelly.  Categories of continuous functors, i.  Journal of Pure and Applied Algebra, 2(3):169–191, 1972.
  * [14] Craig Gentry.  Fully homomorphic encryption using ideal lattices.  In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, page 169–178, New York, NY, USA, 2009. Association for Computing Machinery.
  * [15] Craig Gentry, Amit Sahai, and Brent Waters.  Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based.  Cryptology ePrint Archive, Paper 2013/340, 2013.  https://eprint.iacr.org/2013/340.
  * [16] Shafi Goldwasser and Silvio Micali.  Probabilistic encryption & how to play mental poker keeping secret all partial information.  In Symposium on the Theory of Computing, 1982.
  * [17] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman.  Ntru: A ring-based public key cryptosystem.  In Joe P. Buhler, editor, Algorithmic Number Theory, pages 267–288, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg.
  * [18] G.M. Kelly.  A unified treatment of transfinite constructions for free algebras, free monoids, colimits, associated sheaves, and so on.  Bulletin of the Australian Mathematical Society, 22(1):1–83, 1980\.
  * [19] Saunders Mac Lane.  Categories for the Working Mathematician, volume 5 (2 ed.) of Graduate Texts in Mathematics.  Springer New York, NY, 1978.
  * [20] Adriana López-Alt, Eran Tromer, and Vinod Vaikuntanathan.  On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption.  In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’12, page 1219–1234, New York, NY, USA, 2012. Association for Computing Machinery.
  * [21] Vadim Lyubashevsky, Chris Peikert, and Oded Regev.  On ideal lattices and learning with errors over rings.  In Henri Gilbert, editor, Advances in Cryptology – EUROCRYPT 2010, pages 1–23, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
  * [22] Chiara Marcolla, Victor Sucasas, Marc Manzano, Riccardo Bassoli, Frank H.P. Fitzek, and Najwa Aaraj.  Survey on fully homomorphic encryption, theory, and applications.  2022\.  https://eprint.iacr.org/2022/1602.
  * [23] Pascal Paillier.  Public-key cryptosystems based on composite degree residuosity classes.  In Jacques Stern, editor, Advances in Cryptology — EUROCRYPT ’99, pages 223–238, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg.
  * [24] Oded Regev.  On lattices, learning with errors, random linear codes, and cryptography.  J. ACM, 56(6), sep 2009.
  * [25] Damien Stehlé and Ron Steinfeld.  Making ntru as secure as worst-case problems over ideal lattices.  In Kenneth G. Paterson, editor, Advances in Cryptology – EUROCRYPT 2011, pages 27–47, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
  * [26] Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa.  Efficient public key encryption based on ideal lattices.  In Mitsuru Matsui, editor, Advances in Cryptology – ASIACRYPT 2009, pages 617–635, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.
  * [27] Rémy Tuyéras.  Elimination of quotients in various localisations of premodels into models.  Mathematics, 5(3), 2017.
  * [28] Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan.  Fully homomorphic encryption over the integers.  In Henri Gilbert, editor, Advances in Cryptology – EUROCRYPT 2010, pages 24–43, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.