# Linear Depth Integer-Wise Homomorphic Division

Hiroki Okada, Carlos Cid, Seira Hidano, Shinsaku Kiyomoto

► To cite this version:

Hiroki Okada, Carlos Cid, Seira Hidano, Shinsaku Kiyomoto. Linear Depth Integer-Wise Homomorphic Division. 12th IFIP International Conference on Information Security Theory and Practice (WISTP), Dec 2018, Brussels, Belgium. pp.91-106, 10.1007/978-3-030-20074-9_8. hal-02294597

HAL Id: hal-02294597

https://hal.science/hal-02294597

Submitted on 23 Sep 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Linear Depth Integer-wise Homomorphic Division

Hiroki Okada¹, Carlos Cid², Seira Hidano¹, and Shinsaku Kiyomoto¹

¹ KDDI Research, Inc.
Saitama, Japan

² Royal Holloway, University of London
Egham, Surrey, United Kingdom
ir-okada@kddi-research.jp

**Abstract.** We propose a secure *integer-wise* homomorphic division algorithm on fully homomorphic encryption schemes (FHE). For integer-wise algorithms, we encrypt plaintexts as integers without encoding them into bit values, while in *bit-wise* algorithms, plaintexts are encoded into binary and bit values are encrypted one by one. All the publicly available division algorithms are constructed in bit-wise style, and to the best of our knowledge there are no known integer-wise algorithm for secure division. We derive some empirical results on the FHE library HElib and show that our algorithm is 2.45x faster than the fastest bit-wise algorithm. We also show that the multiplicative depth of our algorithm is $O(l)$, where $l$ is the integer bit length, while that of existing division algorithms is $O(l^2)$. Furthermore, we generalise our secure division algorithm and propose a method for secure calculation of a general 2-variable function. The order of multiplicative depth of the algorithm, which is a main factor of the complexity of a FHE algorithm, is exactly the same as our secure division algorithm.

**Keywords:** Fully homomorphic encryption, HElib, Secure integer arithmetic, Circuit depth

# 1 Introduction

**Fully Homomorphic Encryption.** A fully homomorphic encryption (FHE) scheme presents a way to perform arbitrary calculations on encrypted data without the requirement of decryption. The first construction of FHE [11, 12] was given by Gentry in 2009. Several improvements [4–6, 10, 13, 14, 25, 27] have followed since then, developing a diversity of features and complexity assumptions. HElib [17–19] is a library for FHE widely used in applications, which implements the BGV scheme [3]. It allows for the “packing” of ciphertexts and single instruction multiple data (SIMD) computations, amortizing the cost for certain tasks.

There are numerous applications of FHE, but one of the most remarkable is privacy-preserving delegated computations, such as privacy-preserving machine learning as a service. In the service, users do not wish to reveal their sensitive data to the server, and the server does not want to reveal the cognitive model
to users. FHE enables these scenarios in an elegant way with non-interactivity. However, because of the inefficiency of existing FHE schemes, most applications are constructed evading the *non-crypto-friendly* calculations such as comparison, division, and some non-linear functions.

**Bit-wise encryption vs. Integer-wise encryption.** Most FHE schemes, including the BGV scheme, feature *integer-wise* and *bit-wise* encryption; the size of the plaintext space in the scheme is variable. In bit-wise encryption the plaintext space is $Z_2$, and in integer-wise encryption the plaintext space is $Z_p$ where $p > 2$. Because the main libraries of FHE, including HElib, do not support some basic integer arithmetic operations such as division and comparison, several studies [8,9,28] have been performed on improved arithmetic. The proposed algorithms are primarily for bit-wise encryption, and they simply leverage the existing algorithms for such operations on the bit-wise circuit such as Ripple carry adder, long multiplication, and non-restoring division. Although bit-wise encryption can perform integer comparison very efficiently [7], integer addition and multiplication are not practical since they require homomorphic multiplication. On the other hand, integer-wise arithmetic can naturally perform integer addition and multiplication efficiently, and recent remarkable privacy-preserving machine learning such as [1, 2, 15, 20] use integer-wise encryption. However, the algorithm for these applications evades arithmetic such as division and comparison, which are believed to be inefficient. While a concrete algorithm for secure integer-wise comparison has been recently proposed in [22], to the best of our knowledge there is no known concrete algorithm for secure integer-wise division algorithm. Emergence of efficient algorithms for basic arithmetic operations such as division and comparison will undoubtedly increase options to optimise higher level applications of secure computation.

**Our contribution.** We present a new concrete algorithm for privacy preserving *integer-wise* division. Although several studies have been performed on privacy preserving *bit-wise* division algorithms [8, 9, 28], there is no known concrete algorithm for the *integer-wise* version. We implement our division algorithm using HElib, and test its performance. The experimental results show that our algorithm performs 2.45 times faster than the fastest bit-wise algorithm [8]. We also theoretically analyse the multiplicative depth, which is a barometer for the complexity for the FHE-based algorithm. While the order of the multiplicative depth of existing division algorithms [8, 9, 28] is $O(l^2)$ for $l$-bit size integers, we show that our algorithm can perform with $O(l)$.

Furthermore, we generalise our secure division algorithm and propose an algorithm for secure calculation of a *general 2-variable function*; the order of multiplicative depth of the algorithm is $O(l)$, which is the same as our secure division algorithm. This is the first result to construct a concrete algorithm for performing the general 2-variable function, expanding the FHE application diversity.
# 2 Preliminaries

## 2.1 Notation

In the FHE construction, a ring $R$ is used, whose elements are written in lower case; for example, $r \in R$. For an integer $q$, we use $R_q$ to denote $R/qR$. For $a \in R$, we use the notation $[a]_q$ to refer to $a$ mod $q$, with coefficients reduced to the range $(-\frac{q}{2}, \frac{q}{2}]$. A concrete instantiation for our applications is the quotient polynomial ring $R_q = \mathbb{Z}_q[x]/\Phi_m(x)$, where $q$ is a prime and $\Phi_m(x)$ is the $m$-th cyclotomic polynomial. We denote a ciphertext of $r$, which is encrypted with a FHE scheme, by $C_r$.

We denote the logarithm to base 2 and the natural logarithm as $\log(\cdot)$ and $\ln(\cdot)$, respectively. We denote vectors in bold. The notation $\mathbf{v}[i]$ refers to the $i^{th}$ coefficient of $\mathbf{v}$, while the scalar product of two vectors $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$ is denoted as $\langle \mathbf{u}, \mathbf{v} \rangle = \sum_{i=1}^n \mathbf{u}[i] \cdot \mathbf{v}[i] \in R$. By $(\mathbf{a} \| \mathbf{b})$ we denote the concatenation of two vectors $\mathbf{a}$ and $\mathbf{b}$. We write $\mathbf{s} \stackrel{U}{\leftarrow} \mathcal{S}$ to denote the process of sampling $\mathbf{s}$ uniformly at random over $\mathcal{S}$; when the set $\mathcal{S}$ is clear from the context, we will write $\mathbf{e} \leftarrow \chi$ to denote the process of sampling $\mathbf{e}$ according to the probability distribution $\chi$ over $\mathcal{S}$.

## 2.2 The BGV scheme

A FHE scheme is a public-key cryptographic scheme that includes two operations $(+, \cdot)$ on ciphertexts such that: $\text{Dec}(C_a + C_b) = a + b$, $\text{Dec}(C_a \cdot C_b) = a \cdot b$. The BGV scheme [3] is a widely used FHE scheme for practical applications, which is implemented in the FHE library HElib [16]. The security of the scheme is based on the standard assumptions of the Learning with Error (LWE) problem [23] or Ring-LWE (RLWE) problem [21]. This is in contrast to the earlier FHE constructions [11, 12] which were based on ad-hoc average-case assumptions on ideal lattice problems.

**The Basic Encryption Scheme.** BGV is a public-key cryptography scheme $E = (\text{E.setup}, \text{E.SecKeyGen}, \text{E.PublicKeyGen}, \text{E.Enc}, \text{E.Dec})$ defined as follows.

- **Setup(1^λ)**. Given the security parameter $\lambda$ as input, set an integer $m = m(\lambda)$ that defines the cyclotomic polynomial $\Phi_m(x)$, and the odd modulus $q = q(\lambda)$. If $R = \mathbb{Z}[x]/\Phi_m(x)$, the underlying working ring is $R_q = \mathbb{Z}_q[x]/\Phi_m(x)$. Set a plaintext modulus $p$ that is relatively prime to $q$, with the plaintext space given by $R_p = \mathbb{Z}_p[x]/\Phi_m(x)$. Set a noise distribution $\chi = \chi(\lambda)$ over the underlying working ring, and $N = N(\lambda) = \text{polylog}(q)$. Output $\text{params} = (R, m, q, p, \chi, N)$.

- **SecretKeyGen params**. Sample $\mathbf{s} \leftarrow \chi$. Output the secret key $\mathbf{sk} = \mathbf{s} := (1, s) \in \mathbb{R}_q^2$.

- **PublicKeyGen (params, sk)**. Take as input the secret key $\mathbf{sk} = \mathbf{s} = (1, s)$ and $\text{params}$. Sample $\mathbf{a} \stackrel{U}{\leftarrow} \mathbb{Z}_q^N$ and $\mathbf{e} \leftarrow \chi^N$. Set $\mathbf{b} := \mathbf{sa} + \mathbf{pe} \in \mathbb{Z}_q^N$, and output the public key defined as $\mathbf{pk} = \mathbf{A} := (\mathbf{b}, -\mathbf{a}) \in \mathbb{Z}_q^{N \times 2}$. Notice that $\mathbf{A} \cdot \mathbf{s} = \mathbf{b} - \mathbf{sa} = \mathbf{pe}$, from the definition of $\mathbf{b}$.
- Enc(*params*, *pk*, *m*). To encrypt a message *m* ∈ *R*<sub>*p*</sub>, set **m** = (*m*, 0) ∈ *R*<sub>*p*</sub><sup>2</sup>, sample **r** ← *R*<sub>*p*</sub><sup>*N*</sup> and output the ciphertext **c** := **m** + **r**<sup>†</sup> **A** ∈ *R*<sub>*q*</sub><sup>2</sup>.

- Dec(*params*, *sk*, **c**). Output the message *m* := [[⟨**c**, **s**⟩]<sub>*q*</sub>]<sub>*p*</sub>.

The decryption works because

$$[[\langle c, s \rangle]_q]_p = [[(m + r^\top A) \cdot s]_q]_p = [[m + pr^\top e]_q]_p = [m + pr^\top e]_p = m,$$

where the third equality holds since **r** and **e** have small enough entries so that the value *m* + *pr*†*e* is smaller than the modulus *q*.

**The FHE Scheme.** As a FHE scheme, the BGV scheme supports addition and multiplication over the plaintext and ciphertext spaces. Let $c_a$ and $c_b$ be ciphertexts of plaintexts *a* and *b* under the same key *sk*, respectively. The addition of two ciphertexts is simply a component-wise addition, i.e.

$$c_a + c_b = (c_a[0], c_a[1]) + (c_b[0], c_b[1]) = (c_a[0] + c_b[0], c_b[1] + c_a[1]) = c_{a+b},$$

which is a ciphertext of $a+b \in R_p$. The homomorphic multiplication is performed by the tensor product of two ciphertexts. The tensor product of ciphertexts

$$c_{a \cdot b} := c_a \otimes c_b := (c_a[0]c_b[0], c_a[0]c_b[1] + c_a[1]c_b[0], c_a[1]c_b[1]) \quad (1)$$

is a ciphertext of $a \cdot b \in R_p$ under the new secret key $s' := s \otimes s$. In this way, the homomorphic multiplication increases the size of ciphertexts exponentially. In order to deal with this expanding ciphertext, the BGV scheme features *key switching*. The key switching function $\text{SwitchKey}(\tau_{s' \to \bar{s}}, c', q)$ takes the ciphertext $c'$ under $s'$ and outputs a new ciphertext $\bar{c}$ that encrypts the same message under the secret new key $\bar{s}$. Using this function, we can reduce the size of ciphertext $c_{a \cdot b} \in R_q^3$ to $\bar{c}_{a \cdot b} \in R_q^2 \leftarrow \text{SwitchKey}(\tau_{s' \to \bar{s}}, c_{a \cdot b})$. The BGV scheme also features *modulus switching* techniques, which reduce the magnitude of the noise of the ciphertext by switching the modulus from *q* to the smaller modulus $q'$. The modulus switching function $\text{Scale}(c, q, q', p)$, takes a ciphertext *c* for modulus *q* and outputs a ciphertext under same secret for modulus $q'$.

We now briefly describe the BGV FHE scheme. The scheme is a *levelled* FHE scheme.

- FHE Gibb[1], 1<sup>L</sup>). Takes as input the security parameter $\lambda$ and a number of levels *L*. Set an integer *m* = *m*(*λ*, *L*) that defines the cyclotomic polynomial $\Phi_m(x)$. Let $\mu = \mu(\lambda, L, b) = \theta(\log \lambda + \log L)$ be a parameter to define the bit size of the moduli. For *j* = *L* (input level of circuit) to 0 (output level), run *params*<sub>*j*</sub> ← E. Setup(1<sup>λ</sup>, 1<sup>(j+1)·μ</sup>, b) to obtain a list of parameters, including a list of moduli {q<sub>*L*</sub> ((L + 1) · μ bits), q<sub>*L*−1</sub>, ..., q<sub>0</sub> (μ bits)}.

- FHE. KeyGen(*params*<sub>*j*</sub>). For *j* = *L* down to 0, do the following:

1. Run the basic schemes $s_j \leftarrow E. \text{SecretKeyGen}(\text{params}_j)$, and $A_j \leftarrow E. \text{PublicKeyGen}(\text{params}_j, s_j)$.

2. Set $s'_j \leftarrow s_j \otimes s_j$.
3. Run $\tau_{s'_j \to s_{j-1}} \leftarrow \text{SwitchKeyGen}(s'_j, s_{j-1})$, where SwitchKeyGen is a generator function of auxiliary information $\tau_{s'_j \to s_{j-1}}$ that will be used for SwitchKey. (Note that we omit this step when $j=0$.)

4. Output $sk := \{s_j\}_{j=0}^L$, $pk = \{A_j\}_{j=0}^L$.

- FHE.Enc($params$, $pk$, $m$). Take a message $m$ in $R_p$. Run $c \leftarrow E.Enc($params_L$, $A_L$, $m$) of the basic scheme.

- FHE.Dec($params$, $sk$, $c$). Suppose that the input ciphertext $c$ is under key $s_j$. Here, we know the level (the index $j$) of the ciphertext from its augmented information. Run $E.Dec($params_j$, $s_j$, $c$)$.

- FHE.Eval($pk$, $f$, $c_1, \dots, c_l$). Take as input a circuit $f$ for ciphertexts $c_1, \dots, c_l$. It is assumed that $f$ is a levelled circuit composed of layers of alternating addition and multiplication gates. FHE.Eval will invoke FHE.Add and FHE.Mult, which is described next, to compute the circuit. The ciphertext refreshing procedure FHE刷新 (described later) is invoked after every multiplication layer, in order to reduce the noise in the ciphertexts and move it to a different level.

* FHE.Add($pk$, $c_1$, $c_2$). Takes two ciphertexts encrypted under the same $s_j$. If they are not under the same key, use FHE刷新 to make one of them, the level of which is higher than the other, to be encrypted under $s_j$. Output $c_3 \leftarrow c_1 + c_2 \bmod q_j$.

* FHE.Mult($pk$, $c_1$, $c_2$). Takes two ciphertexts encrypted under the same $s_j$. If they are not under the same key, use FHE刷新 to make one of them, the level of which is higher than the other, to be encrypted under $s_j$. Multiply the two ciphertexts, then obtain the new ciphertext $c_3$ under the long secret key $s'_j = s_j \otimes s_j$. $c_3$ is the coefficient vector of $\langle c \otimes c, x \otimes x \rangle$. Then, output $c_4 \leftarrow \text{FHE刷新}(c_3, \tau_{s'_j \to s_{j-1}}, q_j, q_{j-1})$.

- FHE刷新($c$, $\tau_{s'_j \to s_{j-1}}$, $q_j$, $q_{j-1}$). Takes a ciphertext encrypted under $s'_j$, the auxiliary information $\tau_{s'_j \to s_{j-1}}$ for key switching, and the current and next moduli $q_j$ and $q_{j-1}$. Perform the following.

1. (Key switching.) Set $c_1 \leftarrow \text{SwitchKey}(\tau_{s'_j \to s_{j-1}}, c, q_j)$, a ciphertext under the key $s_{j-1}$ for modulus $q_j$.

2. (Moduli switching.) Set $c_2 \leftarrow \text{Scale}(c_1, q_j, q_{j-1}, p)$, a ciphertext under the key $s_{j-1}$ for modulus $q_{j-1}$. Output $c_2$.

**Multiplicative Depth and Level Parameter $L$.** As mentioned in [3], we do not need to perform FHE刷新 after addition. We do not perform SwitchKey after addition either, since addition does not increase the size of the ciphertext. Moreover, since addition increases the noise much more slowly than multiplication, we do not need to perform Scale after addition either. Finally we also note that in HElib, FHE刷新 is performed only after FHE.Mult is performed.

The parameter $L$, which indicates the number of levels of arithmetic circuit that the scheme is capable of evaluating, is very important when we estimate the complexity of the FHE circuit. Every time we perform FHE.Mult, we perform SwitchKey and move the index $j$ to $j-1$. Thus, basically, we set the level
<table><caption>Table 1: Basic interfaces for homomorphic evaluation in HElib.</caption><thead><tr><td>HElib Interface</td><td>Abbreviation we use</td></tr></thead><tbody><tr><td>Ctxt::addTxt</td><td>FHE.Add(c, c')</td></tr><tr><td>Ctxt::multiplyBy</td><td>FHE.Mult(c, c')</td></tr><tr><td>Ctxt::addConstant</td><td>FHE.addConst(c, m')</td></tr><tr><td>Ctxt::multByConstant</td><td>FHE.multConst(c, m')</td></tr></tbody></table>

parameter $L$ according to the multiplicative depth of the circuit. The level $L$ is related with the complexity of FHE.Add or FHE.Add. Brakerski et al. [3] showed the order of complexity is $O(\lambda L^3)$.

## 2.3 HElib

HElib [16] is a software library that implements the BGV scheme in C++. HElib is based on the number theory library NTL [24]. In addition to the basic scheme, HElib also supports the SIMD feature proposed by Smart and Vercauteren [26]. The SIMD feature enables packing multiple plaintexts into a single element of $R_p$ with the Chinese Remainder Theorem; it also enables parallel component-wise evaluation of the plaintexts in the SIMD “slots”. It produces a much better amortised performance, due to parallelisation.

HElib has an interface for the “constant” evaluation, where addition or multiplication by a plaintext is performed for ciphertext. Note that Table 1 shows basic interfaces for homomorphic evaluation in the HElib. These constant evaluations are efficient when the addend or multiplier are not encrypted values. In particular, constant multiplication is quite efficient compared to the homomorphic multiplication; the constant multiplication does not increase the dimension of the ciphertext, and we do not need to perform SwitchKey after the constant multiplication.

## 2.4 Polynomial interpolation and integer-wise secure comparison

The first integer-wise homomorphic comparison algorithm was proposed in [22]. We refer to the algorithm as Algorithm 1, which is based on the polynomial interpolation technique.

Polynomial interpolation is a process of constructing a polynomial $f(x)$ of degree at most $n$ which satisfies $y_i = f(x_i), i \in \{0, 1, \dots, n\}$, where $\{x_i, y_i\}$ is given for $n + 1$ data points such that $x_i \neq x_j$ when $i \neq j$. We can calculate the polynomial $f(x)$ by

$$f(x) = \sum_{i=0}^{n} \left( \prod_{0 \le j \le n, j \ne i} \frac{x - x_j}{x_i - x_j} \right) y_i. \qquad (2)$$
**Algorithm 1 Comp($C_a, C_b$): Integer-wise Homomorphic Comparison [22]**

**Input:** Ciphertexts $C_a, C_b$.

**Output:** $C_{(a \ge b)}$, such that $C_{(a \ge b)} = \begin{cases} C_0 & (a \ge b), \\ C_1 & (a < b). \end{cases}$

1. (Precomputation): Using the polynomial interpolation algorithm, find polynomial $f(x) \in \mathbb{Z}_p[x]$ that satisfies

$$f(x) = \begin{cases} 0 & (x = 0, 1, 2, \dots, \lfloor \frac{p}{2} \rfloor), \\ 1 & (x = -\lfloor \frac{p}{2} \rfloor, \dots, -2, -1). \end{cases}$$

For example, with plaintext modulus $p = 7$, the interpolation polynomial $f(x)$ of degree 6 is calculated such that

$$f(-3) = 1, f(-2) = 1, f(-1) = 1, f(0) = 0, f(1) = 0, f(2) = 0, f(3) = 0.$$

For this example, $f(x) = 4x^6 - x^5 - 6x^3 - 4x \in \mathbb{Z}_7[x]$.

2. Homomorphically computes $C_{a-b} = C_a - C_b$.

3. Calculate and output $C_{(a \ge b)} = f(C_{a-b})$.

Note that in Algorithm 1, the polynomial interpolation technique is used to construct the Heaviside step function (i.e, comparison with 0). Our sub-algorithms ConstDiv and ConstEq are also constructed based on the polynomial interpolation, as discussed in the next section.

# 3 Our Algorithm for Integer-wise Homomorphic Division

In this section we present our integer-wise secure division algorithm. In the algorithm, the polynomial interpolation technique is used as a precomputation, similar to the integer-wise comparison algorithm from [22] (Algorithm 1).

In the following, we present in Section 3.1 the overview of the algorithms employed in our secure homomorphic division. We describe the algorithms in detail in Section 3.2. Finally, we analyse their complexity and provide empirical results in Section 3.3.

## 3.1 Overview

Our integer-wise homomorphic division algorithm Div($C_a, C_b$) is given in Algorithm 2, and is constructed based on the following subroutines:

- (Algorithm 3) Pows($C_a$): computes powers of a ciphertext $C_a$.

- (Algorithm 4) ConstDiv($C_a^{\text{pow}}, y$): Integer-wise division by public divisor $y$.

- (Algorithm 5) ConstEq($C_d^{\text{pow}}, y$): Integer-wise equality check with a public input $y$.

ConstDiv($C_a^{\text{pow}}, y$) homomorphically computes the ciphertext of a quotient $\lfloor a/y \rfloor$ denoted as $C_{\lfloor a/y \rfloor}$, from the ciphertext of $a \in \mathbb{Z}_p$ denoted as $C_a$, and public
<caption>**Algorithm 2 Div($C_a, C_d$): Integer-wise Homomorphic Division**</caption>

**Input:** Ciphertexts $C_a, C_d$.
**Output:** $C_{\lfloor a/d \rfloor}$
1: $C_{\text{sum}} = 0$
2: $C_a^{\text{pow}} = \text{Pows}(C_a) \quad \triangleright C_a^{\text{pow}} := \{C_a, C_a^2, C_a^3, \dots, C_a^{p-1}\}$
3: $C_d^{\text{pow}} = \text{Pows}(C_d) \quad \triangleright C_d^{\text{pow}} := \{C_d, C_d^2, C_d^3, \dots, C_d^{p-1}\}$
4: **for** $i = 0$ to $(p-1)$ **do**
5:     $C_{\lfloor a/i \rfloor} = \text{ConstDiv}(C_a^{\text{pow}}, i)$
6:     $C_{(d=i)} = \text{ConstEq}(C_d^{\text{pow}}, i)$
7:     $C_{\text{sum}} = C_{\text{sum}} + \text{FHE.Mult}(C_{\lfloor a/i \rfloor}, C_{(d=i)}) \quad \triangleright \text{FHE.Mult}(C_{\lfloor a/i \rfloor}, C_{(i=d)}) =$
8:     **end for**
9: **Output** $C_{\lfloor a/d \rfloor} = C_{\text{sum}} \quad \triangleright C_{\lfloor a/d \rfloor}$ if $i = d$; $C_0$ otherwise

divisor $y \in \mathbb{Z}_p$. $\text{ConstEq}(C_d^{\text{pow}}, y)$ homomorphically computes the ciphertext of the Boolean value $(y=d)$ denoted as $C_{(y=d)}$, where

$$C_{(y=d)} := \begin{cases} C_1 & \text{if } y = d; \\ C_0 & \text{otherwise.} \end{cases}$$

Note that given $C_a, C_d$ for unknown $a, d \in \mathbb{Z}_p$, then for an arbitrary public value $y \in \mathbb{Z}_p$, we have

$$C_{\lfloor a/y \rfloor} * C_{(y=d)} = \begin{cases} C_{\lfloor a/d \rfloor} & \text{if } y = d; \\ C_0 & \text{otherwise.} \end{cases}$$

Our main algorithm for homomorphic division of $a$ by $d$ is then based on a simple idea: calculate $C_{\lfloor a/y \rfloor} * C_{(y=d)}$ for all public values $y$ and sum them:

$$C_{\text{sum}} := \sum_{y \in \mathbb{Z}_p} C_{\lfloor a/y \rfloor} * C_{(y=d)} = C_{\lfloor a/d \rfloor}.$$

## 3.2 Algorithms

**Main algorithm.** Algorithm 2 shows the integer-wise secure division algorithm Div($C_a, C_d$). The algorithm takes two ciphertexts $C_a$ and $C_d$, which are ciphertexts of $a$ and $d$, respectively, then homomorphically calculates a ciphertext $C_{\lfloor a/d \rfloor}$, the decryption of which gives $\lfloor a/d \rfloor$.

The algorithm first calls Pows for both inputs $C_a$ and $C_d$, to obtain the list of powers $C_a^{\text{pow}}$ and $C_d^{\text{pow}}$. This part performs a high number of homomorphic multiplications, but we store these values and can reuse them. Next, in the **for** loop, for all $i \in \{0, 1, 2, \dots, p-1\}$, we exhaustively calculate $C_{\lfloor a/i \rfloor}$ and $C_{(d=i)}$ with ConstDiv and ConstEq, then perform the homomorphic multiplication of $C_{\lfloor a/i \rfloor} * C_{(i=d)} := \text{FHE.Mult}(C_{\lfloor a/i \rfloor}, C_{(i=d)})$. Recall that $C_{\lfloor a/i \rfloor} * C_{(i=d)}$ equals to $C_{\lfloor a/d \rfloor}$ if $y = d$, and $C_0$ otherwise. Thus, at the end of the algorithm we obtain $C_{\lfloor a/d \rfloor} = C_{\text{sum}}$.
<caption>**Algorithm 3 Pows($C_a$):** Computation of powers of $C_a$</caption>

**Input:** Ciphertexts $C_a$
**Output:** $C_a^{\text{pow}} := (C_a, C_a^2, C_a^3, \dots, C_a^{p-1})$
1: Let $l := \lfloor \log p \rfloor$.
2: **for** $i = 0$ to $(l-1)$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;**for** $j = 1$ to $2^i$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Calculate $C_a^{(2^i+j)} := \text{FHE.Mult}(C_a^{(2^i)}, C_a^j)$.
5: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
6: **end for**
7: if $2^l < p-1$ **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;**for** $j = 1$ to $p-1-2^l$ **do**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Calculate $C_a^{(2^l+j)} := \text{FHE.Mult}(C_a^{(2^l)}, C_a^j)$.
10: **end for**
11: **end if**
12: **end for**

$\triangleright$ Here, we have $C_a, C_a^2, C_a^3, \dots, C_a^{2^l}$.

$\triangleright$ Here, we obtain $C_a^{2^l+1}, \dots, C_a^{p-1}$.

$C_a^{\text{pow}} := (C_a, C_a^2, C_a^3, \dots, C_a^{p-1})$.

**Pows($C_a$).** Algorithm 3 shows the sub-algorithm Pows($C_a$). The algorithm takes a ciphertext $C_a$ as an input and homomorphically calculates the powers of $C_a$, returning the list of powers $C_a^{\text{pow}} := (C_a, C_a^2, C_a^3, \dots, C_a^{p-1})$. This sub-algorithm is the most complex part of the main division algorithm Div. In Div, this algorithm is called only once per ciphertext. Note that the multiplicative depth of Pows($C_a$) is $\lfloor \log (p-1) \rfloor$. For example, when $p = 17$, since $C_a^2 = \text{FHE.Mult}(C_a, C_a)$, $C_a^4 = \text{FHE.Mult}(C_a^2, C_a^2)$, $C_a^8 = \text{FHE.Mult}(C_a^4, C_a^4)$, and $C_a^{16} = \text{FHE.Mult}(C_a^8, C_a^8)$, multiplicative depth is $\log(16) = 4$. See Section 3.3 for a more detailed complexity analysis.

**ConstDiv($C_a^{\text{pow}}, d$).** Algorithm 4 shows the sub-algorithm ConstDiv($C_a^{\text{pow}}, d$). The algorithm takes a list of powers of ciphertext $C_a^{\text{pow}} := (C_a, C_a^2, C_a^3, \dots, C_a^{p-1})$ and a plaintext divisor $d$ as input, then homomorphically calculates a ciphertext $C_{\lfloor a/d \rfloor}$, the decryption of which gives $\lfloor a/d \rfloor$. Note that this algorithm does not perform homomorphic multiplication, it only requires multiplication by constant multConst, which can be performed efficiently without increasing the size of the ciphertexts and SwitchKey. Moreover we note that line 1 of Algorithm 4 is performed before the algorithm start, i.e. we precompute coefficient vectors $\{a_{fd}\}_{d \in \mathbb{Z}_p}$, which appear in (3), of the interpolation polynomial.

**ConstEq($C_a^{\text{pow}}, y$).** Algorithm 5 shows the sub-algorithm ConstEq($C_a^{\text{pow}}, y$). The algorithm takes a list of powers of ciphertext $C_a^{\text{pow}} := (C_a, C_a^2, C_a^3, \dots, C_a^{p-1})$ and a plaintext input $y$ as inputs, then homomorphically calculates a ciphertext $C_{(a=y)}$, the decryption of which gives 1 when $a = y$, or 0 when $a \neq y$. This algorithm is similar to ConstDiv, except that the values of the precomputed coefficient vectors $a_{fy}$ are different. Thus, the complexity of the algorithm is almost the same as the ConstDiv, and there is no homomorphic multiplication.
**Algorithm 4** ConstDiv($C_a^{\text{pow}}$, $d$): Integer-wise Constant Division

**Input:** $C_a^{\text{pow}}$: Powers of ciphertexts $C_a$. $d$: public divisor.

**Output:** $C_{\lfloor a/d \rfloor}$

1: (Precomputing): We define a function for dividing by the fixed constant $d$ as

$$g_d(x) := \lfloor \frac{x}{d} \rfloor.$$

Given points $\{g_d(x)\}_{x \in \mathbb{Z}_p}$, calculate the interpolation polynomial $f_d(x)$ that satisfies $\forall x \in \mathbb{Z}_p, f_d(x) = g_d(x)$. For example, when plaintext modulus $p = 7$ and public divisor $d = 2$, an interpolation polynomial $f_d(x)$ is calculated given that

$$f_d(0) = 0, f_d(1) = 0, f_d(2) = 1, f_d(3) = 1, f_d(4) = 2, f_d(5) = 2, f_d(6) = 3.$$

And we obtain $f_d(x) = -2x+3x^3+x^5-2x^6$. We define $\mathbf{a}_{f_d}^{\text{ConstDiv}} := (a_1, \dots, a_{p-1}) = (-2, 0, 3, 0, 5, -2)$ as a coefficient vector of $f_d(x)$.

2: Output

$$C_{\lfloor a/d \rfloor} := (\mathbf{a}_{f_d}^{\text{ConstDiv}})^{\top} C_a^{\text{pow}} := \sum_{i=1}^{p-1} \text{FHE multConst}(C_a^i, a_i). \quad (3)$$

*Note.* We note that $\mathbf{a}_{f_d}^{\text{ConstDiv}}$ is dependent on $d$, and we precompute $\mathbf{a}_{f_d}^{\text{ConstDiv}}$ for all $d \in \mathbb{Z}_p$: We have a list of coefficient vector $\{\mathbf{a}_{f_0}^{\text{ConstDiv}}, \dots, \mathbf{a}_{f_{p-1}}^{\text{ConstDiv}}\}$ as constant.

**Algorithm 5** ConstEq($C_a^{\text{pow}}$, $y$): Integer-wise Constant Equality test

**Input:** $C_a^{\text{pow}}$: Powers of ciphertexts $C_a$. $y$: public constant.

**Output:** $C_{(a=y)}$

1: (Precomputing): We define a function for testing the equality to the fixed constant $y$ as

$$g_y(x) := \begin{cases} 1 & (x = y), \\ 0 & (x \neq y). \end{cases}$$

Given points $\{g_y(x)\}_{y \in \mathbb{Z}_p}$, calculate the interpolation polynomial $f_y(x)$ that satisfies $\forall y \in \mathbb{Z}_p, f_y(x) = g_y(x)$. For example, when $p = 7$ and $y = 3$, an interpolation polynomial $f_y(x)$ is calculated given that

$$f_y(0) = 0, f_y(1) = 0, f_y(2) = 0, f_y(3) = 1, f_y(4) = 0, f_y(5) = 0, f_y(6) = 0.$$

And we obtain $f_y(x) = 2x + 3x^2 + x^3 - 2x^4 - 3x^5 - x^6$, the coefficient vector of which is $\mathbf{a}_{f_y}^{\text{ConstEq}} := (a_1, \dots, a_{p-1}) = (2, 3, 1, -2, -3, -1)$.

2: Output

$$C_{(a=y)} := (\mathbf{a}_{f_y}^{\text{ConstEq}})^{\top} C_a^{\text{pow}} := \sum_{i=1}^{p-1} \text{FHE multConst}(C_a^i, a_i).$$

*Note.* Note that, as with ConstDiv, we precompute the first step and we have a list $\{\mathbf{a}_{f_0}^{\text{ConstEq}}, \dots, \mathbf{a}_{f_{p-1}}^{\text{ConstEq}}\}$ as constant.
<table><caption>Table 2: The multiplicative depth and the number of calls of Mult, Add and multConst in our algorithms for *l*-bit size input.</caption><thead><tr><th></th><th>Multiplicative Depth</th><th>Mult</th><th>Add</th><th>multConst</th></tr></thead><tbody><tr><td>Pows</td><td>O(l)</td><td>O(2<sup>l</sup>)</td><td>0</td><td>0</td></tr><tr><td>ConstEq</td><td>0</td><td>0</td><td>O(2<sup>l</sup>)</td><td>O(2<sup>l</sup>)</td></tr><tr><td>ConstDiv</td><td>0</td><td>0</td><td>O(2<sup>l</sup>)</td><td>O(2<sup>l</sup>)</td></tr><tr><td>Div</td><td>O(l)</td><td>O(2<sup>l</sup>)</td><td>O(2<sup>2l</sup>)</td><td>O(2<sup>2l</sup>)</td></tr></tbody></table>

### 3.3 Complexity analysis and experiments

**Complexity.** Although Algorithm 2 might seem exhaustive and inefficient due to its **for** loop, this homomorphic computation can be performed efficiently. This is mainly because:

- ConstDiv and ConstEq do not include FHE.Mult, but include FHE.multConst. Thus, ConstDiv and ConstEq do not increase the multiplicative depth.

- The most complex part Pows is executed only once for each input ciphertext $C_a$ and $C_d$ before the **for** loop.

In the following, we analyse the multiplicative depth and the total complexity of our algorithm Div. Table 2 shows a summary. In our analysis we denote by *l* the bit length of the input integers.

*Multiplicative depth.* The multiplicative depth of Pows is $O(\log p) = O(l)$, as shown in Section 3.2. The multiplicative depth of Div is also $O(l)$, because we perform only one FHE.Mult after Pows in one loop in the Div algorithm, and ConstDiv and ConstEq do not include FHE.Mult. Chen et al. showed that the multiplicative depth of their bit-wise division algorithm [9] is $O(l^2)$. The other bit-wise division algorithms [8,28] are the same as that of [9], the idea of which is based on the non-restoring division, since their improvements are mainly for bit-wise addition and multiplication. Therefore, our algorithm provides quadratic improvement in regard to the multiplicative depth of homomorphic division.

*Total complexity.* It is not trivial to adequately analyse the total complexity of the FHE circuit, because the cost of the homomorphic calculation depends on the level parameter *L*: the order of the cost of the homomorphic calculation is $O(\lambda L^3)$, as we mentioned in Section 2.2. Moreover, as mentioned in FHE.setup, the level *L* also defines the parameter *m*. The parameter *m* defines the cyclotomic polynomial $\Phi_m(x)$, which in turn defines the ciphertext space. HElib has a bound on the value *L*, and HElib halts if we set *L* too high because of the bound on the size of the cyclotomic polynomial, as noted in [9,28]. Probably based on this fact, the existing works [8, 9, 28] do not show the results on higher (>$4$) bits input integers (see Table 3).
<table><caption>Table 3: Performance comparison.</caption><thead><tr><th>l (bits)</th><th>p</th><th>L</th><th>nslots</th><th>Time (s)</th><th>type</th><th>method</th></tr></thead><tbody><tr><td>4</td><td>2</td><td>21</td><td>720</td><td>67.94</td><td rowspan="3">Bit-wise</td><td>[9]</td></tr><tr><td>4</td><td>2</td><td>21</td><td>720</td><td>14.63</td><td>[28]</td></tr><tr><td>4</td><td>2</td><td>21</td><td>720</td><td>7.74</td><td>[8]</td></tr><tr><td>4</td><td>17</td><td>9</td><td>108</td><td>3.15</td><td rowspan="4">Integer-wise Our (Div)</td><td></td></tr><tr><td><b>5</b></td><td>37</td><td>11</td><td>340</td><td>15.11</td><td></td></tr><tr><td><b>6</b></td><td>67</td><td>13</td><td>165</td><td>51.34</td><td></td></tr><tr><td><b>7</b></td><td>131</td><td>15</td><td>138</td><td>198.92</td><td></td></tr><tr><td><b>8</b></td><td>257</td><td>17</td><td>396</td><td>795.84</td><td></td><td></td></tr></tbody></table>

Although ConstDiv and ConstEq do not include homomorphic multiplication and do not increase the multiplicative depth, we perform them exhaustively in the for loop (from $i = 0$ to $p-1$), and thus we cannot ignore their cost. However, since this for loop is parallelisable, this issue could be decreased by parallelisation. In contrast, existing secure division algorithms are not suitable for parallelisation because of their full-adder circuit (e.g. Ripple Carry adder), as discussed in [8].

We also note that the memory complexity of our algorithm is relatively high. In the precomputation of polynomial interpolation, we generate the coefficient vectors and store them as a matrix, the space for which is $\mathbb{Z}_p^{p \times p}$.

**Experiments.** We implemented our secure division algorithm on HElib [16], and compared timings with existing secure division algorithms based on FHE schemes. We can compare the results only for 4-bit size input, since all the existing works report only for 4-bit integer division. We also implement for higher bit values $l = 5, \dots, 8$, and observe that the results follow our complexity analysis.

**Parameters.** We set the security parameter $\lambda = 80$, following the existing works of the secure division algorithm [8, 9, 28]. Let $l$ be a the bit size of the input integer. Since our algorithm is integer-wise and stores an input integer in $\mathbb{Z}$ into $\mathbb{Z}_p$, we define the size $p$ of the plaintext space $R_p$ as $p = \text{nextprime}(2^l)$. We set the Hamming weight of the secret vector $w = 64$. For the level parameter $L$, which is related to the multiplicative depth of the circuit, we search the minimum level by trial and error. As $L$ is the lower level, we can perform the circuit faster. However, setting $L$ too small leads to incorrectness of the outputs. For the rest of the parameter including “nslots”, which means the number of the SIMD slots, we use the default values automatically calculated by HElib. For further details, we refer the reader to [16].

**Results.** Table 3 shows our timing results, in addition to results given in existing work for bit-wise integer division. All timings were generated on a PC with a
<caption>**Algorithm 6** ConstFunc($C_a^{\text{pow}}$, $y$, $g(\cdot, \cdot)$): Integer-wise Constant Function</caption>

**Input:** $C_a^{\text{pow}}$: Powers of ciphertexts $C_a$. $y$: public constant. $g(\cdot, \cdot)$: 2-variable function.

**Output:** $C_{g(a,y)} = g(C_a, y)$

1: (Precomputing): In this algorithm, fix $y$. Thus, we consider the input 2-variable function $g(x, y) : \mathbb{Z}_p \times \mathbb{Z}_p \to \mathbb{Z}_p$ as 1-variable function $g_y(x) := g(x, y)$. For a fixed $y$, an interpolation polynomial $f_y(x)$ for $g_y(x)$ is calculated given the values $g(0, y)$, $g(1, y)$, ..., $g(p-1, y)$. And we can write the interpolation polynomial as follows: $f_y(x) = a_{\{1,y\}} \cdot x + a_{\{2,y\}} \cdot x^2 + a_{\{3,y\}} \cdot x^3 + \dots + a_{\{p-1,y\}} \cdot x^p \mod p$.

2: Calculate $C_{g(a,y)} = f_y(C_a) = a_{f_y} C_a^{\text{pow}} \mod p$, where $a_{f_y} = \{a_{\{1,y\}}, a_{\{2,y\}}, a_{\{3,y\}}, \dots, a_{\{p-1,y\}}\}$.

3.4 GHz Intel Core i5 and 16 GB RAM. To the best of our knowledge, the work by Chen et al. [8] provides the fastest results for 4-bit size input integers; thus our algorithm is the fastest secure division algorithm. While existing works report only for $l = 4$, we implemented our algorithm also for the higher bit sizes $l = 5, \dots, 8$. We can observe that our algorithm requires only $L = O(l)$, following our analysis given in Section 3.3. Moreover, we can observe that required $L$ of our algorithm is lower than that of the bit-wise algorithm for $l = 4$. Based on this fact, and that the bit-wise algorithm requires $L = O(l^2)$, we can expect that $L$ of our algorithm is globally less than that of the bit-wise algorithm.

We also note that nslots of our algorithm, which are automatically calculated by HElib depending on the other parameters, is lower than in bit-wise algorithms. This means that the amortised cost of our algorithm might be larger than existing algorithms.

# 4 Integer-wise Homomorphic Evaluation of Arbitrary 2-variable Function

We show that our secure division algorithm can be generalised to integer-wise secure computation of any 2-variable function with the same computation cost.

## 4.1 Algorithms

Our integer-wise homomorphic evaluation algorithm of any (predefined) 2-variable function $\text{Func}(C_a, C_d)$ given in Algorithm 7 is constructed based on Div, by replacing $\text{ConstDiv}$ with $\text{ConstFunc}(C_a^{\text{pow}}, y, g(\cdot, \cdot))$ (Algorithm 6), which performs 1-variable function $g_y(x) := g(x, y)$ over a ciphertext $C_a$.

**ConstFunc.** Algorithm 6 shows the ConstFunc algorithm. The algorithm takes a list of powers of ciphertext $C_a^{\text{pow}} := (C_a, C_a^2, C_a^3, \dots, C_a^{p-1})$, a plaintext $y$ and a 2-variable function $g(\cdot, \cdot)$ (i.e., coefficient vectors of its interpolation polynomial), and then homomorphically calculates a ciphertext $C_{g(a,y)}$, the decryption of which gives $g(a, y)$. Recall that, in the $\text{ConstDiv}(C_a^{\text{pow}}, d)$, we used polynomial
**Algorithm 7 Func($C_a, C_b, g(\cdot, \cdot)$):** Integer-wise Homomorphic 2-variable function

**Input:** Ciphertexts $C_a, C_b$. 2-variable function $g$.

**Output:** $C_{g(a,b)} = g(C_a, C_b)$

1: $C_{\text{sum}} = 0$

2: $C_a^{\text{pow}} = \text{Pows}(C_a)$

3: $C_b^{\text{pow}} = \text{Pows}(C_b)$

4: **for** $i = 1$ to $(p-1)$ **do**

5: &nbsp;&nbsp;&nbsp;&nbsp; $C_{g(a,i)} = \text{ConstFunc}(C_a^{\text{pow}}, i, g)$

6: &nbsp;&nbsp;&nbsp;&nbsp; $C_{(i=b)} = \text{ConstEq}(C_b^{\text{pow}}, i)$

$$ \triangleright C_a^{\text{pow}} := \{C_a, C_a^2, C_a^3, \dots, C_a^{p-1}\} $$

$$ \triangleright C_b^{\text{pow}} := \{C_b, C_b^2, C_b^3, \dots, C_b^{p-1}\} $$

$$ \triangleright C_{g(a,i)} = g(C_a, i) $$

$$ \triangleright C_{(i=b)} = C_1 \text{ if } i = b, C_{(i=b)} = C_0 \text{ otherwise.} $$

7: $C_{\text{sum}} = C_{\text{sum}} + \text{FHE.Mult}(C_{g(a,i)}, C_{(i=b)}) \triangleright \text{FHE.Mult}(C_{g(a,i)}, C_{(i=b)}) = C_{g(a,b)}$ if $i = b, C_0$ otherwise.

8: **end for**

9: **Output** $C_{g(a,b)} = C_{\text{sum}}$

interpolation to construct a function $f_d(x) = \lfloor \frac{x}{d} \rfloor$ for all $d \in \mathbb{Z}_p$, giving data points $\{f_d(0), f_d(1), \dots, f_d(p-1)\}$. We can simply generalise ConstDiv as a general function: in ConstFunc, we use polynomial interpolation to construct a required function $g_y(x)$ defined by given data points $\{g_y(0), g_y(1), \dots, g_y(p-1)\}$, for all $y \in \mathbb{Z}_p$. Only the data points (or, coefficient vectors) are different between ConstDiv and ConstFunc. Thus, the order of multiplicative depth of ConstFunc is exactly the same as ConstDiv. Note that we precompute the coefficient vectors $a_{f_y}$ for all $y \in \mathbb{Z}_p$ using the polynomial interpolation, as with ConstDiv.

**Func.** Algorithm 7 shows our algorithm for integer-wise homomorphic evaluation of the arbitrary 2-variable function, Func. The algorithm takes two ciphertexts $C_a$ and $C_b$, which are ciphertexts of $a$ and $b$, respectively, and a 2-variable function $g(\cdot, \cdot)$ (i.e., coefficient vectors of its interpolation polynomial) as inputs. It then homomorphically calculates a ciphertext $C_{g(a,b)}$, which decrypts to $g(a, b)$. This algorithm is almost the same as Div (Algorithm 2), except that ConstDiv is replaced by ConstFunc. Since the order of multiplicative depth of ConstFunc is exactly the same as ConstDiv, that of Func is exactly the same as Div.

## 5 Conclusion

We propose a first secure integer-wise homomorphic division algorithm on fully homomorphic encryption schemes. We implemented the algorithm on HElib, and show that our algorithm is over twice as fast as the fastest existing algorithm given in [8]. We also showed that the multiplicative depth of our algorithm is $O(l)$ for $l$-bit size integer, while that of existing division algorithms is $O(l^2)$.

Furthermore, we generalise our secure division algorithm and propose an algorithm for secure calculation of general 2-variable functions. We showed that the complexity of the algorithm is the same as our division algorithm. This means that the homomorphic calculation of any 2-variable functions taking integer inputs can be performed with multiplicative depth $O(l)$.
References

1. Bost, R., Popa, R.A., Tu, S., Goldwasser, S.: Machine Learning Classification over Encrypted Data. In: NDSS Symposium 2015. p. 04_1_2. Internet Society (2015). https://doi.org/10.14722/ndss.2015.23241

2. Bourse, F., Minelli, M., Minihold, M., Paillier, P.: Fast Homomorphic Evaluation of Deep Discretized Neural Networks. In: Shacham, H., Boldyreva, A. (eds.) Advances in Cryptology – CRYPTO 2018. pp. 483–512. Springer (2018). https://doi.org/10.1007/978-3-319-96878-0_17

3. Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) Fully Homomorphic Encryption Without Bootstrapping. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. pp. 309–325. ITCS ’12, ACM (2012). https://doi.org/10.1145/2090236.2090262

4. Brakerski, Z., Vaikuntanathan, V.: Efficient Fully Homomorphic Encryption from (Standard) LWE. In: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. pp. 97–106. FOCS ’11, IEEE Computer Society (2011). https://doi.org/10.1109/FOCS.2011.12

5. Brakerski, Z., Vaikuntanathan, V.: Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages. In: Rogaway, P. (ed.) Advances in Cryptology – CRYPTO 2011. pp. 505–524. Springer (2011). https://doi.org/10.1007/978-3-642-22792-9_29

6. Brakerski, Z., Vaikuntanathan, V.: Lattice-based FHE As Secure As PKE. In: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science. pp. 1–12. ITCS ’14, ACM (2014). https://doi.org/10.1145/2554797.2554799

7. Çetin, G.S., Doröz, Y., Sunar, B., Savaş, E.: Depth Optimized Efficient Homomorphic Sorting. In: Lauter, K., Rodríguez-Henríquez, F. (eds.) Progress in Cryptology – LATINCRYPT 2015. pp. 61–80. Springer (2015). https://doi.org/10.1007/978-3-319-22174-8_4

8. Chen, J., Feng, Y., Liu, Y., Wu, W.: Faster Binary Arithmetic Operations on Encrypted Integers. In: the 7th International Workshop on Computer Science and Engineering (2017)

9. Chen, Y., Gong, G.: Integer arithmetic over ciphertext and homomorphic data aggregation. In: 2015 IEEE Conference on Communications and Network Security (CNS). pp. 628–632 (Sept 2015). https://doi.org/10.1109/CNS.2015.7346877

10. van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully Homomorphic Encryption over the Integers. In: Gilbert, H. (ed.) Advances in Cryptology – EUROCRYPT 2010. pp. 24–43. Springer (2010). https://doi.org/10.1007/978-3-642-13190-5_2

11. Gentry, C.: A fully homomorphic encryption scheme. Ph.D. thesis, Stanford University (2009). crypto.stanford.edu/craig

12. Gentry, C.: Fully Homomorphic Encryption Using Ideal Lattices. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing. pp. 169–178. STOC ’09, ACM (2009). https://doi.org/10.1145/1536414.1536440

13. Gentry, C., Halevi, S., Smart, N.P.: Homomorphic Evaluation of the AES Circuit. In: Safavi-Naini, R., Canetti, R. (eds.) Advances in Cryptology – CRYPTO 2012. pp. 850–867. Springer (2012). https://doi.org/10.1007/978-3-642-32009-5_49

14. Gentry, C., Sahai, A., Waters, B.: Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In: Canetti, R., Garay, J.A. (eds.) Advances in Cryptology – CRYPTO 2013. pp. 75–92. Springer (2013). https://doi.org/10.1007/978-3-642-40041-4_5
15. Gilad-Bachrach, R., Dowlin, N., Laine, K., Lauter, K., Naehrig, M., Wernsing, J.: CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy. In: Balcan, M.F., Weinberger, K.Q. (eds.) Proceedings of The 33rd International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 48, pp. 201–210. PMLR (20–22 Jun 2016). http://proceedings.mlr press/v48/gilad-bachrach16.html

16. Halevi, S., Shoup, V.: HElib - An Implementation of homomorphic encryption. https://github.com/shaih/HElib/

17. Halevi, S., Shoup, V.: Algorithms in HElib. In: Garay, J.A., Gennaro, R. (eds.) Advances in Cryptology – CRYPTO 2014. pp. 554–571. Springer (2014). https://doi.org/10.1007/978-3-662-44371-2_31

18. Halevi, S., Shoup, V.: Bootstrapping for HElib. In: Oswald, E., Fischlin, M. (eds.) Advances in Cryptology – EUROCRYPT 2015. pp. 641–670. Springer (2015). https://doi.org/10.1007/978-3-662-46800-5_25

19. Halevi, S., Shoup, V.: Faster Homomorphic Linear Transformations in HElib. In: Shacham, H., Boldyreva, A. (eds.) Advances in Cryptology – CRYPTO 2018. pp. 93–120. Springer (2018). https://doi.org/10.1007/978-3-319-96884-1_4

20. Juvekar, C., Vaikuntanathan, V., Chandrakasan, A.: GAZELLE: A Low Latency Framework for Secure Neural Network Inference. In: 27th USENIX Security Symposium (USENIX Security 18). pp. 1651–1669. USENIX Association, Baltimore, MD (2018). https://www.usenix.org/conference/usenixsecurity18/ presentation/juvekar

21. Lyubashevsky, V., Peikert, C., Regev, O.: On Ideal Lattices and Learning with Errors over Rings. In: Gilbert, H. (ed.) Advances in Cryptology – EUROCRYPT 2010. pp. 1–23. Springer (2010). https://doi.org/10.1007/978-3-642-13190-5_1

22. Narumanchi, H., Goyal, D., Emmadi, N., Gauravaram, P.: Performance Analysis of Sorting of FHE Data: Integer-Wise Comparison vs Bit-Wise Comparison. In: 2017 IEEE 31st International Conference on Advanced Information Networking and Applications (AINA). pp. 902–908 (March 2017). https://doi.org/10.1109/AINA.2017.85

23. Regev, O.: On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. J. ACM 56(6), 34:1–34:40 (Sep 2009). https://doi.org/10.1145/1568318.1568324

24. Shoup, V.: NTL: A Library for doing Number Theory. http://shoup.net/ntl/

25. Smart, N.P., Vercauteren, F.: Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes. In: Nguyen, P.Q., Pointcheval, D. (eds.) Public Key Cryptography – PKC 2010. pp. 420–443. Springer (2010). https://doi.org/10.1007/978-3-642-13013-7_25

26. Smart, N.P., Vercauteren, F.: Fully homomorphic SIMD operations. Designs, Codes and Cryptography 71(1), 57–81 (Apr 2014). https://doi.org/10.1007/s10623-012- 9720-4

27. Stehlé, D., Steinfeld, R.: Faster Fully Homomorphic Encryption. In: Abe, M. (ed.) Advances in Cryptology - ASIACRYPT 2010. pp. 377–394. Springer (2010). https://doi.org/10.1007/978-3-642-17373-8_22

28. Xu, C., Chen, J., Wu, W., Feng, Y.: Homomorphically Encrypted Arithmetic Operations Over the Integer Ring. In: Bao, F., Chen, L., Deng, R.H., Wang, G. (eds.) Information Security Practice and Experience. pp. 167–181. Springer (2016). https://doi.org/10.1007/978-3-319-49151-6_12