# Privacy-Preserving Oriented Floating-Point Number Fully Homomorphic Encryption Scheme

Authors: Shuangjie Bai; Geng Yang; Jingqi Shi; Guoxiu Liu; Zhaoe Min
Journal: Security and Communication Networks
 (2018)

---

## Abstract

The issue of the privacy-preserving of information has become more prominent, especially regarding the privacy-preserving problem in a cloud environment. Homomorphic encryption can be operated directly on the ciphertext; this encryption provides a new method for privacy-preserving. However, we face a challenge in understanding how to construct a practical fully homomorphic encryption on non-integer data types. This paper proposes a revised floating-point fully homomorphic encryption scheme (FFHE) that achieves the goal of floating-point numbers operation without privacy leakage to unauthorized parties. We encrypt a matrix of plaintext bits as a single ciphertext to reduce the ciphertext expansion ratio and reduce the public key size by encrypting with a quadratic form in three types of public key elements and pseudo-random number generators. Additionally, we make the FFHE scheme more applicable by generalizing the homomorphism of addition and multiplication of floating-point numbers to analytic functions using the Taylor formula. We prove that the FFHE scheme for ciphertext operation may limit an additional loss of accuracy. Specifically, the precision of the ciphertext operation’s result is similar to unencrypted floating-point number computation. Compared to other schemes, our FFHE scheme is more practical for privacy-preserving in the cloud environment with its low ciphertext expansion ratio and public key size, supporting multiple operation types and high precision.


---

## Body

## 1. Introduction

In this age of big data, the amount of data that identifies individuals is increasing. People are enjoying the convenience created by these data; at the same time, leakage of personal data has attracted more attention because these data are easily accessible to third parties, especially in a cloud environment, and because the service provider can easily access users’ plaintexts in a cloud server. Additionally, the security and privacy of personal data are threatened as we adopt cloud computing services; this threat is considered the biggest challenge in a cloud environment [1]. To avoid the data being leaked, people usually adopt an encryption algorithm such as AES to encrypt these data and store them on a cloud server. However, AES cannot support the operations over ciphertexts directly on the cloud server. When people need to use these data, they must download ciphertexts from the server and decrypt locally. Such downloads require a large consumption of resources. Only immense storage space in the cloud is used while the availability of ciphertexts is lost. Therefore, people have been seeking a scheme that can utilize the advantages of the cloud, including immense storage space and strong computing power, which can effectively protect the privacy of an individual at the same time. Homomorphic encryption is closely related to the confidentiality of data in the cloud and is the key technology to protect data privacy.Homomorphic encryption allows third parties to operate over encrypted values without being aware of the content. The idea of homomorphic encryption is as follows.Enc represents the encryption algorithm, andDec represents the decryption algorithm. For a function f taking plaintexts m0,m1,⋯,ml as inputs, there exists a function f′ taking the corresponding ciphertexts c0,c1,⋯,cl as inputs, where ci=Enc(mi),i=0,1,⋯,l, such that(1)Decf′c0,c2,⋯,cl=fm0,m1,⋯,mlAccording to the property of homomorphic encryption above, to protect a user’s privacy in a cloud environment seems to be an excellent method. We can take advantage of the strong computing power in the cloud to operate over the ciphertexts without exposing the plaintexts. There are some applications such as CryptDB [7, 8] and other encrypted databases [9, 10], which apply a homomorphic encryption scheme to protect data privacy.The present homomorphic encryption schemes have some limitations. Most practical systems apply a partially homomorphic encryption scheme (certain restricted types of computations can be done on ciphertexts), such as Paillier [11], rather than a fully homomorphic encryption scheme. The current fully homomorphic encryption scheme is inefficient. There are also many studies on improving the efficiency of fully homomorphic encryption schemes [3–5, 12, 13], but these schemes cannot be applied to a practical system. Furthermore, most current homomorphic encryption schemes only operate over the integer data type, while most data are not only integers. For example, in the e-healthcare cloud service [14], decision-making models can be used to automatically check a patient’s health status, and the parameters of the decision-making model contain real numbers. Additionally, we often need a mathematic modeling method to analyze a patient’s health data, which may utilize complex functions taking floating-point numbers as input. However, most existing homomorphic encryption schemes [2, 11, 15–18] only focus on operations on integers. Designing a homomorphic encryption scheme to achieve floating-point number calculation without compromising the privacy of the outsourced data is a challenging issue.In this paper, we propose a floating-point fully homomorphic encryption scheme (FFHE) to overcome the above problems. The scheme is based on our proposed revised somewhat homomorphic encryption scheme (RSHE), which is more effective than [3–5]. Although FFHE is not appropriate for practical application to a system, we have improved the efficiency. By using five integers to express a floating-point number [19], we convert the operations on a floating-point number to an integer. FFHE can support addition and multiplication operations on floating-point numbers. We then prove that the operation on ciphertexts of a floating-point number does not increase additional precision loss. Using the Taylor series approximation calculation, our scheme can also calculate the result of analysis functions, such as exponential and logistic functions taking floating-point numbers as input without exposing plaintexts.Our FFHE is more efficient than previous works. It is based on Gentry’s original blueprint and supports a more complex function with more diversified input data types. The main contributions of this paper can be summarized as follows.(i) We construct a more efficient and somewhat homomorphic encryption scheme with a smaller public key size and a secret key size based on [2], which is more effective than Coron’s scheme [3–5].(ii) We follow Gentry’s blueprint and construct a floating-point fully homomorphic encryption scheme (FFHE) that can support addition and multiplication operations on floating-point numbers based on our proposed revised somewhat homomorphic encryption (RSHE). Compared to the operation of plaintexts, addition and multiplication of ciphertexts do not increase additional precision loss.(iii) FFHE can calculate the result of analysis functions taking floating-point numbers as input without exposing plaintexts, and the error of approximate calculation is negligible.The remainder of this paper is organized as follows: related work is discussed in Section2. In Section 3, we describe some preliminaries required for understanding of our proposed revised somewhat homomorphic encryption scheme and FFHE, as well as some prior knowledge about floating-point numbers. In Section 4, we review the DGHV scheme. Then, we present the revised somewhat homomorphic encryption scheme in Section 5, followed by our proposed FFHE in Section 6. In Section 7, we explain the type of operations of FFHE. Section 8 concludes this paper.


## 2. Related Work

In this section, we informally review previous homomorphic encryption schemes. In 1978, Rivest et al. proposed the idea of privacy homomorphism [20]: workers may perform implicit addition and multiplication on plaintext values while exclusively manipulating encrypted data. Homomorphic encryption has attracted significant research attention lately. There are many studies on homomorphic encryption, including a somewhat homomorphic encryption scheme (a crucial component of fully homomorphic encryption which allows many additions and a small number of multiplications on ciphertexts) and a partially homomorphic encryption scheme. For example, RSA [15] is a multiplicatively homomorphic encryption scheme, and Paillier cryptosystem [11] is an additively homomorphic encryption scheme.However, partially or somewhat homomorphic encryption schemes cannot meet the requirements of processing vast privacy data. In a 2009 breakthrough work, Gentry constructed the first encryption scheme based on ideal lattices that support both addition and multiplication on ciphertexts, i.e., a fully homomorphic encryption scheme [16], and detailed the proposed scheme in his Ph.D. thesis [17], which led to the research on fully homomorphic encryption.Based on Gentry’s research, three types of schemes were constructed.(1) Gentry’s original scheme was based on ideal lattices. The construction follows successive steps: first, construct a somewhat homomorphic scheme that supports limited addition and multiplication on ciphertexts. This step is necessary because ciphertexts contain some noise that becomes larger with successive homomorphic multiplication, and only ciphertexts whose noise size remains below a certain threshold can be decrypted correctly. Second, Gentry shows how to squash the decryption procedure so that it can be expressed as a low degree polynomial in the bits of the ciphertext and the secret key. Then, Gentry’s key idea, called bootstrapping, consists in homomorphically evaluating this decryption polynomial on encryptions of the secret key bits, resulting in a different ciphertext (refreshed ciphertext) associated with the same plaintext with possibly reduced noise. The refreshed ciphertext can then be used in subsequent homomorphic operations. By repeatedly refreshing ciphertexts after every operation, the number of homomorphic operations becomes unlimited, resulting in a fully homomorphic encryption scheme. Gentry and Halevi implemented Gentry’s scheme [21] based on algorithmic optimizations proposed by Smart et al. [12].(2) In 2012, Brakerski et al. proposed a fully homomorphic encryption scheme (BGV scheme) based on Learning with Errors (LWE) and Ring Learning with Errors (RLWE) problems [18], which was a new way of constructing a leveled fully homomorphic encryption scheme (capable of evaluating arbitrary polynomial-size circuits), without Gentry’s bootstrapping procedure. They proposed modulus-switching and key switching techniques to reduce noise and the ciphertext expansion ratio. An implementation was described with an efficient homomorphic evaluation of a full AES encryption circuit. At the same time, this branch also drew significant attention, and they proposed a revised scheme based on LWE [13, 22–25].(3) At Eurocrypt 2010, Dijk, Gentry, Halevi, and Vaikuntanathan (DGHV scheme) described a fully homomorphic encryption scheme over the integers [2]. The main appeal of the scheme (compared to Gentry’s original scheme) was its conceptual simplicity; all operations are done over the integers instead of ideal lattices. However, the public key was too large for any practical system. Because of that, Coron et al. [3–5] proposed several optimization techniques to reduce public key size. Homomorphic encryption scheme can also be applied in provable data possession [26–29].The schemes above address operation over integers, while there are few studies of fully homomorphic encryption schemes for non-integers. Real numbers are the most common numbers used in measuring. Recently, there have been papers focusing on designing a fully homomorphic encryption scheme for real numbers. Seiko, Arita, and Shota Nakasato [30] proposed a fully homomorphic encryption for point numbers based on the FV [31] scheme, which is based on the LWE problem. They construct a first homomorphic encryption scheme that supports operations for fixed-point numbers. Based on this, they constructed a fully homomorphic encryption scheme that can homomorphically compute addition and multiplication of encrypted floating-point numbers. Cheon et al. [32] proposed a floating-point homomorphic encryption scheme based on the BGV scheme [18], which was able to evaluate arbitrary polynomial-size circuits, similar to the BGV scheme. Costache [33] proposed a fixed-point arithmetic in a somewhat homomorphic encryption scheme and investigated an application in homomorphic image processing. However, these papers just identified the feasibility of constructing a homomorphic encryption scheme supporting operations over floating-point numbers. These schemes cannot secretly calculate complex functions with floating-point numbers as input. Additionally, because of the low efficiency of basic schemes over integer, their proposed schemes for non-integers also require a large key space and ciphertext space. Liu [34] realized outsourced calculation on floating-point numbers. They utilized Paillier-based cryptosystem to construct operation protocol over the ciphertexts. However, Paillier is only an additively homomorphic scheme, and they construct a multiplicatively homomorphic scheme by setting up two severs, which requires a higher security model.Low efficiency, large public key size, and ciphertext expansion ratio are the main reasons for which most fully homomorphic encryption schemes are not practical, and this problem receives the most attention. However, there are some studies on floating-point number homomorphic encryption, and the supported arithmetic types have many limitations; for example, most analytic functions such as exponential functions and logarithmic functions for floating-point numbers cannot be supported. Therefore, it is necessary to construct a fully homomorphic encryption scheme for floating-point numbers.


## 3. Preliminary

### 3.1. Notations

For a real numberz, we denote using z, z, and z rounded up, down, or to the nearest integer. For a real number z, and an integer p, we denote the reduction of z modulo p by zp with -p/2<zp<p/2, or zp with 0≤zp<p. Let x∗ be a real number. We use the notation x=fl(x∗) to represent the floating-point value of x∗ (the nearest number in the floating-point system). The most useful measures of the accuracy of x are its absolute error Eabs(x)=x-x∗ and its relative error Erel(x)=x-x∗/x∗ [19].The parameters of the somewhat homomorphic DGHV scheme are shown in Section4. Given the security parameter λ, the following parameters are used:γ  is the bit-length of the public keys.η  is the bit-length of the secret keys.ρ  is the bit-length of the first noise parameter.τ  is the number of the public keys.ρ’ is the bit-length of the secondary noise parameter.The other parameters used in our proposed schemes will be described in Sections5 and 6.


### 3.2. Floating-Point Number

The floating-point number is the formulaic representation that approximates a real number to support a trade-off between range and precision. We define the floating-point format used in this paper. A floating-point format is characterized by five integers [19]:(2)x=-1s′·s·be-kwhere s′∈{0,1} is the sign of x. b is the base or radix (b=2 in this paper). e is an integer such that emin≤e≤emax, called the exponent of the x, where emin and emax are two extremal exponents such that emin≤0≤emax. k is the precision (the number of significant digits in the significand), and s is the significand satisfying bk-1≤s≤bk-1. To determine accuracy, we define the quantity u=0.5·b1-k. It is the furthest distance relative to unity between a real number and the nearest floating-point number. According to the definition of the relative error above, we represent the relative error as x=x∗(1+ε) such that Erel(x)=ε≤u. According to different demands in a practical system, we may adjust the parameters in the floating-point format we defined above.


### 3.3. Floating-Point Error Analysis

For real numbersx1∗, x2∗, x1, x2 represent the floating-point value of x1∗, x2∗, which is the nearest number in the floating-point system. For i=1,2, xi=xi∗+Δi, where Δ1, Δ2 represent the absolute error of the real number and the floating-point number, which are subject to Δi≤0.5·be-k, xi∗≥be-1, and the relative error is as follows:(3)Erelxi=Δixi∗≤0.5·b1-kThe addition of the two real numbers can be represented asx1∗+x2∗=x1+Δ1+x2+Δ2, such that(4)Erelx1+x2=Δ1+Δ2x1∗+x2∗≤0.5·b1-kThe addition of floating-point number does not affect the relative error, and the precision is still k.The multiplication of the two real numbers can be represented as(5)x1∗·x2∗=x1+Δ1·x2+Δ2=x1·x2+x1·Δ2+x2·Δ1+Δ1·Δ2such that(6)Erelx1·x2=x1·Δ2+x2·Δ1+Δ1·Δ2x1∗·x2∗≤2·0.5·b1-kFor each multiplication, the relative error approximately doubles. Specifically, the relative error will increase with continuous multiplications [19]. The FFHE we propose below simulates the operations of plaintext in the floating-point system with a Boolean circuit. We prove the relative error of ciphertext is the same as corresponding plaintext in our FFHE.


## 3.1. Notations

For a real numberz, we denote using z, z, and z rounded up, down, or to the nearest integer. For a real number z, and an integer p, we denote the reduction of z modulo p by zp with -p/2<zp<p/2, or zp with 0≤zp<p. Let x∗ be a real number. We use the notation x=fl(x∗) to represent the floating-point value of x∗ (the nearest number in the floating-point system). The most useful measures of the accuracy of x are its absolute error Eabs(x)=x-x∗ and its relative error Erel(x)=x-x∗/x∗ [19].The parameters of the somewhat homomorphic DGHV scheme are shown in Section4. Given the security parameter λ, the following parameters are used:γ  is the bit-length of the public keys.η  is the bit-length of the secret keys.ρ  is the bit-length of the first noise parameter.τ  is the number of the public keys.ρ’ is the bit-length of the secondary noise parameter.The other parameters used in our proposed schemes will be described in Sections5 and 6.


## 3.2. Floating-Point Number

The floating-point number is the formulaic representation that approximates a real number to support a trade-off between range and precision. We define the floating-point format used in this paper. A floating-point format is characterized by five integers [19]:(2)x=-1s′·s·be-kwhere s′∈{0,1} is the sign of x. b is the base or radix (b=2 in this paper). e is an integer such that emin≤e≤emax, called the exponent of the x, where emin and emax are two extremal exponents such that emin≤0≤emax. k is the precision (the number of significant digits in the significand), and s is the significand satisfying bk-1≤s≤bk-1. To determine accuracy, we define the quantity u=0.5·b1-k. It is the furthest distance relative to unity between a real number and the nearest floating-point number. According to the definition of the relative error above, we represent the relative error as x=x∗(1+ε) such that Erel(x)=ε≤u. According to different demands in a practical system, we may adjust the parameters in the floating-point format we defined above.


## 3.3. Floating-Point Error Analysis

For real numbersx1∗, x2∗, x1, x2 represent the floating-point value of x1∗, x2∗, which is the nearest number in the floating-point system. For i=1,2, xi=xi∗+Δi, where Δ1, Δ2 represent the absolute error of the real number and the floating-point number, which are subject to Δi≤0.5·be-k, xi∗≥be-1, and the relative error is as follows:(3)Erelxi=Δixi∗≤0.5·b1-kThe addition of the two real numbers can be represented asx1∗+x2∗=x1+Δ1+x2+Δ2, such that(4)Erelx1+x2=Δ1+Δ2x1∗+x2∗≤0.5·b1-kThe addition of floating-point number does not affect the relative error, and the precision is still k.The multiplication of the two real numbers can be represented as(5)x1∗·x2∗=x1+Δ1·x2+Δ2=x1·x2+x1·Δ2+x2·Δ1+Δ1·Δ2such that(6)Erelx1·x2=x1·Δ2+x2·Δ1+Δ1·Δ2x1∗·x2∗≤2·0.5·b1-kFor each multiplication, the relative error approximately doubles. Specifically, the relative error will increase with continuous multiplications [19]. The FFHE we propose below simulates the operations of plaintext in the floating-point system with a Boolean circuit. We prove the relative error of ciphertext is the same as corresponding plaintext in our FFHE.


## 4. The Somewhat Homomorphic DGHV Scheme

In this section, we recall the somewhat homomorphic encryption scheme over the integers of van Dijk, Gentry, Halevi, and Vaikuntanathan (DGHV) [2]. The notation used in the DGHV scheme is the same as in Section 3.1.For a specificη-bit odd integerp, we use the following distribution over γ-bit integers:(7)Dγ,ρp=Chooseq←Z∩0,2γ/p,r←Z∩-2ρ,2ρ:Output:x=pq+rDGHV.KenGen ( λ ). Generate an η-bit random prime integer p so that p←(2Z+1)∩2η-1,2η. For 0≤i≤τ, sample xi←Dγ,ρ(p). Relabel the xi′s so that x0 is the largest. Restart unless x0 is odd and x0p is even. Let pk:x0,x1,⋯,xτ and sk=p.DGHV.Encrypt(pk,  m∈{0,1}). Choose a random subset S⊆{1,2,⋯,τ} and a random integer r in (-2ρ′,2ρ′), and output the ciphertext: c←m+2r′+2∑i∈sxix0.DGHV.Evaluate ( pk, C , c 1 , c 2 , ⋯ , c t ). Given the circuit C with t input bits and t ciphertexts ci, apply the addition and multiplication gates of C to the ciphertexts, performing all the addition and multiplications over the integers, and return the resulting integer.DGHV.Decrypt ( sk, c ). Output m←(cmodp)mod2.This completes the description of the scheme as shown in [2], and the scheme is a somewhat homomorphic scheme and it is semantically secure under the approximate-GCD assumption, which is proven in [2].Definition 1 (approximate GCD).
The(ρ,η,γ)-approximateGCD problem is as follows: given a random η-bit odd integer p and given many polynomial samples from Dγ,ρ(p), in outputting p.According to the scheme parameter constraints, the following parameters are suggested:ρ=λ, ρ′=2λ, η=O~(λ2), γ=O~(λ5) and τ=γ+λ. The public key size is O~(λ10), which is too large for a practical system.


## 5. Revised Somewhat Homomorphic Encryption Scheme (RSHE)

In this section, we propose our revised somewhat homomorphic encryption scheme (RSHE) with a smaller public key size and ciphertext expansion ratio. As described in Section4, the public key size of DGHV is O~(λ10), which is too large for a practical system. References [3–5] proposed some variants of the DGHV scheme. However, our RSHE is more efficient than these schemes, and the detailed performance comparison of our RSHE with these schemes is shown in Section 5.2.As in the extension in [3], we extend the DGHV scheme for a batch setting. Instead of packing the plaintext vector m0,⋯,ml-1, we packed plaintext matrix mi,j1≤i,j≤μ with μ2 elements into a single ciphertext, where l=μ2. Instead of working with integer xi,j′ of the form xi,j′=xi,0·xj,1 as in [21], we compressed all of the public keys used in RSHE in the same way, that is xi,j′=xi,0′·xj,1′, Πi,j=Πi,0·Πj,1 for 1≤i,j≤μ where l=μ2, and xi,j=xi,0·xj,1 for 1≤i,j≤β where τ=β2. Then, only 4μ+2β integers need to be stored in the public key to generate 2μ2+β2 integers used for encryption in [3]. We considered a linear combination of the Πi,j with coefficients in (-2α′,2α′), and a linear combination of the xi,j in (-2α,2α) to further reduce the public key size. The detailed description of RSHE is as follows.


### 5.1. Description

KeyGen ( λ ): Choose η-bit distinct primes pu,v1≤u,v≤μ, and denote π as their product, that is π=∏1≤u,v≤μpu,v. Define the error-free public key element x0=q0·π, where q0←Z∩0,2γ/π is a 2λ2-rough integer. Initialize two pseudo-random number generatorsf1,f2, with two random seedsse1,se2 (the two pseudo-random number generator functions are independent of each other). Use f1(se1) and f2(se2) to generate a set of integers χi,b∈0,2γ, 1≤i≤β, 0≤b≤1, let τ=β2, compute the first set of public keys:(8)δi,b′=χi,bπ+ξi,b·π-ri,bwhere ri,b←Z∩(-2ρ′,2ρ′) and ξi,b←Z∩0,2λ+ηl/π. For all 1≤i≤β and 0≤b≤1, compute xi,b=χi,b-δi,b′. For noise parameters ωi,b,u,v←Z∩(-2ρ,2ρ), 1≤i≤μ, 0≤b≤1, 1≤u,v≤μ, compute the second set of public keys:(9)Πi,bmodpu,v=2ωi,b,u,v+δi,b,u,v·2ρ′/2+1For noise parameters ri,b,u,v′←Z∩(-2ρ,2ρ), compute the third set of public keys:(10)xi,b′modpu,v=2ri,b,u,v′+δi,b,u,vWe name δi,b,u,v as the extended Kronecker function as follows (the definition of the Kronecker function is shown in [3]):(11)δi,0,u,v=1i=u0i≠u,δi,1,u,v=1i=v0i≠vand using the compression technique used for the first set of public keys, we can also compress x0, let δ0=χ0π+ξ0·π, and compute x0=χ0-δ0.Letsk=pu,v1≤u,v≤μ, pk=δ0,se1,se2,δi,b′1≤i≤β,0≤b≤1,Πi,b1≤i≤μ,0≤b≤1,xi,b′1≤i≤μ,0≤b≤1.Enc (pk, m i , j 1 ≤ i , j ≤ μ ∈ 0 , 1 μ × μ ): Generate random integer matrix b=bi,j1≤i,j≤β∈(-2α,2α), b′=bi,j′1≤i,j≤μ∈(-2α′,2α′). Output the ciphertext:(12)c=∑1≤i,j≤μmi,jxi,0′xj,1′+∑1≤i,j≤μbi,j′Πi,0Πj,1+2∑1≤i,j≤βbi,jxi,0xj,1x0Dec ( s k , c ): Output plaintext matrix m=mi,j1≤i,j≤μ: mi,j=cmodpi,j2Evaluate ( pk, C, c 1 , …, c t ): as in the original DGHV scheme.Add ( pk, c 1 , c 2 ): Output: c1+c2modx0Mult ( pk, c 1 , c 2 ): Output: (c1·c2)modx0


### 5.2. Parameter Analysis

For the security parametersλ, we have the following constraints on our scheme parameters:ρ ≥ 2 λ: to avoid a brute force attack on the noise, and the value is larger than that in [5] to be secure against an attack proposed in [35].γ = ω ( η 2 · l o g  λ ): for thwarting lattice-based attacks against the approximate GCD problem [2].η ≥ ρ · Θ ( λ · l o g 2  λ ): for supporting homomorphic operations for evaluating the squashed decryption circuit [2].η ≥ α ′ + ρ ′ + 5 + 2  l o g 2  β: for correct decryption of a ciphertext (Section 5.3).To satisfy the above constraints, we can takeρ=2λ, η=O~(λ2), γ=O~(λ5), α=O~(λ2), τ=O~(λ3), ρ′=5λ, α′=O~(λ2), l=O~(λ2). As the ciphertexts are preserved in the form of a matrix, let l=μ2, the ciphertext expansion ratio is γ/μ2=O~(λ3), the new secret key size is η·l=O~(λ4), as in [3]. However, compared to the ciphertext expansion ratio γ=O~(λ5) in [2], our scheme has been greatly improved. The new public key for our revised somewhat homomorphic scheme has a size O~(2β·(λ+η·l)+2·2·μ·λ5)=O~(λ6) instead of O~(λ8) as in [3] and O~(λ8) as in [4]. Though the public key size in [5] is O~(λ5), the ciphertext expansion rate is much larger than that in our paper. We prefer a slightly larger public key size for a smaller ciphertext expansion rate. Compared to a public key, ciphertexts require more storage. Additionally, [6] declares the public key size of their scheme as O~(λ5.5); however, the value of the public key xi′ in the scheme does not meet the constraints proposed in [2], and it is vulnerable to lattice-based attacks. To satisfy the constraints, the size of public key xi′ is O~(λ5), and the actual public key size is at least O~(λ7). Therefore, our proposed scheme is better in terms of public key size and ciphertext expansion rate.We also perform computational complexity analysis between these schemes. The computational complexity of [2] is O(λ5) and the computational complexity of [4] is O(λ4). Furthermore, the computational complexity of [3, 5] is all O(λ3). Our scheme’s computational complexity is O(2·μ2+β2)=O(λ3). We have not increased the computational complexity under the premise of reducing the space complexity.A comprehensive comparison of space complexity and computational complexity between the above schemes is shown in Table1.Table 1
Performance comparison of somewhat homomorphic encryption scheme.
Scheme Size ofpk Size ofsk Expansion rate of ciphertext Computational complexity DGHV [2] O ~ λ 10 O ~ λ 2 O ~ λ 5 O λ 5 [3] O ~ λ 8 O ~ λ 4 O ~ λ 3 O λ 3 [4] O ~ λ 7 O ~ λ 2 O ~ λ 5 O λ 4 [5] O ~ λ 5 O ~ λ 2 O ~ λ 5 O λ 3 [6] O ~ λ 7 O ~ λ 4 O ~ λ 3 O λ 3 RSHE O ~ λ 6 O ~ λ 4 O ~ λ 3 O λ 3


### 5.3. Correctness

First, define the permitted circuits as follows.Definition 2 (permitted circuit).
For anyi>1, and any set of integer inputs all less than τi·2i(α′+ρ′+2) in absolute value, it holds that the generalized circuit’s output has an absolute value not exceeding 2i(η-3-n), where n=log2λ+1. Let Cε denote the set of permitted circuits.According to the above scheme, encrypt the plaintext matrixm1, ⋯,mt, and the ciphertext vector C={c1,⋯,ct} generate, where ci=Encrypt(pk,mi). Let C be a circuit with t inputs and an output. We can decrypt properly, if(13)Decryptsk,Evaluatepk,C,C=Cm1,⋯,mtLemma 3.
Our somewhat homomorphic encryption scheme is correct forCε.Proof.
The ciphertext of our scheme is as follows:(14)c=∑1≤i,j≤μmi,jxi,0′xj,1′+∑1≤i,j≤μbi,j′Πi,0Πi,1+2∑1≤i,j≤βbi,jxi,0xj,1x0For 1≤i,j≤μ, we have:(15)cmodpi,j≤μ2·22ρ+2+μ2·2α′+2ρ+2+β2·2α+2ρ+2≤τ·2α′+ρ′+2Let C be a Boolean circuit with t input m1,⋯,mt, and let C′ be the associated integer circuit where Boolean gates are replaced with integer operations with t ciphertexts c1,⋯,ct of plaintext m1,⋯,mt for input. For 1≤i,j≤μ, we have(16)cmodpi,j=C′c1,⋯,ctmodpi,j=C′c1modpi,j,⋯,ctmodpi,jmodpi,jAccording to the Definition 2,(17)C′c1modpi,j,⋯,ctmodpi,j≤2η-4≤pj8so(18)C′c1modpi,j,⋯,ctmodpi,jmodpi,j=C′c1modpi,j,⋯,ctmodpi,jThen,(19)cmodpi,j=C′c1modpi,j,⋯,ctmodpi,jAnd(20)cmodpi,j2=C′c1modpi,j2,⋯,ctmodpi,j22=Cm1,⋯,mtThen, our scheme is correct for the permitted circuit Cε.In the scheme, addition results in a linear increase of noise, while multiplication results in an exponential increase of noise; therefore, multiplication is dominant in increasing noise. According to Definition2, ciphertext outputs have noise not exceeding τ·2α′+ρ′+2; after d multiplication, the new noise does not exceed τ·2α′+ρ′+2d; let d be the degree. Let f(x1,⋯,xt) be the multivariate polynomial computed by C′, and let f1 be the l1 norm of the coefficient vector of f. Then, C∈Cε provided that f1·τ·2α′+ρ′+2d≤2η-3-n, then,(21)d≤η-3-n-log⁡f1α′+ρ′+2+2log⁡βAs in [5], we refer to polynomials f as permitted polynomials and denote the set of these polynomials by Pε.


### 5.4. Semantic Security

Our scheme is semantically secure under a new assumption called the error-free-μ2-approximate GCD assumption. Given integers pu,v1≤u,v≤μ, we define the following oracle Opu,v(m) which, given as input a matrix m∈0,1μ×μ, outputs x with (22)x=CRTpu,vm1,1+4ξ1,1⋯m1,μ+4ξ1,μm2,1+4ξ2,1⋯m2,μ+4ξ2,μ⋮⋱⋮mμ,1+4ξμ,1⋯mμ,μ+4ξμ,μwhere ξu,v←(-2ρ,2ρ). We denote by CRT(pu,v)au,v1≤u,v≤μ the unique integer x smaller than x0=q0·∏1≤u,v≤μpu,v such that x≡au,vmodpu,v for 1≤u,v≤μ. Therefore, O(pu,v)(m) outputs a ciphertext for the plaintext m.Definition 4 (EF-μ2-AGCD).
The error-free-μ2-approximate-GCD problem is as follows. Pick random η-bit integers pu,v1≤u,v≤μ of product π, a random 2λ2-rough q0←Z∩0,2γ/π, integers mu,v=b. Given x0=q0·∏1≤u,v≤μpu,v, x=O(pu,v)(m) and oracle access to x=O(pu,v), guess b.The decisional problem is therefore to distinguish between an encryption of 0 and an encryption of 1.Theorem 5.
Our revised somewhat homomorphic encryption scheme is semantically secure under the error-freeμ2-approximate-GCD assumption.Proof.
An attacker takes as input the public key and outputs two messagesm0 and m1. The challenger returns an encryption of mb for a random bit b. The attacker outputs a guess b′ and succeeds if b′=b.
We introduce a matrix representation of ciphertexts. To any ciphertextcmodx0, we associate the matrix:(23)c=fc=cmodp1,1⋯cmodp1,μcmodp2,1⋯cmodp2,μ⋮⋱⋮cmodpμ,1⋯cmodpμ,μ∈Zμ×μIn the ciphertexts matrix, each ciphertext can be rewritten as a result of matrix operation, for 1≤u,v≤μ,(24)cmodpu,v=mu,v+r0,u,v′T·m·r1,u,v′+r0T·b·r1+ω0,u,vT·b′·ω1,u,vmodx0where m is the matrix of plaintexts m=mu,v1≤u,v≤μ, and r0,u,v′=2r1,0,u,v′,2r2,0,u,v′,⋯,2rμ,0,u,v′T, r1,u,v′=2r1,1,u,v′,2r2,1,u,v′,⋯,2rμ,1,u,v′T are two vectors which contain random noise in the third set of public keys. b=bi,j1≤i,j≤β and b′=bi,j′1≤i,j≤μ are random integer matrixes. r0=r1,0,r2,0,⋯,rβ,0T, r1=r1,1,r2,1,⋯,rβ,1T contain random noise in the second set of public keys, (25)ω0,u,v=2ω1,0,u,v,2ω2,0,u,v,⋯,2ωu,0,u,v+2ρ′/2+1,⋯,2ωμ,0,u,vTω1,u,v=2ω1,1,u,v,2ω2,1,u,v,⋯,2ωv,1,u,v+2ρ′/2+1,⋯,2ωμ,1,u,vT,and contain random noise in the first set of public keys (with the extended Kronecker function terms). According to the constraints on the parameters in Section 5.1, let random variable u=r0,u,v′T·m·r1,u,v′+r0T·b·r1+ω0,u,vT·b′·ω1,u,v be uniform in (26)-μ2·22ρ+21+2α′-β2·22ρ′+α,μ2·22ρ+21+2α′+β2·22ρ′+αThen, the statistical distance between the random variables u and mu,v+u does not exceed 1/(μ2·22ρ+21+2α′+β2·22ρ′+α). Therefore, (27)Pr⁡mu,v=0-Pr⁡mu,v=1≤1μ2·22ρ+21+2α′+β2·22ρ′+αand Pr⁡[mu,v=0]=Pr⁡[mu,v=1]=1/2.
This concludes the proof of Theorem5.


## 5.1. Description

KeyGen ( λ ): Choose η-bit distinct primes pu,v1≤u,v≤μ, and denote π as their product, that is π=∏1≤u,v≤μpu,v. Define the error-free public key element x0=q0·π, where q0←Z∩0,2γ/π is a 2λ2-rough integer. Initialize two pseudo-random number generatorsf1,f2, with two random seedsse1,se2 (the two pseudo-random number generator functions are independent of each other). Use f1(se1) and f2(se2) to generate a set of integers χi,b∈0,2γ, 1≤i≤β, 0≤b≤1, let τ=β2, compute the first set of public keys:(8)δi,b′=χi,bπ+ξi,b·π-ri,bwhere ri,b←Z∩(-2ρ′,2ρ′) and ξi,b←Z∩0,2λ+ηl/π. For all 1≤i≤β and 0≤b≤1, compute xi,b=χi,b-δi,b′. For noise parameters ωi,b,u,v←Z∩(-2ρ,2ρ), 1≤i≤μ, 0≤b≤1, 1≤u,v≤μ, compute the second set of public keys:(9)Πi,bmodpu,v=2ωi,b,u,v+δi,b,u,v·2ρ′/2+1For noise parameters ri,b,u,v′←Z∩(-2ρ,2ρ), compute the third set of public keys:(10)xi,b′modpu,v=2ri,b,u,v′+δi,b,u,vWe name δi,b,u,v as the extended Kronecker function as follows (the definition of the Kronecker function is shown in [3]):(11)δi,0,u,v=1i=u0i≠u,δi,1,u,v=1i=v0i≠vand using the compression technique used for the first set of public keys, we can also compress x0, let δ0=χ0π+ξ0·π, and compute x0=χ0-δ0.Letsk=pu,v1≤u,v≤μ, pk=δ0,se1,se2,δi,b′1≤i≤β,0≤b≤1,Πi,b1≤i≤μ,0≤b≤1,xi,b′1≤i≤μ,0≤b≤1.Enc (pk, m i , j 1 ≤ i , j ≤ μ ∈ 0 , 1 μ × μ ): Generate random integer matrix b=bi,j1≤i,j≤β∈(-2α,2α), b′=bi,j′1≤i,j≤μ∈(-2α′,2α′). Output the ciphertext:(12)c=∑1≤i,j≤μmi,jxi,0′xj,1′+∑1≤i,j≤μbi,j′Πi,0Πj,1+2∑1≤i,j≤βbi,jxi,0xj,1x0Dec ( s k , c ): Output plaintext matrix m=mi,j1≤i,j≤μ: mi,j=cmodpi,j2Evaluate ( pk, C, c 1 , …, c t ): as in the original DGHV scheme.Add ( pk, c 1 , c 2 ): Output: c1+c2modx0Mult ( pk, c 1 , c 2 ): Output: (c1·c2)modx0


## 5.2. Parameter Analysis

For the security parametersλ, we have the following constraints on our scheme parameters:ρ ≥ 2 λ: to avoid a brute force attack on the noise, and the value is larger than that in [5] to be secure against an attack proposed in [35].γ = ω ( η 2 · l o g  λ ): for thwarting lattice-based attacks against the approximate GCD problem [2].η ≥ ρ · Θ ( λ · l o g 2  λ ): for supporting homomorphic operations for evaluating the squashed decryption circuit [2].η ≥ α ′ + ρ ′ + 5 + 2  l o g 2  β: for correct decryption of a ciphertext (Section 5.3).To satisfy the above constraints, we can takeρ=2λ, η=O~(λ2), γ=O~(λ5), α=O~(λ2), τ=O~(λ3), ρ′=5λ, α′=O~(λ2), l=O~(λ2). As the ciphertexts are preserved in the form of a matrix, let l=μ2, the ciphertext expansion ratio is γ/μ2=O~(λ3), the new secret key size is η·l=O~(λ4), as in [3]. However, compared to the ciphertext expansion ratio γ=O~(λ5) in [2], our scheme has been greatly improved. The new public key for our revised somewhat homomorphic scheme has a size O~(2β·(λ+η·l)+2·2·μ·λ5)=O~(λ6) instead of O~(λ8) as in [3] and O~(λ8) as in [4]. Though the public key size in [5] is O~(λ5), the ciphertext expansion rate is much larger than that in our paper. We prefer a slightly larger public key size for a smaller ciphertext expansion rate. Compared to a public key, ciphertexts require more storage. Additionally, [6] declares the public key size of their scheme as O~(λ5.5); however, the value of the public key xi′ in the scheme does not meet the constraints proposed in [2], and it is vulnerable to lattice-based attacks. To satisfy the constraints, the size of public key xi′ is O~(λ5), and the actual public key size is at least O~(λ7). Therefore, our proposed scheme is better in terms of public key size and ciphertext expansion rate.We also perform computational complexity analysis between these schemes. The computational complexity of [2] is O(λ5) and the computational complexity of [4] is O(λ4). Furthermore, the computational complexity of [3, 5] is all O(λ3). Our scheme’s computational complexity is O(2·μ2+β2)=O(λ3). We have not increased the computational complexity under the premise of reducing the space complexity.A comprehensive comparison of space complexity and computational complexity between the above schemes is shown in Table1.Table 1
Performance comparison of somewhat homomorphic encryption scheme.
Scheme Size ofpk Size ofsk Expansion rate of ciphertext Computational complexity DGHV [2] O ~ λ 10 O ~ λ 2 O ~ λ 5 O λ 5 [3] O ~ λ 8 O ~ λ 4 O ~ λ 3 O λ 3 [4] O ~ λ 7 O ~ λ 2 O ~ λ 5 O λ 4 [5] O ~ λ 5 O ~ λ 2 O ~ λ 5 O λ 3 [6] O ~ λ 7 O ~ λ 4 O ~ λ 3 O λ 3 RSHE O ~ λ 6 O ~ λ 4 O ~ λ 3 O λ 3


## 5.3. Correctness

First, define the permitted circuits as follows.Definition 2 (permitted circuit).
For anyi>1, and any set of integer inputs all less than τi·2i(α′+ρ′+2) in absolute value, it holds that the generalized circuit’s output has an absolute value not exceeding 2i(η-3-n), where n=log2λ+1. Let Cε denote the set of permitted circuits.According to the above scheme, encrypt the plaintext matrixm1, ⋯,mt, and the ciphertext vector C={c1,⋯,ct} generate, where ci=Encrypt(pk,mi). Let C be a circuit with t inputs and an output. We can decrypt properly, if(13)Decryptsk,Evaluatepk,C,C=Cm1,⋯,mtLemma 3.
Our somewhat homomorphic encryption scheme is correct forCε.Proof.
The ciphertext of our scheme is as follows:(14)c=∑1≤i,j≤μmi,jxi,0′xj,1′+∑1≤i,j≤μbi,j′Πi,0Πi,1+2∑1≤i,j≤βbi,jxi,0xj,1x0For 1≤i,j≤μ, we have:(15)cmodpi,j≤μ2·22ρ+2+μ2·2α′+2ρ+2+β2·2α+2ρ+2≤τ·2α′+ρ′+2Let C be a Boolean circuit with t input m1,⋯,mt, and let C′ be the associated integer circuit where Boolean gates are replaced with integer operations with t ciphertexts c1,⋯,ct of plaintext m1,⋯,mt for input. For 1≤i,j≤μ, we have(16)cmodpi,j=C′c1,⋯,ctmodpi,j=C′c1modpi,j,⋯,ctmodpi,jmodpi,jAccording to the Definition 2,(17)C′c1modpi,j,⋯,ctmodpi,j≤2η-4≤pj8so(18)C′c1modpi,j,⋯,ctmodpi,jmodpi,j=C′c1modpi,j,⋯,ctmodpi,jThen,(19)cmodpi,j=C′c1modpi,j,⋯,ctmodpi,jAnd(20)cmodpi,j2=C′c1modpi,j2,⋯,ctmodpi,j22=Cm1,⋯,mtThen, our scheme is correct for the permitted circuit Cε.In the scheme, addition results in a linear increase of noise, while multiplication results in an exponential increase of noise; therefore, multiplication is dominant in increasing noise. According to Definition2, ciphertext outputs have noise not exceeding τ·2α′+ρ′+2; after d multiplication, the new noise does not exceed τ·2α′+ρ′+2d; let d be the degree. Let f(x1,⋯,xt) be the multivariate polynomial computed by C′, and let f1 be the l1 norm of the coefficient vector of f. Then, C∈Cε provided that f1·τ·2α′+ρ′+2d≤2η-3-n, then,(21)d≤η-3-n-log⁡f1α′+ρ′+2+2log⁡βAs in [5], we refer to polynomials f as permitted polynomials and denote the set of these polynomials by Pε.


## 5.4. Semantic Security

Our scheme is semantically secure under a new assumption called the error-free-μ2-approximate GCD assumption. Given integers pu,v1≤u,v≤μ, we define the following oracle Opu,v(m) which, given as input a matrix m∈0,1μ×μ, outputs x with (22)x=CRTpu,vm1,1+4ξ1,1⋯m1,μ+4ξ1,μm2,1+4ξ2,1⋯m2,μ+4ξ2,μ⋮⋱⋮mμ,1+4ξμ,1⋯mμ,μ+4ξμ,μwhere ξu,v←(-2ρ,2ρ). We denote by CRT(pu,v)au,v1≤u,v≤μ the unique integer x smaller than x0=q0·∏1≤u,v≤μpu,v such that x≡au,vmodpu,v for 1≤u,v≤μ. Therefore, O(pu,v)(m) outputs a ciphertext for the plaintext m.Definition 4 (EF-μ2-AGCD).
The error-free-μ2-approximate-GCD problem is as follows. Pick random η-bit integers pu,v1≤u,v≤μ of product π, a random 2λ2-rough q0←Z∩0,2γ/π, integers mu,v=b. Given x0=q0·∏1≤u,v≤μpu,v, x=O(pu,v)(m) and oracle access to x=O(pu,v), guess b.The decisional problem is therefore to distinguish between an encryption of 0 and an encryption of 1.Theorem 5.
Our revised somewhat homomorphic encryption scheme is semantically secure under the error-freeμ2-approximate-GCD assumption.Proof.
An attacker takes as input the public key and outputs two messagesm0 and m1. The challenger returns an encryption of mb for a random bit b. The attacker outputs a guess b′ and succeeds if b′=b.
We introduce a matrix representation of ciphertexts. To any ciphertextcmodx0, we associate the matrix:(23)c=fc=cmodp1,1⋯cmodp1,μcmodp2,1⋯cmodp2,μ⋮⋱⋮cmodpμ,1⋯cmodpμ,μ∈Zμ×μIn the ciphertexts matrix, each ciphertext can be rewritten as a result of matrix operation, for 1≤u,v≤μ,(24)cmodpu,v=mu,v+r0,u,v′T·m·r1,u,v′+r0T·b·r1+ω0,u,vT·b′·ω1,u,vmodx0where m is the matrix of plaintexts m=mu,v1≤u,v≤μ, and r0,u,v′=2r1,0,u,v′,2r2,0,u,v′,⋯,2rμ,0,u,v′T, r1,u,v′=2r1,1,u,v′,2r2,1,u,v′,⋯,2rμ,1,u,v′T are two vectors which contain random noise in the third set of public keys. b=bi,j1≤i,j≤β and b′=bi,j′1≤i,j≤μ are random integer matrixes. r0=r1,0,r2,0,⋯,rβ,0T, r1=r1,1,r2,1,⋯,rβ,1T contain random noise in the second set of public keys, (25)ω0,u,v=2ω1,0,u,v,2ω2,0,u,v,⋯,2ωu,0,u,v+2ρ′/2+1,⋯,2ωμ,0,u,vTω1,u,v=2ω1,1,u,v,2ω2,1,u,v,⋯,2ωv,1,u,v+2ρ′/2+1,⋯,2ωμ,1,u,vT,and contain random noise in the first set of public keys (with the extended Kronecker function terms). According to the constraints on the parameters in Section 5.1, let random variable u=r0,u,v′T·m·r1,u,v′+r0T·b·r1+ω0,u,vT·b′·ω1,u,v be uniform in (26)-μ2·22ρ+21+2α′-β2·22ρ′+α,μ2·22ρ+21+2α′+β2·22ρ′+αThen, the statistical distance between the random variables u and mu,v+u does not exceed 1/(μ2·22ρ+21+2α′+β2·22ρ′+α). Therefore, (27)Pr⁡mu,v=0-Pr⁡mu,v=1≤1μ2·22ρ+21+2α′+β2·22ρ′+αand Pr⁡[mu,v=0]=Pr⁡[mu,v=1]=1/2.
This concludes the proof of Theorem5.


## 6. Floating-Point Fully Homomorphic Encryption Scheme (FFHE)

RSHE can only support finite homomorphic operations, so it is necessary to construct a fully homomorphic encryption scheme. In this section, we follow Gentry’s approach to transform RSHE into a fully homomorphic encryption scheme (FFHE), and we identify the scheme supporting operations over floating-point numbers.


### 6.1. Squash the Decryption Circuit

We first need to squash the decryption circuit. Specifically, we must add extra information about the secret key to the public key to “post process” the ciphertext. The ciphertext can be expressed as a low degree polynomial in the bits of the secret key. We add information about the secret key into the public key to construct a lower degree decryption polynomial.We use the same technique as in [2] and generalize it to a batch setting. Let θ,Θ,κ be three new parameters, concretely, θ=λ, Θ=O~(λ3), κ=γ+2+log2⁡(θ+1). We add to the public key a set y=(y0,⋯,yΘ-1) of rational numbers in [0,2) with κ bits of precision after the binary point, such that for all 1≤u,v≤μ there exists a sparse subset Su,v⊂{0,⋯,Θ-1} of size θ with ∑i∈Su,vyi≈1/pu,vmod2. We also replace the secret key with the indicator vector of the subset Su,v. Formally, according to RSHE in Section 5.1, we define FFHE as follows.(1  ) KeyGen ( λ ): Generate sk=pu,v1≤u,v≤μ and pk as before. Let xpu,v←[2κ/pu,v], choose at random Θ-bit vectors su,v={su,v,0,⋯,su,v,Θ-1}, each of Hamming weight θ, for 1≤u,v≤μ. Choose at random Θ integers ui∈0,2κ+1 for 0≤i≤Θ-1, fulfilling the condition that xpu,v=∑i=0Θ-1su,v,i·uimod2κ+1 for 1≤u,v≤μ. Set yi=ui/2κ and y=(y0,⋯,yΘ-1). Each yi is a positive number smaller than two, with κ bits of precision after the binary point, and verifies(28)1pu,v=∑i=0Θ-1su,v,i·yi+εu,vmod2for some εu,v<2-κ.As we set a new public keyy=(y0,⋯,yΘ-1) with κ bits of precision after the binary point, the public key size is Θ·κ=O~(λ8), instead of O~(λ6) as in our revised homomorphic encryption scheme. Using the public key compressing method proposed in Section 5.1, we also generate yi by using a pseudo-random generator f(se) with seedse. So, onlyse and y0 must be stored in a public key.The new secret key issk∗=su,v1≤u,v≤μ, and the new public key is pk∗=(pk,y0,se).(2  ) Enc (pk, m): the same as Section 5.1.(3  ) Expand ( p k ∗ , c): the ciphertext expansion procedure takes as input a ciphertextc and computes an expanded ciphertext: let zi=c·yi2 with n=log2(θ+1) bits of precision after the binary point for 0≤i≤Θ-1. Output the expanded ciphertext c,z0,⋯zΘ-1.(4  ) Dec ( s k ∗ , c , z 0 , ⋯, z Θ - 1 ): output m=mu,v1≤u,v≤μ: mu,v←c-∑i=0Θ-1su,v,i·zi2Lemma 6.
The scheme after squashing the decryption circuit is correct for the setC(Pε) of circuits that compute permitted polynomials.Proof.
According to Lemma3, the correct decrypted message m is given by (c/pi,jmod2)⊕(cmod2), so what we need to show is that(29)cpu,v=∑i=0Θ-1su,v,i·zimod2Then,(30)cpu,v-∑i=0Θ-1su,v,i·zi2=cpu,v-∑i=0Θ-1su,v,i·c·yi2+∑i=0Θ-1su,v,i·Δi2=cpu,v-c·∑i=0Θ-1su,v,i·yi2+∑i=0Θ-1su,v,i·Δi2=cpu,v-c·1pu,v-εpu,v+∑i=0Θ-1su,v,i·Δi2=c·εpu,v+∑i=0Θ-1su,v,i·Δi2To satisfy the constraints on parameters, we have εpu,v≤2-κ, Δi≤2-n, so,(31)c·εpu,v≤2γ-γ-2-log2θ+1≤14θ+1,∑i=0Θ-1su,v,i·Δi≤θ2θ+1then,(32)c·εpi,j+∑i=0Θ-1su,v,i·Δi≤14θ+1+θ2θ+1≤12The total distance is strictly less than 1/2. This concludes the proof.


### 6.2. Bootstrapping

As in [2], one sees that the scheme is bootstrappable. From Gentry’s theorem, we identify homomorphic encryption schemes for circuits of any depth.Theorem 7.
Letε be the scheme above and let Dε be the set of squashed decryption circuits. Then, Dε⊂C(Pε).For each plaintext, theExpand procedures work naturally in parallel. For 1≤u,v≤μ, we consider the decryption equation:(33)mu,v⟵c∗-∑i=0Θ-1su,v,i·zimod2Except for the decryption equation, the proof of Theorem 7 is identical to the proof of Theorem 3 in [2].


### 6.3. Security Analysis

Our squashed scheme is semantically secure under the hardness of subset sum assumption, which is mentioned in [2, 16]. We use the attack analysis in [4] of the sparse subset sum problem. In our scheme, the attacker must solve the following equation:(34)xpu,v=∑i=0Θ-1su,v,i·uimod2κ+1where ui′s are known and the secret key su,v=(su,v,0,⋯,su,v,Θ-1) is of small Hamming weight θ. We assume that the attack knows pu,v and therefore xpu,v.Our squashed scheme makes an additional batch operation based on [4]. Moreover, theExpand procedures works naturally parallel over the plaintext bits, which means that the ciphertexts encrypted by different secret keys will not interfere with each other. For each pu,v, the attack analysis is similar to [4].According to the asymptotic analysis in [4, 36], we can take γ=O~(λ5), Θ=O~(λ3) and θ=λ to avoid known attacks on the sparse subset sum problem.


### 6.4. Floating-Point Calculation

According to Section3.2, we denote a floating-point number x=-1s′·s·2e-k (letb=2), which can be represented as a triple (s′,s,e), and k is the constant precision. To securely store a floating-point number, we use FFHE to encrypt it as s′,s,e, where s′∈{0,1} is the sign bit of x, s is a k-bits number. The encrypted floating-point number x is constructed as x=sx′,sx,ex. Then, we define two types of circuit operations, “⊕” as addition circuit and “⊗” as multiplication circuit, which take binary bits as input in plaintext operation and take large integer ciphertexts as input in ciphertext operation.The comparison of magnitude of ciphertexts cannot be avoided in the operation of the ciphertexts. Suppose we have two ciphertextssx and sy, where sx and sy are all integers. Define a bit b to be 1 if sx≥sy and to be 0 otherwise. We propose a Greater-Than Bit (GTB) protocol to compute an encryption b of the bit b given only ciphertexts sx and sy without knowing the secret key.s x and sy are signed integers. They can be expressed as binary numbers sx=mx0mx1⋯mxk and sy=my0my1⋯myk, and mx0,my0 are sign bits of sx,sy respectively. Through the Boolean circuit, we can calculate sx-sy=mx0mx1⋯mxk-my0my1⋯myk. We can use two’s complement to achieve binary subtraction. For example,(35)7-5indecimal=0111-0101inbinary=0111⊕1101=0111⊕10111011isthetwo′scomplementof1101=0010=2indecimalSpecifically,(36)sx-sy=mx0mx1⋯mxk-my0my1⋯myk=mx0mx1⋯mxk⊕my0+1mod2my1my2⋯myk=mx0mx1⋯mxk⊕my0+1mod2my1+1mod2⋯myk+1mod2⊕1Therefore, using the addition circuit, we define the “⊖” as subtraction circuit as above (we do not need the modulo operation in the subtraction operation of ciphertexts).Greater-Than Bit Protocol. We use the subtraction circuit to implement our proposed GTB protocol. Given two ciphertexts sx and sy, GTB protocol is to show sx≥sy or sx<sy. The overall steps of GTB are shown as follows.Step 1.
We execute the subtraction circuit to calculate the ciphertexts ofsx-sy.(37)sz=sx⊖sy=mx0mx1⋯mxk⊖my0my1⋯myk=mz0mz1⋯mzkThe input of our FFHE scheme is binary bit; therefore, the ciphertext is(38)mz0mz1⋯mzk=mz0mz1⋯mzkand mz0 is the sign bit of sz.Step 2.
We need to check whether the signs ofsx and sy are consistent.(39)same_sign=mx0⊗my0⊕1⊖mx0⊗1⊖my0same_sign is the ciphertext for 1, when the signs of sx and sy are the same, and same_sign is the ciphertext for 0, when the signs of sx and sy are different.Step 3.
(40) G t b = 1 ⊖ s a m e _ s i g n ⊗ m x 0 ⊕ s a m e _ s i g n ⊗ m z 0We define GTB protocol as GTB(sx,sy)=Gtb.Gtb is the ciphertext for 0, when sx≥sy, and Gtb is ciphertext for 1, when sx<sy.Equivalent-Bit Protocol. Additionally, it is necessary to check whether two numbers are equivalent or not. Therefore, we propose the Equivalent-Bit (EB) protocol. Given two ciphertexts sx and sy, the EB protocol is to show whether sx=sy. The overall steps of EB protocol are shown as follows.Step 1.
We execute GTB protocol to checksx>sy or sx<sy.(41)g1=GTBsx,sy,g2=GTBsy,sxStep 2.
(42) g 0 = g 1 ⊗ g 2 ⊕ 1 ⊖ g 1 ⊗ 1 ⊖ g 2We define EB protocol as EBsx,sy=g0. Notice that if g0=1, then sx=sy. Otherwise, sx≠sy.Left Shift Protocol. In floating-point number addition, it is necessary to unify the exponents of these floating-point numbers. Therefore, we propose the Left Shift (LS) protocol to adjust the significand of a floating-point number. Given a ciphertext of the significand sx and two ciphertexts of the exponents ex, ey, we calculate sx∗=sx·2ex-ey, where ex≥ey. The overall steps of LS protocol are shown as follows.Step 1.
Fori in 0,1,⋯,emax (emax is an extremal exponent as described in Section 3.2),(43)a=GTBex⊖ey,ib=EBex⊖ey,isx=1⊖a⊗1⊖b⊗2⊗sx
Returnsx∗=sx.We define LS protocol as(44)LSsx,ex⊖eysx·2ex-eyex≥eysxex<eyWe also propose floating-point number addition (FAdd) protocol and floating-point number multiplication (FMult) protocol to compute the addition and multiplication of the ciphertexts of the floating-point numbers. Suppose we have two floating-point numbers x=-1sx′·sx·2ex-k, y=-1sy′·sy·2ey-k. The ciphertexts are x=sx′,sx,ex and y=sy′,sy,ey respectively. The overall steps of FAdd protocol and FMult protocol are shown as follows.Floating-Point Number Addition ProtocolStep 1.
We need to check whether the signs ofx and y are consistent.(45)same_sign=sx′⊗sy′⊕1⊖sx′⊗1⊖sy′same_sign is the ciphertext for 1, when sx′=sy′, and same_sign is the ciphertext for 0, when sx′≠sy′. Supposing that sx′=sy′, the sign bit of x+y is sx′·sy′.Step 2.
Ifsx′≠sy′, the sign of x+y is the same as the sign of the larger between x and y, specifically, the sign bit of x+y is sd′ as follows:(46)sx∗=LSsx,ex⊖ey,sy∗=LSsy,ey⊖ex,Gs∗=GTBsx∗,sy∗sd′=1⊖Gs⊗sx′⊕Gs⊗sy′Step 3.
We calculate the sign of the addition ofx and y.(47)s+′=same_sign⊗sx′⊗sy′⊕1⊖same_sign⊗sd′Step 4.
Whensx′≠sy′, the significand of x+y is as follows:(48)sd=1⊖Gs⊗sx∗⊖sy∗⊕Gs⊗sy∗⊖sx∗Therefore, we calculate the final significand of the addition of x and y.(49)s+=same_sign⊗sx∗⊕sy∗⊕1⊖same_sign⊗sd=m+0m+1⋯m+k⋯m+k+lIt shows that s+ isk+l binary bits, and the precision of the result isk+l.Step 5.
Ifs+≥2k+ex-ey, it shows that the exponent of x+y is max⁡{ex,ey}+1. If s+<2k+ex-ey, it shows that the exponent of x+y is max⁡ex,ey. The construction is as follows:(50)Ge=GTBex,ey,emax=1⊖Ge⊗ex⊕Ge⊗eyed=1⊖Ge⊗ex⊖ey⊕Ge⊗ey⊖exGs+=GTBs+,LS2k,edWe calculate the exponent of the addition ofx andy.(51)e+=1⊖Gs+⊗emax⊕1⊕Gs+⊗emaxStep 6.
Finally, we need to keep the result significandk bits.(52)g+=EBm+k+1,1s+∗=g+⊗m+0m+1⋯m+k+1⊕1⊖g+⊗m+0m+1⋯m+kTherefore, s+∗ is k binary bits. The result of addition can be represented ass+′,s+∗,e+, specifically, FAddsx′,sx,ex,sy′,sy,ey=s+′,s+∗,e+.As above, the precision is stillk. Floating-point addition does not add additional relative error. For subsequent operations, the precision is still k, and the relative error Erel(x+y)≤0.5·21-k as in Section 3.2.Floating-Point Number Multiplication ProtocolStep 1.
First, we calculate the sign of the multiplication ofx and y.(53)s×′=sx′⊗1⊖sy′⊕1⊖sx′⊗sy′Step 2.
Then, we calculate the exponent.(54)e×=ex⊕eyStep 3.
Finally, we calculate the significand.(55)s×=sx⊗sy=mx0mx1⋯mxk⊗my0my1⋯myk=m×0m×1⋯m×km×k+1⋯m×2kIt shows that s× is 2k binary bits, and the precision of the result is 2k.Step 4.
Thereafter, we need to keep the result significandk bits.(56)g+=EBm×k+1,1s×∗=g+⊗m×0m×1⋯m×k+1⊕1⊖g+⊗m×0m×1⋯m×kTherefore, s×∗ is k binary bits. The result of multiplication can be represented as s×′,s×∗,e×, specifically,(57)FMultsx′,sx,ex,sy′,sy,ey=s×′,s×∗,e×.As above, the precision is stillk. According to Section 3.2, the upper bound of the relative error for multiplication will be twice the original, Erel(x·y)≤2·0.5·21-k. That is, after the n-layer multiplication operation, the upper bound will be 2n·0.5·21-k, which is the same as the floating-point number operation in plaintext.The FFHE scheme completely simulates a floating-point operation in plaintext in the form of a circuit so that the relative error of operation result in ciphertext is not increased compared with the result in plaintext.


## 6.1. Squash the Decryption Circuit

We first need to squash the decryption circuit. Specifically, we must add extra information about the secret key to the public key to “post process” the ciphertext. The ciphertext can be expressed as a low degree polynomial in the bits of the secret key. We add information about the secret key into the public key to construct a lower degree decryption polynomial.We use the same technique as in [2] and generalize it to a batch setting. Let θ,Θ,κ be three new parameters, concretely, θ=λ, Θ=O~(λ3), κ=γ+2+log2⁡(θ+1). We add to the public key a set y=(y0,⋯,yΘ-1) of rational numbers in [0,2) with κ bits of precision after the binary point, such that for all 1≤u,v≤μ there exists a sparse subset Su,v⊂{0,⋯,Θ-1} of size θ with ∑i∈Su,vyi≈1/pu,vmod2. We also replace the secret key with the indicator vector of the subset Su,v. Formally, according to RSHE in Section 5.1, we define FFHE as follows.(1  ) KeyGen ( λ ): Generate sk=pu,v1≤u,v≤μ and pk as before. Let xpu,v←[2κ/pu,v], choose at random Θ-bit vectors su,v={su,v,0,⋯,su,v,Θ-1}, each of Hamming weight θ, for 1≤u,v≤μ. Choose at random Θ integers ui∈0,2κ+1 for 0≤i≤Θ-1, fulfilling the condition that xpu,v=∑i=0Θ-1su,v,i·uimod2κ+1 for 1≤u,v≤μ. Set yi=ui/2κ and y=(y0,⋯,yΘ-1). Each yi is a positive number smaller than two, with κ bits of precision after the binary point, and verifies(28)1pu,v=∑i=0Θ-1su,v,i·yi+εu,vmod2for some εu,v<2-κ.As we set a new public keyy=(y0,⋯,yΘ-1) with κ bits of precision after the binary point, the public key size is Θ·κ=O~(λ8), instead of O~(λ6) as in our revised homomorphic encryption scheme. Using the public key compressing method proposed in Section 5.1, we also generate yi by using a pseudo-random generator f(se) with seedse. So, onlyse and y0 must be stored in a public key.The new secret key issk∗=su,v1≤u,v≤μ, and the new public key is pk∗=(pk,y0,se).(2  ) Enc (pk, m): the same as Section 5.1.(3  ) Expand ( p k ∗ , c): the ciphertext expansion procedure takes as input a ciphertextc and computes an expanded ciphertext: let zi=c·yi2 with n=log2(θ+1) bits of precision after the binary point for 0≤i≤Θ-1. Output the expanded ciphertext c,z0,⋯zΘ-1.(4  ) Dec ( s k ∗ , c , z 0 , ⋯, z Θ - 1 ): output m=mu,v1≤u,v≤μ: mu,v←c-∑i=0Θ-1su,v,i·zi2Lemma 6.
The scheme after squashing the decryption circuit is correct for the setC(Pε) of circuits that compute permitted polynomials.Proof.
According to Lemma3, the correct decrypted message m is given by (c/pi,jmod2)⊕(cmod2), so what we need to show is that(29)cpu,v=∑i=0Θ-1su,v,i·zimod2Then,(30)cpu,v-∑i=0Θ-1su,v,i·zi2=cpu,v-∑i=0Θ-1su,v,i·c·yi2+∑i=0Θ-1su,v,i·Δi2=cpu,v-c·∑i=0Θ-1su,v,i·yi2+∑i=0Θ-1su,v,i·Δi2=cpu,v-c·1pu,v-εpu,v+∑i=0Θ-1su,v,i·Δi2=c·εpu,v+∑i=0Θ-1su,v,i·Δi2To satisfy the constraints on parameters, we have εpu,v≤2-κ, Δi≤2-n, so,(31)c·εpu,v≤2γ-γ-2-log2θ+1≤14θ+1,∑i=0Θ-1su,v,i·Δi≤θ2θ+1then,(32)c·εpi,j+∑i=0Θ-1su,v,i·Δi≤14θ+1+θ2θ+1≤12The total distance is strictly less than 1/2. This concludes the proof.


## 6.2. Bootstrapping

As in [2], one sees that the scheme is bootstrappable. From Gentry’s theorem, we identify homomorphic encryption schemes for circuits of any depth.Theorem 7.
Letε be the scheme above and let Dε be the set of squashed decryption circuits. Then, Dε⊂C(Pε).For each plaintext, theExpand procedures work naturally in parallel. For 1≤u,v≤μ, we consider the decryption equation:(33)mu,v⟵c∗-∑i=0Θ-1su,v,i·zimod2Except for the decryption equation, the proof of Theorem 7 is identical to the proof of Theorem 3 in [2].


## 6.3. Security Analysis

Our squashed scheme is semantically secure under the hardness of subset sum assumption, which is mentioned in [2, 16]. We use the attack analysis in [4] of the sparse subset sum problem. In our scheme, the attacker must solve the following equation:(34)xpu,v=∑i=0Θ-1su,v,i·uimod2κ+1where ui′s are known and the secret key su,v=(su,v,0,⋯,su,v,Θ-1) is of small Hamming weight θ. We assume that the attack knows pu,v and therefore xpu,v.Our squashed scheme makes an additional batch operation based on [4]. Moreover, theExpand procedures works naturally parallel over the plaintext bits, which means that the ciphertexts encrypted by different secret keys will not interfere with each other. For each pu,v, the attack analysis is similar to [4].According to the asymptotic analysis in [4, 36], we can take γ=O~(λ5), Θ=O~(λ3) and θ=λ to avoid known attacks on the sparse subset sum problem.


## 6.4. Floating-Point Calculation

According to Section3.2, we denote a floating-point number x=-1s′·s·2e-k (letb=2), which can be represented as a triple (s′,s,e), and k is the constant precision. To securely store a floating-point number, we use FFHE to encrypt it as s′,s,e, where s′∈{0,1} is the sign bit of x, s is a k-bits number. The encrypted floating-point number x is constructed as x=sx′,sx,ex. Then, we define two types of circuit operations, “⊕” as addition circuit and “⊗” as multiplication circuit, which take binary bits as input in plaintext operation and take large integer ciphertexts as input in ciphertext operation.The comparison of magnitude of ciphertexts cannot be avoided in the operation of the ciphertexts. Suppose we have two ciphertextssx and sy, where sx and sy are all integers. Define a bit b to be 1 if sx≥sy and to be 0 otherwise. We propose a Greater-Than Bit (GTB) protocol to compute an encryption b of the bit b given only ciphertexts sx and sy without knowing the secret key.s x and sy are signed integers. They can be expressed as binary numbers sx=mx0mx1⋯mxk and sy=my0my1⋯myk, and mx0,my0 are sign bits of sx,sy respectively. Through the Boolean circuit, we can calculate sx-sy=mx0mx1⋯mxk-my0my1⋯myk. We can use two’s complement to achieve binary subtraction. For example,(35)7-5indecimal=0111-0101inbinary=0111⊕1101=0111⊕10111011isthetwo′scomplementof1101=0010=2indecimalSpecifically,(36)sx-sy=mx0mx1⋯mxk-my0my1⋯myk=mx0mx1⋯mxk⊕my0+1mod2my1my2⋯myk=mx0mx1⋯mxk⊕my0+1mod2my1+1mod2⋯myk+1mod2⊕1Therefore, using the addition circuit, we define the “⊖” as subtraction circuit as above (we do not need the modulo operation in the subtraction operation of ciphertexts).Greater-Than Bit Protocol. We use the subtraction circuit to implement our proposed GTB protocol. Given two ciphertexts sx and sy, GTB protocol is to show sx≥sy or sx<sy. The overall steps of GTB are shown as follows.Step 1.
We execute the subtraction circuit to calculate the ciphertexts ofsx-sy.(37)sz=sx⊖sy=mx0mx1⋯mxk⊖my0my1⋯myk=mz0mz1⋯mzkThe input of our FFHE scheme is binary bit; therefore, the ciphertext is(38)mz0mz1⋯mzk=mz0mz1⋯mzkand mz0 is the sign bit of sz.Step 2.
We need to check whether the signs ofsx and sy are consistent.(39)same_sign=mx0⊗my0⊕1⊖mx0⊗1⊖my0same_sign is the ciphertext for 1, when the signs of sx and sy are the same, and same_sign is the ciphertext for 0, when the signs of sx and sy are different.Step 3.
(40) G t b = 1 ⊖ s a m e _ s i g n ⊗ m x 0 ⊕ s a m e _ s i g n ⊗ m z 0We define GTB protocol as GTB(sx,sy)=Gtb.Gtb is the ciphertext for 0, when sx≥sy, and Gtb is ciphertext for 1, when sx<sy.Equivalent-Bit Protocol. Additionally, it is necessary to check whether two numbers are equivalent or not. Therefore, we propose the Equivalent-Bit (EB) protocol. Given two ciphertexts sx and sy, the EB protocol is to show whether sx=sy. The overall steps of EB protocol are shown as follows.Step 1.
We execute GTB protocol to checksx>sy or sx<sy.(41)g1=GTBsx,sy,g2=GTBsy,sxStep 2.
(42) g 0 = g 1 ⊗ g 2 ⊕ 1 ⊖ g 1 ⊗ 1 ⊖ g 2We define EB protocol as EBsx,sy=g0. Notice that if g0=1, then sx=sy. Otherwise, sx≠sy.Left Shift Protocol. In floating-point number addition, it is necessary to unify the exponents of these floating-point numbers. Therefore, we propose the Left Shift (LS) protocol to adjust the significand of a floating-point number. Given a ciphertext of the significand sx and two ciphertexts of the exponents ex, ey, we calculate sx∗=sx·2ex-ey, where ex≥ey. The overall steps of LS protocol are shown as follows.Step 1.
Fori in 0,1,⋯,emax (emax is an extremal exponent as described in Section 3.2),(43)a=GTBex⊖ey,ib=EBex⊖ey,isx=1⊖a⊗1⊖b⊗2⊗sx
Returnsx∗=sx.We define LS protocol as(44)LSsx,ex⊖eysx·2ex-eyex≥eysxex<eyWe also propose floating-point number addition (FAdd) protocol and floating-point number multiplication (FMult) protocol to compute the addition and multiplication of the ciphertexts of the floating-point numbers. Suppose we have two floating-point numbers x=-1sx′·sx·2ex-k, y=-1sy′·sy·2ey-k. The ciphertexts are x=sx′,sx,ex and y=sy′,sy,ey respectively. The overall steps of FAdd protocol and FMult protocol are shown as follows.Floating-Point Number Addition ProtocolStep 1.
We need to check whether the signs ofx and y are consistent.(45)same_sign=sx′⊗sy′⊕1⊖sx′⊗1⊖sy′same_sign is the ciphertext for 1, when sx′=sy′, and same_sign is the ciphertext for 0, when sx′≠sy′. Supposing that sx′=sy′, the sign bit of x+y is sx′·sy′.Step 2.
Ifsx′≠sy′, the sign of x+y is the same as the sign of the larger between x and y, specifically, the sign bit of x+y is sd′ as follows:(46)sx∗=LSsx,ex⊖ey,sy∗=LSsy,ey⊖ex,Gs∗=GTBsx∗,sy∗sd′=1⊖Gs⊗sx′⊕Gs⊗sy′Step 3.
We calculate the sign of the addition ofx and y.(47)s+′=same_sign⊗sx′⊗sy′⊕1⊖same_sign⊗sd′Step 4.
Whensx′≠sy′, the significand of x+y is as follows:(48)sd=1⊖Gs⊗sx∗⊖sy∗⊕Gs⊗sy∗⊖sx∗Therefore, we calculate the final significand of the addition of x and y.(49)s+=same_sign⊗sx∗⊕sy∗⊕1⊖same_sign⊗sd=m+0m+1⋯m+k⋯m+k+lIt shows that s+ isk+l binary bits, and the precision of the result isk+l.Step 5.
Ifs+≥2k+ex-ey, it shows that the exponent of x+y is max⁡{ex,ey}+1. If s+<2k+ex-ey, it shows that the exponent of x+y is max⁡ex,ey. The construction is as follows:(50)Ge=GTBex,ey,emax=1⊖Ge⊗ex⊕Ge⊗eyed=1⊖Ge⊗ex⊖ey⊕Ge⊗ey⊖exGs+=GTBs+,LS2k,edWe calculate the exponent of the addition ofx andy.(51)e+=1⊖Gs+⊗emax⊕1⊕Gs+⊗emaxStep 6.
Finally, we need to keep the result significandk bits.(52)g+=EBm+k+1,1s+∗=g+⊗m+0m+1⋯m+k+1⊕1⊖g+⊗m+0m+1⋯m+kTherefore, s+∗ is k binary bits. The result of addition can be represented ass+′,s+∗,e+, specifically, FAddsx′,sx,ex,sy′,sy,ey=s+′,s+∗,e+.As above, the precision is stillk. Floating-point addition does not add additional relative error. For subsequent operations, the precision is still k, and the relative error Erel(x+y)≤0.5·21-k as in Section 3.2.Floating-Point Number Multiplication ProtocolStep 1.
First, we calculate the sign of the multiplication ofx and y.(53)s×′=sx′⊗1⊖sy′⊕1⊖sx′⊗sy′Step 2.
Then, we calculate the exponent.(54)e×=ex⊕eyStep 3.
Finally, we calculate the significand.(55)s×=sx⊗sy=mx0mx1⋯mxk⊗my0my1⋯myk=m×0m×1⋯m×km×k+1⋯m×2kIt shows that s× is 2k binary bits, and the precision of the result is 2k.Step 4.
Thereafter, we need to keep the result significandk bits.(56)g+=EBm×k+1,1s×∗=g+⊗m×0m×1⋯m×k+1⊕1⊖g+⊗m×0m×1⋯m×kTherefore, s×∗ is k binary bits. The result of multiplication can be represented as s×′,s×∗,e×, specifically,(57)FMultsx′,sx,ex,sy′,sy,ey=s×′,s×∗,e×.As above, the precision is stillk. According to Section 3.2, the upper bound of the relative error for multiplication will be twice the original, Erel(x·y)≤2·0.5·21-k. That is, after the n-layer multiplication operation, the upper bound will be 2n·0.5·21-k, which is the same as the floating-point number operation in plaintext.The FFHE scheme completely simulates a floating-point operation in plaintext in the form of a circuit so that the relative error of operation result in ciphertext is not increased compared with the result in plaintext.


## 7. Calculation Types Generalization of FFHE

In Sections5 and 6, we proposed our revised somewhat homomorphic encryption scheme (RSHE) and our floating-point fully homomorphic encryption scheme (FFHE). As we can see, FFHE only describe five basic protocols to achieve different floating-point numbers operations including addition and multiplication, and most of the current homomorphic encryption schemes also only involve addition and multiplication [2–5, 18]. However, complex functions taking floating-point numbers as input are more common in reality, and we also need to protect the privacy of input and output for these complex functions. For example, in the e-healthcare cloud service [14], we often require a mathematic modeling method to analyze patients’ health data, which may utilize some complex functions taking floating-point numbers as input. In this section, supporting calculation types of FFHE are generalized from addition and multiplication to analytic functions, for example, reciprocal function, exponential function, and logarithmic function. The evaluation of reciprocal function also provides a new ideal for computing division without privacy leakage.Definition 8 (function homomorphism).
Letf(x) be an analytic function, homomorphic encryption scheme that satisfies function homomorphism if(58)Decsk,f′Encpk,x=fxwhere f′ is a corresponding function operating over ciphertexts.Using Taylor series, our FFHE can homomorphically evaluate analytic functionsf(x) taking floating-point numbers as input. According to Section 6.3, FFHE achieves protocols of evaluating addition and multiplication for floating-point numbers, and polynomials consist of addition and multiplication. Therefore, FFHE can homomorphically evaluate polynomial function. The Taylor series establishes a connection between the analytic function and polynomial function. The definition of the Taylor series is as follows.Definition 9 (Taylor series).
The Taylor series of a real or complex-valued functionf(x) that is infinitely differentiable at a real or complex numbera is the power series:(59)fa+f′a1!x-a+f′′a2!x-a2+f′′′a3!x-a3+⋯which can be written in the more compact sigma notation as(60)∑n=0∞fnan!x-anwhere n! denotes the factorial of n and f(n)(a) denotes the n-th derivative f evaluated at the point a. The derivative of order zero of f is defined to be f and x-a0 and 0! are both defined to be 1. Whena=0, the series is also called a Maclaurin series.Utilizing the Taylor series, analytic functions can be rewritten as a combination of additions and multiplications, which provide a method for evaluating analytic functions without revealing privacy. However, the essential condition must be satisfied that is the independent variablex must be within the convergent domain. We cite reciprocal and exponent which can be rewritten as Taylor series in the example below. Let n is the degree of the polynomial. The larger the n, the smaller the error. Leta=0 below.Example 10.
reciprocalDescription: calculate the reciprocal ofx, that is, 1/x, without revealing the value of x.Taylor series:(61)1x=∑n=0∞-1nx-1n=1-x-1+⋯+-1nx-1n+-1n+1x-1n+11+θx-1n+2Convergent domain:0<x<2, where 0<θ<1.Error:Δ=max⁡-1n+1x-1n+1/1+θx-1n+2≤x-1n+1,x∈(0,2),0<θ<1The precision of floating-point numbers in our FFHE isk. If Δ<2-k, the Taylor polynomial cannot reduce the precision. Specifically, the degree n must satisfy(62)n>-klog⁡x-1-1Approximate calculation of the reciprocal with the Taylor series provides a method for calculating division.Example 11.
exponentDescription: calculate the exponent ofx, that is, ex.Taylor series:(63)ex=∑n=0∞xnn!=1+x+x22!+⋯+xnn!+eθx·xn+1n+1!Convergent domain:-∞<x<+∞, where 0<θ<1,Error:Δ=max⁡(eθx·xn+1)/(n+1)!<ex/(n+1)!xn+1,0<θ<1Letx=1, then e=1+1+1/2!+⋯+1/n!, and the error Δ<e/(n+1)!<3/(n+1)!, let n=10, e=2.718282, the error will not exceed 10-6.Other analytic functions, such as trigonometric functions, logarithmic functions, and variants of these functions, can also be rewritten as the Taylor series; however, the independent variable must be within the convergent domain. Below, we illustrate how to calculate beyond the convergent domain.As noted above, when calculating the reciprocal ofx, the convergent domain of x is (0,2). Suppose x=-1s′·s·2e-k; we can the transform the formula as(64)1x=1x·2-t=1-1s′·s·2e-t-k·2-tLet x∗=x·2-t∈(0,2), and the exponent of x∗ is e-t. Then, 1/(x·2-t) can be rewritten as the Taylor series as above within the convergent domain. The product of the Taylor series and 2-t is the approximate value of 1/x, with the precision loss of t bits. By increasing the value of n and k, the precision can be increased appropriately. If x<0, the approximate value can be calculated in the same way. Calculation of the other analytic functions with the independent variable being out of the convergent domain may be achieved by a similar method. Enlarging or reducing the range of independent variables is an efficient method to satisfy the condition of the convergent domain. Due to the variety and length restrictions of the paper, they are not addressed here.Precision can be improved by increasingn, but it leads to a higher computation complexity. According to the actual demand, we can determine the size of n to achieve balance between precision and computation complexity.FFHE scheme is a fully homomorphic encryption scheme that supports analytic function operations based on floating-point numbers. Table2 compares our FFHE scheme with [2–4, 6].Table 2
Performance comparison of fully homomorphic encryption scheme.
Scheme Size ofpk Size ofsk Expansion rate of ciphertext Computational complexity Process floating-point numbers operation Process analytic function operation DGHV [2] O ~ λ 13 O ~ λ 7 O ~ λ 5 O λ 5 No No [3] O ~ λ 13 O ~ λ 9 O ~ λ 3 O λ 3 No No [4] O ~ λ 8 O ~ λ 3 O ~ λ 5 O λ 4 No No [6] O ~ λ 7 O ~ λ 3.5 O ~ λ 3 O λ 3 No No FFHE O ~ λ 6 O ~ λ 5 O ~ λ 3 O λ 3 Yes Yes


## 8. Conclusion

In this paper, we followed Gentry’s blueprint to construct a revised fully homomorphic encryption scheme that supports many analytic function operations on floating-point numbers, not just addition and multiplication operations on integers. Through packaging a matrix of plaintext bits as a single ciphertext, we reduce the expansion rate of the ciphertext toO~λ3. At the same time, with a quadratic form instead of a linear form in three types of public key and multiple pseudo-random number generator, we reduce the public key size to O~λ6. We constructed a revised floating-point fully homomorphic encryption scheme (FFHE). The scheme remains semantically secure under the error-free approximate-GCD problem and sparse subset sum problem (SSSP). In FFHE, operation on the ciphertexts of floating-point numbers does not increase additional precision loss. That means addition does not raise the upper bound of the relative error, while n multiplication raises the upper bound of the relative error to n·0.5·21-k, as does the operation on plaintext of a floating-point number.



---

*Source: 2363928-2018-07-24.xml*