strictly positive geodesic curvature. Thus, we can regard it as totally convex
disc inside some complete Riemannian surface. (Cf. Example 2 in Section 8).

As it is always the case, $\omega(M,g)<L(\partial M)$. (This inequality has
been proven in [9], Section 6). On the other hand, all free boundary geodesics
necessarily pass through the tip of $M$. Hence, if we now choose $m$ small and
$x_{1}$ large enough, we guarantee that any free boundary geodesic is longer
than $\partial M$. The curve $\beta$ in Figure 1 represents one free boundary
geodesic, whose length coincides with $w_{\ast}$.

The main theorem of [9] implies that $\omega(M,g)$ is realised by the length
of a geodesic loop $\alpha$ based at a boundary point, also depicted in Figure
1. By the rotational symmetry, $S(\partial M)=diam(\partial M)$. (Cf. Example
3 in Section 8). Hence, the endpoints of the two extremal minimising geodesics
$\gamma_{-}$ and $\gamma_{+}$ in Figure 1 determine a pair of points in
$\partial M$ which is a critical point of $\mathcal{D}$ realising $S(\partial
M)$. Notice that the velocity vectors of $\gamma_{\pm}$ point inside the open
region between $\partial M$ and $\alpha$, because they cannot be part of the
loop $\alpha$, or be part of the strictly convex boundary curve, or cross
$\alpha$ by virtue of their minimisation property. Thus, $\partial M$ and
$\alpha$ act as barriers while minimimising the length of curves with
extremities equal to the extremities of $\gamma_{\pm}$.

Therefore the inequalities (1.10.1) hold in this case, that is,

$S(\partial M)<\frac{L(\partial M)}{2}<\omega(M,g)<L(\partial M)<w_{\ast}.$

We finish this section with the proof of a general comparison, of independent
interest.

######  Theorem 7.1.

Let $(M^{2},g)$ be a Riemannian disc with non-negative Gaussian curvature and
strictly convex boundary. Then

$S(\partial M)\leq\omega(M,g)\leq w_{\ast}.$

Moreover, if $S(\partial M)=\omega(M,g)$, then $S(\partial M)=w_{\ast}$ and
the three numbers are equal to the length of a free boundary minimising
geodesic.

###### Proof.

Both inequalities can be obtained as consequences of the existence of the
sweepouts constructed in Sections 3 and 4 of [9] using the curve shortening
process of Birkhoff adapted to the free boundary setting. Indeed, we know that
$w_{\ast}=L(\beta)$ for some free boundary geodesic $\beta$, by [32].
Proposition 4.4 implies that $M$ can be swept out by a path of curves
$\\{c_{t}\\}$ such that $L(c_{t})\leq L(\beta)$. These curves have extremities
in $\partial M$ and form a sweepout of $M$ that is admissible for
$\omega(M,g)$. Therefore, $\omega(M,g)\leq w_{\ast}$.

If $\omega(M,g)$ is realised as the length of a free boundary geodesic, the
same argument produces a path $\\{c_{t}\\}$ which induces a sweepout
$\\{\partial c_{t}\\}$ of $\partial M$ in the sense of Definition 1.2. In this
case, we conclude that $S(\partial M)\leq\omega(M,g)$.

Alternatively, according to [9], $\omega(M,g)=L(\alpha)$ is realised as the
length of a geodesic loop similarly to the configuration of Figure 1. Let then
$R$ be the region bounded by $\partial M\cup\alpha$. We can use Lemma 3.1 of
[9] to sweep $R$ out by curves $\\{c_{t}\\}$ of lengths bounded by
$L(\alpha)$. This is achieved by an application of the adapted Birkhoff’s
shortening process starting with the loop $\alpha$. As before, $\\{\partial
c_{t}\\}$ defines a sweepout of $\partial M$ that is admissible to estimate
$\mathcal{S}(\partial M)$, which implies that $S(\partial M)\leq\omega(M,g)$.

Notice that the curves $c_{t}$ with length close to $L(\alpha)$ are not
minimising. Indeed, $c_{0}=\alpha$ and this curve has the same initial and
final point. In particular, $\mathcal{D}(\partial\alpha)=0$. Similarly,
$\mathcal{D}(\partial c_{t})$ is close to zero for small values of $t>0$.
Therefore, if $\omega(M,g)$ is realised as the length of a loop, then we
actually have $S(\partial M,g)<\omega(M,g)$.

To finish the proof, suppose now that $S(\partial M)=\omega(M,g)$. By the
previous analysis, these two numbers are realised as the length of a free
boundary geodesic $\beta$. It follows that $w_{\ast}$ must coincide with the
first two invariants. Recall that the sweepout $\\{c_{t}\\}$ of $M$ obtained
before satisfies also $L(c_{t})<L(c_{1/2})=L(\beta)$ for all $t\neq 1/2$. If
$\beta$ is not minimising, then $\mathcal{D}(\partial\beta)<L(\beta)$. This
implies that the maximum of $\mathcal{D}(\partial c_{t})$ is strictly smaller
than $L(\beta)=\omega(M,g)=S(\partial M)$, a contradiction. In conclusion,
$\beta$ is a free boundary minimising geodesic, and $\partial\beta$ is a
critical point of $\mathcal{D}$. ∎

##  8\. Examples

######  Example 1.

The equator of the two-dimensional Euclidean sphere of radius one is a
smoothly embedded curve of length $2\pi$. Any critical point of $\mathcal{D}$
consists of a pair of antipodal boundary points, which are joined by
minimising geodesics of length $\pi$ that form a set parametrised by a circle.
Thinking of the equator as the boundary of the southern hemisphere, it is
clear that any pair of antipodal points is joined by a unique free boundary
minimising geodesic, while any two geodesics that lie in different components
of the hemisphere determined by the free boundary geodesic are simultaneously
stationary. The width of the equator is equal to half of its length. This
closed embedded geodesic has Morse index one.

######  Example 2.

Let $(M^{2},g)$ be a Riemannian surface with compact boundary that is strictly
convex in the sense that the geodesic curvature vector of $\partial M$ points
strictly inside $M$. Then $(M^{2},g)$ can be isometrically embedded into a
larger complete Riemannian manifold in such way that the complement of $M$ is
foliated by circles with geodesic curvature vector pointing towards $M$.
(Proof: move $M$ inside by the gradient flow of the distance to the boundary,
pull back the metric, and blow up the collar region into ends that have the
property above, by a suitable conformal factor). By a curvature comparison
argument for curves that lie on one side of the other and intersect
tangentially, the latter condition implies that $M$ contains all geodesics of
this larger manifold with extremities in $M$. In other words, $(M^{2},g)$ is a
totally convex Riemannian surface with smooth compact boundary in some
complete Riemannian surface. In this case, the width of each boundary
component of $\partial M$ is a geometric invariant of $(M^{2},g)$.

######  Example 3.

Let $(M^{2},g)$ be a Riemannian disc with strictly convex boundary as in
Example 2. Assume, in addition, that $(M^{2},g)$ is rotationally symmetric. We
claim that all non-trivial critical points of $\mathcal{D}$ are of the form
$\\{x,A(x)\\}\subset\partial M$, where $A:M\rightarrow M$ represents the
rotation by $180$ degrees. In particular, $d(x,A(x))=diam(\partial M)$ =
$S(\partial M)$ for all $x\in\partial M$.

Indeed, let $\\{x,y\\}\subset\partial M$ be an arbitrary critical point of
$\mathcal{D}$. If $R_{\theta}:M\rightarrow M$ is a rotation by
$\theta\in[0,2\pi)$, then $\\{R_{\theta}(x),R_{\theta}(y)\\}\subset\partial M$
is also a critical point of $\mathcal{D}$, because $R_{\theta}$ is an
isometry. The uniqueness property (Proposition 2.8) then implies that if
$\theta_{0}$ is such that $R_{\theta_{0}}(x)=y$, then $R_{\theta_{0}}(y)=x$.
Therefore $R_{2\theta_{0}}(x)=x$, i.e. $y=R_{\theta_{0}}(x)=A(x)$ is the
rotation of $x$ by $180$ degrees. The claim follows.

######  Example 4.

Given $a>0$, let

$\mathcal{E}_{a}=\Big{\\{}(x,y,z)\in\mathbb{R}^{3}\,|\,x^{2}+y^{2}+\frac{z^{2}}{a^{2}}=1\Big{\\}}$

be an ellipsoid of revolution around the $z$ axis. Given $\delta>0$, the disc
$M_{a,\delta}=\mathcal{E}_{a}\cap\\{z\geq\delta\\}$ has non-negative Gaussian
curvature and strictly convex boundary. According to Example 3, the critical
points of $\mathcal{D}$ are of the form
$\\{(x,y,\delta),(-x,-y,\delta)\\}\subset\partial M$ and satisfy

$d((x,y,\delta),(-x,-y,\delta))=\mathcal{S}(\partial
M_{a,\delta})=diam(\partial M_{a,\delta}).$

For all $a>0$ and $\delta>0$, the critical points bound an unstable free
boundary geodesic that goes through the point $(0,0,a)$.

For $0<a<1$, the critical points bound exactly one minimising geodesic, which
is the free boundary geodesic with length $<L(\partial M_{a,\delta})/2$.

For $a>1$, if $\delta>0$ is sufficiently small, then none of the free boundary
geodesics are minimising, because they all go through $(0,0,a)$ and therefore
have length strictly bigger than half the length of $\partial M_{a,\delta}$.
The boundary points $(x,y,\delta)$ and $(-x,-y,\delta)$ bound two minimising
geodesics that are simultaneously stationary (in fact, one is the reflected
image of each other, by the reflection that fixes the free boundary geodesic
joining $(x,y,\delta)$ and $(-x,-y,\delta)$).

######  Example 5.

Let $\Omega$ be the plane region bounded by an ellipse determined by the
equation $x^{2}/a^{2}+y^{2}/b^{2}=1$, where $a\geq b>0$ will be chosen. Let
$R_{1},R_{2}\subset\Omega$ be the regions represented in Figure 2. Assume that
$\Omega\setminus(R_{1}\cup R_{2})$ is the union of a small collar
neighbourhood of $\partial\Omega$ with a small neighbourhood of the segment
representing the minor axis of the ellipse.

Figure 2.

Let $g$ be a Riemannian metric on $\Omega$ that coincides with the Euclidean
flat metric outside a small neighbourhood of $R_{1}\cup R_{2}$ contained in
$\Omega$, and is very large compared to the Euclidean metric in $R_{1}\cup
R_{2}$ (in the sense that the size of tangent vectors at points in $R_{1}\cup
R_{2}$ measured according to $g$ are much larger than their Euclidean sizes).
In particular, the metric is Euclidean near $\partial\Omega$. Clearly,
$\Omega$ is a totally convex disc with smooth boundary in
$(\mathbb{R}^{2},g)$, where $g$ extends as the Euclidean outside $\Omega$. We
claim that $(\Omega,g)$ contains a minimising geodesic $\gamma$ that is free
boundary stable, and that

$L(\gamma)<2b<\mathcal{S}(\partial\Omega),$

as soon as $b$ and $a$ are chosen appropriately.

In order to see this, let $p_{i}$ and $q_{i}$ be points in $\partial\Omega$ as
indicated in Figure 2. Let $A$ be the closed arc of the ellipse from $q_{3}$
to $q_{2}$ in the counterclockwise direction, and $B$ be the arc from $p_{2}$
to $p_{3}$. Let $q\in A$ and $p\in B$ be a pair of points realising the
distance between $A$ and $B$ with respect to the metric induced by $g$. If the
arcs $A$ and $B$ are large enough compared to $2b$, then $q\in int(A)$, and
$p\in int(B)$. Indeed, a path joining $p_{2}$ or $p_{3}$ to the arc $A$ either
crosses the region $R_{1}\cup R_{2}$, where the metric is large, or goes
around this region. Making $p_{2}$ and $p_{3}$ far enough from the $y$-axis
and from the vertices of the ellipse, we conclude that the distance with
respect to $g$ from $p_{2}$ or $p_{3}$ to $A$ is larger than $2b$. On the
other hand, since the metric is flat near the minor axis we have $d(A,B)<2b$.
This shows that $p\in int(B)$. Similarly we have $q\in int(A)$. In particular,
$\\{p,q\\}$ is a local minimum of $\mathcal{D}$, which implies that there
exists a free boundary minimising geodesic $\gamma$ from $p$ to $q$ which is
free boundary stable (Proposition 2.9) and $L(\gamma)<2b$.

Let $C$ be the arc of the ellipse from $q_{1}$ to $p_{1}$ in the
counterclockwise direction, and $D$ be the arc from $p_{4}$ to $q_{4}$. Assume
that $p_{1}$ is far from $p_{2}$, $q_{1}$ is far from $q_{2}$, and both
$p_{1}$ and $q_{1}$ are far from the tip of the ellipse compared to the value
$2b$. Therefore, $d(p_{1},q_{1})$ is also large compared to $2b$. Moreover, if
$y\in\partial\Omega$ and $d(p_{1},y)<3b$, then $y$ belongs to the open arc of
the ellipse from $q_{1}$ to $p_{2}$. The points $p_{3}$, $p_{4}$, $q_{3}$, and
$q_{4}$ are centrally symmetric to $p_{2}$, $p_{1}$, $q_{2}$, and $q_{1}$,
respectively. Therefore they have analogous properties.

Finally, we can argue that the width of $\partial\Omega$ in $(\Omega,g)$ is
strictly bigger than $2b$. Fix a sweepout $\\{p_{t},q_{t}\\}$ of
$\partial\Omega$. Arguing as in the proof of Proposition 5.2, we conclude that
every sweepout contains a pair $\\{x,-x\\}$ of centrally symmetric points of
$\partial\Omega$. If $x$ belongs to one of the arcs $C$ or $D$, then $-x$
belongs to the other, and $d(x,-x)\geq 3b$. If $x$ belongs to the arc from
$p_{1}$ to $p_{4}$, then $-x$ belongs to the arc from $q_{4}$ to $q_{1}$. Vary
the pair $\\{x,-x\\}$ continuously by pairs of the sweepout until the first
time one has a pair $\\{p_{t_{0}},q_{t_{0}}\\}$ with a point in $C\cup D$.
This happens because otherwise $p_{t}$ and $q_{t}$ would be trapped in the
disjoint arcs from $q_{4}$ to $q_{1}$, and from $p_{1}$ to $p_{4}$. Without
loss of generality, suppose $p_{t_{0}}=p_{1}$. Our choice implies that
$q_{t_{0}}$ belongs to the arc from $q_{4}$ to $q_{1}$. The property obtained
in the preceding paragraph implies that $d(p_{t_{0}},q_{t_{0}})\geq 3b$. Since
the sweepout is arbitrary, we conclude that $S(\partial\Omega,g)>2b$.

######  Example 6.

Consider again the discs $M_{a,\delta}$ inside the ellipsoid $\mathcal{E}_{a}$
from Example 4, where $a>1$ and $\delta>0$ is sufficiently small. Pick
$\varepsilon>0$ and denote by $B_{\varepsilon}$ the open metric ball around
$(0,0,a)$ of radius $\varepsilon>0$. If $\varepsilon>0$ is sufficiently small
depending only on $a$ and $\delta$, no curve in $M_{a,\delta}$ that joins
points $(x,y,\delta)$ and $(-x,-y,\delta)$ and intersects $B_{\varepsilon}$ is
minimising. Thus, no modification of the metric with compact support in
$B_{\varepsilon}$ changes the value of $\mathcal{D}$ on pairs of points in
$\partial M_{a,\delta}$. In fact, one may even attach handles and cross caps
inside this ball, without changing the fact that the width and the diameter of
$\partial M_{a,\delta}$, as the boundary of these compact totally convex
Riemannian surfaces with different topologies, are equal.

In particular, we may even arrange this modification of the metric supported
on $B_{\varepsilon}$ in such way that the map
$A:x\in\Omega_{a,\delta}\mapsto-x\in\Omega_{a,\delta}$ is still an isometry
without fixed points in $\partial\Omega_{a,\delta}$, while $\Omega_{a,\delta}$
is not rotationally symmetric.

######  Example 7.

There are many other interesting examples of smoothly embedded discs in
Riemannian manifolds whose boundaries satisfy one of the equivalent properties
described in Theorem C (Theorem 5.5). For instance, let $x_{0}$ be a point in
a complete Riemannian surface $(M^{2},g)$, and assume $r>0$ is smaller than
the convexity radius of $(M^{2},g)$ at $x_{0}$. Then the geodesic ball
$B_{r}(x_{0})$ is diffeomorphic to a disc and $\partial B_{r}(x_{0})$ is a
smoothly embedded, strictly convex circle, and moreover the minimising
geodesics joining points of $B_{r}(x_{0})$ lie in $B_{r}(x_{0})$ and are
unique. (This is stronger than $(\star\star)$). Given a unit vector $v\in
T_{x_{0}}M$, the geodesic $t\in[-r,r]\mapsto\exp_{x_{0}}(tv)\in M$ is the
unique minimising geodesic joining the points $\exp_{x_{0}}(\pm rv)$. It has
length $2r$. The obvious continuous map $\exp_{x_{0}}(-rv)\in\partial
B_{r}\mapsto exp_{x_{0}}(rv)\in\partial B_{r}$ is therefore a smooth map such
that $d(\exp_{x_{0}}(-rv),\exp_{x_{0}}(rv))=2r$. Since by the triangle
inequality we have $diam(\partial B_{r})=2r$, it follows from Proposition 5.2
that $\mathcal{S}(\partial B_{r})=diam(\partial B_{r})$.

This class of examples also shows that the characterisation in Theorem F
(Theorem 6.1) is sharp, because if a sufficiently small ball $B$ has an
isometric involution fixing the center of $B$, then it has properties
$(\star\star)$ and $\mathcal{S}(\partial B)=diam(B)$. Notice that such ball is
not necessarily rotationally symmetric.

######  Example 8.

Consider the ellipsoid $\mathcal{E}_{a}$ of Example 4. When $a>1$, the
vertical geodesic $\Gamma=\mathcal{E}_{a}\cap\\{x=0\\}$ satisfies
$\mathcal{S}(\Gamma)<diam(\Gamma)=L(\Gamma)/2$. This can be seen from the
estimates for the horizontal sweepouts determined by the intersection of
$\Gamma$ with horizontal planes, and from Lemma 5.6.

######  Example 9.

When $a>1$, the limit $\delta\rightarrow 0$ of the examples described in
Example 6 are examples of fillings of the unit circle
$\\{(x,y)\in\mathbb{R}^{2}\,|\,x^{2}+y^{2}=1\\}$. This is a particular example
of a much more general construction that yields many examples of smoothly
embedded circles $\Gamma$ with $\mathcal{S}(\Gamma)=L(\Gamma)/2$ in Riemannian
spheres. (Cf. [16]).

Let $g$ be a Riemannian metric on the real projective plane $\mathbb{RP}^{2}$.
Let $\gamma$ be the simple closed geodesic that realises the least length
among homotopically non-trivial loops of $(\mathbb{RP}^{2},g)$. The metric $g$
lifts to a Riemannian metric on the sphere $S^{2}$, and $\gamma$ lifts to a
simple closed geodesic $\Gamma$ in $(S^{2},g)$. We claim that
$\mathcal{S}(\Gamma)=L(\Gamma)/2$. In fact, pick any point $x\in\Gamma$, and
consider the lift of $\gamma$ to $(S^{2},g)$ based at $x$. Since $\gamma$ is
homotopically non-trivial, the lift is an open arc of length
$L(\gamma)=L(\Gamma)/2$ that ends at a point $\phi(x)$. Any other curve $c$
joining $x$ and $\phi(x)$ in $(S^{2},g)$ projects down to a homotopically non-
trivial loop, whose length is therefore at least $L(\gamma)=L(\Gamma)/2$.
Thus, $d(x,\phi(x))=L(\Gamma)/2$. In particular, $diam(\Gamma)=L(\Gamma)/2$.
Since the map $x\in\Gamma\mapsto\phi(x)\in\Gamma$ is continuous (it is just
the restriction to $\Gamma$ of the deck transformation of $S^{2}$ that
produces $\mathbb{RP}^{2}$ as a quotient), the claim now follows by Theorem C
(Theorem 5.5).

######  Example 10.

Consider the cylinder $S^{1}\times\mathbb{R}$ endowed with the flat product
metric. Since it is a complete surface foliated by geodesics
$\Gamma_{t}=S^{1}\times\\{t\\}$, $t\in\mathbb{R}$, it is straightforward to
check that the distance between points in $\Gamma_{t}$ is realised by the
shortest arc of $\Gamma_{t}$ determined by these points. By Theorem C (Theorem
5.5), the curves $\Gamma_{t}$ satisfies $S(\Gamma_{t})=L(\Gamma_{t})/2$.
Notice that, as closed geodesics, $\Gamma_{t}$ have Morse index zero.

An example of smoothly embedded circle with the same properties inside a
compact surface can be obtained by capping the cylinder sufficiently far from
$\Gamma_{0}$ on both sides, so that geodesics with extremities in $\Gamma_{0}$
that leave the cylindrical region have length bigger than $L(\Gamma_{0})/2$.

######  Example 11.

For every $a\neq 1$, the ellipse

$\Omega_{a}=\Big{\\{}(x,y)\in\mathbb{R}^{2}\,|\,x^{2}+\frac{y^{2}}{a^{2}}=1\Big{\\}}$

bounds a disc with strictly convex boundary that contains only two non-trivial
critical points of $\mathcal{D}$, namely, $\\{(-1,0),(1,0)\\}$ and
$\\{(0,-a),(0,a)\\}$.

######  Example 12.

Going beyond space forms, different notions of convex subsets of constant
width in Riemannian manifolds have been proposed. For instance,
generalizations of some classical results for convex bodies in the Euclidean
space are obtained in [7], under much more restrictive convexity conditions
than the ones ever assumed in this paper.

The works of Robertson [27] and Bolton [4] proposed a different
generalisation, which does not involve any convexity assumption and has a more
topological flavour. They call a hypersurface $N$ of a complete Riemannian
manifold a transnormal hypersuface when every geodesic that intersects $N$
orthogonally at one point intersects $N$ orthogonally at every other point of
intersection. These hypersurfaces enjoy interesting topological and geometric
properties (see [27], [4], [25], [26], [29] and [30] for a non-exhaustive list
of works on this subject).

If a transnormal circle $\Gamma$ in a Riemannian surface is the boundary of a
compact totally convex region $(\Omega,g)$, then for every point $x$ there
exists a unique $\phi(x)\neq x$ in $\Gamma$ such that $\\{x,\phi(x)\\}$ bounds
a unique free boundary geodesic. Indeed, every such $\Omega$ contains a free
boundary geodesic $\gamma$. Let $\\{p,q\\}=\partial\gamma$. Since $\gamma$
crosses $\partial\Omega$ transversally at $p$ and $q$, if
$\tilde{p}\in\partial\Omega$ is sufficiently close to $p$, then the geodesic
$\tilde{\gamma}$ starting at $\tilde{p}$ normal to $\partial\Omega$ will cross
the boundary curve a second time at a point $\tilde{q}$ near $q$. The
transnormality of $\partial\Omega$ implies that the portion of
$\tilde{\gamma}$ connecting $\tilde{p}$ and $\tilde{q}$ is a free boundary
geodesic. The compactness of the set of proper free boundary geodesics
finishes the argument.

Moreover, by the first variation formula (1.3.1), all the free boundary
geodesics connecting $x$ and $\phi(x)$ have the same length. Also,
$\phi(\phi(x))=x$. The map $x\in\Gamma\mapsto\phi(x)\in\Gamma$ is therefore a
monotone homeomorphism (Lemma 5.1).

It may happen that these free boundary geodesics are not minimising geodesics,
so it is not clear that $\\{x,\phi(x)\\}$ are critical points of
$\mathcal{D}$. However, if moreover $(\Omega,g)$ has property $(\star\star)$,
then it is clear that these free boundary geodesics are minimising, so that
$\\{x,\phi(x)\\}$, $x\in\Gamma$, are in fact critical points of $\mathcal{D}$.
By Theorem C (Theorem 5.5), it follows that
$\mathcal{S}(\partial\Omega)=diam(\partial\Omega)$ in this case.

The class of examples discussed in Example 6 contains examples of discs with
strictly convex boundary with
$\mathcal{S}(\partial\Omega)=diam(\partial\Omega)$ that are not transnormal.
In what follows, we describe three examples of curves that are not
transnormal, and which nevertheless have the same width and diameter.

Let $\mathcal{E}=\mathcal{E}(a,b,c)$ be an ellipsoid
$x^{2}/a^{2}+y^{2}/b^{2}+z^{2}/c^{2}=1$, with $a>b>c$, all close to $1$. This
surface has exactly simple three simple closed geodesics, the curve
$\Gamma=\mathcal{E}\cap\\{x=0\\}$ being the shortest one. We claim that
$S(\Gamma)=diam(\Gamma)=L(\Gamma)/2$, but $\Gamma$ is not transnormal. In
fact, notice that $\mathcal{E}$ is the Riemannian lift of a Riemannian
$\mathbb{RP}^{2}$, and that $\Gamma$ is the lift of the shortest homotopically
non-trivial curve in that $\mathbb{RP}^{2}$. As in Example 9, the first part
of the claim follows. On the other hand, since the two symmetric halves of the
orthogonal geodesics $\mathcal{E}\cap\\{y=0\\}$ and $\mathcal{E}\cap\\{z=0\\}$
to $\Gamma$ have different lengths, $\Gamma$ is not transnormal.

Next we explain how to obtain an example from those of Example 6. Recall that
these examples have a rotationally symmetric part, and a region where the
metric is modified. In the present context, it is convenient to modify the
metric in such a way that the tip $B_{\varepsilon}$ is the graph of a positive
function $z=f(x,y)$ over a disc, with two points of maximum at $(\alpha,0)$
and $(-\alpha,0)$ and one saddle point at $(0,0)$. Assume that the disc
$\Omega$ is invariant under the reflections with respect to the $xz$-plane and
the $yz$-plane. This surface resembles a mountain with rotationally symmetric
base, and two peaks. The symmetries imply that the curves
$\gamma_{1}=\Omega\cap\\{y=0\\}$ and $\gamma_{2}=\Omega\cap\\{x=0\\}$ are free
boundary geodesics. The curve $\gamma_{1}$ goes up the two peaks, while
$\gamma_{2}$ has maximum height at saddle point. If $L(\gamma_{1})\neq
L(\gamma_{2})$, then $\partial\Omega$ cannot be transnormal.

Finally, we present an example in higher codimension. Let $\Gamma$ be a
smoothly embedded circle in the Euclidean space that is contained in the unit
sphere and is centrally symmetric. Since $d(x,y)=||x-y||\leq 2$ and
$d(x,-x)=2$ for every $x$, $y\in\Gamma$, we have $diam(\Gamma)=2$. Moreover,
the map $\phi:\Gamma\rightarrow\Gamma$ defined by $\phi(x)=-x$ is continuous
and satisfies $d(x,\phi(x))=2$. Thus, Theorem C (Theorem 5.5) implies that
$S(\Gamma)=diam(\Gamma)$. However, not all such curves $\Gamma$ are
transnormal in $(\mathbb{R}^{3},can)$.

(a)

(b)

Figure 3. Curve $\Gamma$, two points $A,B\in\Gamma$ (left), and great circles
normal to $\Gamma$ at the points $A$ and $B$.

We exemplify one of such curves in Figure 3. On the left part of the figure,
we see the curve $\Gamma$ inside the unit sphere and two points $A$,
$B\subset\Gamma$ such that the line segment from $A$ to $B$ is perpendicular
at $A$, but not at $B$. On the right part of the figure, this property can be
better visualised. The depicted great circles in the unit sphere which are
normal to $\Gamma$ at $A$ and $B$ define the planes that contain all segments
orthogonal to $A$ and $B$, respectively. These circles cross $\Gamma$ in 6
points, $A$ and $B$ included. However, the line segment connecting $A$ and $B$
is not normal at $B$, since $A$ is not contained in the normal circle of
$\Gamma$ at $B$.

## References

  * [1] I. Adelstein, Minimizing geodesic nets and critical points of distance, Differential Geom. Appl. 70 (2020), 101624, 5 pp.
  * [2] A. Abbondandolo, B. Bramham, U. Hryniewicz, and P. Salomão, Sharp systolic inequalities for Reeb flows on the three-sphere, Invent. Math. 211 (2018), 687-778.
  * [3] L. Ambrozio and R. Montezuma, On the min-max width of unit volume three-spheres, to appear in the Journal of Differential Geometry, preprint arXiv:1809.03638v2.
  * [4] J. Bolton, Transnormal hypersurfaces, Proc. Cambridge Philos. Soc. 74 (1973), 43-48.
  * [5] W. Bos, Kritische Sehnen auf Riemannschen Elementarraumstücken, Math. Ann. 151 (1963), 431-451.
  * [6] C. Croke, Area and length of the shortest closed geodesic, J. Differential Geometry 27 (1988), 1-21.
  * [7] B. Dekster, Width and breadth for convex bodies in Riemannian manifolds, Arch. Math. 58 (1992), 190-198.
  * [8] S. Donato, The first p-widths of the unit disk. J. Geom. Anal. 32 (2022), no. 6, Paper No. 177, 38 pp.
  * [9] S. Donato and R. Montezuma, The first width of non-negatively curved surfaces with convex boundary, preprint arXiv:2211.14815.
  * [10] J. P. Fillmore, Symmetries of surfaces of constant width, J. Differential Geometry 3 (1969), 103-110.
  * [11] T. Frankel, On the fundamental group of a compact minimal submanifold, Ann. of Math. 83 (1966), 68-73.
  * [12] A. Fraser and M. Li, Compactness of the space of embedded minimal surfaces with free boundary in three-manifolds with nonnegative Ricci curvature and convex boundary, J. Differential Geom. 96 (2014), no.2, 183-200.
  * [13] A. Girouard and I. Polterovich, Spectral geometry of the Steklov problem (survey article), J. Spectr. Theory 7 (2017), no. 2, 321-359.
  * [14] H. Gluck and W. Ziller, Existence of periodic motions of conservative systems. Seminar on minimal submanifolds, 65-98, Ann. of Math. Stud., 103, Princeton Univ. Press, Princeton, NJ, 1983.
  * [15] M. Gromov, Curvature, diameter and Betti numbers, Comment. Math. Helv. 56 (1981), no. 2, 179-195.
  * [16] M. Gromov, Filling Riemannian manifolds, J. Differential Geom. 18 (1983), no. 1, 1-147.
  * [17] K. Grove and K. Shiohama, A generalized sphere theorem, Ann. of Math. (2) 106 (1977), no. 2, 201-211.
  * [18] M. Li, Chord shortening flow and a theorem of Lusternik and Schnirelmann, Pacific J. Math. 299 (2019), no. 2, 469-488.
  * [19] L. Lusternik and L. Schnirelmann, Méthodes Topologiques dans les problèmes variationnels, Hermann and Cie, éditeurs, Paris, 1934.
  * [20] F. C. Marques and A. Neves, Rigidity of min-max minimal spheres in three-manifolds. Duke Math. J. 161 (2012), no. 14, 2725-2752.
  * [21] F. C. Marques and A. Neves, Morse index and multiplicity of min-max minimal hypersurfaces. Camb. J. Math. 4 (2016), no. 4, 463-511.
  * [22] W. Meyer, Toponogov’s Theorem and Applications, Lecture Notes, College on Differential Geometry, Trieste 1989. Digital version publicly available at https://indico.ictp.it/event/a02178/contribution/8/material/0/0.pdf
  * [23] A. Nabutovsky and R. Rotman, Linear bounds for lengths of geodesic loops on Riemannian 2-spheres, J. Differential Geom. 89, no. 2 (2011): 217-32.
  * [24] J. Milnor, Morse Theory, Annals of Mathematics Studies, No. 51 Princeton University Press, Princeton, N.J. 1963 vi+153 pp.
  * [25] S. Nishikawa, Transnormal hypersurfaces: generalized constant width for Riemannian manifolds, Tohoku Math. J. (2) 25 (1973), 451-459.
  * [26] S. Nishikawa. Compact two-transnormal hypersurfaces in a space of constant curvature, J. Math. Soc. Japan 26 (1974), 625-635.
  * [27] S. A. Robertson, Generalised constant width for manifolds, Michigan Math. J. 11 (1964), 97-105.
  * [28] Luis A. Santaló, Integral Geometry and Geometric Probability, Addison-Wesley, Reading, MA, 1976.
  * [29] B. Wegner, Globale Sätze über Raumkurven konstanter Breite I, Math. Nachr. 53 (1972), 337-344.
  * [30] B. Wegner, Globale Sätze über Raumkurven konstanter Breite II, Math. Nachr. 67 (1975), 213-223.
  * [31] A. Weinstein., Periodic orbits for convex Hamiltonian systems. Ann. of Math. (2) 108 (1978), no. 3, 507-518.
  * [32] X. Zhou, On the free boundary min-max geodesics, Int. Math. Res. Not. IMRN 2016, no. 5, 1447-1466.


# Near Threshold Computation of Partitioned Ring Learning With Error (RLWE)
Post Quantum Cryptography on Reconfigurable Architecture

Paresh Baidya1, Swagata Mondal2, Rourab Paul3 Department of CSE, Siksha O
Anusandhan (Deemed to be University), Bhubaneswar, Odisha India Siksha O
Anusandhan, Bhubaneswar, India1,3,
Dept. Electronics and Communication, Jalpaiguri Government Engineering
College, Maulana Abul Kalam Azad University 2

###### Abstract

Ring Learning With Error (RLWE) algorithm is used in Post Quantum Cryptography
(PQC) and Homomorphic Encryption (HE) algorithm. The existing classical crypto
algorithms may be broken in quantum computers. The adversaries can store all
encrypted data. While the quantum computer will be available, these encrypted
data can be exposed by the quantum computer. Therefore, the PQC algorithms are
an essential solution in recent applications. On the other hand, the HE allows
operations on encrypted data which is appropriate for getting services from
third parties without revealing confidential plain-texts. The FPGA based PQC
and HE hardware accelerators like RLWE is much cost-effective than processor
based platform and Application Specific Integrated Circuit (ASIC). FPGA based
hardware accelerators still consume more power compare to ASIC based design.
Near Threshold Computation (NTC) may be a convenient solution for FPGA based
RLWE implementation. In this paper, we have implemented RLWE hardware
accelerator which has 14 subcomponents. This paper creates clusters based on
the critical path of all 14 subcomponents. Each cluster is implemented in an
FPGA partition which has the same biasing voltage $V_{ccint}$. The clusters
that have higher critical paths use higher $V_{ccint}$ to avoid timing
failure. The clusters have lower critical paths use lower biasing voltage
$V_{ccint}$. This voltage scaled, partitioned RLWE can save $\sim$6% and
$\sim$11% power in Vivado and VTR platform respectively. The resource usage
and throughput of the implemented RLWE hardware accelerator is comparatively
better than existing literature.

###### keywords:

FPGA partition, Low Power, Post quantum, Ring-learning with error

##  1 Introduction

Lattice based cryptography is currently considered as one of the most secure
solutions as compared to classical cryptography schemes. The discrete
logarithm (Elliptic Curve Cryptography), RSA and ECDSA classical schemes are
used to secure Internet communications. These asymmetric key crypto-systems
are based on the hardness of prime factor and discrete logarithm. However,
asymmetric key crypto-systems are no longer secure under quantum attacks. Even
in brute force, Grover’s quantum algorithm [1] reduces the searching space of
symmetric key cryptography: Advanced Encryption Scheme (AES) from $O(2^{n})$
to $O(2^{n/2})$, where n is the key size. That means AES-256 is as secure as
AES-128. However, no such computationally strong quantum computer has been
developed yet. IBM and Google have claimed to develop such computationally
extensive quantum computers within a few years. Post-quantum crypto algorithms
generally deal with non-quantum operations but it strongly resists both
classical and quantum attacks. Mainly there are four post quantum cryptography
schemes: Code based cryptography, Lattice based cryptography, Hash based
cryptography and Multivariate quadratic cryptography. Among all these schemes
lattice based cryptography(LBC) is computationally efficient. On 2005, O.
Regev [2] first introduced a lattice based cryptography schemes name as
Learning with error (LWE). Later LBC becomes more popular for its significant
theoretical progress [2, 3]. The LBC becomes more suitable for real life
applications when it was implemented in software and hardware platform by
articles [4, 5, 6, 7, 8]. On the other hand, post-quantum cryptography finds
its application in more advanced schemes such as fully homomorphic encryption,
which allows the operations on the encrypted data without revealing any
information to the third party.

For hardware implementation of RLWE as PQC and RLWE as HE, designer can choose
either FPGA or ASIC platform. In practical, FPGA based PQC and HE hardware
accelerators like RLWE is much cost-effective compared to ASIC. However, FPGA
based hardware accelerator is less energy efficient compared to ASIC [9]
because of its programmable switch. An experimental study [10] shows power
consumption of 8 bit full adder in Xilinx XC4003A is 100 times more compared
to CMOS ASIC platform. The implementation of 8-bit adder in FPGA platform
consumed the power 4.2mW/MHz at 5V and the same implementation in ASIC
consumed 5.5uW/MHz at 3.3V [10]. The power consumption of FPGA based design is
crucial specially for battery powered embedded system. Near Threshold
Computation (NTC) may be an appropriate solution to reduce the power
consumption of FPGA based RLWE implementation.

To the best of our knowledge, all the implementations [5, 11, 4, 12] on RLWE
focuses on the speed and resource optimization of the encryption and
decryption scheme. The primary goal of this paper is to reduce the power
consumption of the RLWE hardware.

###  1.1 Related Work

O. Regev [2] introduced the first hardness proof of LWE cryptography in 2005.
Later, various hardware and software implementation of LWE were proposed.
There are many literature which implemented various subcomponents of RLWE
algorithm. The polynomial multiplication, polynomial division and gaussian
sampler used to generate error polynomials are the most challenging
subcomponents of RLWE. Howe et. al [11] proposed first hardware architecture
for a standard lattice based cryptography (LWE) on a Spartan-6 FPGA platform
on 2016. The primary contribution of this paper is area optimization of
Gaussian Sampler by balancing area and performance. Poppelman et al. [13]
reported a hardware implementations of gaussian sampler of RLWE accelerator.
They implemented Cumulative Distribution Table (CDT) based Gaussian sampler on
reconfigurable hardware. Additionally, authors compared CDT based gaussian
sampler and Bernoulli sampler. Roy et al. [7] implemented gaussian sampler
using Knuth Yao algorithm for sampling from the discrete gaussian
distribution. Poppelman et al. [14] implemented a polynomial multiplier which
stores all twiddle factors in a dedicated memory required for NTT computation.
Article [5] reduces the key size of the conventional LWE schemes and
implements a compact and efficient LWE hardware. The article [5] compared LWE
hardware and software implementations with Lindner and Peikert’s design [15].
Article [5] introduced LWE-matrix and LWE-polynomial and compared these
variants of LWE. Article [5] discarded the idea of LWE-matrix because of its
large area consumption, they have only implemented RLWE-polynomial. Poppelman
et al. [4] implements an efficient hardware of RLWE on Virtex 6 FPGA which can
fit on a low-cost Spartan-6 FPGA. This hardware accelerator improved the work
of [5]. Article [6] proposed a lightest RLWE encryption scheme by reducing the
resource, compared with the high speed implementation of [4]. Roy et al.[12]
implemented a compact ring-LWE coprocessor on Virtex 6 FPGA where they
optimized NTT polynomial multiplication and reduced the computation cost of
the twiddle factors by avoiding the pre-computation overhead. A variation of
the Native Title Research Unit (NTRU) Encrypt system with a quantum security
reduction is used in [16]. Its security is based on the standard model’s LWE
problem in polynomial rings. All the above mentioned RLWE implementations have
mostly focussed on area versus speed issue. More speed causes more area and
more area causes more power consumption. Without affecting the datapaths (area
vs speed), the conventional low power solutions mostly deal with clock gating,
power gating, dynamic voltage and frequency islands, retention power gating,
save and restore power gating architectures. To the best our knowledge. this
is the first RLWE hardware accelerator based on dynamic voltage island concept
where different voltage islands run with near threshold voltages

###  1.2 Proposed RLWE

The literature of RLWE competes the growing high speed applications by
increasing throughput of the architecture. The throughput is mostly achieved
by more parallelism which causes more power consumption. Power consumption is
a severe concern for embedded systems but existing literature has not explored
the possibilities of Near Threshold Computation (NTC) in any PQC
implementation. To the best of our knowledge our proposed RLWE is the first
NTC in FPGA/ASIC platform. In our implementation we designed a RLWE dedicated
hardware which has 14 subcomponents. The critical path of all these
subcomponents are measured and based the value of critical path 4 cluster
algorithms create groups with these 14 subcomponents. The FPGA is partitioned
and different partitions has different biasing voltage $V_{ccint}$. The group
having higher value of critical path is placed in a partition which have
higher $V_{ccint}$ and the group having lower value of critical path is placed
in a partition which have lower $V_{ccint}$. The primary contribution of our
paper is stated below:

  * •

This paper designs and implements RLWE crypto algorithm in Artix-7 (28nm)
FPGA. The RLWE has 14 subcomponents such as Random Number Generator (RND),
Poly_div, NTT Controller, Polynomial Multiplier, Read only Memory (ROM),
Scanner, Datapath Controller, Convolution Controller, Poly_add, reader,
Distance, Row Column Controller and 2 dual port Random Access Memory (RAM).

  * •

The cluster algorithms create groups of subcomponents which have similar
critical paths. Each group are placed in a partitioned FPGA where each
partition runs with different $V_{ccint}$. The group(s) with lower critical
path(s) is placed in a lower $V_{ccint}$ partition and the group(s) with
higher critical path(s) is placed in a higher $V_{ccint}$ partition.

  * •

The proposed FPGA based voltage scaled RLWE can save 11% power consumption in
VTR tool. The throughput, resource and power consumption of proposed RLWE is
reasonably better compared to existing RLWE.

The rest of the paper is organised as follows: Sec. 2 states the background of
the RLWE algorithm followed by Sec. 3 which gives a preliminary idea about
hardware implementation of RLWE. Next, in Sec. 4, the The tool flow of the
proposed model is described. In Sec. 5, the four cluster algorithm used to
partition the FPGA is discussed and in Sec. 6.1 and Sec. 7, the proposed
algorithm to calculate biasing voltage and results are stated respectively.
Finally, Sec. 8. concludes the paper

##  2 The Ring-LWE Schemes

The Learning With Error (LWE) was proposed by O Regev in [2] 2005\. The LWE
become popular because it is developed in secure lattice based cryptosystem
which resists quantum attacks. Later LWE achieves computational efficiency and
it reduces the key size by adopting polynomial Ring [17]. The LWE schemes
perform in $R_{q}=Z_{q}[x]/<f>$, where $f$ is irreducible polynomial of degree
$n-1$, and $n=2^{k}\geq 1$ and a prime $q$ is chosen such a way that
$q\equiv~{}1~{}mod~{}2n$. There is an error distribution called discrete
Gaussian distribution $\chi_{\sigma}$ with the standard deviation $\sigma>1$
and mean 0. The LWE scheme defined as follows:

  * •

KeyGEN($a$): choose $r_{1}$,$r_{2}\in R_{q}$ sampled from $\chi_{\sigma}$ .
Let $p=r_{1}-a\ast r_{2}$. The public key is $(a,p)$ and private key is
$r_{2}$.The polynomial $a\in R_{q}$ chosen uniformly during the key
generation.

  * •

EnCrypt($a,p,m$): choose error polynomials $e_{1},e_{2},e_{3}\in R$ sampled
from $\chi_{\sigma}$. Then compute the cipher text as a polynomial

$c_{1}=a\ast e_{1}+e_{2}$ (1) $c_{2}=p\ast e_{1}+e_{3}+\tilde{m}$ (2)

where $\tilde{m}isencode(m)$ and $c_{1}$ and $c_{2}$ are the encrypted
message.

  * •

DeCrypt($c_{1},c_{2},r_{2}$): Decryption process requires to compute below
equation.

$m^{\prime}=c_{1}\ast r_{2}+c_{2}$ (3)

Thereafter, to get the original message $m$, it needs to decode $m^{\prime}$.

##  3 Hardware Architecture of RLWE

The proposed $RLWE$ has 14 components such as Random Number Generator (RND),
Polynomial Divider (Poly_Div), NTT Controller, Polynomial Multiplier,
Polynomial Subtraction (Sub_mod), Scanner, Datapath Controller, Convolution
Controller, Polynomial Adder (Poly_add), reader, Distance, Row Column
Controller and 2 dual port Random Access Memory (RAM).The main components in
the architecture are: the memory file, Gaussian sampler, random number
generator,NTT controller and datapath controller. The brief description of all
hardware components are stated below:

###  3.1 Random Number Generator (RND)

This paper uses Trivium Random [18] number generator to generate error
polynomial $e_{3}$. In our application the secret key required for the RLWE is
predefined. In real application the secret key should be generated randomly
which can be done by the Trivium Random Number Generator. Trivium require one
key and initialize vector to generate random numbers.

###  3.2 Polynomial Divider (poly_div)

The polynomial divider is required to divide polynomials. The resultant value
of all the arithmetic operations stated in equ. 1, equ. 2 and equ. 3 need to
bring under $R_{q}=Z_{q}[x]/<f>$.

###  3.3 Dual Port RAM

This ram stores the public key, message, gaussian sample value required for
RLW execution.

###  3.4 Datapath Controller

The Datapath Controller has three sub components such
as:$Polynomial~{}Multiplier$, $Polynomial~{}Adder(poly\\_add)$ and
$PolynomialSubtraction(Sub\\_mod)$ which are used to multiply, addition and
subtraction of the polynomials.

####  3.4.1 Polynomial Multiplier

The polynomial multiplier (poly_mul) is required to multiply $a$ and $e_{1}$
in equ. 1 and $p$ and $e_{1}$ in in equ. 2

####  3.4.2 Polynomial Adder (poly_add)

The polynomial Adder (Poly_add) is required to add polynomials $a\ast e_{1}$
and $e_{2}$ in equ. 1 and $p\ast e_{1}$, $e_{3}$ and $\tilde{m}$ in equ. 2.

####  3.4.3 Polynomial Subtraction (Sub_mod)

The Polynomial Subtraction (Sub_mod) is required to subtract polynomials. This
block is required when Polynomial Divider (poly_div) will perform.

###  3.5 Convolution Controller

The convolution controller decides whether addition or multiplication will be
executed. This block used to control the Datapath Controller.

###  3.6 reader

The reader block perform loading operation to load the coefficients of
polynomials and Gaussian noise coefficients. It also encode the message bit
before make into cipher text.

###  3.7 NTT Controller

In RLWE scheme, polynomial multiplication is one of the the main operation of
the encryption and decryption process. hardware implementation of coefficient
wise multiplication of two polynomial functions is computationally expensive.
Therefore, we convert the coefficient wise representation to point wise
representation using the Number Theoretic Transformation (NTT).
$NTTController$ performs the NTT operation on the polynomial functions
$a,p,r_{2},e_{1},e_{2},e_{3}$ to generate $\tilde{a}$, $\tilde{p}$,
$\tilde{r_{2}}$, $\tilde{e_{1}}$, $\tilde{e_{2}}$, $\tilde{e_{3}}$.

###  3.8 Gaussian Sampler:scanner, distance, row column controller

The Gaussian Sampler is based on Knuth Yao Sampler [19]. The Knuth Yao Sampler
is a tree based sampler which stores the binary expansion of the samples in a
probability matrix. This probability matrix stores probabilities of the
samples. Roy et al.[7] implemented the first hardware of Gaussian sampler
using Knuth Yao algorithm which used pre-computed table of the probability
matrix. Knuth Yao algorithm uses a random walk model for sampling process.
This sampling process creates a discrete distribution generating (DDG) tree
using the probability matrix. Our $Gaussian~{}Sampler$ has three subcomponents
such as: $scanner$, $distance$, $row~{}column~{}controller$ modules which are
dedicated for traversing the tree, scanning the bit from the ROM and calculate
the distance in the tree of visited node and intermediate node. The detail of
the Knuth Yao sampler and DDG tree are describe in [19].

####  3.8.1 Scanner

Scanner block performs the scanning operation on the ROM block. It scans the
bits from a ROM word. When all bits are read from a ROM word then it fetch
next ROM word to scan.

####  3.8.2 Row ColumnController

Row ColumnController has two registers: an up counter named as
$column\\_length$ and a down counter named as $row\\_number$. The
$column\\_length$ stores the length of the different column length of the
probability matrix. At the first step of column scanning process,
$row\\_number$ is initialized by the $column\\_length$. If the $row\\_number$
reaches to zero, the column scanning process is completed.

####  3.8.3 Distance

The distance block requires to construct the DDG tree of the probability
matrix. For this purpose a subtracter is used to control the random walk. When
the subtracter value is $<0$, then it indicates completion of the sampling
operation. After the completion of the sampling operation, the
$row~{}column~{}controller$ selects current $row\\_number$ as a sample output.

##  4 Tool Flow

This paper uses two environments 1)Python-Vivado and 2) Python-VTR. In Python-
Vivado environment, the vivado generates the synthesis report which includes
timing report of RLWE. The timing report consists of all timing related
information of RLWE including the critical path length of all design paths.
This timing report is sent to python environment to cluster the 14
subcomponents of RLWE using cluster algorithms mentioned in Sec. 5. This
python environment generates the Xilinx Design Constraints (XDC) file which
mentions coordinates of all 14 subcomponent of RLWE in FPGA floor. This
coordinates of RLWE subcomponents are generated based on the partition or
cluster.This XDC then includes in the implementation process of of $Vivado$
environment. The $Vivado$ used Artix 7, 28 nm FPGA. The VTR [20] also uses the
same process as mentioned for $Vivado$. VTR generates Synopsys Design
Constraint (SDC) file instead of XDC. The VTR uses 3 academic FPGAs : 22nm,
45nm and 180nm.

##  5 Cluster Algorithms

This paper analyses four clustering algorithms to group the different sub
components of RLWE hardware accelerator. All these four algorithms follow
different set of rules to find the similarity of the data in the data
distribution. Based on our design requirements this paper implements four
algorithms as stated below:

###  5.1 K-Means Clustering

K-Means clustering algorithm performs on data to find K division sto satisfy a
certain criterion. Firstly, it computes the distance between the data points
and the randomly initialized centroids [21], then accordingly form the cluster
of all the data which are close to the center. This iterative process is
repeated until the criterion of the functions converges to the local minimum.
Euclidean distance is used to compute distances between the data and its time
complexity is $\mathcal{O}(Kn)$, where K number of cluster and n number of
data.

###  5.2 DBSCAN

The DBSCAN algorithm works on the assumption that clusters are in high-density
regions and outliers tend to be in low-density regions. Unlike the K-Means
algorithm, DBSCAN does not require the declaration of number of clusters
beforehand. This algorithm finds the number of clusters [22] based on two
parameters $\mathbb{epsilon}$ and $\mathbb{minpoint}$. The $\mathbb{epsilon:}$
is a radius of the circle around a particular point that is to be considered
as in the neighborhood of the other point. The $\mathbb{minpoint:}$ is the
threshold on the least number of points in the circle to be considered as core
points. To find the cluster DBSCAN choose any arbitrary point p that has not
been visited before and takes all the points density-reachable from p with
respect to epsilon and minpoints then a cluster is started. If there are less
number of points than the minpoints, p point consider noise. In a newly
created cluster, if all points are marked as accessed, then same process used
to deal with unvisited points and create a new cluster. This process will
continue until all points are marked in cluster or noise. The main advantage
of DBSCAN algorithm over the other algorithm is that it can identify the
outlier point as a noise. The time complexity of this algorithm is
$\mathcal{O}(n)$ for reasonable epsilon.

###  5.3 Mean-Shift Clustering

Mean Shift Clustering [23] algorithm is based on the concept of Kernel Density
Estimation (KDE). KDE assumes that the data points are sampled from a
probability distribution and estimate the distribution by a weight function
named as Kernel on each point in the data set. Among many kernels, the
Gaussian kernel is the most popular. The mean shift algorithm works in such a
way that the points climb uphill to the nearest peak on the KDE surface by
iteratively shifting each point of the data set. It starts with a selected
random point as the center of the kernel considering a circle having a certain
radius in the data set. The kernel is then moved towards a higher density
region by shifting the centroid to the mean of the points within the circle of
the center. The mean shift clustering does not need prior knowledge of the
number of clusters. It needs only one parameter: bandwidth to determine the
number of clusters. This clustering algorithm is computationally expensive
compared to K-means algorithm, time complexity in lower dimensions is
$\mathcal{O}(n*log(n))$.

###  5.4 Hierarchical Clustering

The Hierarchical clustering [24] algorithm start with every point is its own
cluster and compute distance matrix between two clusters based upon chosen
distance measurement method(in this case Euclidean distance). Then it choose
two clusters to be merged that has the smallest distance.This process will
repeat until all clusters grouped into a single cluster.The dendogram creates
a binary tree for visualizing the hierarchy of clusters. The number of
clusters can be determine from the dendogram. This algorithm is
computationally expensive for large datasets, having a time complexity of
$\mathcal{O}(n^{3})$ where n is the number of data-points.

(a)

(b)

(c)

(d)

Figure 1: Clustering Algorithms

##  6 Voltage Calibration and ErrorControl Unit

The most challenging part of NTC is (i)Actual voltage allocation for specific
FPGA partition and (ii)Run time timing errors.

###  6.1 Offline Voltage Calibration Algorithm

The proposed voltage scaled RLWE has 14 hardware components. These hardware
components have different critical paths. The 4 cluster algorithms mentioned
in Sec. 5 group these 14 components in different voltage island. Each FPGA
partition has different biasing voltage $V_{CCint}$. The designer knows if the
critical path of a hardware components is more, it needs more amount of
$V_{CCint}$ to avoid timing failure. However, designer does not know the
actual amount of $V_{CCint}$ required for particular length of critical path.
This calibration of $V_{CCint}$ depends on several design constraints, such as
number of partition $P$, critical path $C_{i}$ and critical region
($V_{ccintmax}-V_{ccintmin}$) as shown in Fig. 3. This Offline Voltage
Calibration Algorithm has two parts: (i)Average Critical Path of each
Partition shown in Algorithm 1 (ii)Voltage Scaling of each Partition shown in
2.

Calculation of average critical path $CP_{k}$ describes in Algorithm. 1. Total
critical path $A_{critical}$ of each partition is computed in Line 4 of
Algorithm. 1. Thereafter, Line 6 calculates the average critical path $CP_{k}$
of $k^{th}$ partition based on $A_{critical}$ and number of components $N(k)$
in $k^{th}$ partition. The distributed scaled voltage $VP_{k}$ for each
partition is computed by Algorithm. 2. It calculates voltage $V_{r/c}$ for per
unit critical path from $V_{ccintmax}$ and $V_{ccintmin}$ as shown in Line 5.
After that, the $VP_{k}$ of the $k^{th}$ partition is calculated depends on
the $V_{r/c}$, average critical path $CP_{k}$ and $V_{ccintmin}$.

###  6.2 Timing Errors

Despite of accurate $V_{CCint}$ allocation, NTC on RLWE may causes timing
errors. This paper designs a timing error control unit which uses razor flip
in the datapath of each RLWE subcomponents. The razor or shadow flipflop in
FPGA platform is driven by a delayed clock [25]. We have assumed that one or
more timing pathways leading from any of the source registers terminate at a
circuit register $R$. The shadow register $S$ samples the same data as the
main register $R$, but it does so on a delayed clock $DCLK$ that is delayed
from $CLK$ by $T_{del}$. Any data that enters the circuit after $R$ samples
but prior to $S$ samples will result in a disparity between the two registers,
which is identified by the error flag $F$. This razor flipflop is put in the
datapaths of the subcomponents. Razor increases the resource consumption, but
it also has the ability to detect runtime timing errors in RLWE caused by
near-threshold biassing voltage. Fig.3 displays the timing diagram for the
razor.

Figure 2: Voltage behaviour for $V_{CCint}$

Figure 3: Razor Timing Diagram of Fault Detection

Table 1: K-Means Cluster # Partition | Hardwares | Critical Paths(ns) | $V_{ccint}(Volt)$
---|---|---|---
1 | Dual port ram:1 | 2.217 |
| Dual port ram:2 | 2.217 |
| Row Column Controller | 1.9 | 0.96
| Distance | 1.9 |
| reader Wrapper | 2.394 |
| Poly_add | 2.101 |
2 | Datapath | 8.603 | 1.00
3 | Scanner | 3.332 | 0.97
| ROM | 3.654 |
4 | Polynomial multiplier | 5.327 | 0.98
5 | NTT Controller | 1.17 |
| Convolution Controller | 1.725 | 0.95
| Poly_div | 1.323 |
| rand | 1.412 |
Table 2: DBSCAN Cluster # Partition | Hardwares | Critical Paths(ns) | $V_{ccint}(Volt)$
---|---|---|---
1 | Dual port ram:1 | 2.217 |
| Dual port ram:2 | 2.217 | 0.96
| reader Wrapper | 2.394 |
| Poly_add | 2.101 |
2 | Row Column Controller | 1.9 |
| Distance | 1.9 | 0.96
| Convolution Controller | 1.725 |
3 | Datapath | 8.603 | 0.98
4 | Scanner | 3.332 | 0.97
| ROM | 3.654 |
5 | Polynomial multiplier | 5.327 | 0.97
6 | NTT Controller | 1.17 |
| Poly_div | 1.323 | 0.96
| rand | 1.412 |
Table 3: Mean-Shift Cluster # Partition | Hardwares | Critical Paths(ns) | $V_{ccint}(Volt)$
---|---|---|---
1 | Dual port ram:1 | 2.217 |
| Dual port ram:2 | 2.217 |
| Row Column Controller | 1.9 | 0.96
| Distance | 1.9 |
| reader Wrapper | 2.394 |
| Poly_add | 2.101 |
| NTT Controller | 1.17 |
| Convolution Controller | 1.725 |
| Poly_div | 1.323 |
| rand | 1.412 |
2 | Datapath | 8.603 | 1.00
3 | Scanner | 3.332 | 0.97
| ROM | 3.654 |
4 | Polynomial multiplier | 5.327 | 0.98
Table 4: Hierarchical # Partition | Hardwares | Critical Paths(ns) | $V_{ccint}(Volt)$
---|---|---|---
1 | Dual port ram:1 | 2.217 |
| Dual port ram:2 | 2.217 |
| Row Column Controller | 1.9 | 0.96
| Distance | 1.9 |
| reader Wrapper | 2.394 |
| Poly_add | 2.101 |
| Convolution Controller | 1.725 |
2 | Datapath | 8.603 | 0.98
3 | Scanner | 3.332 | 0.97
| ROM | 3.654 |
4 | Polynomial multiplier | 5.327 | 0.98
5 | NTT Controller | 1.17 |
| Poly_div | 1.323 | 0.96
| rand | 1.412 |
Algorithm 1 Average Critical Path of each Partition

1:$n_{k}^{\prime}s,P$ $\triangleright$ $k\leftarrow 0,1,2,....P$

2:$A_{Critical}\leftarrow 0$

3:for $k\leftarrow 1$ to $P$ do

4: for $i\leftarrow 1$ to $N(k)$ do

5: $A_{Critical}$ $\leftarrow$ $A_{Critical}+C_{i}$

6: end for

7: $CP_{K}\leftarrow A_{Critical}/N(k)$

8:end for

Algorithm 2 Voltage Scaling of each Partition

1:$V_{ccint_{max}},V_{ccint_{min}},CP_{K}^{\prime}s$ $\triangleright$
$k\leftarrow 0,1,2,....P$

2:$T_{Critical}\leftarrow 0$

3:for $k\leftarrow 1$ to $P$ do

4: $T_{Critical}\leftarrow T_{Critical}+CP_{K}$

5:end for

6:$V_{r/c}\leftarrow\frac{V_{ccint_{max}}-V_{ccint_{min}}}{T_{Critical}}$

7:for $k\leftarrow 1$ to $P$ do

8: $VP_{k}\leftarrow V_{ccint_{min}}+CP_{K}*V_{r/c}$

9:end for

##  7 Result and Implementation

The aforementioned 5 cluster algorithms are implemented by Python using the
Scikit-learn library for two environments (i) Commercial Vivado tool with
Artix-7 FPGA (ii) VTR tool for 22nm, 45nm and 130nm academic FPGAs. This paper
proposes two different architectures of RLWE encryption [12] scheme for the
parameter set (n, q, s) : (256, 7681, 11.32). The first approach implements
RLWE hardware accelerator without voltage scaling, whereas the second RLWE
architecture is designed with different voltage partitions. Presently, there
is no FPGA which supports multiple $V_{ccint}$. Therefore, the power results
are carried out separately where one partition is considered as individual
circuit. These two designs are studied in two voltages regions. The
$V_{ccint}$ of each partitions are calculated by algorithm 1 and 2.

###  7.1 Vivado and VTR: Voltage Region: $V_{ccint_{min}}=$ 0.95 volt to
$V_{ccint_{max}}=$1.05 volt

The guard band voltage region of Artix-7 is $V_{ccint_{min}}=$ 0.95 volt to
$V_{ccint_{max}}=$1.05 volt. Though academic FPGAs on VTR platform supports
voltages of critical region, for sake of better comparative study we have
implemented 14 components of RLWE with voltage range of $V_{ccint_{min}}=$
0.95 volt to $V_{ccint_{max}}=$1.05 volt for both $Vivado$ and $VTR$. Table 5
shows $Vivado$ 28nm Artix-7, $VTR$ 22nm, $VTR$ 45nm and $VTR$ 130nm can save
4.34%, 1.19%, 1.18% and 1% power respectively.

###  7.2 VTR: Voltage Region: $V_{ccint_{min}}=$ 0.5 volt to
$V_{ccint_{max}}=$1.3 volt

Unlike $VTR$, $Vivado$ does not allow any $V_{ccint}$ below $0.95$ and above
$1.05$. As shown in Table 6, different number of clusters generated from
K-Means, Mean-Shift, DBScan and Hierarchical algorithms consider voltage
region from $V_{ccint_{min}}=$ 0.5 volt to $V_{ccint_{max}}=$1.3 volt for
22nm, 45nm and 130nm in VTR flow.

Table 5: Power Consumption of Vivado and VTR : Voltage Region:
$V_{ccint_{min}}=$ 0.95 volt to $V_{ccint_{max}}=$1.05

Our Design | Cluster | Partition | $V_{ccint_{i}}$ | Vivado | VTR | VTR | VTR
---|---|---|---|---|---|---|---
Under | algorithms | No. | Volt | 28nm | 22nm | 45nm | 130nm
$25^{\circ}$ Ambient |  |  |  |  |  |  |
Temparature |  |  |  |  |  |  |
& 100 MHZ Clock |  |  |  |  |  |  |
Without |  |  |  |  |  |  |
Voltage | NA | NA | 1.00 | 22.45 | 46.44 | 59.09 | 190.38
scaling |  |  |  |  |  |  |
Voltage |  | Partition-1 | 0.96 |  |  |  |
scaled |  | Partition-2 | 1.00 |  |  |  |
| K-Means | Partition-3 | 0.97 | 21.48 | 45.89 | 58.402 | 188.49
|  | Partition-4 | 0.98 |  |  |  |
|  | Partition-5 | 0.95 |  |  |  |
% of Reduction | 4.34 | 1.19 | 1.18 | 1.005
Without |  |  |  |  |  |  |
Voltage | NA | NA | 1.00 | 22.45 | 46.44 | 59.09 | 190.38
scaling |  |  |  |  |  |  |
Voltage |  | Partition-1 | 0.96 |  |  |  |
scaled |  | Partition-2 | 0.97 | 21.62 | 45.94 | 58.46 | 187.2
| Mean-Shift | Partition-3 | 1 |  |  |  |
|  | Partition-4 | 0.98 |  |  |  |
% of Reduction | 3.73 | 1.1 | 1.09 | 1.69
Without |  |  |  |  |  |  |
Voltage | NA | NA | 1.00 | 22.45 | 46.44 | 59.09 | 190.38
scaling |  |  |  |  |  |  |
Voltage |  | Partition-1 | 0.96 |  |  |  |
scaled |  | Partition-2 | 0.96 |  |  |  |
| DBSCAN | Partition-3 | 0.97 | 21.16 | 45.87 | 58.38 | 188.5
|  | Partition-4 | 0.98 |  |  |  |
% of Reduction | 5.78 | 1.24 | 1.21 | 0.99
Without |  |  |  |  |  |  |
Voltage | NA | NA | 1.00 | 22.45 | 46.44 | 59.09 | 190.38
scaling |  |  |  |  |  |  |
Voltage |  | Partition-1 | 0.96 |  |  |  |
scaled |  | Partition-2 | 0.96 |  |  |  |
| Hierarchical | Partition-3 | 0.97 | 21.62 | 45.94 | 58.46 | 188.6
|  | Partition-4 | 0.98 |  |  |  |
|  | Partition-5 | 1 |  |  |  |
% of Reduction | 3.73 | 1.1 | 1.09 | 0.93

As an example, K-Means algorithm generates five partitions. Algorithm 1
calculates average critical path $CP_{k}$ of the $k^{th}$ partition where
$A_{Critical}$ is the total critical path the $k^{th}$ partition.Then
algorithm 2 first computes the voltage per unit critical path $V_{r/c}$, after
that required biasing voltage $VP_{k}$ for $k^{th}$ partition is calculated in
line 7 of algorithm 2. The five $V_{ccint}$s calculated by algorithm 2 using
K-Means are : $V_{ccint_{1}}=0.96$ $V_{ccint_{2}}=0.995\approx 1$,
$V_{ccint_{3}}=0.965\approx 0.97$ $V_{ccint_{4}}=0.975\approx 0.98$,
$V_{ccint_{5}}=0.955\approx 0.95$. In Table 5, our voltage scaling method in
same voltage ranges, reduces the dynamic power consumption $3.73\%$ to
$5.78\%$ in $Vivado$ environment and reduces $0.93\%$ to $1.24\%$ in VTR
environment.Table 6 shows adoption of voltage scaling technology reduces
dynamic power consumption $10.19\%$ to $11.15\%$, $9.83\%$ to $10.82\%$ and
$4.82\%$ to $6.38\%$ for 22nm, 45nm and 130nm VTR flow respectively.

Table 6: Power Consumption for VTR, Voltage Region: $V_{ccint_{min}}=$ 0.5
volt to $V_{ccint_{max}}=$1.3

Our Design | Cluster | Partition | $V_{ccint_{i}}$ | VTR | VTR | VTR
---|---|---|---|---|---|---
Under | algorithms | No. | Volt | 22nm | 45nm | 130nm
$25^{\circ}$ Ambient |  |  |  |  |  |
Temparature |  |  |  |  |  |
& 100 MHZ Clock |  |  |  |  |  |
Without |  |  |  |  |  |
Voltage | NA | NA | 1.00 | 46.44 | 59.09 | 190.38
scaling |  |  |  |  |  |
Voltage |  | Partition-1 | 0.96 |  |  |
scaled |  | Partition-2 | 1.00 |  |  |
| K-Means | Partition-3 | 0.97 | 41.41 | 52.69 | 179.55
|  | Partition-4 | 0.98 |  |  |
|  | Partition-5 | 0.95 |  |  |
% of Reduction | 10.83 | 10.82 | 5.68
Without |  |  |  |  |  |
Voltage | NA | NA | 1.00 | 46.44 | 59.09 | 190.38
scaling |  |  |  |  |  |
Voltage |  | Partition-1 | 0.96 |  |  |
scaled |  | Partition-2 | 0.97 | 41.71 | 53.28 | 181.2
| Mean-Shift | Partition-3 | 1 |  |  |
|  | Partition-4 | 0.98 |  |  |
% of Reduction | 10.19 | 9.83 | 4.82
Without |  |  |  |  |  |
Voltage | NA | NA | 1.00 | 46.44 | 59.09 | 190.38
scaling |  |  |  |  |  |
Voltage |  | Partition-1 | 0.96 |  |  |
scaled |  | Partition-2 | 0.96 |  |  |
| DBSCAN | Partition-3 | 0.97 | 41.27 | 52.77 | 178.2
|  | Partition-4 | 0.98 |  |  |
% of Reduction | 11.15 | 10.71 | 6.38
Without |  |  |  |  |  |
Voltage | NA | NA | 1.00 | 46.44 | 59.09 | 190.38
scaling |  |  |  |  |  |
Voltage |  | Partition-1 | 0.96 |  |  |
scaled |  | Partition-2 | 0.96 |  |  |
| Hierarchical | Partition-3 | 0.97 | 41.48 | 53 | 181.1
|  | Partition-4 | 0.98 |  |  |
|  | Partition-5 | 1 |  |  |
% of Reduction | 10.69 | 10.32 | 4.89

Table 7: Compare between Vivado and VTR

Designs | Slice | Slice | DSP | BRAM | Critical | Throughput
---|---|---|---|---|---|---
| Register | LUT |  |  | Path (NS) |
Our | 665 | 846 | 2 | 1 | 2.539 |
Design |  |  |  |  |  |
[4] | 1506 | 4549 | 1 | 12 |  |
[26]-V1 | 1624 | 4365 | 1 | 5 |  |
[26]-V2 | 2122 | 5616 | 6 | 8 |  |
[27] | - | 1349 | 1 | 2 |  |
[28]512 | 1145 | 3228 | 4 | 7 |  |
[28]256 | 640 | 1637 | 4 | 5.5 |  |

##  8 Conclusion

This paper implements a low power RLWE hardware accelerator in Artix-7 28nm
commercial FPGA , 22nm, 45nm and 130 nm academic FPGA using $Vivado$ and $VTR$
tool. The proposed methedology creates clusters of the subcomponents of of
RLWE based on its critical path. The FPGA floor is partitioned and each
cluster is placed in each FPGA partition. The clsuters which have higher
average critical path is connected with higher biasing voltage and the
clusters which have lower average critical path is connected with lower
biasing voltage to avoid the timing failure. This paper proposes an algorithm
to calculate the actual biasing voltage required for certain amount of avarage
critical path of a partition based in the available FPGA technology
($V_{ccint_{max}},V_{ccint_{min}}$) and numnber of partitions. This voltage
scaled, partitioned RLWE can save $\sim$6% and $\sim$11% power in Vivado and
VTR platform respectively. The resource usage and throughput of the
implemented RLWE hardware accelerator is comparatively better than existing
literature.

## References

  * [1] Markus Grassl, Brandon Langenberg, Martin Roetteler, and Rainer Steinwandt.  Applying grover’s algorithm to aes: quantum resource estimates.  In Post-Quantum Cryptography, pages 29–43. Springer, 2016.
  * [2] Oded Regev.  On lattices, learning with errors, random linear codes, and cryptography.  In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 84–93, 2005.
  * [3] Daniele Micciancio and Oded Regev.  Lattice-based cryptography.  In Post-quantum cryptography, pages 147–191. Springer, 2009.
  * [4] Thomas Pöppelmann and Tim Güneysu.  Towards practical lattice-based public-key encryption on reconfigurable hardware.  In International Conference on Selected Areas in Cryptography, pages 68–85. Springer, 2013.
  * [5] Norman Göttert, Thomas Feller, Michael Schneider, Johannes Buchmann, and Sorin Huss.  On the design of hardware building blocks for modern lattice-based encryption schemes.  In International Workshop on Cryptographic Hardware and Embedded Systems, pages 512–529. Springer, 2012.
  * [6] Thomas Pöppelmann and Tim Güneysu.  Area optimization of lightweight lattice-based encryption on reconfigurable hardware.  In 2014 IEEE international symposium on circuits and systems (ISCAS), pages 2796–2799. IEEE, 2014.
  * [7] Sujoy Sinha Roy, Frederik Vercauteren, and Ingrid Verbauwhede.  High precision discrete gaussian sampling on fpgas.  In International Conference on Selected Areas in Cryptography, pages 383–401. Springer, 2013.
  * [8] Aydin Aysu, Cameron Patterson, and Patrick Schaumont.  Low-cost and area-efficient fpga implementations of lattice-based cryptography.  In 2013 IEEE international symposium on hardware-oriented security and trust (HOST), pages 81–86. IEEE, 2013.
  * [9] Paul S Zuchowski, Christopher B Reynolds, Richard J Grupp, Shelly G Davis, Brendan Cremen, and Bill Troxel.  A hybrid asic and fpga architecture.  In IEEE/ACM International Conference on Computer Aided Design, 2002\. ICCAD 2002., pages 187–194. IEEE, 2002.
  * [10] E. Kusse and J. Rabaey.  Low-energy embedded fpga structures.  In Proceedings. 1998 International Symposium on Low Power Electronics and Design (IEEE Cat. No.98TH8379), pages 155–160, 1998.
  * [11] J. Howe, C. Moore, M. O’Neill, F. Regazzoni, T. Güneysu, and K. Beeden.  Lattice-based encryption over standard lattices in hardware.  In 2016 53nd ACM/EDAC/IEEE Design Automation Conference (DAC), pages 1–6, 2016.
  * [12] Sujoy Sinha Roy, Frederik Vercauteren, Nele Mentens, Donald Donglong Chen, and Ingrid Verbauwhede.  Compact ring-lwe cryptoprocessor.  In International workshop on cryptographic hardware and embedded systems, pages 371–391. Springer, 2014.
  * [13] Thomas Pöppelmann, Léo Ducas, and Tim Güneysu.  Enhanced lattice-based signatures on reconfigurable hardware.  In International Workshop on Cryptographic Hardware and Embedded Systems, pages 353–370. Springer, 2014.
  * [14] Thomas Pöppelmann and Tim Güneysu.  Towards efficient arithmetic for lattice-based cryptography on reconfigurable hardware.  In International conference on cryptology and information security in Latin America, pages 139–158. Springer, 2012.
  * [15] Richard Lindner and Chris Peikert.  Better key sizes (and attacks) for lwe-based encryption.  In Cryptographers’ Track at the RSA Conference, pages 319–339. Springer, 2011.
  * [16] Damien Stehlé and Ron Steinfeld.  Making ntru as secure as worst-case problems over ideal lattices.  In Annual international conference on the theory and applications of cryptographic techniques, pages 27–47. Springer, 2011.
  * [17] Vadim Lyubashevsky, Chris Peikert, and Oded Regev.  On ideal lattices and learning with errors over rings.  In Annual international conference on the theory and applications of cryptographic techniques, pages 1–23. Springer, 2010.
  * [18] Turgay Kaya.  Memristor and Trivium-based true random number generator.  Physica A Statistical Mechanics and its Applications, 542:124071, March 2020.
  * [19] Donald E Knuth and YAO AC.  The complexity of nonuniform random number generation.  1976\.
  * [20] Kevin E. Murray, Oleg Petelin, Sheng Zhong, Jia Min Wang, Mohamed Eldafrawy, Jean-Philippe Legault, Eugene Sha, Aaron G. Graham, Jean Wu, Matthew J. P. Walker, Hanqing Zeng, Panagiotis Patros, Jason Luu, Kenneth B. Kent, and Vaughn Betz.  Vtr 8: High-performance cad and customizable fpga architecture modelling.  ACM Trans. Reconfigurable Technol. Syst., 13(2), May 2020.
  * [21] David Arthur and Sergei Vassilvitskii.  k-means++: The advantages of careful seeding.  Technical report, Stanford, 2006.
  * [22] Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, et al.  A density-based algorithm for discovering clusters in large spatial databases with noise.  In kdd, volume 96, pages 226–231, 1996.
  * [23] Dorin Comaniciu and Peter Meer.  Mean shift: A robust approach toward feature space analysis.  IEEE Transactions on pattern analysis and machine intelligence, 24(5):603–619, 2002.
  * [24] D Manning Christopher, Raghavan Prabhakar, and Schutze Hinrich.  Introduction to information retrieval, 2008.
  * [25] D. Ernst, Nam Sung Kim, S. Das, S. Pant, R. Rao, Toan Pham, C. Ziesler, D. Blaauw, T. Austin, K. Flautner, and T. Mudge.  Razor: a low-power pipeline based on circuit-level timing speculation.  In Proceedings. 36th Annual IEEE/ACM International Symposium on Microarchitecture, 2003. MICRO-36., pages 7–18, 2003.
  * [26] Timo Zijlstra, Karim Bigou, and Arnaud Tisserand.  Fpga implementation and comparison of protections against scas for rlwe.  In International Conference on Cryptology in India, pages 535–555. Springer, 2019.
  * [27] Ruan De Clercq, Oscar Reparaz, Sujoy Sinha Roy, Fréderik Vercauteren, and Ingrid Verbauwhede.  Masking ring-lwe.  Journal of Cryptographic Engineering, 6(2):139–153, 2016.
  * [28] Markus Rückert and Michael Schneider.  Estimating the security of lattice-based cryptosystems.  Cryptology ePrint Archive, 2010.