# EDLaaS; Fully Homomorphic Encryption
Over Neural Network Graphs

George Onoufriou, Marc Hanheide, and Georgios Leontidis G. Onoufriou and M.
Hanheide are both with the University of Lincoln.
E-mail: GOnoufriou at lincoln dot ac dot uk Georgios Leontidis is with with
the University of Aberdeen.Manuscript received ; revised never.

###### Abstract

We present automatically parameterised Fully Homomorphic Encryption (FHE), for
encrypted neural network inference. We present and exemplify our inference
over FHE compatible neural networks with our own open-source framework and
reproducible step-by-step examples. We use the 4th generation Cheon, Kim, Kim
and Song (CKKS) FHE scheme over fixed points provided by the Microsoft Simple
Encrypted Arithmetic Library (MS-SEAL). We significantly enhance the usability
and applicability of FHE in deep learning contexts, with a focus on the
constituent graphs, traversal, and optimisation. We find that FHE is not a
panacea for all privacy preserving machine learning (PPML) problems, and that
certain limitations still remain, such as model training. However we also find
that in certain contexts FHE is well suited for computing completely private
predictions with neural networks. We focus on convolutional neural networks
(CNNs), fashion-MNIST, and levelled FHE operations. The ability to privately
compute sensitive problems more easily, while lowering the barriers to entry,
can allow otherwise too-sensitive fields to begin advantaging themselves of
performant third-party neural networks. Lastly we show encrypted deep
learning, applied to a sensitive real world problem in agri-food, and how this
can have a large positive impact on food-waste and encourage much-needed data
sharing.

###### Index Terms:

fully homomorphic encryption, deep learning, machine learning, privacy-
preserving technologies, agri-food, data sharing

##  1 Introduction

Fully Homomorphic Encryption (FHE) is a structure-preserving encryption
transformation [1], proposed by Craig Gentry in 2009 [2], allowing computation
on cyphertexts ($\varepsilon(x)$) directly (addition and multiplication)
without the need for decryption. This is what could be considered the first
generation of FHE as implemented by Gentry in 2011 [3] and the Smart-
Vercauteren implementation [4]. Gentry’s implementation for any given
bootstrapping operating took anywhere from 30 seconds, for the smallest most
”toy” example, to 30 minutes for the largest most secure example, with the
former having a public-key of 70 Megabytes, and the latter a public-key of 2.4
Gigabytes in size. [3] Clearly this would be far too lengthy to be practically
viable, however there have been several generations of FHE since building on
these initial works and improving computational and spacial complexity; Second
generation: BV [5], BGV [6], LTV [7], BFV [8], BLLN [9]; Third generation: GSW
[10]; Fourth generation: CKKS [11]. Here we focus on CKKS, for a plethora of
reasons:

  * •

Operates with fixed point precision unlike all other schemes, which are
necessary for computation of neural networks with activations and inputs
usually falling in the range $0,\pm 1$ [12]

  * •

Has multiple available implementations (PALISADE [13], HEAAN [14], Microsoft
Simple Encrypted Arithmetic Library (MS-SEAL) [15], HElib [16], etc). Only
PALISADE [13] and Lattigo [17] are known to implement CKKS with bootstrapping,
although many others have these features road-mapped like MS-SEAL.

Our implementation uses MS-Seal, an incredibly popular FHE library. Many of
our techniques proposed here stretch to almost all other implementations since
they follow the same basic rules, albeit with slightly different implications
on things like parameters. We will in future translate our work to other
implementations to advantage our work of things such as bootstrapping.
Bootstrapping can afford us longer-effective viable-computational-depth. Thus
our work here focuses on using FHE without bootstrapping, or more precisely
levelled-fully-homomorphic-encryption (LFHE), meaning we calculate specific
sized although generalized (implementation) neural network circuits. Despite
CKKS being the best candidate for forms of encrypted deep learning, it has
certain shortcomings.

CKKS cyphertexts are the most atomic form of the data. This is a consequence
from the optimization used in many FHE schemes where a sequence of values (the
”message” or plaintext data) are encoded into a single polynomial, and then
this polynomial is what is then encrypted (Figure: 1). This means there is
less overhead since we are encrypting multiple values together, but it means
we cannot operate on this value alone, we must always be homomorphic i.e
maintain the same structure and operate on all values. Thus if we encrypt a
polynomial of length 10, that shall be the smallest form of the data until it
is either bootstrapped or re-encrypted. We are hence only able to operate on
the 10 elements as a single whole, E.G we cannot operate on the 3rd element in
the array alone to produce a single number answer.

CKKS cyphertexts computational depth (pre-bootstrapping) is directly related
to the length of the polynomial slots. Which means we must choose our
parameters carefully to ensure we do not have unnecessarily large cyphertexts,
and thus slow operations.

CKKS as with many schemes requires that two cyphertexts operating with each
other, must share the same parameters and be from the same private key. This
means when for instance we have multiple inputs into a neural network, all
directly interacting cyphertexts must be of the same key. This complicates
some automatic parameterisation logic which we will discuss later.

Figure 1: Fully Homomorphic Encryption (FHE) overview of distinct stages and
properties. [18]

###  1.1 The Significance of FHE

Figure 2: Trends of privacy (blue), Edward Snowden (red), and Cambridge
Analytica topics (yellow) on Google trends since 2010 showing a slow but
steady increase in the interest of privacy, and particular peaks around events
such as the Cambridge Analytica scandal and smaller peaks roughly correlated
to Julian Assange. [19]

Privacy is slowly becoming of greater interest (Figure: 2) to the broader
public, especially during and after particular scandals, such as Cambridge
Analytica (corporate actors), Edward Snowden on the five eyes (state actors),
[20] and more recently the Pegasus project on the cyberarms NSO group (both
corporate and state). This increased concern for privacy has over time
manifested itself in many forms one of the most notable being in legislation
such as the General Data Protection Regulation (GDPR) [21].

FHE promises much in our ability to compute cyphertexts without the ability to
detect or discern its contents, acting as a truly blind data processor in
Encrypted Deep Learning as a Service (EDLaaS) applications. [22] In particular
EDLaaS is especially useful in highly sensitive/ highly regulated industries
such as medicine/ patient data (especially due to GDPR), trade secrets, and
military applications. FHE is not a panacea. Special care must be taken to
ensure/ maximize the security of cyphertexts and the biggest problem with this
is it is not immediately apparent if this is not ensured often requiring a
deep understanding of the underlying cryptography such that the
parametrization can be understood, analysed, and balanced against.

###  1.2 Related Works

####  1.2.1 Encrypted Deep Learning

There have been many other works that use FHE (bootstrappable) or Levelled-FHE
to compute some form of neural network. A few notable examples for FHE and
Convolutional Neural Networks (CNNs) are by Lee, [23], Meftah, [24], Juvekar
[25], and Marcano, [26]. Lee uses a modified version of the Microsoft Simple
Encrypted Arithmetic Library (MS-SEAL) to add bootstrapping as MS-SEAL does
not currently support it. Lee shows FHE and DL used on the CIFAR-10 [27]
dataset to mimic the ResNet-20 model achieving a classification accuracy of
90.67%. Juvekar uses the PALISADE library implementation of the BFV scheme
with their own (LFHE) packed additive (PAHE) neural network framework to
compute both MNIST and CIFAR-10. Meftah uses Homomorphic Encryption Library
(HELib) [16] similarly to Lee is particularly focused on improving the
practicality of (L)FHE as a means to compute deep learning circuit. Meftah
seeks to do this towards computing ImageNet [28] with the second generation
BGV scheme [6] (on integers) as opposed to Lee using the fourth generation
CKKS scheme [11] (on floating points). Lastly Marcano similarly to the
previous is also concerned with the computational, and spatial complexity of
using FHE as a means to compute convolutional circuits. Marcano appears to use
a custom FHE implementation on fixed point number format, taking 36 hours to
train on the MNIST dataset. It is unclear in all of these papers however, how
exactly the gradient descent or backward pass of the neural networks are
implemented, which is necessary for neural network training. They also lack
detail in key stages of the forward pass such as how they dealt with
calculating the sum-of-products of the CNN since a homomorphic cyphertext
cannot be folded on itself to form a single number sum, or if they used point-
wise encryption to be able to sum between cyphertexts how they dealt with the
sheer size of this plethora of cyphertexts. Lastly the above papers do
describe in some detail how some of their parameters are decided in particular
with regards to security, but they do not cover much on the computational
depth or precision effects these parameters have on the cyphertext such as the
modulus-switching chain.

####  1.2.2 FHE Graph Parameterisation

Here FHE graph parameterisation means deriving the FHE parameters from a
graph, such as the computational depth and thus the parameters like the
modulus size. There have been a few works that define FHE graph
parameterisation, the most notable and similar of which is Microsoft Encrypted
Vector Arithmetic (MS-EVA) [29]. MS-EVA uses Directed Acyclic Graphs (DAGs) to
represent simple operations applied to some input constant. Since MS-EVA also
uses MS-SEAL this means it also uses RNS-CKKS the purportedly most efficient
CKKS implementation. [29] MS-EVA has been applied to encrypted deep learning
inference, specifically LeNet-5 towards MNIST. Dathathri particularly
emphasises the non-trivial nature and how parameterisation can be a large
barrier to the adoption of FHE. However there are no examples currently
available to help lower this barrier. Subsequently their nodes representing
single atomic operations means there is overhead when compared to block
operations which could be an area of improvement.

###  1.3 Contributions

Our contributions towards FHE-deep-learning given the current state of the
field and related works (Section: 1.2) are:

  * •

To provide and showcase open-source encrypted deep learning with a
reproducible step-by-step example on an open dataset, in this case MNIST/
Fashion-MNIST. Provided through a dockerised Jupyter-lab container, such that
others can readily and easily explore FHE with deep learning and verify our
results.

  * •

To outline a new block-level automatic cyphertext parameterisation algorithm,
we call autoFHE. We also seek to showcase autoFHE in both regression and
classification networks.

  * •

Show a new application for encrypted deep learning; to a confidential real-
world and thus messy dataset.

  * •

Detail how neuronal firing in multi-directed graphs can be achieved in our
different approach.

  * •

Show and detail precisely the computational graph of how a CNN can be
constructed using FHE in particular how handling of the sum-of-products can
occur. This along with our easily reproduced example, should help clarify many
otherwise omitted details from previous works.

  * •

Show recent advancements in FHE compatibility like ReLU approximations in
greater detail along with problems/ considerations as part of a whole
computational graph. We also backpropogate the dynamically approximate range
of ReLU.

###  1.4 Threat Model

Just like similar works in FHE we assume a semi-honest/ honest-but-curious
threat model. [29] Where parties follow the specified protocol but attempt to
garner as much possible information from their received messages as possible.
Or indeed one party has malicious intrusion which can read the data shared,
but not necessarily write/ change the protocol.

##  2 Methodology

Algorithm 1 Neuronal-Firing, our exhaustive neuron stimulating, depth-first,
blocking, node-centric, graph/ neuron stimulation function.

$g$: Neural network multi-directed computational graph

$n$: Vector of neurons/ computational nodes for sequential stimulation

$s$: Vector of signals to be induced in the corresponding neuron

$r$: Vector of receptors to call on respective node

$g^{\prime}$: Stimulated neural network/ modified computational graph

for $i\leftarrow 0\ \text{to}\ $length($n$) do

signal_carrier($g,n[i],r[i],s[i]$)

Algorithm 2 Neuronal-firing-signal-carrier; Propagate a single signal thought
all possible nodes in the neural network graph recursively based on its
position.

function signal_carrier($g,\ n,\ r,\ \textit{bootstrap}$)

$s\leftarrow$get_inbound_signal($g,n,r,\textit{bootstrap}$)

if $s=\textit{None}$ then

return None

$s\leftarrow$apply_signal($g,n,r,s$)

if $s=\textit{None}$ then

return None

set_outbound_signals($g,n,r,s$)

for all $\textit{successors}\ \text{in}\ g\text{.node}(n)\text{.successors}()$
do

signal_carrier($g,n,r,\textit{None}$)

Algorithm 3 Get accumulated inbound signal from edges.

function get_inbound_signal($g$, $n$, $r$, bootstrap)

if $\textit{bootstrap}\neq\textit{None}$ then

return bootstrap

$s\ \leftarrow\ [\ ]$

for all $\text{edges}\ \text{in}\ g\text{.in\\_edges(}n\text{)}$ do

$s\text{.append}(\text{edge.signal}(r))$

if $\text{length}(s)=1$ then

return $s[0]$ return $s$

Algorithm 4 Activate current node using the accumulated signal and get
outbound signal.

function apply_signal($g$, $n$, $r$, $s$)

if $s=\textit{None}$ then

return None

$s\leftarrow g\text{.nodes}(n)\text{.receptor}(r,\ s)$

return $s$

Algorithm 5 Set outbound edges with activation signal.

function set_outbound_signals($g$, $n$, $r$, $s$)

if $s=\textit{None}$ then

return None

for all $\text{edges}\ \text{in}\ g\text{.out\\_edges(}n\text{)}$ do

if $\text{isinstance}(s,\ \textit{generator})$ then

$\text{edge.signal}(r)\leftarrow next(s)$

else

$\text{edge.signal}(r)\leftarrow s$

We created our own python-based FHE compatible deep learning library because
there was still a significant lack of compatibility between existing deep
learning libraries and existing FHE libraries. While it may be possible to
create some form of interface or bridge this left much to be desired in terms
of usability and flexibility to explore different research avenues like
various FHE backends. As a consequence we created a NumPy API focused library,
where the inputs to the neural networks need only conform to the basic NumPy
custom containers specification, allowing the objects passed in to handle
their own nature. This means any NumPy conforming object can be used in our
networks, this includes NumPy itself (for pure plaintexts) or in this case
arbitrary FHE objects. Two notable examples of existing use of this custom
container specification are Dask and CuPy, the former enabling distributed
parallelism, while the later enabling NVIDIA-CUDA GPU-based computations. CuPy
could for instance be used in place of NumPy to make our networks operate over
NVIDIA GPUs. This could even go as far as a complex abstraction that merges
both FHE and CuPy to enable GPU accelerated cyphertext calculations. Encrypted
deep learning accelerated by GPUs is an area we seek to explore in the future,
for the rest of this paper however all operations are conducted on CPUs. Our
entire source code for our library Python-FHEz is available online along with
the respective documentation. [18] We use the MS-SEAL C++ library bound to
python using community pybind11 bindings as our primary FHE back end that is
wrapped in the NumPy custom container specification. [30]

Furthermore in this section we outline our specific implementation,
techniques, equations, and methods used to exemplify EDLaaS in practice using
both an open dataset, and a preview of more real-world/ complicated but
proprietary data scenario:

  * •

We chose to use Fashion-MNIST as our open dataset and as our classification
example as it is a drop in replacement for the MNIST dataset while being more
complex, but still familiar to most, while also showing more valid performance
results which are more distributed/ noticeable.

  * •

We also chose to use an agri-food but proprietary dataset to exemplify a
different kind of regression network and how FHE might play a role in this
sensitive industry where data sharing/ availability is scarce due to a barrier
in concerns over competition, of which FHE might help reduce. Agri-food is
also a key industry which has had a troubled few years due to climate change
bringing hotter/ record-breaking summers, while also being effected by both
coronavirus and Brexit shortages in staffing and thus supplying.

For our neural networks we used a node-centric, multi-directed graph approach
where:

  * •

Each node represents some computation object usually a neuron.

  * •

Each edge represents the movement of data between neurons/ computation
objects.

  * •

Each node can accept many inputs that are stacked on top of each other in the
same order as the edges, unless there is a single input edge where it is
instead mapped to the input of the neuron.

  * •

Each edge can only connect two nodes directed from the first to the second
node, parallel edges are possible and are treated as completely separate edges
with no special handling.

  * •

A node can only be activated/ computed once all predecessor edges carry some
data.

  * •

All nodes can have several receptors, that is to say different functions that
can be pointed to by the edges, in particular forward and backward receptors
for calculating the forward neural network pass, and gradients using the chain
rule in the backward pass.

  * •

Nodes return either an iterable to be equally broadcast to all successor edges
or a generator to generate independent results for each successor edge.

  * •

The weight of each edge corresponds to the computational depth of the
directed-to node. These weights are not used to optimise the path since the
majority of nodes must be activated to achieve some desired output, but
instead these weights are used to find the longest path between key-rotations
to determine the minimum required encryption parameters to traverse from one
rotation to the next.

  * •

Self-loop edges are not treated differently, instead relying on the
configuration of the node itself to consider termination of the loop.

  * •

A single activation pass of the graph may have multiple input and multiple
output nodes/ neurons, like in the two blue regions in the sphira graph
(Figure: 5).

To activate our neural network graph we used our own neuronal-firing algorithm
(Algorithm: 1).

###  2.1 FHE parameterisation

Algorithm 6 Automatic FHE-parameterisation by source and cost discovery, over
multi-directed graphs.

function autoHE($g$, $n$, concern)

for $i\ \text{in}\ n$ do$\triangleright$ Label graph sources and costs

$\text{autoHE\\_discover}(g,i,i,\textit{concern},0)$

$r\ \leftarrow\
\text{tuple}(\text{dictionary()},\text{list()})$$\triangleright$ Group
representation

for $i\ \text{in}\ n$ do$\triangleright$ Assign + merge groups from labels

if $r[0]\text{.get}(i)\ \text{is}\ \textit{None}$ then

$r[0][i]\ \leftarrow\ \text{len}(r[1])$

$r[1]\text{.append}(0)$

for $j\ \text{in}\ g\text{.nodes}()$ do

$\textit{src}\ \leftarrow\ j[1][\text{"sources"}]$

if $i\ \text{in}\ \textit{src}$ then

for $k\ \text{in}\ \textit{src}$ do

$r[0][k]\ \leftarrow\ r[0][i]$

if $\textit{src}[k]\ >\ r[1][r[0][i]]$ then

$r[1][r[0][i]]=\textit{src}[k]$ return $r$

Algorithm 7 Recursive FHE-parameterisation source, and cost discovery over
multi-directed graphs.

function autoHE_discover($g$, $n$, $s$, concern, $c$)

$d\ \leftarrow\ g\text{.nodes}()\text{.get}(n)$

if $d\text{.get("sources")}=\textit{None}$ then

$d[\text{"sources"}]\ \leftarrow\ \text{dict}()$

if $s\ \neq\ n$ then

if $d[\text{"sources"}]\text{.get}(s)\ =\ \textit{None}$ then

$d[\text{"sources"}][s]\ \leftarrow\ c$

else if $d[\text{"sources"}]\text{.get}(s)\ <\ \textit{c}$ then

$d[\text{"sources"}][s]\ \leftarrow\ c$

if $\text{isinstance}(d[\text{"node"}],\textit{concern})$ then

$\text{autoHE\\_discover}(g,n,n,\textit{concern},0)$

else

for $i\ \text{in}\ g\text{.successors}(n)$ do

$\textit{nxt}\ \leftarrow\ c+g\text{.nodes}()[i][\text{"node"}]\text{.cost}()$

$\text{autoHE\\_discover}(g,i,s,\textit{concern},\textit{nxt})$

Our automatic FHE parameterisation approach is similar to that of MS-EVA [29]
where we use (in our case our existing neural network) graphs to represent the
computation the cyphertexts will experience. This allows us to automatically
generate the smallest secure cyphertext possible that meets the requirements
of the proceeding computational circuit. How we differ however is that since
we are using neural network neurons instead of atomic (addition,
multiplication, etc) operations, there are fewer nodes and edges, and thus
less overhead necessary of both the graph, and any intermediate storage along
edges. Also our neural network graphs are Multi Directed Graphs (MDGs) as
opposed to DAGs which means we can model more complex operations involving
more than two inputs.

In our abstraction automatic FHE parameterisation becomes a variation of the
travelling-salesman problem, but instead of finding the shortest path we need
to find the longest possible path or more specifically the highest
computational depth experienced by the cyphertext, between sources and sinks.
However even in our abstraction we must still conform to the constraints of
CKKS, like that interacting cyphertexts must match, in cyphertext scales, and
must be originating of the same private key which means other adjoining paths
must be considered where they intersect. A key distinction compared to MS-
EVA’s approach is that our graphs are interpreted instead of being compiled
down to some intermediate representation. Our cyphertext objects are also not
raw, and are instead part of a larger NumPy-API compatible objects that
interpret invocations. These meta objects are also responsible for the
decision making of both relinearisation and rescaling, taking that complexity
away from the implementation of encrypted deep learning. An example of this
rescaling interpretation is when two cyphertexts are multiplied, the meta-
object is responsible for ensuring both cyphertexts match, I.E swapping down
the modulus chain to equal scales depending on which of the two cyphertexts is
higher up the modulus switching chain. Similarly an example of relinearisation
is when two of our meta-objects are multiplied the computing member (usually
the first meta-object in sequence) automatically relinearises the new meta-
object, before passing the new meta-result back. This means we offload
rescaling and relinearisation, and it is not necessary to plan for these two
operations, instead we need only calculate the longest paths, and the ”groups”
of cyphertexts. Here groups of cyphertexts means cyphertexts that interact,
and must then share encryption parameters.

In short the minimum necessary information we need to derive from the graph
using our algorithms (Algorithms: 6, 7) is:

  * •

Which cyphertexts interact at which nodes

  * •

Thus which nodes belong to which group

  * •

What is the maximum computational depth of each group necessary to go from one
(type-of-concern) source to another (type-of-concern) sink/ rotation

Each of our nodes must be labelled with its computational depth, so that the
highest-cost traversal can take place. This may need to occur multiple times
in a single graph, depending on the number of sources and sinks in said graph.
The more sources to sinks, the more paths the more intersections and co-
dependency. Take for instance $x_{0}$, and $x_{1}$ in the dummy network
depicted in Figure: 3. The cyphertexts $x_{0}$ and $x_{1}$ passed in must be
able to reach the end of both paths leading to $r_{0}$ the very next
sink/rotation. To do this they must be inter-operable with each-other at the
point at which they meet. This means they must have matching scales,
encryption parameters, and must originate from the same private key. However
consider that $x_{1}$ experiences computations $c_{0}$ and $c_{1}$ whereas
$x_{0}$ only experiences $c_{1}$. Each computation changes the scale, and thus
necessarily their remaining primes in the modulus switching chain which would
make them inoperable if not for our specialised logic in the meta-object to
match them automatically.

E.G spacial and temporal data in the case of multi-modal datasets (of which
Fashion-MNIST is not) would have multiple inputs that require matching. Since
decisions on relinearisation and rescaling are left to the meta-object the
only information we need to ordain from the graph is the computational depth,
and co-dependency of parameters. This can then be used to associate parameters
together and select the minimum viable polynomial modulus degree.

In our node centric view of the graphs we say an edge from node A to B has the
cost associated with B. This algorithm should be able to handle multiple
cyphertext ingress nodes ($x$, $y$, etc), multiple cyphertext egress nodes
($y_{h}at$, and any others), and key-rotation stages in-between that will also
need to be parameterised along the way. Our proposed algorithm can be seen in
Algorithm: 6. The output of this algorithm is a tuple representation of the
graphs parameterisation-groups. We will know which nodes need to share
parameters, and what the highest cost of that parameter-group is. If we
combine this graph parameter representation and some basic logic, we can tune/
parameterise automatically. This will of course vary for each implementation
of FHE, from CKKS to BFV for example, requiring different parameters. The
difference in parameterisation is why we separate out this final step, so that
custom functions can be injected.

The FHE parameters we deal with here primarily geared toward the MS-SEAL CKKS
backend are:

  * •

Scale; Computational scale/ fixed point precision

  * •

Polynomial modulus degree; polynomial degree with which to encode the
plaintext message, this dictates the number of available slots, and the
available number total bits which the coefficient modulus chain can contain.

  * •

Coefficient modulus chain; a list of byte sizes with which to switch down the
modulus chain, this dictates the computational depth available before
bootstrapping or key-rotation is necessary.

However the information we derive from the graph is generic and can be broadly
adapted to generate parameters for other schemes also.

We use the default 128-bit security level of MS-SEAL just as MS-EVA [29],
being the most similar existing framework. This is security level is broadly
considered reasonably secure [23, 24, 29], and matches our threat model of
honest-but-curious.

Figure 3: Example automatic FHE parameterisation problem, over a multi-
directed graph. Sources are where data becomes a cyphertext. Sinks are where
cyphertexts become plaintexts. Computation nodes are generic nodes that
represent some operation that can be applied to both cyphertexts and
plaintexts. Explicit rotation nodes are where a cyphertexts keys are rotated,
either to refresh them, or to change the form of the cyphertext, potentially
into multiple smaller cyphertexts. Please note this does not necessarily
follow the colour coding of our other automatically-generated graphs. [18]

Lastly now that we have calculated the groups, the cost of the groups, and the
associated nodes that belong to which groups, we can use a rough heuristic
(Figure: 8) to estimate the necessary FHE parameters to accompany these
groups. This heuristic can be tuned, and overridden for other FHE schemes to
more tightly parameterise if necessary.

Algorithm 8 Heuristically parameterise RNS-CKKS scheme using expected cost of
computation.

$c$: Integer maximal-cost of this cyphertext group.

$s$: Integer scale-power, the scale of the cyphertext. Default: $s=40$. We
advise not to go below $30$ due to noise accumulation and lack of prime
availability.

$p$: Float special-prime-multiplier, the multiplier that dictates the scale-
stabilised special-primes in the coefficient-modulus chain. Default: $p=1.5$

parms: MS-SEAL RNS-CKKS parameter dictionary/ map.

function parameterise($c$, $s$, $p$)

$\textit{parms}\ \leftarrow\ \text{dict}()$

$\textit{parms}[\text{"scheme"}]\ \leftarrow\ 2$$\triangleright$ 2 is CKKS in
MS-SEAL

$\textit{parms}[\text{"scale"}]\ \leftarrow\ \text{pow}(2,s)$$\triangleright$
scale power

$m\ \leftarrow\ [s\ \text{for}\ i\ \text{in range}(c+2)]$

$m[0]\ \leftarrow\ \text{int}(m[0]*p)$$\triangleright$ Mult first special
prime

$m[-1]\ \leftarrow\ \text{int}(m[-1]*p)$$\triangleright$ Mult last special
prime

$b\ \leftarrow\ 27$

while $b\ <\ \text{sum}(m)$ do

$b\ \leftarrow\ b*2$

$\textit{parms}[\text{"poly\\_modulus\\_degree"}]\ \leftarrow\
\text{int}(1024*(b/27))$

return parms

###  2.2 Open Data Fashion-MNIST

Figure 4: Fashion-MNIST sample showing examples of data such as: boots, bags,
jumpers, and trousers. [31] Figure 5: Fashion-MNIST computational graph we
call ”sphira”, showing the colour coded graph and the respective nodes used to
train/ compute Fashion-MNIST using our neuronal-firing algorithm. Blue
represents the input and input transformation circuit that deals with passing
the signals into the neural network in a way it is expecting them. Yellow
represents the convolutional neural network components where one filter neuron
passes multiple output cyphertexts to a plethora of summing nodes. Pink
represents the fully connected dense layer for each class. Purple represents
the loss calculation circuit necessary for backpropagation. Orange represents
the output/ prediction circuit. Red represents the generic glue operations
necessary to bind components together. Green represents the encryption
specific nodes like decryption, rotation, encryption. An interactive version
of this graph is available in our source code documentation so that clusters
of nodes can be peeled apart for investigating individual nodes and
connections. [18]

In this section we describe our openly available Jupyter implementation [18]
of an FHE-compatible CNN operating on the open dataset called Fashion-MNIST as
can be seen in Figure: 4. This dataset contains in total 70,000 images, 60,000
training/ cross validating, and for 10,000 testing. This dataset contains
images of certain items of clothing, constituting 10 classes. Each image is a
mere 28x28x1 pixels. The full implementation can be found in the examples of
our source code repository. [18]

We chose Fashion-MNIST as it is a drop in replacement for MNIST while also
being a somewhat more difficult problem than standard MNIST. Coincidentally
being that MNIST and thus Fashion-MNIST are both classification rather than
regression they represent an even more difficult scenario for encrypted deep
learning since they do not provide one continuous/ regressed output so the
computational circuit becomes more complex/ deeper as far as necessary to
process these classifications I.E the extra dense nodes for each class, and
the whole addition of both softmax and categorical cross entropy (CCE) to
replace the mean squared error (MSE) loss function in the case of would be
regression networks. This also poses a problem as methods usually used towards
classification like softmax (Equation: 2) are not compatible with FHE since
they include division although some alternative approximations do exist such
as those used by Lee [23].

####  2.2.1 Data Wrangling and Inputs

Fashion-MNIST is largely pre-wrangled especially if you use one of many forks
of the data which present each figure-classification, and image as a one-
dimensional feature vector between 0-255 stacked in a CSV file. This means the
only two necessary steps toward this data are to normalise between 0-1, and
reshape the individual feature vectors back into their original shape of
28x28x1. The feature vector is encrypted and the cyphertext passed in as a
signal to node ”x” in the sphira network (Figure 5), and the figure-
classification is passed in to node ”y” as a separate signal. Whereby our
neuronal-firing algorithm (Algorithm 1) will propagate these signals
thereafter.

####  2.2.2 CNN

Figure 6: Encrypted convolutional neural network (CNN), this is a particular
unusual implementation since there can be no summing of the filters, and
instead this sum is commuted in the case where the filter operates on an input
that is a single cyphertext (I.E not a composite of multiple cyphertexts).
[18]

$\displaystyle a^{(i)<t>}=g(\sum_{t=0}^{T_{x}-1}(k^{<t>}x^{(i)}+b/N))$ (1)

As our CNN (yellow in Figure: 4) we use a biased cross correlation layer (CC)
to calculate the product of a given filter against the input cyphertext. We
use a SIMO scheme we call kernel masquerading. Here kernel-masquerading shall
mean the merging of weights and a respective zeros mask into a sparse
n-dimensional array such that they become a single operation conducted on the
input cyphertext (Figure: 7), reducing the computational depth experienced by
the input cyphertext to 1 (multiplication) and allowing for subset operations
to be conducted on the cyphertext to selectively pick regions of interest.
This is only possible in the plaintext-weights strategy, since this allows the
weights to be operated on arbitrarily and selectively to reform them into the
shape of the input cyphertext and sparsity of the filter/ kernel. This is a
simple operation of which a two and three dimensional variant can be seen in
Juvekar’s, and Meftah’s work [25, 24]. The main drawback of the kernel-
masquerade is that if we were to apply a convolutional-kernel-mask on some
cyphertext $\varepsilon(x^{(i)})$ we would end up with separate modified
cyphertexts $\varepsilon(x^{(i)<t>})$ that correspond to different portions of
the data, however we are unable to sum them without a key rotation such that
we are summing between different cyphertexts since we cannot fold a cyphertext
in on itself. This means we have a choice at this stage, we can either rotate
the keys now to reduce complexity or try to save computation time by doing as
much processing while the values are encoded in one larger cyphertext which is
significantly more efficient from findings in Juvekars work on SISO
cyphertexts [25].

Figure 7: Merged mask and kernel together to create a single sparse kernel
which zeros undesired components in the cyphertexts polynomial of values using
Hadmard products. [18]

Since key rotation would make the outputs normally-processable for operations
like summation we wont address that variant here instead we choose to see how
far we can instead commute this sum to get the maximum performance as far
fewer cyphertexts. One thing we can and did do in our CNN implementation is to
commute the bias forward to be before summation. so instead of
$z=\sum^{N}_{i=0}(x_{i}w_{i})+b$ we decompose $b$ into the product calculation
before summation as $z=\sum^{N}_{i=0}(x_{i}w_{i}+\frac{b}{N})$ since this is
equivalent over the full computation of the cyphertext. We could have
simplified to just $z=\sum^{N}_{i=0}(x_{i}w_{i}+b)$ if we calculate the
gradient with respect to the bias $\frac{df}{db}$ as $\frac{df}{db}=Nx$
instead of $\frac{df}{db}=x$ such that the neural network is effectively aware
of this higher contribution of the bias, and it would be naturally
accommodated through the gradient descent process.

From here forward special logic/ considerations need to be made to ensure the
output cyphertexts of the biased-cross-correlation are treated as a singular
un-summed-value. We tried to push this cyphertext through the neural network
further but we had to ensure all further operations were both linear and
abelian compatible. Take for instance an encoded non-summed sequence as a
cyphertext $x$, $x=(1+2+3+4)=10_{\text{plntxt}}$, then lets try a
multiplication
$4x=4(1+2+3+4)=(4*1+4*2+4*3+4*4)=(4+8+12+16)=4*10_{\text{plntxt}}=40_{\text{plntxt}}$,
but now lets try a multiplication against itself or another non-summed
sequence so for instance a nonlinear
$x^{2}=(1+2+3+4)(1+2+3+4)=(1*1+1*2+1*3+1*4+2*1+2*2+2*3+2*4+3*1+3*2+3*3+3*4+4*1+4*2+4*3+4*4)=10^{2}_{\text{plntxt}}=100_{\text{plntxt}}$.

This is a problem since we cannot cross-multiply cyphertexts since we cannot
select elements from either cyphertext, if we were to attempt to multiply this
cyphertext with itself it would calculate the element-wise product of the two.
The best we could do if we did want to compute this would be to conduct a key
rotation to expose the elements we desired as separate cyphertext but if we
are going to do that we would be just as well served by just rotating to sum
then passing it through the element-wise product as normal. It is possible to
commute the sum further if we use linear approximations of our activation
functions like if we take Sigmoid (Equation: 3) and its approximation
Equation: 5 then if we ensure our products will always be between 0-1 through
a modified version of batch norm ([24]) we could then safely use only the
linear component of the Sigmoid approximation (Equation: 5)
$\sigma(x)\approx\sigma_{a}(x)=0.5+0.197x$ since it would still closely follow
in the -1 to 1 range and loses approximation beyond this range instead of the
usual -5 to 5 range the full approximation affords and would also cut down the
computational cost. For ourselves we choose to key rotate to encrypt the
elements to be summed until such a time as we have fully fleshed out a fully-
commuted-sum alternative.

For our cross-correlation activation function we use the more recent ReLU
(Equation: 4) approximation (Equation: 6) and the derivative of this
approximation for backward propagation (Equation: 10) as its own separate node
to allow them to be decoupled and easily swapped out with new or improved
variants and so interjection with batch norm is readily variable without
having to rewrite existing nodes.

####  2.2.3 Dense/ ANN

Figure 8: Encrypted variant of an ANN/ dense neural network, usually used in
our case to merge divergent times/ branches/ filters back together into a
single output. [18]

For each of our classes we have a dense fully-connected neuron (Figure: 8, red
in Figure: 4) to interpret the activation vector of the biased-cross-
correlation and activation combination / CNN. Thus our dense layer is
comprised one 10 ANN nodes. There is nothing of any note in this layer other
than it must accept multiple cyphertexts that are added together / summed
across the first axis, otherwise it behaves almost the same as a standard
neuron as depicted in figure. However careful attention should be paid to
broadcasting such that the gradient is still correct and we do not attain an
exploded result that could fall outside of approximation golden zones like
sigmoids -5 to 5.

We accompany each neuron with its own ReLU approximation node before passing
the activations on to the different forward evaluation circuits for loss
calculation and prediction output.

####  2.2.4 Prediction

Argmax is an effective and quick computation of the highest value in a vector.
Since the ANN layer outputs a vector of 10 values one for each class the
Argmax function serves to take the highest activation and turn it into a
1-hot-encoded representation of the predicted class. This can be passed into a
1-hot-decoder to attain the predicted class $\hat{y}$. However since argmax
relies on the context to find the max, it is necessary to conduct this
operation in plaintext on the client side, to effectively pick from this 10
element vector. There is no backpropagation from this branch, it is purely an
output branch for providing predictions to the data owner. These stages are
pink in Figure: 5.

####  2.2.5 Loss

The loss calculation stage is represented by purple in Figure: 5. Argmax is
not an effective function for the purposes of backpropagation of the loss
since only one of the ten input ANN neurons would receive all of the gradient
multiplied by 1, which does not give the majority of the network much
information to update the weights from any single given example. Thus as-per-
norm we used a Softmax layer instead which better distributes the gradient
between not only what neuron was responsible for positive activation but also
the others that should not be activating.

The softmax ensures that all output values summed together equal 1, and that
they are effective predicted probabilities of the network that a certain class
is what was given in the input. We use a standard categorical cross-entropy
(CCE) function to calculate the loss and subsequently the derivative with
respect to each of the 10 classes to pass back to the softmax and hence the
ANN layer.

The CCE function also receives input/ stimulation from a 1-hot-encoder that
encodes the ground-truth $y$ value or the actual class that the input $x$
corresponds to for the purposes of loss calculation.

$\displaystyle\sigma(\overrightarrow{a})_{i}=\frac{e^{a_{i}}}{\sum^{K}_{j=1}e^{a_{j}}}$
(2)

It should also be noted that the loss circuit (pink) requires decryption since
both softmax and CCE are not FHE compatible operations. There have been
proposed ways to allow for softmax to be computed with cyphertexts by Lee [23]
however we were unable to create a working fhe-compatible softmax from what
information was available and would require bootstrapping 22 times, and it
would still need to be unencrypted for the CCE calculation. Given this data
using the sphira (5) network we garnered the following results:

Figure 9: Model performance using different activation functions in the sphira
network on the fashion-MNIST dataset. All activations here are their FHE
compatible approximations unless otherwise specified. Each dot is a different
network, or the same network with a different data type(cyphertext,
plaintext). [18] Figure 10: Model inference time, by different types.
Plaintext types mean where the graph is run using plaintext data. Cyphertext
types mean where the graph is run using cyphertext data. Both plaintext and
cyphertext data conforms to the same NumPy API, meaning they can be used
interchangeably. Each dot is a different network (I.E differently initialised
weights but the same structure), or the same network with a different data
type (cyphertext, plaintext). [18]

###  2.3 Strawberry Yield Data

Figure 11: Strawberry yield/ regression computational graph we call
”constelation”, showing the colour coded graph representation and nodes used
to train on strawberry yield, based on environmental factors. Blue are input/
encryption nodes. Yellow are convolutional-related nodes. Green are
operational nodes necessary to ”glue” the network together. Pink are dense/
ANN nodes. Orange is the output prediction node. Red is the loss calculation
node. Purple is an FHE specific node used for decryption of the input data.
[18]

Unfortunately we do not have permission to publicise the specific data used in
this section. As such we shall preview this application and seek to further
elaborate and develop the techniques used here in-depth in future papers. We
will only touch briefly here of this data as a means to show how FHE can be
used in real world problems effectively, and for a different kind of problem;
regression instead of classification.

This data is geared towards yield prediction often weeks in advance. The
prediction horizon is typically between one to three weeks ahead of the
strawberry fruit becoming ripe. This allows time for logistical constraints
such as price negotiation, and picker/ staff scheduling. Thus performance of
these predictive models is critically important to ensure all the fruit is
being accounted for in negotiations with retailers (and thus can be sold), and
that there is sufficient manpower at the point of need to gather this produce.
Over predicting can result in insufficient harvests to meet contractual
obligations, most likely meaning the yield must be covered by buying other
producers yields. However if there is a shortfall of yield from one producer,
the factors that lead to that shortfall such as adverse environmental
conditions are felt by most other producers in the geographic region. This
means that usually (in the UK) the yields must be imported from abroad
increasing the price substantially. Conversely if there is under-prediction of
yield this results in unsold fruit, which is either sold at a significant
discount if possible or destroyed. There is also a clear and significant lack
of agriculture data available due to perceived data sensitivity. This affects
many forms of agriculture for various reasons. In the soft-fruit industry this
tends to be proprietary genetic varieties, and operational specifics such as
irrigation nutrition mixtures. However there is a tendency to distrust and a
perceived lack of benefit to data sharing, due to no obvious performant
outcomes.

Due to a lack of available data, we use historic yield data we gathered in our
Riseholme campus polytunnel/ tabletop over two years, and combine this with
environmental data experienced by these strawberries leading up to the point-
of-prediction. The environmental data includes: wind speed, wind direction,
temperature, light-intensity, humidity, precipitation, positions-of-
strawberries, yield-per-row-of-strawberries, and many more less significant
features. This data also includes irrigation data such as nutrition, soil-
moisture, soil-temperature, irrigation-status. We normalised, one-hot encoded
categorical variables and split the data (80-20) randomly into training and
test sets. We then further subdivided the training set into validation sets
for model selection purposes.

We applied a 1D/ time-series CNN (Equations: 1, 5 as depicted in Figure: 6)
followed by a dense ANN, and Sigmoid again as depicted in Figure: 8) to
summarise the feature vector and to predict the output/ yield of the
strawberries. This prediction will then be based on the environment the
strawberries experienced leading up to the point of prediction. Given our
data, and our feature engineering, we were able to obtain the following
outcomes in Table: I.

Days Ahead |  | Mean Absolute Percentage Error
---
(MAPE)
7 | 8.001
14 | 14.669
21 | 22.326
TABLE I: Table of predictive results of the constelation network (Figure: 11)
predicting strawberry yield.

###  2.4 Equations

####  2.4.1 Sigmoid

$\displaystyle\sigma(x)=\frac{1}{1+e^{-x}}$ (3)

####  2.4.2 ReLU

$\displaystyle R(x)=\text{max}(0,x)$ (4)

####  2.4.3 Sigmoid-Approximate

$\displaystyle\sigma(x)\approx\sigma_{a}(x)=0.5+0.197x+-0.004x^{3}$ (5)

####  2.4.4 ReLU-Approximate

$\displaystyle R(x)\approx R_{a}(x)=\frac{4}{3\pi
q}x^{2}+\frac{1}{2}x+\frac{q}{3\pi}$ (6)

####  2.4.5 Sigmoid-Derivative

$\displaystyle\frac{d\sigma(x)}{dx}=\frac{e^{-x}}{(1+e^{-x})^{2}}=(\frac{1+e^{-x}-1}{1+e^{-x}})(\frac{1}{1+e^{-x}})=(1-\sigma(x))\sigma(x)$
(7)

####  2.4.6 ReLU-Derivative

$\displaystyle\frac{dR(x)}{dx}=\begin{cases}1,&\text{if}\ x>0\\\
0,&\text{otherwise}\end{cases}$ (8)

####  2.4.7 Sigmoid-Approximate-Derivative

$\displaystyle\frac{d\sigma(x)}{dx}\approx\frac{d\sigma_{a}(x)}{dx}=0.197+-0.012x^{2}$
(9)

####  2.4.8 ReLU-Approximate-Derivative

$\displaystyle\frac{dR(x)}{dx}\approx\frac{dR_{a}(x)}{dx}=\frac{8}{3\pi
q}x+\frac{1}{2}$ (10)

##  3 Results Discussion

As can be seen in Figure: 9 using the same network sphira (Figure: 5) with
different approximated activation functions Sigmoid (Equation: 5) and ReLU
(Equation: 6) dramatically effects the precision of the neural network over
multiple training attempts with randomised weights. However the accuracy of
both on average is roughly equal within a few percent. This shows that in our
implementation at least that this ReLU approximation being backpropagated may
indeed cause some instability, more frequently. Sigmoid in contrast is a
static approximation which may be part of the reason for its greater
stability, and thus consistency provided randomised weights to the rest of the
network. We can see that both the sphira (Figure: 5) and constellation (Figure
11) networks can produce acceptable results on the testing set while computing
over cyphertexts and plaintexts. Our networks can be seen working in both
classification and regression problems, Fashion-MNIST, and strawberry yield
prediction respectively.

We find however that in our strawberry yield prediction one of the weaknesses
of our approach was to completely randomise the sequences, as some sequences
could possibly overlap, meaning that the network may have at least some prior
experience of the gap between point-of-prediction and point-predicted. This
should be an area of possible future expansion is to split the data
differently by time, and use only environmental data in the future that is
distinct. Another area where improvement could be garnered is by using smaller
but bootstrappable cyphertexts, this may reduce predictive performance of the
networks since each bootstrapping operation would incur a noise penalty, but
this would significantly improve the speed of computation since we could use
smaller cyphertexts that take less time to transverse, transmit, and compute.
We can see from Figure: 10 that the time taken for computing plaintexts is
relatively small, producing results rapidly. The same network however provided
cyphertexts computes near equivalent results, but significantly slower. Not
only are cyphertexts more time intensive, but they are also significantly more
space intensive. We could see during cyphertext inference anywhere from
72-80GiB of RAM usage, meaning this is certainly not plausible on low-
specification machines. We could see significant gains in computational
performance if we added more rotation nodes to refresh the cyphertext more
frequently, to limit the number of levels it would contain, and thus the size
of the cyphertext. However in our case we wanted to reduce the number of
rotations as in practical applications this would result in more transmissions
from client-server which itself can be an expensive operation. This is a good
example of why bootstrapping while incurring a high cost itself, could save
computational time and space in the future, when it is more widely available.

The absolute performance of the two models in Figure 9 and Table I is
acceptable despite being fairly shallow models compared to those used in many
normal deep learning models. Our absolute performance is probably quite
limited by the shallowness of these models, in that the model may not be
complex enough to properly model some of these problems. In particular there
are a plethora of standard models that achieve 90% accuracy or greater, many
of which use 2-3 convolutional layers, with batch-normalisation, and max-
pooling. Clearly we cannot ordain context from a cyphertext making max-pooling
impossible however we can and do use strides as a way to reduce the
dimensionality in a similar way that max-pooling does. There have also been
proposals for batch-normalisation that involve multiplying by small fractions
that are occasionally recalculated, however this is quite complex and not
something we have been able to implement ourselves as of yet. This would
however stabilise the activations between nodes, and reduce the likelihood of
escaping the dynamically predicted range in the ReLU approximation causing the
in-precision in Figure 9.

Given that we can get acceptable performance, in different scenarios like
agricultural yield regression and image classification, this opens avenues for
data sharing. There are two avenues in particular, through encryption, and
through trust. In our case we assume a semi-honest threat model, yet we have
outlined a way of computation that does not need to reveal any data to the
third party. This means if we can provide sufficient predictive performance
then there are few barriers preventing sharing of encrypted data for
inference. There is of course the notable exception of any yet unknown
vulnerabilities in the underlying FHE scheme with default parameters provided
by MS-SEAL. The other avenue of data sharing that FHE fosters is that of
trust. Given a track record of reliable data processing in the encrypted form,
that this could lead to an increased awareness of the gains of deep learning
applied to various fields. With this greater awareness, and track record, it
could be surmised that it is more likely that over time the data owners might
choose to share data in the perceived-sensitivity scenario.

###  3.1 Limitations

Our work on encrypted deep learning has certain limitations we would like to
highlight:

FHE Training; In this paper we laboriously implement, describe, and show how
encrypted deep learning inference can be conducted. However there is little
reference to encrypted learning, that is to say where a neural network is
trained on cyphertexts. This is due to multiple limitations prevalent in the
field such as the lack of FHE compatibility with certain functions, such as
loss functions. This is an active area of research which we and the broader
research community are actively working on, to complete the encrypted
learning-to-inference chain. Another issue with cyphertext training for
example is when do we decide to stop training? As we cannot see the results,
and thus cannot gauge whether the network has under or over-fit. This is a
particularly interesting and challenging problem which we seek to also tackle
in future. Here however it can be thought that the models would be pre-trained
or transferred from a similar problem to avoid privacy leaks involved in
training.

LFHE; As previously mentioned our work here is over Levelled-FHE, where we
create optimised circuits for cyphertexts with discrete scales and primes,
which we swap down for each multiplication, a ”level”. LFHE is FHE without
bootstrapping. Bootstrapping is an expensive operation that refreshes the
cyphertexts levels allowing for an effective limitless depth to computations
(albeit with noise), while also helping to keep cyphertexts smaller than their
LFHE counterparts. Smaller cyphertexts can be operated on faster, but
bootstrapping in small circuits can often outweigh the benefit of using a
smaller but bootstrapped cyphertext, due to how expensive of an operation it
is. This limitation comes from a lack of bootstrapping support in MS-SEAL.
Once bootstrapping is supported however existing networks we propose here will
still be compatible assuming appropriate NumPy-container abstractions of FHE
will be passed in.

##  4 Conclusion

We have shown how FHE can be automatically parameterised directly from multi-
directed graphs for neural networks, using groups and a variation of the
travelling salesman problem for costs. We have shown how multi-directed graphs
can be used in an FHE compatible manner with FHE compatible nodes to
facilitate encrypted deep learning. We have evaluated a recent ReLU
approximation (with additionally backpropagated approximation range), against
the Sigmoid activation function, finding it slightly less accurate but much
less precise due to instabilities in the weight initialisation. We have
utilised our encrypted deep learning procedures, discussed throughout, in both
classification and regression problems. We have used an open dataset Fashion-
MNIST with open-source reproducible code examples to aid reproduction and
experimentation. We have briefly summarised applying encrypted deep learning
to an real world (sensitive) problem predicting strawberry yield with quite
some success. Our implementation is the most comprehensive encrypted deep
learning library currently available, now with automatic FHE parameterisation,
traversal, cross-compatible/ interoperable NumPy custom-containers,
documentation and expandability for future distributed or GPU accelerated
computations with FHE, using the state-of-the-art RNS-CKKS FHE scheme provided
by the MS-SEAL back end.

There is still much research that needs to be conducted, in particular with
FHE and training. Encrypted deep learning is not a solution currently to any
problem that relies on very specific data that is very dissimilar to other
problems, meaning we cannot transfer some understanding in a private manner.
We are still limited by multi/parallel-processing, however in the case of
Python-FHEz we leave the back end open-ended following the NumPy custom
container specification such that this gap can be easily retrofitted later,
just like Dask and CuPy have for standard NumPy.

Finally with encrypted deep learning we can open avenues for data sharing that
have previously been untenable in the face of their rightful privacy concerns.
The more of the pitfalls of FHE that are solved, and the more usable encrypted
deep learning becomes, the more likely we are to see it provide some critical
predictive service to improve fields like agriculture, and medicine.

## Acknowledgments

The authors would like to thank the British Biotechnology and Biological
Sciences Research Council (BBSRC) in collaboration with Berry Gardens Growers
and the University of Lincoln for funding and support.

## References

  * [1] Ran Gilad-Bachrach et al.  “Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy”  In _International Conference on Machine Learning_ , 2016, pp. 201–210
  * [2] Craig Gentry  “Fully homomorphic encryption using ideal lattices”  In _Proceedings of the forty-first annual ACM symposium on Theory of computing_ , 2009, pp. 169–178
  * [3] Craig Gentry and Shai Halevi  “Implementing Gentry’s Fully-Homomorphic Encryption Scheme” https://eprint.iacr.org/2010/520, Cryptology ePrint Archive, Report 2010/520, 2010
  * [4] Nigel P Smart and Frederik Vercauteren  “Fully homomorphic encryption with relatively small key and ciphertext sizes”  In _International Workshop on Public Key Cryptography_ , 2010, pp. 420–443  Springer
  * [5] Zvika Brakerski and Vinod Vaikuntanathan  “Efficient Fully Homomorphic Encryption from (Standard) LWE” https://eprint.iacr.org/2011/344, Cryptology ePrint Archive, Report 2011/344, 2011
  * [6] Zvika Brakerski, Craig Gentry and Vinod Vaikuntanathan  “Fully Homomorphic Encryption without Bootstrapping” https://eprint.iacr.org/2011/277, Cryptology ePrint Archive, Report 2011/277, 2011
  * [7] Adriana Lopez-Alt, Eran Tromer and Vinod Vaikuntanathan  “On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption” https://eprint.iacr.org/2013/094, Cryptology ePrint Archive, Report 2013/094, 2013
  * [8] Junfeng Fan and Frederik Vercauteren  “Somewhat Practical Fully Homomorphic Encryption” https://eprint.iacr.org/2012/144, Cryptology ePrint Archive, Report 2012/144, 2012
  * [9] Joppe W. Bos, Kristin Lauter, Jake Loftus and Michael Naehrig  “Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme” https://eprint.iacr.org/2013/075, Cryptology ePrint Archive, Report 2013/075, 2013
  * [10] Craig Gentry, Amit Sahai and Brent Waters  “Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based” https://eprint.iacr.org/2013/340, Cryptology ePrint Archive, Report 2013/340, 2013
  * [11] Jung Hee Cheon, Andrey Kim, Miran Kim and Yongsoo Song  “Homomorphic encryption for arithmetic of approximate numbers”  In _International Conference on the Theory and Application of Cryptology and Information Security_ , 2017, pp. 409–437  Springer
  * [12] Jung Hee Cheon et al.  “Bootstrapping for approximate homomorphic encryption”  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , 2018, pp. 360–384  Springer
  * [13] PALISADE  “PALISADE Release”, 2021  URL: https://gitlab.com/palisade/palisade-release
  * [14] Seoul National University Cryptography LAB  “HEAAN”, 2020  URL: https://github.com/snucrypto/HEAAN
  * [15] “Microsoft SEAL (release 3.4.5)” Microsoft Research, Redmond, WA., https://github.com/Microsoft/SEAL, 2020
  * [16] IBM  “helib”, 2021  URL: https://github.com/homenc/HElib
  * [17] “Lattigo v2.1.1” EPFL-LDS, Online: http://github.com/ldsec/lattigo, 2020
  * [18] George Onoufriou  “Python-FHEz Source Repository”, 2021  URL: https://gitlab.com/DeepCypher/Python-FHEz
  * [19] Google  “Google trends topics: Privacy, Edward Snowden, Cambridge Analytica”, 2021  URL: https://trends.google.co.uk/trends/explore?date=2010-01-01%202021-07-19&geo=GB&q=%2Fm%2F06804,%2Fm%2F0vzv0rq,%2Fg%2F11clljsm74
  * [20] Edward Snowden  “Permanent Record”  Metropolitan Books, 2019
  * [21] United Kingdom Parliament  “Data Protection Act 2018”, 2018  URL: https://www.legislation.gov.uk/ukpga/2018/12/contents/enacted
  * [22] George Onoufriou, Paul Mayfield and Georgios Leontidis  “Fully Homomorphically Encrypted Deep Learning as a Service”  In _Machine Learning and Knowledge Extraction_ 3.4 Multidisciplinary Digital Publishing Institute, 2021, pp. 819–834
  * [23] Joon-Woo Lee et al.  “Privacy-Preserving Machine Learning with Fully Homomorphic Encryption for Deep Neural Network”  In _arXiv preprint arXiv:2106.07229_ , 2021
  * [24] Souhail Meftah et al.  “DOReN: Towards Efficient Deep Convolutional Neural Networks with Fully Homomorphic Encryption”  In _IEEE Transactions on Information Forensics and Security_ IEEE, 2021
  * [25] Chiraag Juvekar, Vinod Vaikuntanathan and Anantha Chandrakasan  “GAZELLE: A low latency framework for secure neural network inference”  In _27th USENIX Security Symposium (USENIX Security 18)_ , 2018, pp. 1651–1669
  * [26] Néstor J Hernández Marcano, Mads Moller, Soren Hansen and Rune Hylsberg Jacobsen  “On fully homomorphic encryption for privacy-preserving deep learning”  In _2019 IEEE Globecom Workshops (GC Wkshps)_ , 2019, pp. 1–6  IEEE
  * [27] Alex Krizhevsky and Geoffrey Hinton  “Learning multiple layers of features from tiny images”  Citeseer, 2009
  * [28] Jia Deng et al.  “Imagenet: A large-scale hierarchical image database”  In _2009 IEEE conference on computer vision and pattern recognition_ , 2009, pp. 248–255  Ieee
  * [29] Roshan Dathathri et al.  “EVA: an encrypted vector arithmetic language and compiler for efficient homomorphic computation”  In _Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation_ ACM, 2020  DOI: 10.1145/3385412.3386023
  * [30] Zhigang Chen  “SEAL-Python Bindings Source Repository”, 2021  Wanli university  URL: https://github.com/Huelse/SEAL-Python
  * [31] Han Xiao, Kashif Rasul and Roland Vollgraf  “Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms”  In _CoRR_ abs/1708.07747, 2017  arXiv: http://arxiv.org/abs/1708.07747


# Geometry in the Furstenberg Conjecture

Yunping JIANG  Yunping Jiang: Department of Mathematics, Queens College of the
City University of New York, Flushing, NY 11367-1597 and Department of
Mathematics Graduate School of the City University of New York 365 Fifth
Avenue, New York, NY 10016<EMAIL_ADDRESS>
###### Abstract.

In this paper, we show how geometry plays in the study of the Furstenberg
conjecture (refer to [1]). Let $p>1$ and $q>1$ be two relative prime positive
integers. We prove that a non-atomic $p$\- and $q$-invariant measure having
balanced geometry must be the Lebesgue measure. In the proof, we will not
assume the ergodicity of the measure. The result provides an intuitive
geometric criterion to either prove the Furstenberg conjecture or construct a
counter-example.

###### Key words and phrases:

the Furstenberg conjecture, balanced geometry, Lebesgue measure, invariant
measure

###### 2010 Mathematics Subject Classification:

Primary 37A05, 37E05; Secondary 28D20, 28D05

This material is based upon work supported by the National Science Foundation.
It is also supported by the Simons Foundation (grant number 523341) and PSC-
CUNY awards.

##  1\. Balanced Geometry.

Suppose $\mathbb{R}$ is the real line, and suppose $\mathbb{Z}$ is the set of
integers. We call $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ the unit circle. Let
$\mathcal{B}$ be the standard Borel $\sigma$-field on $\mathbb{T}$. Let
$\mu_{0}(A)=\int_{A}dx$ be the Lebesgue probability measure on $\mathbb{T}$.
We use $|x-y|=\mu_{0}([x,y])$ to denote the length of the interval $[x,y]$.
Let $\mu$ be a non-atomic probability Borel measure on $\mathbb{T}$ with full
support. We simply call it a measure.

Let $\mathbb{N}$ be the set of natural numbers. For an integer $p>1$, consider
the $p$-action on $\mathbb{T}$,

$f_{p}:x\mapsto px\pmod{1}.$

The $p$-action gives a partition on $\mathbb{T}$ by intervals,

$\eta_{1}=\Big{\\{}I_{i}=\Big{[}\frac{i}{p},\frac{i+1}{p}\Big{]}\;\Big{|}\;0\leq
i\leq p-1\Big{\\}}.$

Pull-back $\eta_{1}$, we get a sequence of nested partitions on $\mathbb{T}$
by intervals

$\eta_{n}=f^{-(n-1)}_{p}\eta_{1},\quad n\in\mathbb{N}.$

The intervals in $\eta_{n}$ can be labeled by using the symbolic space,

$\Sigma_{n}=\prod_{0}^{n-1}\\{0,1,\cdots,p-1\\}$ $=\\{w_{n}=i_{0}i_{1}\cdots
i_{k}\cdots i_{n-1}\;|\;i_{k}\in\\{0,1,\cdots,p-1\\},0\leq k\leq n-1\\}$

with the shift

$\sigma:w_{n}\in\Sigma_{n}\mapsto\sigma(w_{n})=i_{1}\cdots
i_{n-1}\in\Sigma_{n-1}.$

The interval $I_{w_{n}}$ is defined inductively such that

$f_{p}:I_{w_{n}}\in\eta_{n}\to I_{\sigma(w_{n})}\in\eta_{n-1}$

is a homeomorphism and $\eta_{n}=\\{I_{w_{n}}\;|\;w_{n}\in\Sigma_{n}\\}.$

For any $w_{n}=i_{0}i_{1}\cdots i_{n-1}\in\Sigma_{n}$, let
$w_{n-1}=i_{0}i_{1}\cdots i_{n-2}\in\Sigma_{n-1}$. One can check that

$I_{w_{n-1}}=\cup_{i=0}^{p-1}I_{w_{n-1}i}\quad\hbox{and}\quad
f^{-1}_{p}(I_{w_{n-1}})=\cup_{i=0}^{p-1}I_{iw_{n-1}}.$

Take the inverse limit of $\\{(\Sigma_{n},\sigma)\\}_{n=1}^{\infty}$, we have
the full shift $\sigma:\Sigma\to\Sigma$ where

$\Sigma=\\{w=i_{0}i_{1}\cdots
i_{n-1}\cdots\;|\;i_{n-1}\in\\{0,1,\cdots,p-1\\},\;1\leq n<\infty\\}$

and

$\sigma(w)=i_{1}\cdots i_{n-1}\cdots.$

It gives a symbolic coding for every point in $\mathbb{T}$ with

$\\{x_{w}\\}=\cap_{n=1}^{\infty}I_{w_{n}},\quad w=w_{n}i_{n}\cdots\in\Sigma.$

This symbolic coding is almost one-to-one except for those endpoints of
$I_{w_{n}}$ on which this symbolic coding is two-to-one.

A measure $\mu$ is said to be $p$-invariant if

$\mu(f^{-1}_{p}(A))=\mu(A)$

for all $A\in\mathcal{B}$.

######  Definition 1.

We say a measure $\mu$ has balanced geometry (with respective to the
$p$-action) if there is a constant $C_{0}>0$ such that for any $n\geq 2$ and
any $w_{n-1}\in\Sigma_{n-1}$ and any $0\leq i\leq p-1$,

$\frac{\sum_{0\leq j\not=i\leq p-1}\mu(I_{jw_{n-1}})}{\mu(I_{iw_{n-1}})}\geq
C_{0}.$

The Lebesgue measure $\mu_{0}$ is $p$-invariant and has balanced geometry. In
Appendix II, we will give a non-trivial example (Example 1) of $p$-invariant
measures having balanced geometry and an example (Example 2) of $2$-invariant
measure having imbalanced geometry.

##  2\. Balanced Geometry And Rigidity.

The main result in this paper is the following theorem.

######  Theorem 1.

Suppose $p>1$ and $q>1$ are two relative prime positive integers. Suppose
$\mu$ is a $p$\- and $q$-invariant measure having balanced geometry. Then
$\mu$ must be the Lebesgue measure $\mu_{0}$.

###### Proof.

We define a sequence of (probability) measures $\nu_{n}$ on $\mathbb{T}$ for
$n\geq 1$,

$\nu_{n}(A)=\frac{1}{p^{n}}\sum_{k=0}^{p^{n}-1}\mu\Big{(}A+\frac{k}{p^{n}}\Big{)}\quad
A\in\mathcal{B}.$

Let $g_{i}$, $0\leq i\leq p-1$, be all the inverse branches of $f_{p}$. Then

$g_{w_{n}}=g_{i_{0}}\circ\cdots\circ g_{i_{n-1}}\quad w_{n}=i_{0}i_{1}\cdots
i_{n-1}\in\Sigma_{n}$

are all the inverse branches of $f^{n}_{p}$. Let
$k=\sum_{j=0}^{n-1}i_{j}p^{j}$, one can check that

$g_{w_{n}}(x)=\frac{x}{p^{n}}+\frac{k}{p^{n}}\pmod{1}.$

When $A$ is contained in an interval in $\eta_{n}$, we have that

$\nu_{n}(A)=\frac{1}{p^{n}}\sum_{w_{n}\in\Sigma_{n}}\mu(g_{w_{n}}(f^{n}_{p}(A)))=\frac{1}{p^{n}}\mu(f_{p}^{-n}(f^{n}_{p}(A)))=\frac{1}{p^{n}}\mu(f^{n}_{p}(A)).$

The last equality holds because $\mu$ is $p$-invariant. One can check that
$\nu_{n-1}(A)\leq p\nu_{n}(A)$ for all $n\geq 1$ (we denote $\nu_{0}=\mu$).
Thus $\nu_{n-1}$ is absolutely continuous with respect to $\nu_{n}$ and we
have the Radon-Nikodym derivative $d\nu_{n-1}/d\nu_{n}$ for all $n\geq 1$. Let

$\phi_{n}=\frac{d\mu}{d\nu_{n}}\quad n\geq 1$

be the Radon-Nikodym derivative of $\mu$ to $\nu_{n}$.

For $\nu_{n}$-a.e. $x_{w}$ where $w=w_{k}\cdots=i_{0}i_{1}\cdots
i_{k-1}\cdots\in\Sigma$ and for any $k>n>m\geq 0$, we have that

$\frac{\nu_{m}(I_{w_{k}})}{\nu_{m+1}(I_{w_{k}})}=\frac{\frac{1}{p^{m}}\mu(f_{p}^{-m}(f_{p}^{m}(I_{w_{k}})))}{\frac{1}{p^{m+1}}\mu(f_{p}^{-(m+1)}(f_{p}^{(m+1)}(I_{w_{k}})))}$
$=\frac{p\mu(I_{\sigma^{m}(w_{k})})}{\mu(f_{p}^{-1}(f_{p}(I_{\sigma^{m}(w_{k})})))}=\frac{p\mu(I_{\sigma^{m}(w_{k})})}{\sum_{j=0}^{p-1}\mu(I_{j\sigma^{m+1}(w_{k})})}$
$=\frac{p}{1+\frac{\sum_{0\leq j\leq
p-1,j\sigma^{m+1}(w_{k})\not=\sigma^{m}(w_{k})}\mu(I_{j\sigma^{m+1}(w_{k})})}{\mu(I_{\sigma^{m}(w_{k})})}}\leq\frac{p}{1+C_{0}}$

because of balanced geometry. Therefore we have that

$\frac{\mu(I_{w_{k}})}{\nu_{n}(I_{w_{k}})}=\prod_{m=0}^{n-1}\frac{\nu_{m}(I_{w_{k}})}{\nu_{m+1}(I_{w_{k}})}\leq\frac{p^{n}}{(1+C_{0})^{n}}$

and

(1)
$~{}\phi_{n}(x_{w})=\lim_{k\to\infty}\frac{\mu(I_{w_{k}})}{\nu_{n}(I_{w_{k}})}\leq\frac{p^{n}}{(1+C_{0})^{n}}$

(refer to Lemma 2 in Appendix I).

Let $B_{n}=\\{x\in\mathbb{T}\;|\;\phi_{n}(x)\hbox{ is not defined}\\}$. We
have $\mu(B_{n})\leq\nu_{n}(B_{n})=0$. Consider

$A_{n}=\\{x\in\mathbb{T}\setminus
B_{n}\;|\;\phi_{n}(x)=0\\}=\phi_{n}^{-1}(0).$

It is measurable and

$\mu(A_{n})=\int_{A_{n}}\;d\mu(x)=\int_{A_{n}}\phi_{n}(x)\;d\nu_{n}(x)=0$

Let

$K=\\{x\;|\;\phi_{n}(x)>0\mbox{ for all }n\geq 1\\}=\bigcap_{n\geq
1}(A_{n}\cup B_{n})^{c}=\Big{(}\bigcup_{n=1}^{\infty}(A_{n}\cup
B_{n})\Big{)}^{c}$

Then we have that $\mu(K)=1$. On $K$, we have

$d\nu_{n}(x)=\frac{1}{\phi_{n}(x)}\;d\mu(x).$

for all $n\geq 1$.

The measure $\mu$ is the Lebesgue measure $\mu_{0}$ if and only if its Fourier
coefficient $f_{m}=\int_{\mathbb{T}}e^{2\pi imx}d\mu(x)=0$ for all integers
$m\geq 1$. Denote $e(x)=e^{2\pi ix}$ and let us fix an integer $m\geq 1$. Let
$T_{n}$ and $C_{1}$ and $n_{0}$ be the numbers in Lemma 1 in Appendix I. For
each $n>n_{0}$, we define

$\beta_{T_{n}}(x)=\frac{1}{T_{n}}\sum_{k=0}^{T_{n}-1}e(mq^{k}x).$

Then

$\int_{K}\frac{|\beta_{T_{n}}(x)|^{2}}{\phi_{n}(x)}\,d\mu(x)=\int_{K}|\beta_{T_{n}}(x)|^{2}\,d\nu_{n}(x)$
$=\frac{1}{p^{n}}\int_{K}\sum_{k=0}^{p^{n}-1}\Big{|}\beta_{T_{n}}\Big{(}x+\frac{k}{p^{n}}\Big{)}\Big{|}^{2}\,d\mu(x)=\int_{K}h(x)\,d\mu(x)=\int_{\mathbb{T}}h(x)\,d\mu(x),$

where

$h(x)=\frac{1}{p^{n}}\frac{1}{T_{n}^{2}}\sum_{k=0}^{T_{n}-1}\sum_{l=0}^{T_{n}-1}e(m(q^{k}-q^{l})x)\sum_{j=0}^{p^{n}-1}e\Big{(}m\Big{(}\frac{(q^{k}-p^{l})j}{p^{n}}\Big{)}\Big{)}.$

If $0\leq k\neq l\leq T_{n}$, then $q^{k}\neq q^{l}\mod p^{n}$. This implies
that

$\sum_{j=0}^{p^{n}-1}e\Big{(}m\Big{(}\frac{(q^{k}-q^{l})j}{p^{n}}\Big{)}\Big{)}=0.$

So we have $h(x)=1/T_{n}$, and $\int_{\mathbb{T}}h(x)d\mu(x)=1/T_{n}$. This
implies that

$\int_{K}\frac{|\beta_{T_{n}}(x)|^{2}}{\phi_{n}(x)}\,d\mu(x)=\frac{1}{T_{n}}.$

Using the Cauchy-Schwarz inequality,

$\left|\int_{\mathbb{T}}\beta_{T_{n}}(x)\,d\mu(x)\right|^{2}=\left|\int_{K}\beta_{T_{n}}(x)\,d\mu(x)\right|^{2}\leq\int_{K}\frac{|\beta_{T_{n}}(x)|^{2}}{\phi_{n}(x)}\,d\mu(x)\cdot\int_{K}\phi_{n}(x)\,d\mu(x)$
$=\frac{1}{T_{n}}\int_{K}\phi_{n}(x)\,d\mu(x)=\frac{1}{C_{1}p^{n}}\int_{K}\phi_{n}(x)\,d\mu(x)=\frac{1}{C_{1}p^{n}}\int_{\mathbb{T}}\phi_{n}(x)\,d\mu(x).$

From (1), we have

$\Big{|}\int_{\mathbb{T}}\beta_{n}(x)\,d\mu(x)\Big{|}\leq\frac{1}{\sqrt{C_{1}}(1+C_{0})^{\frac{n}{2}}}\to
0\quad\hbox{as}\quad n\to\infty.$

Since $\mu$ is $q$-invariant,

$\int_{\mathbb{T}}\beta_{T_{n}}(x)\,d\mu(x)=\int_{\mathbb{T}}e(mx)\,d\mu(x),\;\;\forall\;n\geq
n_{0},$

we get

$\int_{\mathbb{T}}e(mx)\,d\mu(x)=0.$

Since $m\geq 1$ is any integer, $\mu=\mu_{0}$. This completes the proof of the
theorem.

∎

######  Remark 1.

In Theorem 1, we have no assumption about the ergodicity on $\mu$. The
balanced geometry condition is not preserved under the ergodic decomposition.
One can show that the balanced geometry condition plus the ergodicity
assumption on $\mu$ is essentially equivalent to the positivity of the metric
entropy $h_{\mu}(f_{p})$. Theorem 1 plus the ergodicity assumption will give
Rudolph’s theorem in [7] (see [6] in a more general setting). However, the
balanced geometry condition gives an intuitive geometric view to either verify
Furstenburg’s conjecture or construct a counter-example (as suggested by
Dennis Sullivan to the author). The counter-example should have very
imbalanced geometry like the devil’s staircase but still need to be ergodic.

##  3\. Appendix I

In Appendix I, we give a detailed proof of a result in number theory (Lemma 1)
and state the martingale convergence theorem (Lemma 2) in our case. Both of
them are used in the proof of Theorem 1.

######  Lemma 1.

Suppose $p>1$ and $q>1$ are two relatively prime integers. Suppose $a\geq 1$
is an interger. Let

$T_{n}=\\#\Big{(}\\{aq^{k}\pmod{p^{n}}\;\;|\;k=0,1,\cdots\\}\Big{)}$

Then there is a constant $C_{1}=C_{1}(a,p,q)>0$ and a constant integer
$n_{0}=n_{0}(a,p,q)$ such that

$T_{n}=C_{1}p^{n},\;\;\forall\;n\geq n_{0}.$

###### Proof.

Let $a=bp^{r}$ with $\gcd(b,p)=1$. For every $n\geq r+1$, consider two
integers $k>l$ such that $aq^{k}=aq^{l}\pmod{p^{n}}$. That is,

$aq^{l}(q^{k-l}-1)=mp^{n}$

for some integer $m\geq 0$. This implies that

$bq^{l}(q^{k-l}-1)=mp^{n-r}$

Since $b$ and $q$ are both relatively prime to $p$, we have
$p^{n-r}|(q^{k-l}-1)$, that is,

$q^{k-l}=1\pmod{p^{n-r}}.$

Thus $T_{n}$ is the smallest positive integer such that $q^{T_{n}}=1\mod
p^{n-r}$.

Suppose $q^{T_{n}}=k_{n}p^{n-r}+1$ for some integer $k_{n}\geq 1$. For
$n=r+1$, we have $q^{T_{r+1}}=k_{r+1}p+1$. Let us write $k_{r+1}=u_{0}p^{s}$,
where $(u_{0},p)=1$. Then

$q^{T_{r+1}}=u_{0}p^{s+1}+1=u_{0}p^{(r+s+1)-r}+1=q^{T_{r+s+1}}.$

This implies

$q^{pT_{r+s+1}}=(u_{0}p^{s+1}+1)^{p}$
$=\sum_{j=0}^{p}\left(\begin{array}[]{l}p\cr
j\end{array}\right)(u_{0}p^{s+1})^{p-j}=(u_{0}p^{s+1})^{p}+p(u_{0}p^{s+1})^{p-1}+\ldots+p(u_{0}p^{s+1})+1$
$=u_{1}p^{s+2}+1.$

Note that $u_{1}=u_{0}+p(\cdots)=u_{0}\pmod{p}$. Since $(u_{0},p)=1$, we have
$(u_{1},p)=1$ and thus

$u_{1}p^{s+2}+1=q^{T_{r+s+2}}.$

Therefore,

$pT_{r+s+1}=T_{r+s+2}.$

Inductively we get

$T_{r+s+1+m}=p^{m}T_{r+s+1},\;\;\forall\;m\geq 0.$

Setting $n_{0}=r+s+1$ we have

$T_{n_{0}+m}=p^{m}T_{n_{0}},\;\;\forall\;m\geq 0.$

That is,

$\frac{T_{n_{0}+m}}{p^{n_{0}+m}}=\frac{T_{n_{0}}}{p^{n_{0}}},\;\;\forall m\geq
0.$

Therefore, let

$C_{1}=\frac{T_{n_{0}}}{p^{n_{0}}}.$

Then

$T_{n}=C_{1}p^{n},\quad\forall n\geq n_{0}.$

∎

Consider $\mathcal{P}=(\mathbb{T},\mathcal{B},\nu_{n})$ as a probability space
where $\nu_{n}$ is the probability measure constructed in the proof of Theorem
1. Consider $X=\phi_{n}$ as a random variable on $\mathcal{P}$. Let
$\mathcal{B}_{k}$ be the $\sigma$-field generated by
$\eta_{k}=\\{I_{w_{k}}|w_{k}\in\Sigma_{k}\\}$ for every $k\geq 1$. Then we
have a sequence of increasing $\sigma$-fields

$\mathcal{B}_{1}\subset\mathcal{B}_{2}\subset\cdots\subset\mathcal{B}_{k}\subset\mathcal{B}_{k+1}\subset\cdots\subset\mathcal{B}$

and $\mathcal{B}=\cup_{k=1}^{\infty}\mathcal{B}_{k}$. Let
$X_{k}=E(X|\mathcal{B}_{k})$ be the expectation of $X$ on $\mathcal{B}_{k}$,
which is a $\mathcal{B}_{k}$-measurable function. Then we have
$X_{k}=E(X_{k+1}|\mathcal{B}_{k})$, $\nu_{n}$-a.e.. Thus,
$\\{(X_{k},\mathcal{B}_{k})\\}_{k=1}^{\infty}$ gives us a martingale on
$\mathcal{P}$ and

$X_{k}(x)=\frac{\int_{I_{w_{k}}}Xd\nu_{n}}{\nu_{n}(I_{w_{k}})}=\frac{\mu(I_{w_{k}})}{\nu_{n}(I_{w_{k}})}\quad\hbox{for
$\nu_{n}$-a.e. $x\in I_{w_{k}}$}.$

Now we apply Theorem 5.7 in [8] to our case.

######  Lemma 2 (Martingale Convergence Theorem).

Since $X\in L_{1}(\nu_{n})$, the martingale
$\\{X_{k}=E(X|\mathcal{B}_{k})\\}_{k=1}^{\infty}$ converges to $X$ for almost
all points with respect to $\nu_{n}$ as $k$ goes to $\infty$.

##  4\. Appendix II

In Appendix II, we give a non-trivial example of a $p$-invariant measure
having balanced geometry (Example 1) and an example of $p$-invariant measure
having imbalanced geometry (Example 2). From these two examples, one can see
that the balanced geometry condition is interesting in studying the rigidity
theory.

Suppose $f:\mathbb{T}\to\mathbb{T}$ is a covering map of degree $p$. We call
it a circle endomorphism. We say $f$ is $C^{1}$ if it has a continuous
derivative $f^{\prime}$. We say a $C^{1}$ circle endomorphism $f$ expanding if
there are two constants $D>0$ and $\lambda>1$ such that

$|(f^{n})^{\prime}(x)|\geq D\lambda^{n}\quad x\in\mathbb{T}.$

We say $f$ is $C^{1+\alpha}$ if $f^{\prime}$ is an $\alpha$-Hölder continuous
function for some $0<\alpha\leq 1$, that is, there are two constants $0<d<1$
and $D>0$ such that

$|f^{\prime}(x)-f^{\prime}(y)|\leq D|x-y|^{\alpha}\quad x,y\in\mathbb{T}\hbox{
with }|x-y|<d.$

Any $C^{1+\alpha}$ expanding endomorphism $f$ has a unique smooth
$f$-invariant probability measure $\nu$ (refer to [3, 4]). This means that we
have a positive $\alpha$-Hölder continuous function $\rho(x)$ on $\mathbb{T}$
such that

$\nu(A)=\int_{A}\rho(x)dx\quad\hbox{and}\quad\nu(f^{-1}(A))=\nu(A)\quad\forall
A\in\mathcal{B}.$

The formula $h_{0}(x)=\int_{0}^{x}\rho(x)dx$ defines a
$C^{1+\alpha}$-diffeomorphism of $\mathbb{T}$. One can check that

$g=h_{0}\circ f\circ h_{0}^{-1}$

preserves the Lebesgue measure $\mu_{0}$. Furthermore, $g$ is topologically
conjugate to $f_{p}$, that is, we have a homeomorphism
$h:\mathbb{T}\to\mathbb{T}$ such that

$g\circ h=h\circ f_{p}$

Let $\mu=(h^{-1})_{*}\mu_{0}$ defined as $\mu(A)=\mu_{0}(h(A))$ for all
$A\in\mathcal{B}$. In general, $\mu$ is totally singular with respective to
$\mu_{0}$ since, otherwise, $g=f_{p}$ (see [4]). Actually, in general,
$h\not=id$ is a quasisymmetric homomorphism and as long as $h$ is symmetric,
then $h=id$ (see [4]).

######  Example 1.

The measure $\mu$ constructed above is $p$-invariant and has balanced
geometry.

###### Proof.

For $p$-invariance, it is because that for any $A\in\mathcal{B}$,

$\mu(f_{p}^{-1}(A))=\mu_{0}(h(f_{p}^{-1}(A)))=\mu_{0}(g^{-1}(h(A)))=\mu_{0}(h(A))=\mu(A).$

For balanced geometry, without loss of generality, we assume that

$1<a=\min_{x\in\mathbb{T}}|g^{\prime}(x)|\leq
A=\max_{x\in\mathbb{T}}|g^{\prime}(x)|<\infty.$

For any $n\geq 2$ and $w_{n-1}\in\Sigma_{n-1}$ and $0\leq i\leq p-1$ , we have
that

$f_{p}^{-1}(I_{w_{n-1}})=I_{iw_{n-1}}\cup\cup_{0\leq j\not=i\leq
p-1}I_{jw_{n-1}}.$

and

$g^{-1}(h(I_{w_{n}}))=h(I_{iw_{n-1}})\cup\cup_{0\leq j\not=i\leq
p-1}h(I_{jw_{n-1}}).$

Since $g$ preserves the Lebesgue measure $\mu_{0}$, we have that

$|h(I_{w_{n-1}})|=|g^{-1}(h(I_{w_{n}}))|=|h(I_{iw_{n-1}})|+\sum_{0\leq
j\not=i\leq p-1}|h(I_{jw_{n-1}})|.$

Since $g(h(I_{iw_{n-1}}))=h(I_{w_{n-1}})$, we have that, for any $j\not=i$,

$\frac{|g(h(I_{iw_{n-1}}))|}{|h(I_{iw_{n-1}})|}=1+\frac{|h(I_{jw_{n-1}})|}{|h(I_{iw_{n-1}})|}+\sum_{0\leq
k\not=i,j\leq p-1}\frac{|h(I_{kw_{n-1}})|}{|h(I_{iw_{n-1}})|}.$

This implies that

$\frac{|h(I_{jw_{n-1}})|}{|h(I_{iw_{n-1}})|}\Big{(}1+\sum_{0\leq k\not=i,j\leq
p-1}\frac{|h(I_{kw_{n-1}})|}{|h(I_{jw_{n-1}})|}\Big{)}$
$=\frac{|g(h(I_{iw_{n-1}}))|}{|h(I_{iw_{n-1}})|}-1\geq a-1.$

Thus, we have that, for the constant $D=1+(p-2)A/a>0$,

$\frac{\mu(I_{jw_{n-1}})}{\mu(I_{iw_{n-1}})}=\frac{|h(I_{jw_{n-1}})|}{|h(I_{iw_{n-1}})|}\geq
C_{0}=\frac{a-1}{D}>0.$

This proves that $\mu$ has balanced geometry.

∎

For a given $0<\alpha<1$, let $f$ be a $C^{1+\alpha}$ almost expanding circle
endomorphism of degree $2$, that is, $f(0)=0$ and $f^{\prime}(0)=1$ and
$|f^{\prime}(x)|>1$ for all $x\not=0\in\mathbb{T}$. Assume
$f(x)=x+x^{1+\alpha}+o(x^{1+\alpha})$ in a small neighborhood of $0$. Then $f$
has an $f$-invariant measure $\mu$ absolutely continuous with respect to the
Lebesgue measure $\mu_{0}$ such that the density $\rho(x)=d\mu/d\mu_{0}(x)$ is
continuous on $(0,1]$ but $\rho(x)\to\infty$ as $x\to 0$ (refer to [2]). The
formula $h_{0}(x)=\int_{0}^{x}\rho(x)dx$ defines a homeomorphism of
$\mathbb{T}$ and $C^{1}$ on $(0,1)$. The map

$g=h_{0}\circ f\circ h_{0}^{-1}$

preserves the Lebesgue measure $\mu_{0}$ and $g(0)=0$ and $g^{\prime}(0)=1$.
It is topologically conjugate to $f_{2}$. There is a homeomorphism
$h:\mathbb{T}\to\mathbb{T}$ such that

$g\circ h=h\circ f_{2}$

Let $\mu=(h^{-1})_{*}\mu_{0}$ defined as $\mu(A)=\mu_{0}(h(A))$ for all
$A\in\mathcal{B}$.

######  Example 2.

The measure $\mu$ is $2$-invariant and has imbalanced geometry.

###### Proof.

For $2$-invariance, it is because that for any $A\in\mathcal{B}$,

$\mu(f_{p}^{-1}(A))=\mu_{0}(h(f_{p}^{-1}(A)))=\mu_{0}(g^{-1}(h(A)))=\mu_{0}(h(A))=\mu(A).$

For any $n\geq 2$ and $0_{n-1}=\underbrace{0\cdots 0}_{n-1}\in\Sigma_{n-1}$
and $i=0$ , we have that

$f_{p}^{-1}(I_{0_{n-1}})=I_{0_{n}}\cup I_{10_{n-1}}.$

and

$g^{-1}(h(I_{0_{n-1}}))=h(I_{0_{n}})\cup h(I_{10_{n-1}}).$

Since $g$ preserves the Lebesgue measure $\mu_{0}$, we have that

$|h(I_{0_{n-1}})|=|g^{-1}(h(I_{0_{n}}))|=|h(I_{0_{n}})|+|h(I_{10_{n-1}})|$

and that

$\frac{|h(I_{0_{n-1}})|}{|h(I_{0_{n}})|}=1+\frac{|h(I_{10_{n-1}})|}{|h(I_{0_{n}})|}$

Since $g(h(I_{0_{n}}))=h(I_{0_{n-1}})$ and $g^{\prime}(0)=1$,

$\frac{|h(I_{10_{n-1}})|}{|h(I_{0_{n}})|}\to 0\quad\hbox{as}\quad n\to\infty.$

This says that $\mu$ has imbalanced geometry. ∎

Acknowledgment: I would like to thank Professor Huyi Hu and my student Yuan
(Jessica) Liu for for listening and helpful conversations on the initial
version of this paper and pointed out some typos.

## References

  * [1] H. Furstenberg, Disjointness in ergodic theory, minimal sets, and a problem in diophantine approximation. Math. Sys. Theory 1 (1967), 1-49.
  * [2] H. Hu, Decay of correlations for piecewise smooth maps with indifferent fixed points. Ergodic Theory and Dynamical Systems, Volume 24 (2004), Issue 2, 495-524. https://doi.org/10.1017/S0143385703000671
  * [3] Y. Jiang, A proof of existence and simplicity of a maximal eigenvalue for Ruelle-Perron-Frobenius operators. Letters in Mathematical Physics, 48 (1999), no. 3, 211-219. https://doi.org/10.1023/A:1007595323704
  * [4] Y. Jiang, Symmetric invariant measures. Contemporary Mathematics, AMS, Vol. 575, 2012, 211-218. http://dx.doi.org/10.1090/conm/575/11399
  * [5] Y. Jiang, Renormalization and Geometry in One-Dimensional and Complex Dynamics. Advanced Series in Nonlinear Dynamics, Vol. 10 (1996), World Scientific Publishing Co. Pte. Ltd., River Edge, NJ, xvi+309 pp. ISBN 981-02-2326-9.
  * [6] A. Johsson, Measures on the circle invariant under multiplication by a nonlacunary subsemigroup of the integers. Israel Journal of Mathematics, 77 (1992), 211-240.
  * [7] D. Rudolph, $\times 2$ and $\times 3$ invariant measures and entropy. Ergod. Th. & Dynam. Sys. 10 (1990), 395-406.
  * [8] S. R. S. Varadhan, Probability Theory. Courant AMS Lecture Notes 7, 2001.