# Homomorphic Evaluation of the Integer Arithmetic Operations for Mobile Edge Computing

Authors: Changqing Gong; Mengfei Li; Liang Zhao; Zhenzhou Guo; Guangjie Han
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

With the rapid development of the 5G network and Internet of Things (IoT), lots of mobile and IoT devices generate massive amounts of multisource heterogeneous data. Effective processing of such data becomes an urgent problem. However, traditional centralised models of cloud computing are challenging to process multisource heterogeneous data effectively. Mobile edge computing (MEC) emerges as a new technology to optimise applications or cloud computing systems. However, the features of MEC such as content perception, real-time computing, and parallel processing make the data security and privacy issues that exist in the cloud computing environment more prominent. Protecting sensitive data through traditional encryption is a very secure method, but this will make it impossible for the MEC to calculate the encrypted data. The fully homomorphic encryption (FHE) overcomes this limitation. FHE can be used to compute ciphertext directly. Therefore, we propose a ciphertext arithmetic operation that implements data with integer homomorphic encryption to ensure data privacy and computability. Our scheme refers to the integer operation rules of complement, addition, subtraction, multiplication, and division. First, we use Boolean polynomials (BP) of containing logical AND, XOR operations to represent the rulers. Second, we convert the BP into homomorphic polynomials (HP) to perform ciphertext operations. Then, we optimise our scheme. We divide the ciphertext vector of integer encryption into subvectors of length 2 and increase the length of private key of FHE to support the 3-multiplication level additional. We test our optimised scheme in DGHV and CMNT. In the number of ciphertext refreshes, the optimised scheme is reduced by 2/3 compared to the original scheme, and the time overhead of our scheme is reduced by 1/3. We also examine our scheme in CNT of without bootstrapping. The time overhead of optimised scheme over DGHV and CMNT is close to the original scheme over CNT.


---

## Body

## 1. Introduction

With the rapid development of the 5G network and Internet of Things (IoT), mobile devices and IoT devices are more convenient to access the internet and generate massive amounts of data. Since these data come from edge network devices, traditional centralised cloud computing models are difficult to process these multisource heterogeneous data quickly and efficiently. If we migrate some of the features of cloud computing to an edge network as [1–3], it will be beneficial to data collection and calculation. Therefore, mobile edge computing (MEC) emerges as the above requires. Edge computing [4] is a method of optimizing applications or cloud computing systems by taking some portion of an application, its data, or services away from one or more central nodes (the “core”) to the other logical extreme (the “edge”) of the internet which contacts with the physical world or end users. In one vision of this architecture, specifically for IoT devices, data comes in from the physical world via various sensors, and actions are taken to change physical state via various forms of output and actuators; by performing analytics and knowledge generation at the edge, communications bandwidth between systems under control and the central data centre is reduced. The MEC is to put any computer program that needs low latency nearer to the requests in particular for mobile networks such as 5G. MEC allows terminal devices to migrate storage and computing tasks to network edge nodes. The architecture of edge computing is shown in Figure 1.Figure 1
The architecture of mobile edge computing.MEC covers a wide range of technologies including wireless sensor networks, mobile data acquisition, mobile signature analysis, cooperative distributed peer-to-peer ad hoc networking, and processing. The foundation of MEC is traditional network, wireless network, mobile network, and Internet of Vehicles (IoV), in which a large number of network infrastructure technologies and services are applied. Include energy efficiency and spectral efficiency tradeoff in device-to-device [5], QoS-aware interdomain multicast [6], efficient cross-layer relay node selection model [7], mobile anchors assisted localization [8], and vehicular communications [9]. Mobile edge computing (see Figure 1) is a service for multiple entities (mobile devices and IoT devices). Many entities put their real-time data (outsourced data in cloud computing) on mobile edge computing for analysis or storage. The extensive features of mobile edge computing such as data collection, real-time analytics, and parallel processing make the privacy issues that exist in the cloud computing environment become more prominent. Therefore, the security of outsourced data remains a fundamental issue for data security of MEC. The red dotted lines (see Figure 1) represent safety risk between the different entities and mobile edge computing, such as IoV and smart home services provided by mobile edge computing. In IoV, the location information of the vehicle and the online browsing records generated by the owner are collected by the mobile edge calculation, so as to feed back the precise navigation information of the vehicle, and the push information for the owner’s preferences. In this process, the data of the owner and the car are exposed to the mobile edge computing, which is extremely unsafe. In smart home, many sensors monitor environment changes in the room, such as temperature, humidity, surveillance video, etc., through mobile edge calculation storage and analysis, giving the best home environment settings. This process is also unsafe. Traditional methods, including intrusion detection, access control, and virtual isolation, can only protect data from being stolen by external attackers. For internal attacks (honest and curious mobile edge computing), data security is still not guaranteed. The encrypted data are relatively considered a safe storage status. However, it is unable to satisfy the computability of ciphertext data. If we want the edge computing to be able to do nontrivial computations with the ciphertext data, and therefore the problem is severe to solve. The nontrivial computations include deep learning for the IoV with Edge Computing [10], offloading computation for MEC [11]. The fully homomorphic encryption (FHE) overcomes this limitation. Gentry described the first encryption scheme that supports both addition and multiplication base on ciphertexts, i.e., FHE scheme [12]. The FHE scheme allows anyone to perform arbitrary computations on encrypted data, despite not having the secret decryption key.The development of FHE can be partitioned into three generations [13]. The first generation includes Gentry’s original scheme using ideal lattices [12], the somewhat simpler scheme of van Dijk et al. [14], and some optimisations for first generation in public key size [15–17]. All these schemes have a problem of rapidly growing noise, which affected both efficiency and security. The second generation begin with Brakerski-Vaikuntanathan [18, 19] and Brakerski et al. [20] and is characterized by modulus-switching and key-switching techniques for controlling the noise, resulting in improved efficiency, including LWE [18], Ring-LWE [19], and NTRU [21, 22] hardness assumption. The third generation begins with the scheme of Gentry et al. [23]. Third-generation schemes are usually slightly less efficient than second-generation ones, but they can be based on somewhat weaker hardness assumptions.In the homomorphic evaluation of FHE, different circuits in the real world are realized by multiplication homomorphic, addition homomorphic, and decryption homomorphic (ciphertext refresh). The application of FHE is ciphertext arithmetic operation and ciphertext retrieval. Gentry, Halevi, and Smart propose the first evaluation of a complex circuit, i.e., a full AES-128 block evaluation [24] by using a BGV [20] style scheme. The scheme makes use of batching [25, 26], key switching, and modulus switching techniques to obtain an efficient levelled implementation. Chen Y. et al. [27] propose the integer arithmetic over ciphertext and homomorphic data aggregation by using a BGV style scheme. The scheme uses the HElib library to implement homomorphic evaluation for addition, subtraction, multiplication, and division of unsigned integrins. Gai K. et al. [28] propose the blend arithmetic operations on tensor-based FHE over real numbers and proposes a novel tensor-based FHE solution [29]. Yang J. et al. [30] propose the secure tensor decomposition using FHE scheme.In [24], AES-128 block evaluation cannot implement carry operation. In [27], the integer arithmetic over ciphertext just implement 2-4 bits arithmetic operation of unsigned integer. In [28], the blend arithmetic operations do not implement division operation over tensor-based FHE over real numbers. Therefore, the [24, 27, 28] cannot be used as a complete homomorphic evaluation of a signed integer arithmetic operations scheme by using addition and multiplication homomorphism in MEC. The homomorphic evaluation of integer arithmetic operations is an important foundation for nontrivial computations with the ciphertext data. Therefore, it is significant to construct homomorphic evaluation of integer arithmetic operations scheme.Contribution. We propose the homomorphic evaluations of integer arithmetic operations base on DGHV [14] and its variants [15, 31, 32] in mobile edge computing. And we use the features of homomorphic encryption to prevent sensitive data from being stolen. At the same time, we can also calculate ciphertext data in mobile edge computing.(i)
Our scheme refers to the integer operation rules which are expressed in Boolean polynomials (BP) that only contains logical AND, XOR operations. Then, we convert BP into homomorphic polynomials (HP) by using addition and multiplication on ciphertexts.(ii)
We propose judgment choose Boolean polynomials (JCBP) to solve the constantly choose problem in the multiplication and division. Then we convert JCBP into judgment choose homomorphic polynomials (JCHP) by using addition and multiplication on ciphertexts.(iii)
We optimise the process of homomorphic evaluation of integer arithmetic operations. We divide the ciphertext vector of integer encryption into subvectors of length 2 and add the length of the private key of FHE to support the 3-multiplication level additional, except for the 15-multiplication level required by bootstrapping.(iv)
We test the optimized scheme in DGHV [14] and CMNT [17]. In the number of ciphertext refreshes, the optimized scheme is reduced by 2/3 compared to the original scheme, and the homomorphic evaluation time overhead of integer arithmetic operations is reduced by 1/3. We also test our scheme in CNT [31] of without bootstrapping. The time overhead of optimized scheme over DGHV [14] and CMNT [17] is close to the original scheme over CNT [31].Organization. In Section 2, we will introduce DGHV [14], the variants of DGHV [17, 31, 32] and some homomorphic evaluation in detail. In Section 3, we modify the polynomials of integer arithmetic operation according to the computation process of complement, addition, subtraction, multiplication, and division of integer in the computer. We also propose the BP of integer arithmetic operation and convert the BP into the HP of integer arithmetic operation. In Section 4, we analyse the noise ceiling and optimize the process of homomorphic evaluation of integer arithmetic operations. In Section 5, we show our implementation and experimental result. We show the efficiency and conclusion of our scheme.


## 2. Related Work

Fully homomorphic encryption scheme over the integers and its variants are an essential branch of homomorphic encryption research. Also, we propose the homomorphic evaluations of integer arithmetic operations base on DGHV and its variants. We use DGHV and its variants to encrypt data and upload ciphertext data to a MEC data center. The server of MEC can process ciphertext data by using features of homomorphic encryption. Our scheme involves homomorphic encryption and ciphertext computing. Therefore, we will introduce the original homomorphic encryption scheme DGHV [14] and its variants on integer, including shorter public keys CMNT [17], public keys compress and modulus switching CNT [31], batch encryption CCKL+ [32]. Below we will replace [14, 17, 31, 32] with DGHV, CMNT, CNT, and CCKL+. At the same time, we will also introduce some ciphertext computing techniques related to our scheme, including full AES-128 block evaluation [24] by using a BGV style scheme, integer arithmetic over ciphertext and homomorphic data aggregation [27], the blend arithmetic operations on tensor-based FHE over real numbers [28].


### 2.1. DGHV and Variants Scheme

The DGHV scheme is described by van Dijk et al. base on integer and to simplify [12]. The advantages of DGHV include simple encryption process and being easy to understand. However, it has a weakness that the noise in ciphertext increases rapidly with the multiplicative level increases. The scheme is based on a set of public integers: xi=qip+ri,0≤i≤τ, where the integer p is secret. We use the same notation as in DGHV. The DGHV use the following parameters (all polynomial in the security parameter λ):(i)
γ is the bit-length of the xi’s.(ii)
η is the bit-length of private key p.(iii)
ρ is the bit-length of the noise ri.(iv)
τ is the number of xi’s in the public key.(v)
ρ′ is used for encryption.For a specificη-bit odd integer p, DGHV use the following distribution over γ-bit integers:(1)Dγ,ρp=Chooseq←Z∩0,2γp,r←Z∩-2ρ,2ρ:Outputx=q·p+rK e y G e n ( λ ). Generate a random odd integer p of size η bits as a sk. For the public key, sample xi←Dγ,ρp for 0≤i≤τ. Relabel so that x0 is the largest. Let x0 be odd and x0p even. Let pk=x0,x1,…,xτ and sk=p.E n c r y p t ( p k , m ∈ 0,1 ). Choose a random subset S⊆1,2,…,τ and a random integer r∈(-2ρ,2ρ), and output c←[m+2r+2∑i∈Sxi]x0.D e c r y p t s k , c. Output m′=cmod⁡pmod⁡2=(cmod⁡2)(c/pmod⁡2).E v a l u a t e p k , C , c 1 , c 2 , … , c t. Given the function F with t input, and t ciphertexts ci, convert logic AND and logic XOR of F into addition and multiplication, performing all the addition and multiplication, and return the resulting integer.The following parameter set is suggested in DGHV:ρ=λ, ρ′=2λ, η=O~λ2, γ=O~λ5, τ=γ+λ. The public key size is then O~λ10.The CMNT scheme is described by Coron et al. to reduce the public key size of the DGHV scheme fromO~λ10 down to O~λ7. CMNT scheme applies a new parameter β by the form xij′=xi,0∙xj,1mod⁡x0,1≤i,j≤β to generate the τ=β2 integers xij′ used for encryption. CMNT scheme enables reducing the public key size from τ down to roughly 2τ integers of bits. CMNT scheme uses an error-free x0, that is, x0=q0p, since otherwise, the error would grow too large. Additionally, for encryption CMNT scheme consider a linear combination of the xij′ with a coefficient vector b=bi,j instead of bits; this enables reducing the public key size further. The vector b with components in [0,2α).The CMNT scheme takesρ=λ, η=O~λ2, and γ=O~λ5 as in the DGHV scheme. However, it takes α=λ,  β2=O~λ2, and ρ′=4λ. The main difference is that instead of having τ=O~λ5 integers xi’s, CMNT scheme has only 2β=O~λ2 integers xi. Hence the public key size becomes O~λ7 instead of O~λ10.Coron and Naccache et al. describe the CNT scheme. The CMT describes a method that can compress the public key size of the DGHV scheme and optimise the noise management technique by modifying the modulus switching technology [20]. The noise ceiling of CNT scheme increases only linearly with the multiplicative level instead of exponentially. So, a levelled DGHV variant was implemented. This scheme gives two optimisations for homomorphic encryption on DGHV as below.The first optimisation is public keys compression. First generate the secret keyp of size η bits and use a pseudo-random function f with random seed se to generate a set of χi∈0,2γ, 1≤i≤τ. Finally, compute δi that xi=χi-δi is small modulo p and store δi in the public key, instead of the full xi’s.The second optimisation is Modulus-Switching Technique. The CMNT show how to adapt Brakerski, Gentry, and Vaikuntanathan’s (BGV) FHE framework [20] to the DGHV scheme over the integers. Under the [20] framework, the noise ceiling increases only linearly with multiplicative depth, instead of exponentially.The CNT scheme takesρ=λ, η=O~λ2, γ=O~λ5, α=O~λ2, τ=O~λ3, and ρ′=O~λ2. The new public key of CNT scheme has size γ+τ∙η+λ=O~λ5 instead of O~λ10 of DGHV.J.H. Cheon et al. describe the CCKL+ scheme. It extends DGHV to support the same batching capability as in RLWE-based schemes [20, 25], and to homomorphically evaluate a full AES circuit with roughly the same level of efficiency as [24]. The CCKL+ scheme is a merger of two independent works [33, 34] built on the same basic idea but with different contributions. Its security under the (stronger) Error-Free Approximate-GCD assumption already DGHV, CMNT, and CNT.The CCKL+ scheme extends the DGHV scheme by packingl plaintexts m0,⋯ml-1 into a single ciphertext, using the Chinese Remainder Theorem (CRT). For somewhat homomorphic encryption, this allows us to encrypt not only bits but elements from rings of form ZQ. The CKLL+ scheme takes ρ=2λ, η=O~λ2, γ=O~λ5, α=O~λ2, and τ=O~λ3 as in CNT scheme, with ρ′=O~λ, α′=O~λ2, and l=O~λ2.We can conclude (see Table1) that the CNT scheme performs best in public key storage and only 10.1 MB. We test public key size of DGHV by using “large” parameters of CMNT, and up to 41 GB. The CNT scheme has better noise management technique, in which the noise ceiling increases only linearly with the multiplicative level. Therefore, the CNT scheme supports more multiplication level than other schemes. The CCKL+ scheme implements batch FHE scheme to encrypt a plaintext vector to a ciphertext by using the CRT. However, each one of the components in the plaintext vector is required to be independent. If we encrypt a plaintext vector, the encryption result is a plaintext vector using DGHV, CMNT, and CNT scheme, and the encryption result is a ciphertext by using CCKL+. Therefore, when we do arithmetic operations on the ciphertext of a plaintext vector, we can perform carry operation by using DGHV, CMNT, and CNT scheme, instead of using CCKL+.Table 1
The parameters of DGHV, CMNT, CNT and CCKL+, and public key storage size.
FHE scheme λ ρ ′ η γ pk length pk size DGHV λ 2 λ O ~ λ 2 O ~ λ 5 O ~ λ 10 41 GB CMNT λ 4 λ O ~ λ 2 O ~ λ 5 O ~ λ 7 800 MB CNT λ O ~ λ 2 O ~ λ 2 O ~ λ 5 O ~ λ 5 10.1 MB CCKL+ λ 3 λ O ~ λ 2 O ~ λ 5 O ~ λ 8 5.6 GB


### 2.2. Homomorphic Evaluation

The advantage of homomorphic evaluation is implementing various operations in the real world on ciphertext and is not only multiplication homomorphic, addition homomorphic, and decryption homomorphic (ciphertext refresh). The FHE abstracts various operations of the real world as a collection of circuits consisting of logical XOR and logical AND. The homomorphic evaluation is to implement different circuits in this collection of circuits. Below we will introduce some relevant schemes for homomorphic evaluation of arithmetic operations.Gentry, Halevi, and Smart propose the first evaluation of a complex circuit, i.e., a full AES-128 block evaluation [24] by using a BGV [20] style scheme. The scheme makes use of batching [25, 26], key switching, and modulus switching techniques to obtain an efficient levelled implementation. After that, Gentry, Smart, and Halevi publish significantly improved runtime results. Compared to the earlier implementation [21], Gentry et al. use the latest version of the HElib library [35]. Two variations of the implementation are reported: one with bootstrapping and one without bootstrapping.Chen Y. et al. [27] propose the integer arithmetic over ciphertext and homomorphic data aggregation by using a BGV [20] style scheme. The scheme uses the HElib library [35] to implement homomorphic evaluation for addition, subtraction, multiplication, and division of unsigned integrins. However, the scheme report time overhead of integer arithmetic over ciphertext without bootstrapping and modulus switching (somewhat homomorphic encryption). The length of integer ciphertext only sets 2, 3, 4 bits and sets 128 security level to guarantee right result. The scheme does not optimise the operations of integer arithmetic over ciphertext with bootstrapping and modulus switching.Gai K. et al. [28] propose the blend arithmetic operations on tensor-based FHE over real numbers and propose a novel tensor-based FHE solution [29]. The scheme uses tensor laws to carry the computations of blend arithmetic operations over real numbers. However, blend arithmetic operations only include addition and multiplication. The scheme does not implement blend arithmetic operations with the division.


## 2.1. DGHV and Variants Scheme

The DGHV scheme is described by van Dijk et al. base on integer and to simplify [12]. The advantages of DGHV include simple encryption process and being easy to understand. However, it has a weakness that the noise in ciphertext increases rapidly with the multiplicative level increases. The scheme is based on a set of public integers: xi=qip+ri,0≤i≤τ, where the integer p is secret. We use the same notation as in DGHV. The DGHV use the following parameters (all polynomial in the security parameter λ):(i)
γ is the bit-length of the xi’s.(ii)
η is the bit-length of private key p.(iii)
ρ is the bit-length of the noise ri.(iv)
τ is the number of xi’s in the public key.(v)
ρ′ is used for encryption.For a specificη-bit odd integer p, DGHV use the following distribution over γ-bit integers:(1)Dγ,ρp=Chooseq←Z∩0,2γp,r←Z∩-2ρ,2ρ:Outputx=q·p+rK e y G e n ( λ ). Generate a random odd integer p of size η bits as a sk. For the public key, sample xi←Dγ,ρp for 0≤i≤τ. Relabel so that x0 is the largest. Let x0 be odd and x0p even. Let pk=x0,x1,…,xτ and sk=p.E n c r y p t ( p k , m ∈ 0,1 ). Choose a random subset S⊆1,2,…,τ and a random integer r∈(-2ρ,2ρ), and output c←[m+2r+2∑i∈Sxi]x0.D e c r y p t s k , c. Output m′=cmod⁡pmod⁡2=(cmod⁡2)(c/pmod⁡2).E v a l u a t e p k , C , c 1 , c 2 , … , c t. Given the function F with t input, and t ciphertexts ci, convert logic AND and logic XOR of F into addition and multiplication, performing all the addition and multiplication, and return the resulting integer.The following parameter set is suggested in DGHV:ρ=λ, ρ′=2λ, η=O~λ2, γ=O~λ5, τ=γ+λ. The public key size is then O~λ10.The CMNT scheme is described by Coron et al. to reduce the public key size of the DGHV scheme fromO~λ10 down to O~λ7. CMNT scheme applies a new parameter β by the form xij′=xi,0∙xj,1mod⁡x0,1≤i,j≤β to generate the τ=β2 integers xij′ used for encryption. CMNT scheme enables reducing the public key size from τ down to roughly 2τ integers of bits. CMNT scheme uses an error-free x0, that is, x0=q0p, since otherwise, the error would grow too large. Additionally, for encryption CMNT scheme consider a linear combination of the xij′ with a coefficient vector b=bi,j instead of bits; this enables reducing the public key size further. The vector b with components in [0,2α).The CMNT scheme takesρ=λ, η=O~λ2, and γ=O~λ5 as in the DGHV scheme. However, it takes α=λ,  β2=O~λ2, and ρ′=4λ. The main difference is that instead of having τ=O~λ5 integers xi’s, CMNT scheme has only 2β=O~λ2 integers xi. Hence the public key size becomes O~λ7 instead of O~λ10.Coron and Naccache et al. describe the CNT scheme. The CMT describes a method that can compress the public key size of the DGHV scheme and optimise the noise management technique by modifying the modulus switching technology [20]. The noise ceiling of CNT scheme increases only linearly with the multiplicative level instead of exponentially. So, a levelled DGHV variant was implemented. This scheme gives two optimisations for homomorphic encryption on DGHV as below.The first optimisation is public keys compression. First generate the secret keyp of size η bits and use a pseudo-random function f with random seed se to generate a set of χi∈0,2γ, 1≤i≤τ. Finally, compute δi that xi=χi-δi is small modulo p and store δi in the public key, instead of the full xi’s.The second optimisation is Modulus-Switching Technique. The CMNT show how to adapt Brakerski, Gentry, and Vaikuntanathan’s (BGV) FHE framework [20] to the DGHV scheme over the integers. Under the [20] framework, the noise ceiling increases only linearly with multiplicative depth, instead of exponentially.The CNT scheme takesρ=λ, η=O~λ2, γ=O~λ5, α=O~λ2, τ=O~λ3, and ρ′=O~λ2. The new public key of CNT scheme has size γ+τ∙η+λ=O~λ5 instead of O~λ10 of DGHV.J.H. Cheon et al. describe the CCKL+ scheme. It extends DGHV to support the same batching capability as in RLWE-based schemes [20, 25], and to homomorphically evaluate a full AES circuit with roughly the same level of efficiency as [24]. The CCKL+ scheme is a merger of two independent works [33, 34] built on the same basic idea but with different contributions. Its security under the (stronger) Error-Free Approximate-GCD assumption already DGHV, CMNT, and CNT.The CCKL+ scheme extends the DGHV scheme by packingl plaintexts m0,⋯ml-1 into a single ciphertext, using the Chinese Remainder Theorem (CRT). For somewhat homomorphic encryption, this allows us to encrypt not only bits but elements from rings of form ZQ. The CKLL+ scheme takes ρ=2λ, η=O~λ2, γ=O~λ5, α=O~λ2, and τ=O~λ3 as in CNT scheme, with ρ′=O~λ, α′=O~λ2, and l=O~λ2.We can conclude (see Table1) that the CNT scheme performs best in public key storage and only 10.1 MB. We test public key size of DGHV by using “large” parameters of CMNT, and up to 41 GB. The CNT scheme has better noise management technique, in which the noise ceiling increases only linearly with the multiplicative level. Therefore, the CNT scheme supports more multiplication level than other schemes. The CCKL+ scheme implements batch FHE scheme to encrypt a plaintext vector to a ciphertext by using the CRT. However, each one of the components in the plaintext vector is required to be independent. If we encrypt a plaintext vector, the encryption result is a plaintext vector using DGHV, CMNT, and CNT scheme, and the encryption result is a ciphertext by using CCKL+. Therefore, when we do arithmetic operations on the ciphertext of a plaintext vector, we can perform carry operation by using DGHV, CMNT, and CNT scheme, instead of using CCKL+.Table 1
The parameters of DGHV, CMNT, CNT and CCKL+, and public key storage size.
FHE scheme λ ρ ′ η γ pk length pk size DGHV λ 2 λ O ~ λ 2 O ~ λ 5 O ~ λ 10 41 GB CMNT λ 4 λ O ~ λ 2 O ~ λ 5 O ~ λ 7 800 MB CNT λ O ~ λ 2 O ~ λ 2 O ~ λ 5 O ~ λ 5 10.1 MB CCKL+ λ 3 λ O ~ λ 2 O ~ λ 5 O ~ λ 8 5.6 GB


## 2.2. Homomorphic Evaluation

The advantage of homomorphic evaluation is implementing various operations in the real world on ciphertext and is not only multiplication homomorphic, addition homomorphic, and decryption homomorphic (ciphertext refresh). The FHE abstracts various operations of the real world as a collection of circuits consisting of logical XOR and logical AND. The homomorphic evaluation is to implement different circuits in this collection of circuits. Below we will introduce some relevant schemes for homomorphic evaluation of arithmetic operations.Gentry, Halevi, and Smart propose the first evaluation of a complex circuit, i.e., a full AES-128 block evaluation [24] by using a BGV [20] style scheme. The scheme makes use of batching [25, 26], key switching, and modulus switching techniques to obtain an efficient levelled implementation. After that, Gentry, Smart, and Halevi publish significantly improved runtime results. Compared to the earlier implementation [21], Gentry et al. use the latest version of the HElib library [35]. Two variations of the implementation are reported: one with bootstrapping and one without bootstrapping.Chen Y. et al. [27] propose the integer arithmetic over ciphertext and homomorphic data aggregation by using a BGV [20] style scheme. The scheme uses the HElib library [35] to implement homomorphic evaluation for addition, subtraction, multiplication, and division of unsigned integrins. However, the scheme report time overhead of integer arithmetic over ciphertext without bootstrapping and modulus switching (somewhat homomorphic encryption). The length of integer ciphertext only sets 2, 3, 4 bits and sets 128 security level to guarantee right result. The scheme does not optimise the operations of integer arithmetic over ciphertext with bootstrapping and modulus switching.Gai K. et al. [28] propose the blend arithmetic operations on tensor-based FHE over real numbers and propose a novel tensor-based FHE solution [29]. The scheme uses tensor laws to carry the computations of blend arithmetic operations over real numbers. However, blend arithmetic operations only include addition and multiplication. The scheme does not implement blend arithmetic operations with the division.


## 3. Homomorphic Evaluation of the Integer Arithmetic Operations

Integer addition, subtraction, multiplication, and division are operated by complement addition and shift. One bit full-adder uses XOR (⨁) gate to get sum and uses AND (∧) gate to get carry. Below we will explain our notation. The integer arithmetic operations will take A=an-1⋯a0, B=bn-1⋯b0 and A∗=an-1∗⋯a0∗, B∗=bn-1∗⋯b0∗ as inputs. A and B are the complements. A∗ and B∗ are two’s complement of A and B. However, in complement operation, A is original code, A∗ is the complement of the A. The A=an-1,…,a0 represents ciphertext vector of A. Let ai=Encai,  0≤i≤n-1. The A∗=an-1∗,…,a0∗ represents ciphertext vector of A∗, ai∗=Encai∗,  0≤i≤n-1. The V represents the ciphertext vector of B, bi=Encbi,0≤i≤n-1. The B∗=bn-1∗,…,b0∗ represents ciphertext vector of B∗, bi∗=Encbi∗, 0≤i≤n-1. The A, V, A∗, and B∗ are inputs of homomorphic evaluation of the integer arithmetic operations. The n is big enough. We do not consider the overflow about integer arithmetic operations.


### 3.1. Homomorphic Evaluation of the Complement Operations

Fixed-point number use the complement to finish arithmetic operations. The rules of converting original code into complement:(i)
Positive number: a positive complement and the same original code.(ii)
Negative number: negative complement is the symbol for the numerical bit reverse and then at the bottom (LSB) plus 1.Given the original codeA, apply the XOR and AND to get complement A∗. The MSB an-1 is the signed bit of A, and the size of the remaining bits an-2⋯a0 represent the value. Given an initialised carry c-1=0, we output the A∗. The BP of complement:(2)c-1=0ci=ai∨ci-1ai∗=ai⊕anci-10≤i≤n-2We convert ci into a BP by using XOR gate and AND gate. The BP: ci=aici-1⊕ai⊕ci-1,0≤i≤n-2. Due to initialised carry c-1=0, we can convert ci into a polynomial without c-1:(3)ci=∑k=1i+1∑S=i+1∏j∈Sajmod⁡2where S=ai,⋯a0,0≤i≤n-3, S is the Hamming weight of the S. We can convert above polynomials into HP of complement by using addition and multiplication on ciphertexts. The HP of complement: (4)ci=∑k=1i+1∑S=i+1∏j∈Sajmod⁡x0ai∗=ai+an∗∙ci-1mod⁡x00≤i≤n-2where ci represents the ciphertext result of ci, and Decci=ci. Let an-1∗=an-1. The x0 is the largest odd public key in FHE. We can get ciphertext complement A∗ by using above HP.


### 3.2. Homomorphic Evaluation of the Addition and Subtraction Operations

Integer complement addition operation needs to calculate results in order from low to high. Every result bit requires an addend bit, an augend bit, and a carry bit from the low. Every carry bit requires an addend bit, an augend bit, and a carry bit from low as well. By iterating above operations, we can get the result of complement addition. We set integer complementA and B as inputs to calculate S=A+B, where S=sn-1⋯s0. The n is big enough. We do not consider the overflow of the S. The BP of addition:(5)c-1=0si=ai⊕bi⊕ci-1ci=aibi⊕ci-1ai⊕bi0≤i≤n-1We can convert above BP into HP of addition by using addition and multiplication on ciphertexts. The HP of addition:(6)c-1=Enc0si=ai+bi+ci-1mod⁡x0ci=aibi+ci-1ai+ci-1bimod⁡x00≤i≤n-1where the si is i-th ciphertext of result vector S=sn-1,⋯s0, and DecA+DecB=DecS.The addition operation can do integer subtraction operation. If we calculateA-B, we can convert B to B∗, and calculate A+B∗ by using integer addition operation. In order to get B∗, we need to use the complement operation to get B′=bn-1′⋯b0′, and then let bn-1∗=bn-1′⊕1, bi∗=bi′,0≤i≤n-2. The HP of subtraction contains two parts, including HP of complement and HP of addition.


### 3.3. Homomorphic Evaluation of the Multiplication Operations

Integer multiplication operation is based on Booth’s multiplication algorithm [36]. It is a multiplication algorithm that multiplies two signed numbers in two’s complement notation. We set multiplicand A, and multiplier B. Booth’s algorithm examines adjacent pairs of bits of the multiplier B in signed two’s complement representation, including an implicit bit below the least significant bit, b-1=0. Also, we denote by P the product accumulator. The steps of the basic algorithm for multiplication operations:(1)
We reinitialise the value ofA, A∗, and P.
(i)
A: A=A≪n, arithmetic left shift (n+1) bits. A=anan-1⋯a00⋯0.(ii)
A∗: A∗=A∗≪n, arithmetic left shift (n+1) bits. A∗=an-1∗⋯a0∗0⋯0.(iii)
P: fill the most significant n bits with 0. To the right of this, append the value of B. Fill the LSB with a 0. P=0⋯0bn-1⋯b00.(2)
Determine the two least significant (rightmost) bits ofP.
(i)
Ifb-1=b0, do nothing. Use P directly in the next step. Arithmetic right shift 1 bit.(ii)
Ifb0b-1=01, find the value of P=P+A. Ignore any overflow. Arithmetic right shift 1 bit.(iii)
Ifb0b-1=10, find the value of P=P+A∗. Ignore any overflow. Arithmetic right shift 1 bit.Repeat above second steps until they have been donen-1 times. Drop the LSB from P. According to second steps mentioned technique, we can summarise a judgment choice Boolean polynomial (JCBP):(7)JCBPmultb0,b-1,A∗,A=b0⊕b-1b0A∗+b-1AWe use Pi to represent i-th times iteration. The BP of multiplication operation:(8)Pi=Pi-1+JCBPmultb0,b-1,A∗,APi=Pi-1≫10≤i<n-1where ≫ represent the arithmetic right shift. We can convert formula (7) into HP of addition by using addition and multiplication on ciphertexts. The HP of JCBPmultb0,b-1,A∗,A:(9)JCHPmult,x0,ρ′b0,b-1,A∗,A,r,switch⊕,∧=b0+b-1b0A∗+b-1A+2rmod⁡x0The A and A∗ represent ciphertext vector of reinitialising A and A∗. The r=r0,…,rn-1 is a noise vector, and ri←Z∩-2ρ′,2ρ′,0≤i≤n-1. The HP of multiplication:(10)Pi=Pi-1+JCHPmult,x0,ρ′b0,b-1,A∗,A,r,switch⊕,∧Pi=Pi-1~≫10≤i<n-1where ~≫ represent the right shift of ciphertext vector Pn-1. When the right shift of Pn-1 by 1 ciphertext slot, the most significant component of Pn-1 is filled with a copy of the original most significant component. The final value of Pn-1 is the signed ciphertext product.


### 3.4. Homomorphic Evaluation of the Division Operation

Division is the most complex of the basic arithmetic operations. For a simple computer that operate with an adder circuit for its arithmetic operations, a variant using traditional long division, called nonrestoring division, provides a simpler and faster speed. This method only needs one decision and addition/subtraction per quotient bit, and need not restoring step after the subtraction. We set dividendA and divisor B. The B∗ is two’s complement of B. The R is the partial remainder, and the Q is quotient. The basic algorithm for binary (radix 2) nonrestoring division is as follows:(1)
Reinitialize value ofB, B∗, R, and Q.
(i)
B: B=B≫n, do arithmetic left shift n bits. B=bn-1⋯b00⋯0.(ii)
B∗: B∗=B∗≫n, do arithmetic left shift n bits. B∗=bn-1∗⋯b0∗0⋯0.(iii)
R: R=A≫n, do arithmetic right shift n bits. R=r2n-1⋯r0.(iv)
Q: Q=qn-1⋯q0, fill it n bits with 0.(2)
Determine the one most significant (a signed bit) bit ofR.
(i)
Ifr2n-1=0, fill the LSB of Q with 1 digit, do logical left shift 1 bit. Find the value of R=2∗R+B∗.(ii)
Ifr2n-1=1, fill the LSB of Q with 0 digit, do logical left shift 1 bit. Find the value of R=2∗R+B.(3)
Repeat above second steps until they have been donen-1 times.(4)
Convert the quotientQ. We suppose original Q=11101010.
(i)
Start:Q=11101010.(ii)
Mask the zero term (Signed binary notation with one’s complement):Q-=00010101.(iii)
SubtractQ=Q-Q-: Q=11010101.(5)
The actual remainder isR=R≫n. Final result of quotient is always odd, and the remainder R is in the range -B<R<B. To convert to a positive remainder, do a single restoring step after Q is converted from a nonstandard form to standard form. If R<0, find the value of Q=Q-1 and R=R+B.According to the second step mentioned technique, we can summarise a judgment choice Boolean polynomial (JCBP):(11)JCBPdivr2n-1,B,B∗=r2n-1B+r2n-1⊕1B∗We use Ri to represent i-th times iteration. The BP of division operation:(12)Ri=2Ri-1+JCBPdivr2n-1,B,B∗0≤i<n-1qn-1-i=ri,2n-1⊕10≤i<n-1Q=Q-Q-Rn-1=Rn-1≫nwhere ri,2n-1 represent the MSB of Ri. Finally, doing the fifth step corrects Q and Rn-1. We can convert above BP into HP of addition by using addition and multiplication on ciphertexts. The HP of JCBPdivr2n-1,B,B∗:(13)JCBPdiv,,x0,ρ′r2n-1,B∗,V,r,switch⊕,∧=r2n-1V+r2n-1+Enc1V+2rmod⁡x0where V and B∗ represent ciphertext vector of reinitialising B and B∗, respectively. The HP of division:(14)Ri=2Ri-1+JCBPdiv,,x0,ρ′r2n-1,B∗,V,r,switch⊕,∧0≤i<n-1qn-1-i=ri,2n-1+Enc1mod⁡x00≤i<n-1Q=Q-Q̿Rn-1=Rn-1~≫nwhere Ri=ri,2n-1,⋯ri,0 represents ciphertext vector of Ri and Q=qn-1⋯q0 represents ciphertext vector of Q. Q̿ represent qi=qi+Enc1mod⁡x0, 0≤i<n. Finally, we need to correct Q and Rn-1 by the following operations:(15)Q=rn-1,n-1Q-Enc1mod⁡x0R=rn-1,n-1Rn-1+Vmod⁡x0The final value of Q and R is the result of HP of division.


## 3.1. Homomorphic Evaluation of the Complement Operations

Fixed-point number use the complement to finish arithmetic operations. The rules of converting original code into complement:(i)
Positive number: a positive complement and the same original code.(ii)
Negative number: negative complement is the symbol for the numerical bit reverse and then at the bottom (LSB) plus 1.Given the original codeA, apply the XOR and AND to get complement A∗. The MSB an-1 is the signed bit of A, and the size of the remaining bits an-2⋯a0 represent the value. Given an initialised carry c-1=0, we output the A∗. The BP of complement:(2)c-1=0ci=ai∨ci-1ai∗=ai⊕anci-10≤i≤n-2We convert ci into a BP by using XOR gate and AND gate. The BP: ci=aici-1⊕ai⊕ci-1,0≤i≤n-2. Due to initialised carry c-1=0, we can convert ci into a polynomial without c-1:(3)ci=∑k=1i+1∑S=i+1∏j∈Sajmod⁡2where S=ai,⋯a0,0≤i≤n-3, S is the Hamming weight of the S. We can convert above polynomials into HP of complement by using addition and multiplication on ciphertexts. The HP of complement: (4)ci=∑k=1i+1∑S=i+1∏j∈Sajmod⁡x0ai∗=ai+an∗∙ci-1mod⁡x00≤i≤n-2where ci represents the ciphertext result of ci, and Decci=ci. Let an-1∗=an-1. The x0 is the largest odd public key in FHE. We can get ciphertext complement A∗ by using above HP.


## 3.2. Homomorphic Evaluation of the Addition and Subtraction Operations

Integer complement addition operation needs to calculate results in order from low to high. Every result bit requires an addend bit, an augend bit, and a carry bit from the low. Every carry bit requires an addend bit, an augend bit, and a carry bit from low as well. By iterating above operations, we can get the result of complement addition. We set integer complementA and B as inputs to calculate S=A+B, where S=sn-1⋯s0. The n is big enough. We do not consider the overflow of the S. The BP of addition:(5)c-1=0si=ai⊕bi⊕ci-1ci=aibi⊕ci-1ai⊕bi0≤i≤n-1We can convert above BP into HP of addition by using addition and multiplication on ciphertexts. The HP of addition:(6)c-1=Enc0si=ai+bi+ci-1mod⁡x0ci=aibi+ci-1ai+ci-1bimod⁡x00≤i≤n-1where the si is i-th ciphertext of result vector S=sn-1,⋯s0, and DecA+DecB=DecS.The addition operation can do integer subtraction operation. If we calculateA-B, we can convert B to B∗, and calculate A+B∗ by using integer addition operation. In order to get B∗, we need to use the complement operation to get B′=bn-1′⋯b0′, and then let bn-1∗=bn-1′⊕1, bi∗=bi′,0≤i≤n-2. The HP of subtraction contains two parts, including HP of complement and HP of addition.


## 3.3. Homomorphic Evaluation of the Multiplication Operations

Integer multiplication operation is based on Booth’s multiplication algorithm [36]. It is a multiplication algorithm that multiplies two signed numbers in two’s complement notation. We set multiplicand A, and multiplier B. Booth’s algorithm examines adjacent pairs of bits of the multiplier B in signed two’s complement representation, including an implicit bit below the least significant bit, b-1=0. Also, we denote by P the product accumulator. The steps of the basic algorithm for multiplication operations:(1)
We reinitialise the value ofA, A∗, and P.
(i)
A: A=A≪n, arithmetic left shift (n+1) bits. A=anan-1⋯a00⋯0.(ii)
A∗: A∗=A∗≪n, arithmetic left shift (n+1) bits. A∗=an-1∗⋯a0∗0⋯0.(iii)
P: fill the most significant n bits with 0. To the right of this, append the value of B. Fill the LSB with a 0. P=0⋯0bn-1⋯b00.(2)
Determine the two least significant (rightmost) bits ofP.
(i)
Ifb-1=b0, do nothing. Use P directly in the next step. Arithmetic right shift 1 bit.(ii)
Ifb0b-1=01, find the value of P=P+A. Ignore any overflow. Arithmetic right shift 1 bit.(iii)
Ifb0b-1=10, find the value of P=P+A∗. Ignore any overflow. Arithmetic right shift 1 bit.Repeat above second steps until they have been donen-1 times. Drop the LSB from P. According to second steps mentioned technique, we can summarise a judgment choice Boolean polynomial (JCBP):(7)JCBPmultb0,b-1,A∗,A=b0⊕b-1b0A∗+b-1AWe use Pi to represent i-th times iteration. The BP of multiplication operation:(8)Pi=Pi-1+JCBPmultb0,b-1,A∗,APi=Pi-1≫10≤i<n-1where ≫ represent the arithmetic right shift. We can convert formula (7) into HP of addition by using addition and multiplication on ciphertexts. The HP of JCBPmultb0,b-1,A∗,A:(9)JCHPmult,x0,ρ′b0,b-1,A∗,A,r,switch⊕,∧=b0+b-1b0A∗+b-1A+2rmod⁡x0The A and A∗ represent ciphertext vector of reinitialising A and A∗. The r=r0,…,rn-1 is a noise vector, and ri←Z∩-2ρ′,2ρ′,0≤i≤n-1. The HP of multiplication:(10)Pi=Pi-1+JCHPmult,x0,ρ′b0,b-1,A∗,A,r,switch⊕,∧Pi=Pi-1~≫10≤i<n-1where ~≫ represent the right shift of ciphertext vector Pn-1. When the right shift of Pn-1 by 1 ciphertext slot, the most significant component of Pn-1 is filled with a copy of the original most significant component. The final value of Pn-1 is the signed ciphertext product.


## 3.4. Homomorphic Evaluation of the Division Operation

Division is the most complex of the basic arithmetic operations. For a simple computer that operate with an adder circuit for its arithmetic operations, a variant using traditional long division, called nonrestoring division, provides a simpler and faster speed. This method only needs one decision and addition/subtraction per quotient bit, and need not restoring step after the subtraction. We set dividendA and divisor B. The B∗ is two’s complement of B. The R is the partial remainder, and the Q is quotient. The basic algorithm for binary (radix 2) nonrestoring division is as follows:(1)
Reinitialize value ofB, B∗, R, and Q.
(i)
B: B=B≫n, do arithmetic left shift n bits. B=bn-1⋯b00⋯0.(ii)
B∗: B∗=B∗≫n, do arithmetic left shift n bits. B∗=bn-1∗⋯b0∗0⋯0.(iii)
R: R=A≫n, do arithmetic right shift n bits. R=r2n-1⋯r0.(iv)
Q: Q=qn-1⋯q0, fill it n bits with 0.(2)
Determine the one most significant (a signed bit) bit ofR.
(i)
Ifr2n-1=0, fill the LSB of Q with 1 digit, do logical left shift 1 bit. Find the value of R=2∗R+B∗.(ii)
Ifr2n-1=1, fill the LSB of Q with 0 digit, do logical left shift 1 bit. Find the value of R=2∗R+B.(3)
Repeat above second steps until they have been donen-1 times.(4)
Convert the quotientQ. We suppose original Q=11101010.
(i)
Start:Q=11101010.(ii)
Mask the zero term (Signed binary notation with one’s complement):Q-=00010101.(iii)
SubtractQ=Q-Q-: Q=11010101.(5)
The actual remainder isR=R≫n. Final result of quotient is always odd, and the remainder R is in the range -B<R<B. To convert to a positive remainder, do a single restoring step after Q is converted from a nonstandard form to standard form. If R<0, find the value of Q=Q-1 and R=R+B.According to the second step mentioned technique, we can summarise a judgment choice Boolean polynomial (JCBP):(11)JCBPdivr2n-1,B,B∗=r2n-1B+r2n-1⊕1B∗We use Ri to represent i-th times iteration. The BP of division operation:(12)Ri=2Ri-1+JCBPdivr2n-1,B,B∗0≤i<n-1qn-1-i=ri,2n-1⊕10≤i<n-1Q=Q-Q-Rn-1=Rn-1≫nwhere ri,2n-1 represent the MSB of Ri. Finally, doing the fifth step corrects Q and Rn-1. We can convert above BP into HP of addition by using addition and multiplication on ciphertexts. The HP of JCBPdivr2n-1,B,B∗:(13)JCBPdiv,,x0,ρ′r2n-1,B∗,V,r,switch⊕,∧=r2n-1V+r2n-1+Enc1V+2rmod⁡x0where V and B∗ represent ciphertext vector of reinitialising B and B∗, respectively. The HP of division:(14)Ri=2Ri-1+JCBPdiv,,x0,ρ′r2n-1,B∗,V,r,switch⊕,∧0≤i<n-1qn-1-i=ri,2n-1+Enc1mod⁡x00≤i<n-1Q=Q-Q̿Rn-1=Rn-1~≫nwhere Ri=ri,2n-1,⋯ri,0 represents ciphertext vector of Ri and Q=qn-1⋯q0 represents ciphertext vector of Q. Q̿ represent qi=qi+Enc1mod⁡x0, 0≤i<n. Finally, we need to correct Q and Rn-1 by the following operations:(15)Q=rn-1,n-1Q-Enc1mod⁡x0R=rn-1,n-1Rn-1+Vmod⁡x0The final value of Q and R is the result of HP of division.


## 4. Noise Analysis and Optimization

In Section3, we describe the homomorphic evaluation of the integer arithmetic operations including complement, addition, subtraction, multiplication, and division. In this section, we will analyse the noise ceiling and optimisation for our scheme. Under the DGHV scheme, the noise ceiling increases exponentially with the multiplicative degree. When ciphertexts have noise at most 2η-2<p/2, the ciphertexts cannot be decrypted correctly. Therefore, we need bootstrapping to control noise of ciphertexts, but using bootstrapping to refresh ciphertext will reduce the efficiency of DGHV. We will show the noise ceiling about the homomorphic evaluation of the integer arithmetic operations in this section. Moreover, we will describe an optimisation for the process of integer arithmetic operations to reduce time overhead in FHE with bootstrapping.


### 4.1. Noise Analysis of Our Scheme

According to Section3, we show the noise ceiling and items of homomorphic evaluation of the n bits signed integer arithmetic operations. We denote by HE-IAO the homomorphic evaluation of the integer arithmetic operations and use HE-com, HE-add, HE-sub, HE-mul, HE-div to represent five operations of HE-IAO. The details are shown in Table 2.Table 2
The degree ceiling and items of homomorphic evaluation of then bits signed integer arithmetic operations. Above showing the HP of integer arithmetic operations n-th iterations ciphertext results’ degree and term.
HE-IAO degree term HE-com n - 1 2 n - 2 HE-add n 2 n - 1 + 1 HE-sub n 2 n - 1 + 1 HE-mul ψ ∙ 2 2 n - 4 - HE-div φ ∙ 2 2 n - 4 -Proof.
According to homomorphic evaluation of the complement operations formula (3),(16)ci=∑k=1i+1∑S=i+1∏j∈Sajmod⁡2,0≤i≤n-2∑S=i∏j∈Saj has n-2i+1 terms, and degree amounts to i+1. According to binomial theorem, the term of formula (3) can be represented as 1+xn-2-1=∑i=0n-2n-2ixi-1, when x=1. Therefore, the polynomial ci of term is up to 2n-2-1, and degree amounts to n-2. Because of ai∗=ai⊕anci-10≤i≤n-1, ai∗ of term amounts to 2n-2, and degree amounts to n-1.
According to homomorphic evaluation of the addition operations formula (5), the degree of carry formula ci=aibi⊕ci-1ai⊕bi is higher 1 than ci-1, and the term of ci is higher 2∗termci-1+1 than ci-1, where termci-1 represents the term of ci-1. The degree of c0=a0b0 amounts to 2, and the term of c0=a0b0 amounts to 1. The degree of cn-2 amounts to n, and terms of cn-2 amount to 2n-1-1. The MSB of Ssn-1=an-1⊕bn-1⊕cn-2 where the degree of sn-1 amounts to n, and the term of sn-1 amounts to 2n-1+1. If we do not consider complement operation, subtraction and addition have the same process. Therefore, the degree and term are the same as the addition. Multiplication and division require iteration n-1 times addition and shift. The processes of multiplication and division are particularly complicated, we can’t find the formula to express the degree. According to our calculations, the degree of multiplication and division is close to the 2 to the power of 2n-4. Therefore, the degree of multiplication is not more than ψ∙22n-4, and the degree of division is not more than φ∙22n-4. The term of multiplication and division is too high, and the degree has made noise more than the limitation of correct decryption.We can conclude (see Table2) the degree of homomorphic evaluation of addition and subtraction is O~n, and the depth of the homomorphic evaluation of multiplication and division is O~ψ∙22n-4. We use items that represent the l1 norm of HP (the coefficient vector of HP). The noise ceiling of homomorphic evaluation of the n bits integer arithmetic operations can be calculated by the following polynomial:(17)Noise=ρ′log⁡d+log⁡f→where d represents the degree of HP and log⁡d represents multiplication level of HP. f→ is the l1 norm of HP. ρ′ is the noise of length in every ciphertext. The noise ceiling of homomorphic evaluation of the n bits integer arithmetic operations is shown in Table 3.Table 3
The noise ceiling of homomorphic evaluation of then bits signed integer arithmetic operations. The base of the log is 2.
HE-IAO noise ceiling HE-com ρ ′ log ⁡ ( n - 1 ) + log ⁡ 2 n - 3 HE-add ρ ′ log ⁡ ( n ) + log ⁡ 2 n - 1 + 1 HE-sub ρ ′ log ⁡ ( n ) + log ⁡ 2 n - 1 + 1 HE-mul ρ ′ log ⁡ ψ ∙ 2 2 n - 4 + - HE-div ρ ′ log ⁡ φ ∙ 2 2 n - 4 + -We can conclude (see Table3) the noise of homomorphic evaluation of the n bits signed integer arithmetic operations. The noise increases very rapidly. In the homomorphic evaluation of the complement, addition, and subtraction, noise increases up to O~ρ′n. In the homomorphic evaluation of the multiplication and division, noise is more than O~ρ′ψ∙22n-4.


### 4.2. Optimization of Our Scheme

From the analysis of noise ceiling in Section4.1, we need to control the noise increases by using ciphertext refresh, or modulus-switching technique in each multiplication level of homomorphic evaluation of the n bits signed integer arithmetic operations. However, the ciphertext refresh or modulus-switching technique will reduce our scheme efficiency. Therefore, we will describe an optimisation for our scheme in this section. The optimisation can reduce the number of ciphertext refresh and improve efficiency.Because the integer arithmetic operation is completed based on the addition operation, we optimise the homomorphic evaluation of the integer addition. We divide the ciphertext vector of integer encryption into subvectors of lengthL. The homomorphic evaluation of arithmetic operations between the subvectors in the same position do not need ciphertext refresh, and the subvectors in different positions need to refresh ciphertext-carry once. Therefore, the optimised scheme need not ciphertext refresh in each multiplication level and reduces the number of ciphertext refresh. We take addition operations of the product accumulator to explain our optimisation. In the homomorphic evaluation of the multiplication operations, the product accumulator Pi is as formula (9). The formula (9) is a polynomial of degree three, and Pi is a ciphertext vector of degree one. We denote by F vector of JCHPmult,x0,ρ′. We divide the ciphertext vector of Pi and F into ciphertext subvectors of length L. The ciphertext operations of subvectors of the same position are the same as homomorphic evaluation of the addition operations (without ciphertext refresh). The ciphertext operations of subvectors of different position need to refresh ciphertext-carry once (see Figure 2).Figure 2
The optimised addition operations; each colour block represents same position subvectors ofPi and F, the length of each colour block is L, “r shift” represents ciphertext vector right shift one position, “recrypt” represents ciphertext refresh. This figure shows the degree change of each component of Pi and F.The subvectors ofPi and F generate ciphertext-result block and ciphertext-carry. In every ciphertext-result block, the maximum degree is 3L-2 (leftmost), and the minimum degree is 3 (rightmost). The ciphertext-carry degree is 3L+1 in each subvector of the different position. Each ciphertext of ciphertext-result block and ciphertext-carry can use ciphertext refresh (recrypt) to reduce degree up to one. The number of ciphertext refresh of once product accumulator Pi+F for ciphertext-carry:(i)
Ifn is divisible by L, it will generate n/L-1 ciphertext-carry, and the number of ciphertext refresh is cnt=n/L-1 times.(ii)
Ifn is inalienable by L, it will generate n/L ciphertext-carry, and the number of ciphertext refresh is cnt=n/L times.Homomorphic evaluation of the multiplication operations needsn-1 times product accumulator, and whole operations need n-1∙cnt times ciphertext refresh for ciphertext-carry, and n-1∙n times ciphertext refresh for ciphertext-result block. Total times of ciphertext refresh for homomorphic evaluation of the multiplication operations:(18)CNT=n-1∙n+n-1∙cntIn the original homomorphic evaluation of the multiplication operations, every multiplication level needs once ciphertext refresh. Whole operations needn-13n-3+nn-1+2n-3 times ciphertext refresh. We apply above optimisation to the homomorphic evaluation of the complement, addition, subtraction, multiplication, and division operations, and set n=16, L=1,2,3,4. We show the number of ciphertext refresh of the original scheme (L=0) and an optimised scheme (L=1,2,3,4) as Table 4.Table 4
The number of ciphertext refresh of homomorphic evaluation of the integer arithmetic operations.
HE-IAO L = 0 L = 1 L = 2 L = 3 L = 4 HE-com 29 29 22 20 18 HE-add 45 31 23 21 19 HE-sub 74 60 45 41 37 HE-mul 944 494 367 335 303 HE-div 1095 585 437 397 359In order to implement our optimisation, we need to adjust the parameters of homomorphic encryption and make FHE support thelog⁡3L+1 multiplication level additional, except for the 15-multiplication level required by bootstrapping. Therefore, we reset the length of the private key: η≥ρ′∙Θλlog2⁡λ+ρ′∙2log⁡3L+1+log⁡2L-1+1. We set security parameter λ=52, the length of noise ρ′=24, and θ=15, Θ=500. Parameters are set as Table 5.Table 5
Concrete parameters, based on the “small” parameters of CMNT scheme, and reset the length of public keyη and γ. Fixed λ, ρ′ and the number of public keys τ, only changed η and γ according to L.
parameters λ ρ ′ η γ τ L = 0 52 24 1632 2.0 ∙ 10 6 1000 L = 1 52 24 1728 2.5 ∙ 10 6 1000 L = 2 52 24 1801 3.0 ∙ 10 6 1000 L = 3 52 24 1874 3.5 ∙ 10 6 1000 L = 4 52 24 1993 4.2 ∙ 10 6 1000


## 4.1. Noise Analysis of Our Scheme

According to Section3, we show the noise ceiling and items of homomorphic evaluation of the n bits signed integer arithmetic operations. We denote by HE-IAO the homomorphic evaluation of the integer arithmetic operations and use HE-com, HE-add, HE-sub, HE-mul, HE-div to represent five operations of HE-IAO. The details are shown in Table 2.Table 2
The degree ceiling and items of homomorphic evaluation of then bits signed integer arithmetic operations. Above showing the HP of integer arithmetic operations n-th iterations ciphertext results’ degree and term.
HE-IAO degree term HE-com n - 1 2 n - 2 HE-add n 2 n - 1 + 1 HE-sub n 2 n - 1 + 1 HE-mul ψ ∙ 2 2 n - 4 - HE-div φ ∙ 2 2 n - 4 -Proof.
According to homomorphic evaluation of the complement operations formula (3),(16)ci=∑k=1i+1∑S=i+1∏j∈Sajmod⁡2,0≤i≤n-2∑S=i∏j∈Saj has n-2i+1 terms, and degree amounts to i+1. According to binomial theorem, the term of formula (3) can be represented as 1+xn-2-1=∑i=0n-2n-2ixi-1, when x=1. Therefore, the polynomial ci of term is up to 2n-2-1, and degree amounts to n-2. Because of ai∗=ai⊕anci-10≤i≤n-1, ai∗ of term amounts to 2n-2, and degree amounts to n-1.
According to homomorphic evaluation of the addition operations formula (5), the degree of carry formula ci=aibi⊕ci-1ai⊕bi is higher 1 than ci-1, and the term of ci is higher 2∗termci-1+1 than ci-1, where termci-1 represents the term of ci-1. The degree of c0=a0b0 amounts to 2, and the term of c0=a0b0 amounts to 1. The degree of cn-2 amounts to n, and terms of cn-2 amount to 2n-1-1. The MSB of Ssn-1=an-1⊕bn-1⊕cn-2 where the degree of sn-1 amounts to n, and the term of sn-1 amounts to 2n-1+1. If we do not consider complement operation, subtraction and addition have the same process. Therefore, the degree and term are the same as the addition. Multiplication and division require iteration n-1 times addition and shift. The processes of multiplication and division are particularly complicated, we can’t find the formula to express the degree. According to our calculations, the degree of multiplication and division is close to the 2 to the power of 2n-4. Therefore, the degree of multiplication is not more than ψ∙22n-4, and the degree of division is not more than φ∙22n-4. The term of multiplication and division is too high, and the degree has made noise more than the limitation of correct decryption.We can conclude (see Table2) the degree of homomorphic evaluation of addition and subtraction is O~n, and the depth of the homomorphic evaluation of multiplication and division is O~ψ∙22n-4. We use items that represent the l1 norm of HP (the coefficient vector of HP). The noise ceiling of homomorphic evaluation of the n bits integer arithmetic operations can be calculated by the following polynomial:(17)Noise=ρ′log⁡d+log⁡f→where d represents the degree of HP and log⁡d represents multiplication level of HP. f→ is the l1 norm of HP. ρ′ is the noise of length in every ciphertext. The noise ceiling of homomorphic evaluation of the n bits integer arithmetic operations is shown in Table 3.Table 3
The noise ceiling of homomorphic evaluation of then bits signed integer arithmetic operations. The base of the log is 2.
HE-IAO noise ceiling HE-com ρ ′ log ⁡ ( n - 1 ) + log ⁡ 2 n - 3 HE-add ρ ′ log ⁡ ( n ) + log ⁡ 2 n - 1 + 1 HE-sub ρ ′ log ⁡ ( n ) + log ⁡ 2 n - 1 + 1 HE-mul ρ ′ log ⁡ ψ ∙ 2 2 n - 4 + - HE-div ρ ′ log ⁡ φ ∙ 2 2 n - 4 + -We can conclude (see Table3) the noise of homomorphic evaluation of the n bits signed integer arithmetic operations. The noise increases very rapidly. In the homomorphic evaluation of the complement, addition, and subtraction, noise increases up to O~ρ′n. In the homomorphic evaluation of the multiplication and division, noise is more than O~ρ′ψ∙22n-4.


## 4.2. Optimization of Our Scheme

From the analysis of noise ceiling in Section4.1, we need to control the noise increases by using ciphertext refresh, or modulus-switching technique in each multiplication level of homomorphic evaluation of the n bits signed integer arithmetic operations. However, the ciphertext refresh or modulus-switching technique will reduce our scheme efficiency. Therefore, we will describe an optimisation for our scheme in this section. The optimisation can reduce the number of ciphertext refresh and improve efficiency.Because the integer arithmetic operation is completed based on the addition operation, we optimise the homomorphic evaluation of the integer addition. We divide the ciphertext vector of integer encryption into subvectors of lengthL. The homomorphic evaluation of arithmetic operations between the subvectors in the same position do not need ciphertext refresh, and the subvectors in different positions need to refresh ciphertext-carry once. Therefore, the optimised scheme need not ciphertext refresh in each multiplication level and reduces the number of ciphertext refresh. We take addition operations of the product accumulator to explain our optimisation. In the homomorphic evaluation of the multiplication operations, the product accumulator Pi is as formula (9). The formula (9) is a polynomial of degree three, and Pi is a ciphertext vector of degree one. We denote by F vector of JCHPmult,x0,ρ′. We divide the ciphertext vector of Pi and F into ciphertext subvectors of length L. The ciphertext operations of subvectors of the same position are the same as homomorphic evaluation of the addition operations (without ciphertext refresh). The ciphertext operations of subvectors of different position need to refresh ciphertext-carry once (see Figure 2).Figure 2
The optimised addition operations; each colour block represents same position subvectors ofPi and F, the length of each colour block is L, “r shift” represents ciphertext vector right shift one position, “recrypt” represents ciphertext refresh. This figure shows the degree change of each component of Pi and F.The subvectors ofPi and F generate ciphertext-result block and ciphertext-carry. In every ciphertext-result block, the maximum degree is 3L-2 (leftmost), and the minimum degree is 3 (rightmost). The ciphertext-carry degree is 3L+1 in each subvector of the different position. Each ciphertext of ciphertext-result block and ciphertext-carry can use ciphertext refresh (recrypt) to reduce degree up to one. The number of ciphertext refresh of once product accumulator Pi+F for ciphertext-carry:(i)
Ifn is divisible by L, it will generate n/L-1 ciphertext-carry, and the number of ciphertext refresh is cnt=n/L-1 times.(ii)
Ifn is inalienable by L, it will generate n/L ciphertext-carry, and the number of ciphertext refresh is cnt=n/L times.Homomorphic evaluation of the multiplication operations needsn-1 times product accumulator, and whole operations need n-1∙cnt times ciphertext refresh for ciphertext-carry, and n-1∙n times ciphertext refresh for ciphertext-result block. Total times of ciphertext refresh for homomorphic evaluation of the multiplication operations:(18)CNT=n-1∙n+n-1∙cntIn the original homomorphic evaluation of the multiplication operations, every multiplication level needs once ciphertext refresh. Whole operations needn-13n-3+nn-1+2n-3 times ciphertext refresh. We apply above optimisation to the homomorphic evaluation of the complement, addition, subtraction, multiplication, and division operations, and set n=16, L=1,2,3,4. We show the number of ciphertext refresh of the original scheme (L=0) and an optimised scheme (L=1,2,3,4) as Table 4.Table 4
The number of ciphertext refresh of homomorphic evaluation of the integer arithmetic operations.
HE-IAO L = 0 L = 1 L = 2 L = 3 L = 4 HE-com 29 29 22 20 18 HE-add 45 31 23 21 19 HE-sub 74 60 45 41 37 HE-mul 944 494 367 335 303 HE-div 1095 585 437 397 359In order to implement our optimisation, we need to adjust the parameters of homomorphic encryption and make FHE support thelog⁡3L+1 multiplication level additional, except for the 15-multiplication level required by bootstrapping. Therefore, we reset the length of the private key: η≥ρ′∙Θλlog2⁡λ+ρ′∙2log⁡3L+1+log⁡2L-1+1. We set security parameter λ=52, the length of noise ρ′=24, and θ=15, Θ=500. Parameters are set as Table 5.Table 5
Concrete parameters, based on the “small” parameters of CMNT scheme, and reset the length of public keyη and γ. Fixed λ, ρ′ and the number of public keys τ, only changed η and γ according to L.
parameters λ ρ ′ η γ τ L = 0 52 24 1632 2.0 ∙ 10 6 1000 L = 1 52 24 1728 2.5 ∙ 10 6 1000 L = 2 52 24 1801 3.0 ∙ 10 6 1000 L = 3 52 24 1874 3.5 ∙ 10 6 1000 L = 4 52 24 1993 4.2 ∙ 10 6 1000


## 5. Experimental Result

Our optimisations described in our scheme were incorporated in our code, which is built on top of GnuMP. We tested our implementation on a desktop computer with Intel Core i5-3470 running at 3.2 GHz, on which we run an Ubuntu 18.04 with 8 GB of RAM and with the gcc compiler version 6.2. We regard this desktop computer as an edge data centre to test our scheme efficiency in edge computing. We choose the ciphertext vector of 16 and 8 bits signed integer as input. Due to our optimisations for the FHE with bootstrapping, we test our original scheme (L=0) and optimised scheme (L=1,2,3,4) in DGHV and CMNT scheme (see Figures 3(a), 3(b), 3(c), 3(d), and 3(e)). In CNT scheme, we only use modulus-switching technique to control noise. So, we test the original scheme in CNT scheme (see Figures 4(a) and 4(b)). In our figures, “HE-com (CMNT 16)” represent the homomorphic evaluation of the complement operations and calculate the ciphertext vector of 16 bits signed integer in the CMNT scheme. “HE-com (DGHV 8)” represent the homomorphic evaluation of the complement operations and calculate the ciphertext vector of 8 bits signed integer in DGHV scheme. The explanation of other legends is the same as above. We show the following experimental results based on the Section 4.2 parameter settings.Figure 3
Tested (a) HE-com, (b) HE-add, (c) HE-sub, (d) HE-mul, (e) HE-div CPU time.
(a) (b) (c) (d) (e)Figure 4
(a) Tested HE-IAO CPU time of ciphertext vector of length 8. (b) Tested HE-IAO CPU time of ciphertext vector of length 16.
(a) (b)We can conclude (see Figures3(b), 3(c), 3(d), and 3(e)) that L=2 is best parameters setting for homomorphic evaluation of the addition, subtraction, multiplication, and division. However, the time overhead of homomorphic evaluation of the complement operations is monotone increasing at L (see Figure 3(a)). When L=0, the time overhead is the absolute minimum. When L=0 and L=1, the number of ciphertext refresh is the same. Also, the degree of complement operations is 2n-3. When n=16, the degree is 29 in L=0. It is the same as L=1. The reduced time overhead of the optimised complement operations cannot offset the computation cost caused by the increase in ciphertext length. However, the relative minimum value appears at L=2 (see Figures 3(a), 3(b), 3(c), 3(d), and 3(e)). It shows that our optimisation is useful and can reduce the time overhead for our scheme, except homomorphic evaluation of the complement operations. Namely, we divide the ciphertext vector of integer encryption into subvectors of length 2 and make DGHV and CMNT scheme to support the log⁡3∙2+1≈3 multiplication level additional. The optimisation of our scheme can achieve the best results. In the number of ciphertext refreshes, the optimised scheme is reduced by 2/3 compared to the original scheme over DGHV and CMNT, and the homomorphic evaluation time overhead of integer arithmetic operation is reduced by 1/3.The DGHV and CMNT schemes are different with CNT scheme in noise management technology. The DGHV and CMNT schemes use bootstrapping to control noise, and the CNT scheme uses the modulus switching technology to control noise. Our optimization is used for homomorphic evaluation of integer arithmetic operations which are implemented by DGHV and CMNT schemes (with bootstrapping), rather than by CNT scheme (modulus-switching). Therefore, we just compare the beat result (L=2) of our scheme based on DGHV and CMNT schemes with CNT scheme (L=0). We can draw a conclusion (see Figures 4(a) and 4(b)) that the time overhead of our optimised scheme based on DGHV and CMNT schemes (bootstrapping) with L=2 close to the time overhead of basing on CNT (modulus-switching) with L=0. It also shows that our optimisation is effective. And our optimized scheme can be applied to mobile edge computing to solve privacy data computing problems in ciphertext.


## 6. Conclusion

We implement the homomorphic evaluation scheme of integer arithmetic operations under DGHV and its variants in edge computing. We use the features of homomorphic encryption to prevent sensitive data from being stolen in edge computing. At the same time, we can also calculate ciphertext data in edge computing and improve the QoS of edge computing. Through scheme design, noise analysis, scheme optimisation, and experimental comparison, the different performance of homomorphic evaluation of the integer arithmetic operations is obtained under different FHE schemes. Although we optimise our scheme in Section4.2, the time overhead of our scheme is still high. The primary open problem is to improve the efficiency of the FHE scheme. This requires us to work together to find a natural FHE scheme or to continue to optimise the FHE architecture to achieve more efficient noise management techniques.



---

*Source: 8142102-2018-11-15.xml*