Christina Boura
email: christina.boura@uvsq.fr

Nicolas Gama
email: nicolas@inpher.io

Mariya Georgieva
email: mariya@inpher.io

Dimitar P Jetchev
email: dimitar@inpher.io

Simulating homomorphic evaluation of deep learning predictions

Keywords: neural networks, homomorphic encryption, TFHE, HEAAN

Introduction

Neural networks (NN) are extremely powerful machine learning algorithms for classification or recognition of complex data such as images, handwriting or speech. These algorithms are used in many domains and so, they often treat highly sensitive data like medical records or confidential financial information. One of the most popular choices for achieving privacy guarantee in these settings is Fully Homomorphic Encryption (FHE) [START_REF] Bourse | Fast homomorphic evaluation of deep discretized neural networks[END_REF][START_REF] Jiang | Secure outsourced matrix computation and application to neural networks[END_REF]. FHE schemes allow for computing on encrypted data in the sense that decrypting the encrypted result yields the result that would have been produced if the computation had been performed on the plaintext. Compared to other privacy-preserving solutions (e.g. Multiparty Computation (MPC)), FHE operations are non-interactive and thus, they save on communication costs. Second, MPC schemes require non-collusion assumptions on the computing parties in order to achieve privacy and such assumptions can often be challenging. In FHE applications, no such assumptions are needed.

The three FHE schemes B/FV [START_REF] Brakerski | Fully homomorphic encryption without modulus switching from classical gapsvp[END_REF][START_REF] Fan | Somewhat practical fully homomorphic encryption[END_REF][START_REF] Chen | Simple encrypted arithmetic library -SEAL v2.1[END_REF], TFHE [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF][START_REF] Chillotti | TFHE: Fast Fully Homomorphic Encryption over the Torus[END_REF], based on [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF][START_REF] Ducas | FHEW: bootstrapping homomorphic encryption in less than a second[END_REF] and HEAAN [START_REF] Cheon | Homomorphic encryption for arithmetic of approximate numbers[END_REF][START_REF] Cheon | Bootstrapping for approximate homomorphic encryption[END_REF], all based on the Ring-LWE problem, are currently among the most efficient constructions. For all of them, a homomorphic noise is added on the top of the plaintext. The scheme B/FV was initially designed to perform exact SIMD operations modulo a prime. Thus, for B/FV the added noise does not affect the outcome of the decryption in the sense that the decrypted value is exactly the plaintext. In this context the noise quantifies how many operations can be homomorphically executed with the decrypted value remaining correct. The notion of bootstrapping in B/FV has therefore the meaning of "noise reduction".

On the other hand, in HEAAN, homomorphic operations are floating-point operations where the least-significant bits of the mantissa are randomly rounded at each arithmetic operation to a value that is close to the exact result. The entropy in the errors induced by these least-significant roundings arise from many factors such as the randomness of the ciphertexts as well as the the randomness of the large evaluation keys. These errors, unpredictable to the users, are corrected by neither decryption nor bootstrapping (the decryption of the encryption is not the original message) and accumulate throughout the whole computation.

There is still a notion of the maximum number of homomorphic operations, or multiplicative level, that designs the maximum number of operations that can be applied on a given ciphertext: if we do less operations than this level, the decryption produces an approximate result (as opposed to the exact result in B/FV); if we exceed this level, the decryption fails completely in an undefined behaviour manner. The bootstrapping of HEAAN can still extend this level to allow further computations, but it does not reduce noise. As shown in [START_REF] Boura | Chimera: a unified framework for B/FV, TFHE and HEAAN fully homomorphic encryption and predictions for deep learning[END_REF], TFHE (the last of the above-mentioned schemes) can be interfaced with both B/FV and HEAAN, and thus, supports both exact or approximated arithmetic: in this paper, we only consider the approximate mode of operation.

For evaluating CNNs with FHE, one can either select one scheme over the other, or propose a hybrid solution combining HEAAN and TFHE. Indeed, some of the computations performed during a CNN evaluation are easier with TFHE while some others are more natural with HEAAN. For instance, in the case when many approximated computations have to be performed and a decision must be taken on the result, it is optimal to use the HEAAN scheme for the first part and switch to TFHE for evaluating the decision function. This hybrid approach based on the Chimera framework has already been used by one of the solutions proposed to the Idash'18 Track 2 [START_REF]Track 2: Secure parallel genome wide association studies using homomorphic encryption[END_REF][START_REF] Carpov | Privacypreserving semi-parallel logistic regression training with fully homomorphic encryption[END_REF] competition on designing homomorphic solutions for semi-parallel Genome Wide Association Studies (GWAS) based on logistic regression using homomorphically encrypted data. Here, the logistic re-gression requiring many iterations was performed with TFHE in order to use a fast bootstrapping to reduce the noise, whereas the linear algebra computations on matrix of large dimensions was performed with HEAAN using massively vectorized SIMD computations offered by the scheme.

Our Contributions

The goal of this paper is to efficienty simulate homomorphic evaluation of neural network predictions (in particular, CNN predictions) in order to analyze the stability of the performance (evaluation accuracy) of neural networks in the presence of noise due to FHE decryptions (what we refer to as the approximated computational model). Performing such an analysis on encrypted data can be extremely time consuming, the reason why we choose to do our analysis on the plaintext and simulate the noise resulting from the homomorphic computations and the function approximations.

In order to perform our experiments on approximate operations, we have chosen exclusively the HEAAN and TFHE schemes implemented in the context of the Chimera [START_REF] Boura | Chimera: a unified framework for B/FV, TFHE and HEAAN fully homomorphic encryption and predictions for deep learning[END_REF] framework. After analyzing the noise in the homomorphic operations in Section 2 and explaining how/why this noise can be modeled with Gaussian distributions in the context of both TFHE and HEAAN, we show in Section 3 how one can homomorphically evaluate various commonly used functions for deep learning (e.g., Abs, Sign, max and ReLU) with TFHE and HEAAN and discuss the potential difficulties of such an approach. We remark that the choice of a scheme also depends on the desired level of precision in the output. Through the simulation approach, one is able to efficiently determine the best CNN structure and the smallest FHE parameters required during a preliminary study phase.

We performed experiments with perturbations on three distinct convolutional neural networks of small (LeNet-5), medium (cat-and-dog-9) and large (ResNet-34) size and observed that all these networks support large relative errors of at least 10% without almost any impact on the global accuracy (see Section 2). This means, as we show, that only 4 bits of precision (instead of 20 to 40 bits usually) are needed on all fixed-point operations throughout the network, which yields very small parameter sets and fast homomorphic operations. Finally, these experiments allowed to make useful deductions about the stability of some common CNN operations (e.g., different pooling functions). As we show, all operations are not equally stable and thus, some of them should be preferred when used in a FHE context.

Outline. In Section 2 we recall the homomorphic schemes TFHE and HEAAN and we analyse the noise propagation for basic arithmetic (linear combination, multiplication, rotation/permutation and bootstrapping). In Section 3, we show how to tweak the bootstrapping to evaluate the activation functions of the CNN. Finally, in Section 4, we simulate the noise propagation during the homomorphic evaluation and measure its effect on the CNN prediction accuracy.

Homomorphic RLWE encryption schemes and noise propagation

The goal of this section is to introduce the key concepts concerning both the TFHE and HEAAN schemes that are necessary to understand the core of this article. As explained earlier, both schemes will be introduced via the Chimera framework [START_REF] Boura | Chimera: a unified framework for B/FV, TFHE and HEAAN fully homomorphic encryption and predictions for deep learning[END_REF] that provides a unified representation of these schemes as well as a uniform noise analysis. We start by introducing some necessary notation.

Notation. Let T = R/Z be the real torus, that is the set of real numbers modulo 1. We denote further by Z N [X] = Z[X]/(X N + 1) the ring of polynomials with integer coefficients modulo

X N +1. Respectively, R N [X] = R[X]/(X N +1
) is the ring of real polynomials modulo X N + 1. Informally, the elements of Z N [X] are seen as integer polynomials with N coefficients whereas the elements of R N [X] are seen as real polynomials with N coefficients.

In order to introduce the notion of slots (real or complex), we use the following two isomorphisms of R-vector spaces:

R[X]/(X N + 1) R N , f = a 0 + • • • + a N -1 X N -1 → (a 0 , . . . , a N ), (1)
and

R[X]/(X N + 1) C N/2 , f → (f (ζ), f (ζ 3 ), . . . , f (ζ N -1 )). (2)
Here ζ = e πi/N is a primitive root of X N + 1. Representation (1) corresponds to what is called the coefficient packing and representation [START_REF]Track 2: Secure parallel genome wide association studies using homomorphic encryption[END_REF] corresponds to what is called the slot packing.

HEAAN and TFHE through the Chimera framework

The Chimera framework introduced in [START_REF] Boura | Chimera: a unified framework for B/FV, TFHE and HEAAN fully homomorphic encryption and predictions for deep learning[END_REF] allows to apply elementary operations either from the HEAAN or the TFHE library to RLWE ciphertexts [START_REF] Lyubashevsky | EUROCRYPT, chapter On Ideal Lattices and Learning with Errors over Rings[END_REF] within the same FHE computation. Both use the same ciphertext space.

In this work, we describe these libraries mostly from the user point of view without going into the details of their internal representation. In particular, we view an RLWE ciphertext as an encryption of a plaintext in C N/2 (i.e., N/2 complex plaintext slots under the isomorphism ( 2)) on which one can perform approximated arithmetic. The coefficients to slots representation and slots to coefficients representation can be used at any moment to switch between a slotbased representation in C N/2 and a coefficient-based representation in R N .

The slots in a given ciphertext vector have a fixed public precision ρ > 0 in the following sense: the complex coordinates of the vector are all of the form (x + iy) • 2 τ for some public exponent τ > 0 (uniform across all the coordinates and precomputed in advance) and some secret x, y ∈ [-1, 1]. In addition, both x and y are assumed to have ρ fractional bits of precision (i.e., the size of the mantissa is exactly ρ bits, where ρ is usually a fixed constant across the entire computation).

During the FHE computation, only the ρ-bits of the mantissa are secret and are the only ones that are homomorphically evaluated.

In a pure floating-point model, the result of some operations cannot always be exactly represented on the target precision: these results are usually rounded to the nearest mantissa. In FHE, these roundings are more random and difficult to predict and we modelize this via a noise propagation model, whose mean and standard deviation depend on the elementary operation.

We will only refer to the internal cryptographic representation of the ciphertexts in the section where we define our noise propagation model. Namely, both TFHE and HEAAN schemes use RLWE ciphertexts in R N [X] 2 mod 1 (or R N [X] 2 mod q), the same key space Z N [X] with small coefficients and the same phase function ϕ s (a, b) = bs • a introduced in [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF]. In this framework, the approximated decryption, common to HEAAN and TFHE, considers that the phase is always close to the actual message and is a good enough approximation thereof. Then, accumulated errors are not corrected by the cryptosystem but rather by the numerical stability of the homomorphically evaluated algorithm.

Finally, the notion of level common to TFHE and HEAAN is defined as the maximal multiplicative depth supported by the ciphertext. Each homomorphic product reduces the level of the resulting ciphertext; when the level 0 is reached, the ciphertext must be bootstrapped to continue operating on it.

Consider a security parameter λ, a maximal level L and a target precision ρ, then these parameters implicitly define a minimal key size N . For more details see the FHE standardization workshop security document [START_REF] Albrecht | Homomorphic encryption security standard[END_REF].

Below, we describe the algorithms for encryption and decryption that are used in TFHE and HEAAN, both enabling error-tolerant decryption functions, and hence approximated arithmetic.

KeyGen: A uniformly random binary key s ∈ Z N [X] (with small coefficients).

In order to support non-linear operations, KeyGen also needs to generate various encryptions of s, such as evaluation, key-switching or bootstrapping keys, which are not essential to this paper (see [START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF][START_REF] Fan | Somewhat practical fully homomorphic encryption[END_REF][START_REF] Cheon | Homomorphic encryption for arithmetic of approximate numbers[END_REF] for more details). EncryptAtLevel τ,L (x, s): The plaintext x is in C N/2 (complex slots bounded by |x| ≤ 2 τ ). Divide x by 2 τ +L and apply the isomorphism (1) to obtain a small real polynomial µ bounded by 2 -L . Then, pick a uniformly random a ∈ R N [X] mod 1, and a small Gaussian error e with standard deviation 2 -L-ρ , and return (a, s

• a + µ + e). DecryptApproxAtLevel τ,L (c, s): Compute the phase ϕ s (c) = b-s•a mod 1,
lift all its coefficients to the real field in the interval [-1 2 , 1 2 ) which recovers an approximation of µ, then apply the isomorphism (1) and multiply by 2 τ +L to recover the slots x (up to an error 2 τ -ρ ).

Remark 1. Here we describe only a symmetric key version. Note however that the public key version is obtained by evaluation of constant functions using the secret key.

Noise models for homomorphic operations

We now analyze the resulting output noise of the main homomorphic operations for TFHE and HEAAN. The most common operations are linear combinations, multiplications, slot permutations as well as functional bootstrapping.

Linear combination. Let k i=1 α i c i be a linear combination, where the c i are RLWE ciphertexts that encrypt the plaintexts x i and α i ∈ Z are small integers. Given independent normally distributed Gaussian noises

e i ∈ C N/2 (slot representation) with multivariate normal distribution N (x i , σ 2 i ) (x i ∈ C N/2 is the mean and σ i ∈ C N/2×N/2 is the covariance matrix), the noise of the decryp- tion of k i=1 α i c i is k i=1 α i e i which is normally distributed with multivariate distribution N k i=1 α i µ i , k i=1 α 2 i σ 2 i .
We can thus simulate this noise by computing the exact result k i=1 α i x i , applying a random multivariate (discrete) Gaussian noise of amplitude α i 2 τi-ρ and expressing the outcome as an exact multiple of 2 τ -ρ .

Multiplication. The homomorphic evaluation of a multiplication corresponds to the internal product of ciphertexts of HEAAN [START_REF] Cheon | Homomorphic encryption for arithmetic of approximate numbers[END_REF] or to the external product of Chimera/TFHE [START_REF] Chillotti | TFHE: Fast Fully Homomorphic Encryption over the Torus[END_REF][START_REF] Boura | Chimera: a unified framework for B/FV, TFHE and HEAAN fully homomorphic encryption and predictions for deep learning[END_REF] if one of the operands is a fresh ciphertext.

Assuming that c 1 and c 2 are ciphertexts corresponding to the two plaintexts x 1 , x 2 and assuming that the noise parameters e 1 , e 2 ∈ C N/2 in the decryptions of c 1 and c 2 , respectively, are independent and normally distributed according to N (µ i , σ i ), then the distribution of the noise parameter for the decryption of the product c 1 c 2 can be approximated with a normal distribution. Indeed, note that, (x 1 + e 1 )(x 2 + e 2 ) = x 1 x 2 + x 1 e 2 + x 2 e 1 + e 1 e 2 .

Now, for fixed x 1 , the terms x 1 e 2 and x 2 e 1 are clearly normally distributed and e 1 e 2 is negligible, so the distribution of the noise in the decryption of the product can be approximated with the normal distribution for x 1 e 2 + x 2 e 1 . This has already been studied (see e.g. [START_REF] Cheon | Homomorphic encryption for arithmetic of approximate numbers[END_REF][START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF]). Thus, when multiplying homomorphically two ciphertexts c 1 , c 2 representing plaintexts x 1 , x 2 with public exponents τ 1 , τ 2 and precision ρ, we obtain a ciphertext c with exponent τ = τ 1 +τ 2 and precision ρ, which can be modeled as follows: compute the exact product x 1 x 2 , add a random (discrete) multivariate Gaussian noise of amplitude 2 τi-ρ and express the outcome as an exact multiple of 2 τ -ρ .

Rotations/permutations. One of the possibilities for permuting or rotating the elements in the slot representation is to switch to the coefficient packing. This last operation is easy. Knowing that the transformation between coefficients to slots representation and inversely corresponds to applying an orthogonal (or hermitian) matrix, the effect on the noise is numerically stable and it preserves the Gaussian noise amount. However, this consumes (at least) one homomorphic multiplicative level, because the transformation involves a homomorphic evaluation of a Discrete Fourier Transformation.

Bootstrapping. Traditionally, a bootstrapping applies homomorphically the identity function to the plaintext and resets the multiplicative level to a high value.

Here, we omit the noise-reduction part which does not occur in the floatingpoint mode [START_REF] Cheon | Bootstrapping for approximate homomorphic encryption[END_REF]. Complex non-linear functions are traditionally evaluated by interleaving bootstrappings, SIMD additions and multiplications and slot rotations. However, it is not optimal to proceed this way for three reasons: 1) After a costly bootstrapping, one still needs to evaluate the non-linear function which is time consuming, thus sacrificing efficiency. 2) One can approximate the nonlinear function by polynomials: if the approximation can be made arbitrarily precise within a fixed range, the degree and the size of the coefficients rapidly diverge for large ranges and the expression gets numerically unstable outside the specified range (Runge's phenomenon). Therefore, any plaintext outlier can destroy the correctness of the result, which leads to a precision sacrifice. 3) Finally, the bootstrapping needs to raise the multiplicative level very high to leave room for the homomorphic function evaluation, thus requiring excessively large parameters (again, sacrificing efficiency). In the cases of both TFHE and HEAAN, we thus focus on a more numerically stable strategy where the bootstrapping includes the evaluation of the non-linear function.

Functional bootstrapping in TFHE. Recall that the TFHE scheme evaluates functions via evaluating lookup tables on discretized input [16, §4.3, Alg.4]. As such, the bootstrapping of TFHE approximates a given function by a step function (in exactly the same way as one performs Riemann integration) and then evaluates the approximation by a homomorphic lookup table evaluation. For example, the ReLU function f (x) = max(0, x) for -1 ≤ x ≤ 1 can be approximated by the step function defined as follows:

f δ (x) = 0 if x ≤ 0 kδ if x ∈ [(k -1)δ, kδ),
where k ∈ Z and k ≤ 1/δ (see Figure 1 (left)). Thus, given a plaintext x, instead of computing f (x), one obtains the value f δ (x + e 1 ) + e 2 where e 1 and e 2 are two error terms, e 2 being Gaussian noise and e 1 corresponding to an internal rounding error (see the rounding in Step 2 of [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF]Alg.3]).

Functional bootstrapping in HEAAN. In contrast to TFHE, the original version of HEAAN evaluates the sine function by Taylor approximation [14, §3.2]. Moreover, the extension of HEAAN proposed in Chimera generalizes this method to evaluation of Fourier series and thus, evaluation of the given target function via a low-degree Fourier series. Graphically, the target function f is replaced by a smooth function S f and then a Gaussian noise is added on the top of that (see Figure 1 (right)). Finally, when the function has a point of singularity (such as the ReLU at the point x = 0), the HEAAN approximation is biased at that point (strictly above x = 0). It is thus desirable to validate the effect of this biased approximation to the quality of prediction of the trained convolutional neural network. In conclusion of this section, since every elementary FHE operation has a Gaussian noise in output, we can omit the input noise from the bootstrapping and merge it with the output noise of the previous operation in our simulation.

x y 0 y = f (x) y = f δ (x) y ← f δ (x) + err x y 0 y = f (x) y = S f (x) y ← S f (x) + err

Evaluation of nonlinear functions in neural networks

Non-linear functions are central building blocks in deep learning and as such it is important to analyse how to homomorphically evaluate them. Examples of such operations are comparisons, max functions, piecewise functions (e.g. the REctified Linear Unit (ReLU) := max(0, x) activation function), rounding, a decryption function (equivalent to the sign function) or continuous functions such as the sigmoid sigmoid(x) = 1/1 + exp(-x).

Note that the ReLU and max are easily expressed with the absolute value: for x, y in (-1/4, 1/4), 2 max(x, y) = (x + y) + |x -y|, and for 2ReLU(x) = x + |x|.

Non-linear functions in TFHE

In TFHE, given a non-linear function f : T → T, one can compute f (ϕ s (c)) (see Section 2.1) for a LWE ciphertext c via functional boostrapping under the following constraints: the domain of the function is restricted to multiples of 1/2N where N is the bootstrapping key size (in particular, it is a medium-sized power of 2), and the function must be (1/2)-antiperiodic, i.e. f (x+1/2) = -f (x). On the half-period, the function can be defined pointwise, so its graph can be arbitrary. Some particular functions such as Abs(x) -1/4 and Sign(x) already coincide with a (1/2)-antiperiodic function over [-1/2, 1/2] (see Figure 2). More general functions such as sigmoid(γx) -1/2 can be defined over [-1/2, 1/2] and extended to R by anti-periodicity.

Once the (1/2)-antiperiodic function f to evaluate is chosen, its graph is mapped to the element ν =

N -1 i=0 ν i X i ∈ R N [X] mod 1 where ν i = f (i/2N
) and used as a test vector in the bootstrapping of TFHE to evaluate f (see [16, §6.1]). In the output of the bootstrapping, the decrypted value is within a small Gaussian error around f (x) as discussed in Section 2.

0 1 4 1 2 -1 4 -1 2 0 1 2 -1 2
Fig. 2: Absolute (on the left) and Sign (on the right) values TFHE

Non-linear functions in HEAAN

In HEAAN, non-linear functions can be evaluated via approximations by either complex-valued polynomials (via traditional products) or trigonometric polynomials (Fourier approach within the bootstrapping). As explained in [START_REF] Boura | Highprecision privacy-preserving real-valued function evaluation[END_REF], Fourier series of smooth and regular functions converge rapidly: for instance, the Fourier series of a C ∞ -function converges superalgebraically and if one smooths any periodic function by convolution with a small Gaussian, its Fourier series converges exponentially fast. However, the convergence is slower if the function has discontinuities (pointwise convergence in Ω(1/k)), or discontinuities in its derivative (uniform convergence in

Ω(1/k 2 ))
where k is the number of harmonics used in the series.

For example, the absolute value is a triangular signal on [-1/2, 1/2) which extends naturally to a 1-periodic continuous function (piecewise C 1 ). Given N/2 LWE ciphertexts, we can efficiently pack the complex exponential of their phases exp(2iπµ) in the slots of a single HEAAN ciphertext. Subsequently, we can evaluate any trigonometric polynomial of small degree and extract the results back to LWE samples. For instance, the triangular signal (corresponding to the absolute value) has the following Fourier series with only cosine terms of odd degrees that converge in O(k 2 ) and the square signal (corresponding to the sign or decryption function) has only sine terms of odd degrees.

Abs(x) = K 1 ∞ k=0 cos 2π(2k + 1)x (2k + 1) 2 + K 2 , Sign(x) = K 1 ∞ k=0 sin 2π(2k + 1)x (2k + 1) + K 2
Figure 3 shows that the first three (resp. six) terms of the Fourier series of the absolute value and the sign function already provide a good approximation on the interval [-1/2, 1/2).

Compared to classical approximations of functions by polynomials in [START_REF] Gilad-Bachrach | Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy[END_REF][START_REF] Chabanne | Privacypreserving classification on deep neural network[END_REF] (i.e. Taylor series or Weierstrass approximation theorem), Fourier series have three main advantages: they do not diverge to ∞ outside of the interval (better numerical stability), the Fourier coefficients are small (square integrable), and the series converge uniformly to the function on any interval that does not contain any discontinuity in the derivative. However, in the particular case of Abs and Sign, the presence of a singularity or discontinuity at x = 0 in both graphs implies that the series converge poorly around 0. Unfortunately, native plaintexts in HEAAN ciphertext at level L have by definition tiny phases in the interval -1/2 L , 1/2 L . We address this problem using the bootstrapping capability of HEAAN: First, we decrease the level L = 0 or L = 1 (using the algorithm of re-scaling defined in [START_REF] Cheon | Homomorphic encryption for arithmetic of approximate numbers[END_REF]), so that input phases range over a large torus interval (-1/2, 1/2) or (-1/4, 1/4), and then, divide K 1 by 2 L so that the output has level L.

With this bootstrapping trick, HEAAN can at the same time evaluate a nonlinear function and bootstrap its output to a level L even higher than its input. Taking this fact into account, instead of writing ReLU(x) = max(0, x) as 1 2 (|x|+x) like in TFHE, where the term +x/2 is not bootstrapped, it is actually better to extend the graph of ReLU from a half period (-1/4, 1/4) directly to a 1periodic continuous function and to decompose the whole graph as a Fourier series. In the latter case, the output level L can be freely set to an arbitrary large value. Figure 3 shows a degree-7 approximation of the odd-even periodic extension of the graph of ReLU(x). If the ReLU is evaluated via this technique, the output message is the Fourier approximation, and the phase still carries an additional Gaussian noise on top of it, as shown in Section 2. In the next section, we also study the robustness of neural networks with this approximation and perturbation model. Preserving the privacy of sensitive data (e.g., medical or financial) while applying machine learning algorithms and still ensuring good performance and high output accuracy is currently a problem of interest to both the cryptographic and the machine learning communities [START_REF] Chabanne | Privacypreserving classification on deep neural network[END_REF][START_REF] Gilad-Bachrach | Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy[END_REF][START_REF] Bourse | Fast homomorphic evaluation of deep discretized neural networks[END_REF][START_REF] Carpov | Privacypreserving semi-parallel logistic regression training with fully homomorphic encryption[END_REF][START_REF] Badawi | The alexnet moment for homomorphic encryption: Hcnn, the first homomorphic cnn on encrypted data with gpus[END_REF][START_REF] Jiang | Secure outsourced matrix computation and application to neural networks[END_REF][START_REF] Wagh | Securenn: Efficient and private neural network training[END_REF]. We briefly describe now the main layers composing a CNN from a FHE point of view.

Convolution It is an operation that extracts features from the input image (such as lines or borders) and is achieved by computing convolutions (via element-wise products) of the input matrix and a filter. Convolution is viewed as a secret affine function that can be efficiently evaluated using the external product of [START_REF] Chillotti | TFHE: Fast Fully Homomorphic Encryption over the Torus[END_REF][START_REF] Boura | Chimera: a unified framework for B/FV, TFHE and HEAAN fully homomorphic encryption and predictions for deep learning[END_REF]. Non-linearity To introduce non-linearity, an activation function is then applied to the output of the convolution. Nowadays, this is almost always achieved by the ReLU function. In almost all previous works, the standard approach was to replace the ReLU by a function with a lower multiplicative depth. In [START_REF] Gilad-Bachrach | Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy[END_REF],

ReLU is notably approximated by the square function f (x) = x 2 , in [START_REF] Bourse | Fast homomorphic evaluation of deep discretized neural networks[END_REF] it is replaced by the sign function, while in [START_REF] Chabanne | Privacypreserving classification on deep neural network[END_REF] the ReLU is approximated by low-degree polynomials. Pooling This layer reduces the dimensions of the input by retaining the most important information. This is typically done by a procedure called max pooling or more rarely by average pooling that compute the maximum (resp. average) value for every disjoint region of the input. Today, no efficient algorithm is known to compute the maximum of a large number of values. On the contrary, average pooling is linear with public coefficients and therefore FHE-friendly. In [START_REF] Gilad-Bachrach | Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy[END_REF] the authors replace max pooling by sum pooling, while in [START_REF] Chabanne | Privacypreserving classification on deep neural network[END_REF] max pooling is replaced by average pooling. Fully Connected (FC) Layer All the neurons of this layer are all connected to all neurons of the previous layer. Their activation is computed by a matrix multiplication plus a bias offset. This is again a secret precomputed affine step that can be achieved via the external product. Loss Layer This is normally the last layer of a CNN. During the evaluation, the loss layer becomes an argmax operation. This last step is in general ignored in other homomorphic implementations of neural networks. For example, in [START_REF] Gilad-Bachrach | Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy[END_REF][START_REF] Bourse | Fast homomorphic evaluation of deep discretized neural networks[END_REF], the authors simply output the score vectors and the recipient computes the best one after decryption. To do this final step homomorphically, the boolean approach of TFHE seems to be the most suited to this non-SIMD step.

Robustness against the FHE error models

In this section, we simulate the homomorphic execution of the neural network by replacing the value output of each non-linear layer by a random sample which has the same distribution as the phase of RLWE samples after a homomorphic evaluation of the layer. This approach allows us to simulate a homomorphic evaluation, and to obtain accurate predictions on the outcome without having to run the expensive homomorphic computation. This allows to estimate the largest noise standard deviation α that can be tolerated by the network, and therefore, the smallest FHE parameters required to evaluate it. In our experiments we add Gaussian noise with varying standard deviation and look for the maximal standard deviation of the noise that can be tolerated by the network.

As explained above, in the context of FHE, the training of networks is usually done on the plaintexts without any perturbations occurring, and only then, the network is encrypted to the cloud to protect the privacy of the model during predictions. In this direction, we carried out many experiments on three different convolutional neural networks structures, using the TFHE and HEAAN noise models of Section 2, in order to measure their robustness against such perturbations. This approach is not new. For example, in [START_REF] Cheney | On the robustness of convolutional neural networks to internal architecture and weight perturbations[END_REF] the authors studied the stability of CNNs by applying among others a Gaussian perturbation to the internal weights inside the convolutional layers. The applied Gaussian was centered at zero and had a standard deviation relative to the standard deviation of that layer's original weight distribution. This type of perturbation modifies the average value of the inputs to the convolutional layer. Even, if the motivation of this paper is not linked to homomorphic computations, their conclusions and ours intersect at some points. Indeed, the authors of [START_REF] Cheney | On the robustness of convolutional neural networks to internal architecture and weight perturbations[END_REF] noticed that the last convolutional layers are surprisingly stable, while the first convolutional layers are much more fragile and so the accuracy depends on the level the perturbation applies. The most surprising result that we obtain in our experiments is that all the neural networks we tested support quite large relative errors of at least 10% of 2 τ , without any impact on the global accuracy. In a TFHE context, raising the error amplitude from a usually required 2 -40 negligible amount to 2 -4 means that the depth of leveled circuits (number of transitions in automata in leveled circuits in [START_REF] Chillotti | TFHE: Fast Fully Homomorphic Encryption over the Torus[END_REF]) can be increased by a factor (2 36 ) 2 without changing the parameter sets. This also means that only 4 bits of precision (instead of 20 to 40 bits usually) are needed on all fixed point operations throughout the network, which results notably in very small parameter sets for HEAAN.

Experiments

We conducted experiments with three different convolutional neural networks and for all of them we used the dlib C++ library [START_REF] King | Dlib-ml: A machine learning toolkit[END_REF]. The first network is LeNet-5 [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF], that can be trained to recognize handwritten digits, the secondone is a 9-layer CNN trained to distinguish cat from dog pictures, and the last one is the ResNet-34 network [START_REF] He | Deep residual learning for image recognition[END_REF], a deep network of 34 layers able to classify an input image into one of 1000 objects. We briefly describe each of the networks and the experiments done on it.

LeNet-5: Recognition of handwritten digits LeNet-5 is a well-known convolutional 7-layer neural network designed by LeCun et al. in 1998 to recognize handwritten digits [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF]. In the original version of the network, the sigmoid was used as the activation function. In the version that we manipulated (dlib library [START_REF] King | Dlib-ml: A machine learning toolkit[END_REF]), the ReLU activation function is used instead.

We trained this network on the MNIST dataset [START_REF] Lecun | The MNIST database of handwritten digits[END_REF], composed of 60000 training and 10000 testing images, with two different versions of the pooling algorithm. We first trained the network by using max pool for both pooling layers and at a second stage we re-trained it from scratch by replacing now max pool by average pool. Our goal was to see how each version reacts to perturbations. In particular, we added to each output value of the activation function a value drawn from a Gaussian distribution with mean value zero and some standard deviation σ. This was done for the activation function of all levels. For our experiments we further used two different activation functions: the original ReLU activation function and then an approximation of the ReLU function by a trigonometric function, depicted in Figure 3 (right), or in green in Figure 1 (right) which can be used in HEAAN as a replacement of max(0, x). Finally, we perturbed the output of the activation function in two different ways. First by a Gaussian distribution of fixed standard deviation σ and in a second experiment by a standard deviation proportional to the input's standard deviation (which can be publicly estimated during training).

The results of these experiments are summarized in Table 1 and Figure 5. In this example, we pushed standard deviation from 0.0 to 1.0 for both trained CNNs, the one trained with max pool and the other one trained with average pool. In Table 1 we give both the accuracy on the testing set but also on the training set. In order to correctly interpret the right part of Figure 5 it has to be noted that the mean value of the ReLU entries was measured between 0.4 and 1.91 and the standard deviation between 0.97 and 2.63. The first remark that can be done by looking into these experiments is that average pool is much more stable to perturbations than max pool and provides a high accuracy even for large values of the standard deviation. The second remark concerns the accuracy when an approximation of the ReLU function is used instead of the original one. As it can be seen from the left part of Figure 5, the accuracy for the average pool version is clearly lower when a ReLU approximation is used, but still has a very good score (over 95%) for standard deviations as high as 0.6. Finally, special care has to be taken when interpreting the results corresponding to the application of a proportional perturbation of the input data standard deviation. In the right part of Figure 5 the x-axis corresponds to a perturbation equal to the percentage of the inputs' standard deviation. Depending on the original deviation of the input distribution, the perturbation can be extremely important and this is why the accuracy shows to drop. Therefore, one has to keep in mind that the perturbation of the right-side figures is in general more important and probably also more meaningful than the one of the left-side figures.

Cats versus Dogs Classifier

In this section we present our results and remarks on a simple 9-layer neural network that was trained to classify pictures as cats or dogs. For this, we used again the dlib library [START_REF] King | Dlib-ml: A machine learning toolkit[END_REF] and coded with it the 9-layer NN presented in [1]. The structure of this NN is depicted in Figure 6. This network is composed of 3 convolution layers followed by the ReLU activation function, two fully connected (FC) layers and two pooling layers. In the original net, the max pool operation is used at this step. The 7-th layer is a dropout layer, that is a standard technique for reducing overfitting and consists in ignoring a different randomly chosen part of neurons during the different stages of the training phase [START_REF] Srivastava | Dropout: a simple way to prevent neural networks from overfitting[END_REF]. We trained this network on the Asirra dataset [START_REF] Elson | Asirra: a CAPTCHA that exploits interest-aligned manual image categorization[END_REF] We did exactly the same type of experiments for this network and the results can be found in Table 2 or visualized in the lower part of Figure 5. This network is a little-bit more complex than LeNet-5 and seems to be less stable. For this reason, the higher standard deviation considered here is 0.4. However, globally, the same remarks as for LeNet-5 network result. Again, for correctly interpreting the right part of the table, it has to be noted that the mean value of the inputs of the activation function ranges between 0.0004 and 0.628 and the standard deviation ranges between 0.0067 and 3.51.

ResNet-34 ResNet (Residual Network) is a recent family of very deep convolutional neural networks showed to perform extremely well [START_REF] He | Deep residual learning for image recognition[END_REF]. The global layer structure is very similar to a classical CNN, however better performances are achieved by the introduction of a shortcut connection, that consists in skipping one or more layers. The version that we used is composed of 34 layers, and is abbreviated as ResNet-34. This network, once trained, is able to classify photos of objects into 1000 distinct object categories.

The training of such residual networks is extremely time consuming (two weeks on a 16-GB Titan GPU, and about 20 times more on 16-CPU cores) and because of time constraints we were not able to finish the training on a network where max pooling is replaced by average pooling. Thus, we were only able to perform our experiments on the pre-trained network on the imagenet ILSVRC2015 dataset [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF] and the results are reported in Table 3. Top 1 and Top 5 labels report respectively the percentage of the pictures in the validation set that were correctly classified (Top 1) and whose correct label appeared in the five top suggestions provided by the network (Top 5). 3: Experiments on ResNet-34 with max pooling and with perturbations of standard deviation ranging from 0.0 to 0.5. The right columns correspond to perturbations proportional to the input's standard deviation.

Non-proportional perturbation Proportional perturbation

ReLU

Conclusion/Discussion

Finally, we summarize the experiments with the three different CNNs, provide links to Section 3 and give recommendations on which operation should be performed with which FHE scheme (depending on the given use case).

Max pool versus Average pool

We conducted experiments on LeNet-5 and the 9-layer CNN classifying cats and dogs, by replacing during the training and the evaluation the classical max pooling operation by the average pool. This modification, applied also in [START_REF] Chabanne | Privacypreserving classification on deep neural network[END_REF] and to some extend in [START_REF] Gilad-Bachrach | Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy[END_REF], offers a significant advantage for all FHE schemes, as this operation is affine with public coefficients, compared to max pool that is non-linear. Our experiments showed that this approach offers a further advantage in FHE, as it is way more stable than max pool to perturbations. This behaviour has a natural mathematical explanation, since the standard deviation of an average of independent samples is smaller than the input standard deviations. Proportional versus non-proportional perturbations We applied two types of perturbations to all three networks. The first type of perturbations was the addition at the output of the activation function of a value drawn from a Gaussian distribution with zero mean and a fixed standard deviation. In the second type of perturbations, the value added had a standard deviation proportional to the standard deviation of the input distribution. The second scenario corresponds to the fixed-point arithmetic model, where the public plaintext exponent τ is set to match the amplitude during the training phase, and therefore, the noise α is by definition relative to 2 τ . Surprisingly, without impacting the result, neural networks are able to absorb very large relative errors between 10% and 20% after each ReLU (there are respectively thousands, millions, and billions of them in the three tested networks). This means homomorphic parameters need only to ensure ρ = 4 bits of precision on the plaintext, instead of the usually recommended ρ = 30. Approximating the ReLU activation function The main source of non-linearity of a convolutional neural network is coming from the ReLU function. In TFHE these functions are evaluated exactly either as circuits, or as point-wisedefined arbitrary functions. Approximating the ReLU by something easier is thus a natural approach [START_REF] Gilad-Bachrach | Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy[END_REF][START_REF] Chabanne | Privacypreserving classification on deep neural network[END_REF][START_REF] Bourse | Fast homomorphic evaluation of deep discretized neural networks[END_REF]. In HEAAN such continuous functions can be approximated accurately by low degree trigonometric polynomials.

In our experiments with ResNet-34 (see Table 3) the output accuracy is surprisingly even better with an approximated ReLU of this type than with the classical one, in the presence of small noise, which proves that this approach is realistic. Number of layers In the plaintext model, the accuracy can in general be improved by adding more layers, if no overfitting occurs. However, in the homomorphic model, what happens with accuracy is still an open question, because with the number of layers, the complexity of computation grows and the activation function can only be approximated. This generates additional noise that can affect the accuracy.

Fig. 1 :

 1 Fig. 1: Functional bootstrap in TFHE for the ReLU function (in left) and Functional bootstrap in HEAAN for the ReLU function (in right).

Fig. 3 :

 3 Fig. 3: Abs (on the left), Sign (in the middle) and ReLU (on the right) for HEAAN

Fig. 5 :

 5 Fig.5: Experiments with LeNet-5 (up) and the cat versus dog classifier (down). The results with proportional perturbations are on the right, while with non-proportional perturbations on the left.

Fig. 6 :

 6 Fig. 6: 9-layer neural network [1] trained to classify pictures as cats or dogs.

Table 1 :

 1 Train acc. Test acc. Train acc. Test acc. Train acc. Test acc. Train acc. Test acc. Experiments on the LeNet-5 network trained first with max pool and then with average pool. ReLU means that during the evaluation the original ReLU function was used, while ReLU signifies that an approximation was used instead.

		Non-proportional perturbation	Proportional perturbation
		ReLU	ReLU	ReLU	ReLU
	Pool type σ max 0.0 0.9999	0.9924	0.9999	0.9924	0.9999	0.9924	0.9999	0.9924
	average	0.9994	0.9903	0.9994	0.9903	0.9994	0.9903	0.9975	0.9903
	max	0.1 0.9998	0.9918	0.9996	0.9916	0.9984	0.9908	0.9980	0.9905
	average	0.9994	0.9903	0.9993	0.9904	0.9977	0.9891	0.9976	0.9892
	max	0.2 0.9990	0.9910	0.9976	0.9899	0.9883	0.9835	0.9842	0.9787
	average	0.9991	0.9901	0.9985	0.9894	0.9897	0.9843	0.9878	0.9826
	max	0.3 0.9966	0.9894	0.9901	0.9833	0.9540	0.9501	0.9199	0.9192
	average	0.9981	0.9898	0.9960	0.9872	0.9699	0.9655	0.9595	0.9581
	max	0.4 0.9919	0.9843	0.9654	0.9610	0.8686	0.8723	0.7695	0.7815
	average	0.9968	0.9884	0.9908	0.9845	0.9308	0.9296	0.9014	0.9039
	max	0.5 0.9823	0.9766	0.8942	0.8966	0.7475	0.7587	0.5901	0.5959
	average	0.9947	0.9869	0.9792	0.9737	0.8728	0.8745	0.8156	0.8214
	max	0.6 0.9626	0.9610	0.7644	0.7737	0.6199	0.6248	0.4325	0.4317
	average	0.9919	0.9842	0.9552	0.9517	0.8007	0.8054	0.7179	0.7245
	max	0.7 0.9284	0.9280	0.6166	0.6288	0.5013	0.5024	0.3233	0.3274
	average	0.9883	0.9816	0.9171	0.917	0.7219	0.7288	0.6212	0.6332
	max	0.8 0.8756	0.8808	0.4809	0.4953	0.4040	0.4056	0.2526	0.2576
	average	0.9843	0.9779	0.8633	0.8698	0.6433	0.6506	0.5295	0.5383
	max	0.9 0.8103	0.8191	0.3826	0.3884	0.3316	0.3322	0.2036	0.2094
	average	0.9779	0.9724	0.8044	0.8135	0.5691	0.5727	0.4498	0.4538
	max	1.0 0.7399	0.7462	0.3179	0.326	0.2757	0.2803	0.1719	0.1732
	average	0.9696	0.9636	0.7434	0.7548	0.4989	0.5062	0.3822	0.3862

  used by Microsoft Research in the context of a CAPTCHA (Completely Automated Public Turing test to tell Computers and Humans Apart) challenge. Most of the good CNNs trained to distinguish dogs from cats achieve more than 80% accuracy on the testing set while the accuracy on the training set is usually around 100%. The difference in the two performances is usually due to some overfitting occuring.

		32 filters of size 3 × 3 Stride size: 1	2 × 2 windows Stride size: 2	64 filters of size 3 × 3 Stride size: 1		64 filters of size 3 × 3 Stride size: 1
	64 × 64 × 3	Layer Conv	ReLu	Pool	Layer Conv	ReLu	Layer Conv	ReLu
	Input Image	Layer 1		Layer 2	Layer 3		Layer 4
		2 × 2 windows
		Stride size: 2	512			1
		Pool	FC	ReLu	Dropout	FC	Loss Layer
		Layer 5	Layer 6		Layer 7	Layer 8	Layer 9

Table 2 :

 2 Experiments on a 9-layer CNN trained to distinguish cats from dogs.

			Non-proportional perturbation Proportional perturbation
			ReLU		ReLU	ReLU	ReLU
	Pool type σ Training acc. Test acc. Test acc. Test acc.	Test acc.
	max	0.0	0.9999	0.8530 0.8500	0.8524	0.85
	average		0.99995	0.8202 0.8138	0.8232	0.814
	max	0.1	0.9944	0.8316 0.8112	0.801	0.784
	average		0.99995	0.8232 0.7880	0.8234	0.7812
	max	0.2	0.8782	0.7446 0.6246	0.6942	0.5892
	average		0.9999	0.8174 0.6726	0.8174	0.6574
	max	0.3	0.6234	0.5872 0.5368	0.5736	0.4996
	average		0.99965	0.8146 0.5868	0.8134	0.5776
	max	0.4	0.5228	0.512	0.5222	0.514	0.4916
	average		0.998	0.8074 0.5522	0.8092	0.5444

  ReLU ReLU ReLU Pool type σ Top 1 Top 5 Top 1 Top 5 Top 1. Top 5 Top 1 Top 5

	max	0.0 0.7416 0.9158 0.7428 0.9187 0.7439 0.9202 0.7398 0.9166
	max	0.1 0.7357 0.9132 0.7056 0.9165 0.7132 0.8948 0.7586 0.9252
	max	0.2 0.6991 0.8860 0.7056 0.8967 0.1562 0.3294 0.3658 0.6027
	max	0.3 0.5068 0.7267 0.4829 0.7171 0.0019 0.0089 0.0012 0.0079
	max	0.4 0.1500 0.0498 0.1065 0.0817 0.0018 0.0085 0.000 0.0009
	max	0.5 0.0233 0.0608 0.0017 0.0066 0.0001 0.0044 0.000 0.0010
	Table