Printer Friendly

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

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 ofthe content. The idea of homomorphic encryption is as follows. Enc represents the encryption algorithm, and Dec represents the decryption algorithm. For a function f taking plaintexts [m.sub.0], [m.sub.1], ..., [m.sub.l] as inputs, there exists a function f taking the corresponding ciphertexts [c.sub.0], [c.sub.1], ..., [c.sub.l] as inputs, where [c.sub.i] = Enc([m.sub.i]), i = 0, 1, ..., l, such that

Dec (f' ([c.sub.0], [c.sub.1], ..., [c.sub.l])) = f ([m.sub.0], [m.sub.1], ..., [m.sub.l]) (1)

According 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 basedon[2], which is more effective than Corons 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 Section 2. 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, Brakerskietal. 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, Dij'k, 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 theBGV scheme. Costache[33] proposeda 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 number z, 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 [[z].sub.p] with -p/2 < [[z].sub.p] < p/2, or [<z>.sub.p] with 0 [less than or equal to] [<z>.sub.p] < p. Let [x.sup.*] be a real number. We use the notation x = fl([x.sup.*]) to represent the floating-point value of [x.sup.*] (the nearest number in the floating-point system). The most useful measures of the accuracy of x are its absolute error [E.sub.abs](x) = [absolute value of x - [x.sup.*]] and its relative error [E.sub.rel](x) = [absolute value of x - [x.sup.*]]/ [absolute value of [x.sup.*]] [19].

The parameters of the somewhat homomorphic DGHV scheme are shown in Section 4. Given the security parameter A, the following parameters are used:

[gamma] is the bit-length of the public keys.

[eta] is the bit-length of the secret keys.

[rho] is the bit-length of the first noise parameter.

[tau] is the number of the public keys.

[rho]' is the bit-length of the secondary noise parameter.

The other parameters used in our proposed schemes will be described in Sections 5 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]:

x = [(-1).sup.s'] x s x [b.sup.e-k] (2)

where s' [member of] {0,1} is the sign of x. b is the base or radix (b=2 in this paper). e is an integer such that [e.sub.min] [less than or equal to] e [less than or equal to] [e.sub.max], called

the exponent of the x, where [e.sub.min] and [e.sub.max] are two extremal exponents such that [e.sub.min] [less than or equal to] 0 [less than or equal to] [e.sub.max]. k is the precision (the number of significant digits in the significand), and s is the significant satisfying [b.sup.k-1] [less than or equal to] s [less than or equal to] [b.sup.k-1]. To determine accuracy, we define the quantity u = 0.5-[b.sup.1-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.sup.*](1 + [epsilon]) such that [E.sub.rel](x) = [absolute value of [epsilon]] [less than or equal to] 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 numbers [x.sup.*.sub.1], [x.sup.*.sub.2], [x.sub.1], [x.sub.2] represent the floating-point value of [x.sup.*.sub.1], [x.sup.*.sub.2], which is the nearest number in the floating-point system. For i = 1, 2, [x.sub.i] = [x.sup.*.sub.i] + [[DELTA].sub.i], where [[DELTA].sub.1], [[DELTA].sub.2] represent the absolute error of the real number and the floating-point number, which are subject to [absolute value of [[DELTA].sub.i]] [less than or equal to] 0.5 x [b.sup.e-k], [absolute value of [x.sup.*.sub.i]] > [b.sup.e-1], and the relative error is as follows:

[mathematical expression not reproducible] (3)

The addition of the two real numbers can be represented as [x.sup.*.sub.1] + [x.sup.*.sub.2] = [x.sub.1] + [[DELTA].sub.1] + [x.sub.2] + [[DELTA].sub.2], such that

[mathematical expression not reproducible] (4)

The 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

[mathematical expression not reproducible] (5)

such that

[mathematical expression not reproducible] (6)

For 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 [eta]-bit odd integer p, we use the following distribution over [gamma]-bit integers:

[mathematical expression not reproducible] (7)

DGHV.KenGen(A). Generate an [eta]-bit random prime integer p so that p [left arrow] (2Z +1) [intersection] [[2.sup.n,-1], [2.sup.[eta]]). For 0 [less than or equal to] i [less than or equal to] [tau], sample [x.sub.i] [left arrow] [D.sub.[gamma],[rho]](p). Relabel the [x.sub.i]'s so that [x.sub.0] is the largest. Restart unless [x.sub.0] is odd and [[[x.sub.0]].sub.p] is even. Let pk : <[x.sub.0], [x.sub.1], ..., [x.sub.[tau]]) and sk = p.

DGHV.Encrypt(pk, m [member of] {0,1}). Choose a random subset S [subset] {1, 2, ..., [tau]} and a random integer r in (-[2.sup.[rho]'], [2.sup.[rho]']), and output the ciphertext: [mathematical expression not reproducible].

DGHV.Evaluate(pk, C, [c.sub.1], [c.sub.2], ..., [c.sub.t]). Given the circuit C with t input bits and t ciphertexts [c.sub.i], 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 [left arrow] (c mod p)mod 2.

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 ([rho], [eta], [gamma]) approximate GCD problem is as follows: given a random [eta]-bit odd integer p and given many polynomial samples from [D.sub.[gamma],[rho]](p), in outputting p.

According to the scheme parameter constraints, the following parameters are suggested: [mathematical expression not reproducible]. The public key size is [??]([[lambda].sup.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 Section 4, the public key size of DGHV is [??]([[lambda].sup.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 [m.sub.0], ..., [m.sub.l-1], we packed plaintext matrix [{[m.sub.i,j]}.sub.1[less than or equal to]i,j[less than or equal to][mu]] with [[mu].sup.2] elements into a single ciphertext, where l = [[mu].sup.2]. Instead of working with integer [x'.sub.i,j] of the form [x'.sub.i,j] = [x.sub.i,0] x [x.sub.i,0] as in [21], we compressed all of the public keys used in RSHE in the same way, that is [mathematical expression not reproducible]2. Then, only 4[mu]+2[beta] integers need to be stored in the public key to generate 2[[mu].sup.2] + [[beta].sup.2] integers used for encryption in [3]. We considered a linear combination of the [[PI].sub.i,j] with coefficients in (-[2.sup.[alpha]'], [2.sup.[alpha]']), and a linear combination of the [x.sub.i,j] in (-[2.sup.[alpha]], [2.sup.[alpha]]) to further reduce the public key size. The detailed description of RSHE is as follows.

5.1. Description. KeyGen([lambda]): Choose [eta]-bit distinct primes [{[p.sub.u,v]}.sub.1[less than or equal to]u,v[less than or equal to][mu]], and denote n as their product, that is n = [{[[PI].sub.i,j]}.sub.1[less than or equal to]u,v[less than or equal to][mu]] [p.sub.u,v]. Define the error-free public key element [mathematical expression not reproducible]-rough integer. Initialize two pseudo-random number generators [f.sub.1] x, [f.sub.2], with two random seeds [se.sub.1], [se.sub.2] (the two pseudo-random number generator functions are independent of each other). Use [f.sub.1]([se.sub.1]) and [f.sub.2]([se.sub.2]) to generate a set of integers [[chi].sub.i,b] [member of] [0, [2.sup.[gamma]]), 1 [less than or equal to] i [less than or equal to] [beta], 0 [less than or equal to] b [less than or equal to] 1, let [tau] = [[beta].sup.2], compute the first set of public keys:

[mathematical expression not reproducible] (8)

where [mathematical expression not reproducible]. For all 1 [less than or equal to] i [less than or equal to] [beta] and 0 [less than or equal to] b [less than or equal to] 1, compute [x.sub.i,b] = [[delta]'.sub.i,b]. For noise parameters [mathematical expression not reproducible], compute the second set of public keys:

[mathematical expression not reproducible] (9)

For noise parameters [r'.sub.i,b,u,v] [left arrow] Z [intersection] (~[2.sup.[rho]], [2.sup.[rho]]), compute the third set of public keys:

[x'.sub.i,b] mod [p.sub.u,v] = 2[r'.sub.i,b,u,v] + [[delta].sub.i,b,u,v] (10)

We name [[delta].sub.i,b,u,v] v as the extended Kronecker function as follows (the definition of the Kronecker function is shown in [3]):

[mathematical expression not reproducible] (11)

and using the compression technique used for the first set of public keys, we can also compress [x.sub.0], let [[delta].sub.0] = [<[[chi].sub.0]>.sub.[pi]] + [[xi].sub.0] x [pi], and compute [x.sub.0] = [[chi].sub.0] - [[delta].sub.0].

Let [mathematical expression not reproducible].

Enc (pk), [{[m.sub.i,j]}.sub.1[less than or equal to]i,j[less than or equal to][mu]] [member of] [{0,1}.sub.[mu]x[mu]): Generate random integer matrix [mathematical expression not reproducible]. Output the ciphertext:

[mathematical expression not reproducible] (12)

Dec (sk, c): Output plaintext matrix m = [{[m.sub.i,j]}.sub.1[less than or equal to]i,j[less than or equal to][mu]]: [m.sub.i,j] = [[c mod [p.sub.i,j]].sub.2]

Evaluate (pk, C, [c.sub.1], ..., [c.sub.t]): as in the original DGHV scheme.

Add (pk, [c.sub.1], [c.sub.2]): Output: ([c.sub.1] + [c.sub.2]) mod [x.sub.0]

Mult (pk, [c.sub.1], [c.sub.2]): Output: ([c.sub.1] x [c.sub.2]) mod[x.sub.0]

5.2. Parameter Analysis. For the security parameters [lambda], we have the following constraints on our scheme parameters:

[rho] [greater than or equal to] 2[lambda]: 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].

[gamma] = [omega]([[eta].sup.2] x log [lambda]): for thwarting lattice-based attacks against the approximate GCD problem [2].

[eta] [greater than or equal to] [rho] x [THETA]([lambda] x [log.sup.2] [lambda]): for supporting homomorphic operations for evaluating the squashed decryption circuit [2].

[eta] [greater than or equal to] [alpha]' + [rho]' + 5 + 2 [log.sub.2] [beta]: for correct decryption of a ciphertext (Section 5.3).

To satisfy the above constraints, we can take [mathematical expression not reproducible]. As the ciphertexts are preserved in the form of a matrix, let l = [[mu].sup.2], the ciphertext expansion ratio is [gamma]/[[mu].sup.2] = O([[lambda].sup.3]), the new secret key size is [eta] x l = [??]([[lambda].sup.4]), as in [3]. However, compared to the ciphertext expansion ratio [gamma] = O([[lambda].sup.5]) in [2], our scheme has been greatly improved. The new public key for our revised somewhat homomorphic scheme has a size [mathematical expression not reproducible] instead of [??]([[lambda].sup.8]) as in [3] and [??]([[lambda].sup.8]) as in [4]. Though the public key size in [5] is [??]([[lambda].sup.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 [??]([[lambda].sup.5.5]); however, the value of the public key [x'.sub.i] 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 [x'.sub.i] is [??]([[lambda].sup.5]), and the actual public key size is at least [??]([[lambda].sup.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([[lambda].sup.5]) and the computational complexity of [4] is O([[lambda].sup.4]). Furthermore, the computational complexity of [3, 5] is all O([[lambda].sup.3]). Our scheme's computational complexity is O(2 x [[mu].sup.2] + [[beta].sup.2]) = O([[lambda].sup.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 Table 1.

5.3. Correctness. First, define the permitted circuits as follows.

Definition 2 (permitted circuit). For any i > 1, and any set of integer inputs all less than [[tau].sup.i] x [2.sup.i([alpha]'+[rho]'+2) in absolute value, it holds that the generalized circuit's output has an absolute value not exceeding [2.sup.i(n-3-m)], where n = [??][log.sub.2]([lambda] + 1)[??]. Let [C.sub.[epsilon]] denote the set of permitted circuits.

According to the above scheme, encrypt the plaintext matrix [m.sub.1], ..., [m.sub.t], and the ciphertext vector C = {[c.sub.1], ..., [c.sub.t]} generate, where [c.sub.i] = Encrypt(pk, [m.sub.i]). Let C be a circuit with t inputs and an output. We can decrypt properly, if

Decrypt (sk, Evaluate (pk, C, C)) = C ([m.sub.1], ..., [m.sub.t]) (13)

Lemma 3. Our somewhat homomorphic encryption scheme is correct for [C.sub.[epsilon]].

Proof. The ciphertext of our scheme is as follows:

[mathematical expression not reproducible] (14)

For 1 [less than or equal to] i, j [less than or equal to] [mu], we have:

[mathematical expression not reproducible] (15)

Let C be a Boolean circuit with t input [m.sub.1], ..., [m.sub.t], and let C' be the associated integer circuit where Boolean gates are replaced with integer operations with t ciphertexts [c.sub.1], ..., [c.sub.t] of plaintext [m.sub.1], ..., [m.sub.t] for input. For 1 [less than or equal to] i, j [less than or equal to] [mu], we have

[mathematical expression not reproducible] (16)

According to the Definition 2,

[mathematical expression not reproducible] (17)

so

[mathematical expression not reproducible] (18)

Then,

c mod [p.sub.i,j] = C' (q mod [p.sub.i,j], ..., [c.sub.t] mod [p.sub.i,j]) (19)

And

[mathematical expression not reproducible] (20)

Then, our scheme is correct for the permitted circuit [C.sub.[epsilon]].

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 Definition 2, ciphertext outputs have noise not exceeding [tau] x [2.sup.[alpha]'+[rho]+2]; after d multiplication, the new noise does not exceed ([tau] x [2.sup.[alpha]'+[rho]+2]).sup.d]; let d be the degree. Let f([x.sub.1], ..., [x.sub.t]) be the multivariate polynomial computed by C', and let [[parallel]f[parallel].sub.1] be the [l.sub.1] norm of the coefficient vector of f. Then, C [member of] [C.sub.[epsilon]] provided that [[parallel]f[parallel].sub.1] x ([tau] x [2.sup.[alpha]'+[rho]+2]).sup.d] [less than or equal to] [2.sup.[eta]-3-n], then,

[mathematical expression not reproducible] (21)

As in [5], we refer to polynomials f as permitted polynomials and denote the set of these polynomials by [P.sub.[epsilon]].

5.4. Semantic Security. Our scheme is semantically secure under a new assumption called the error-free-[[mu].sup.2]- approximate GCD assumption. Given integers [{[m.sub.u,v]}.sub.1[less than or equal to]u,v[less than or equal to][mu]], we define the following oracle [mathematical expression not reproducible] which, given as input a matrix m [member of] [{0, 1}.sup.[mu]x[mu]], outputs x with

[mathematical expression not reproducible] (22)

Where [[xi].sub.u,v] [left arrow] (-[2.sup.[rho]], [2.sup.[rho]]). We denote by [mathematical expression not reproducible] the unique integer x smaller than [x.sub.0] = [q.sub.0] x [{[[PI].sub.u,v]}.sub.1[less than or equal to]u,v[less than or equal to][mu]] [p.sub.u,v] such that x [equivalent to] [a.sub.u,v] mod [p.sub.u,v] for 1 [less than or equal to] w, v [less than or equal to] [mu]. Therefore, [mathematical expression not reproducible] outputs a ciphertext for the plaintext m.

Definition 4 (EF-[[mu].sup.2]-AGCD). The error-free-[[mu].sup.2]-approximate-GCD problem is as follows. Pick random [eta]-bit integers [mathematical expression not reproducible], integers [m.sub.u,v] = b. Given [mathematical expression not reproducible] and oracle access to [mathematical expression not reproducible], 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 p approximate-GCD assumption.

Proof. An attacker takes as input the public key and outputs two messages [m.sub.0] and [m.sub.1]. The challenger returns an encryption of [m.sub.b] 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 ciphertext c mod [x.sub.0], we associate the matrix:

[mathematical expression not reproducible] (23)

In the ciphertexts matrix, each ciphertext can be rewritten as a result of matrix operation, for 1 [less than or equal to] u, v [less than or equal to] [mu],

[mathematical expression not reproducible] (24)

where m is the matrix of plaintexts [mathematical expression not reproducible] are two vectors which contain random noise in the third set of public keys. b = [([b.sub.i,j]).sub.1[less than or equal to]i,j[less than or equal to][beta]] and b = [([b'.sub.i,j]).sub.1[less than or equal to]i,j[less than or equal to][beta]] are random integer matrixes. [mathematical expression not reproducible] contain random noise in the second set of public keys,

[mathematical expression not reproducible], (25)

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 [mathematical expression not reproducible] be uniform in

[mathematical expression not reproducible] (26)

Then, the statistical distance between the random variables u and [m.sub.u,v] + u does not exceed 1/([[mu].sup.2] x [2.sup.2[rho]+2](1 + [2.sup.[alpha]']) + [[beta].sup.2] x [2.sup.2[rho]+[alpha]]). Therefore,

[mathematical expression not reproducible] (27)

and Pr[[m.sub.u,v] = 0] = Pr[[m.sub.u,v] = 1] = 1/2.

This concludes the proof of Theorem 5.

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 [theta], [THETA], [kappa] be three new parameters, concretely, [theta] = [lambda], [THETA] = [??]([[lambda].sup.3]), [kappa] = [gamma] + 2 + [[??][log.sub.2]([theta] + 1) [??]. We add to the public key a set y = ([y.sub.0], ..., [y.sub.[THETA]-1]) of rational numbers in [0, 2) with [kappa] bits of precision after the binary point, such that for all 1 [less than or equal to] u, v [less than or equal to] [mu] there exists a sparse subset [mathematical expression not reproducible]. We also replace the secret key with the indicator vector of the subset [S.sub.u,v]. Formally, according to RSHE in Section 5.1, we define FFHE as follows.

(1) KeyGen([lambda]): Generate [mathematical expression not reproducible], choose at random [THETA]-bit vectors [s.sub.u,v] = {[s.sub.u,v,0], ..., [s.sub.u,v,[THETA]-1]}, each of Hamming weight [theta], for 1 [less than or equal to] u, v [less than or equal to] [mu]. Choose at random [THETA] integers [u.sub.i] [member of] [0, [2.sup.[kappa]+1]) for 0 [less than or equal to] i [less than or equal to] [THETA] - 1, fulfilling the condition that [mathematical expression not reproducible]. Each [y.sub.i] is a positive number smaller than two, with [kappa] bits of precision after the binary point, and verifies

1/[p.sub.u,v] = [[THETA]-1.summation over (i=0)] [s.sub.u,v,i] x [y.sub.i] + [[epsilon].sub.u,v] mod 2 (28)

for some [[absolute value of [[epsilon].sub.u,v]] < [2.sup.[kappa]].

As we set a new public key y = ([y.sub.0], ... > [y.sub.[theta]-1]) with k bits of precision after the binary point, the public key size is [THETA] x [kappa] = [??]([[lambda].sup.8]), instead of [??]([[lambda].sup.6]) as in our revised homomorphic encryption scheme. Using the public key compressing method proposed in Section 5.1, we also generate [y.sub.i] by using a pseudo-random generator f(se) with seed se. So, only se and [y.sub.0] must be stored in a public key. The new secret key is [sk.sup.*] = [{[s.sub.u,v]}.sub.1[less than or equal to]u,v[less than or equal to][mu]], and the new public key is [pk.sup.*] = (pk, [y.sub.0], se).

(2) Enc (pk, m): the same as Section 5.1 .

(3) Expand ([pk.sup.*], c): the ciphertext expansion procedure takes as input a ciphertext c and computes an expanded ciphertext: let [z.sub.i] = [[c x [y.sub.i]].sub.2] with n = [[log.sub.2] ([theta] + 1)] bits of precision after the binary point for 0 [less than or equal to] i [less than or equal to] [THETA] - 1. Output the expanded ciphertext (c, [z.sub.0], ... [z.sub.[THETA]-1]).

(4) Dec ([sk.sup.*], c, [z.sub.0], ... [z.sub.[THETA]-1]): output m = [{[s.sub.u,v]}.sub.1[less than or equal to]u,v[less than or equal to][mu]]: [m.sub.u,v] [left arrow] [[c - [[??][[summation].sup.[theta]-1.sub.i=0] [s.sub.u,v,i] * [z.subi][??]].sub.2]

Lemma 6. The scheme after squashing the decryption circuit is correct for the set C([P.sub.[epsilon]]) of circuits that compute permitted polynomials.

Proof. According to Lemma 3, the correct decrypted message m is given by ([??]c/[p.sub.i,j][??] mod 2) [direct sum] (c mod 2), so what we need to show is that

[mathematical expression not reproducible] (29)

Then,

[mathematical expression not reproducible] (30)

To satisfy the constraints on parameters, we have [mathematical expression not reproducible], so,

[mathematical expression not reproducible] (31)

then,

[mathematical expression not reproducible] (32)

The 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 [epsilon] be the scheme above and let [D.sub.[epsilon]] be the set of squashed decryption circuits. Then, [D.sub.[epsilon]] [subset] C([P.sub.[epsilon]]).

For each plaintext, the Expand procedures work naturally in parallel. For 1 [less than or equal to] w, v [less than or equal to] [mu], we consider the decryption equation:

[mathematical expression not reproducible] (33)

Except 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:

[mathematical expression not reproducible] (34)

where [u.sub.i]'s are known and the secret key [s.sub.u,v] = ([s.sub.u,v,0], ..., [s.sub.u,v,[THETA]-1]) is of small Hamming weight [theta]. We assume that the attack knows [p.sub.u,v] and therefore [mathematical expression not reproducible].

Our squashed scheme makes an additional batch operation based on [4]. Moreover, the Expand 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 [p.sub.u,v], the attack analysis is similar to [4].

According to the asymptotic analysis in [4, 36], we can take [gamma] = [??]([[lambda].sup.5]), [THETA] = [??]([[lambda].sup.3]) and [theta] = [lambda] to avoid known attacks on the sparse subset sum problem.

6.4. Floating-Point Calculation. According to Section 3.2, we denote a floating-point number x = [(-1).sup.s'] x s x [2.sup.e-k] (let b=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' [member of] {0,1} is the sign bit of x, s is a k-bits number. The encrypted floating-point number x is constructed as [[x]] = ([[[s'.sub.x]]], [[[s.sub.x]]], [[[e.sub.x]]]). Then, we define two types of circuit operations, "[direct sum]" as addition circuit and "[cross product]" 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 ciphertexts j and j, where [[[s.sub.x]]] and [[[s.sub.y]]] are all integers.

Define a bit b to be 1 if [s.sub.x] [greater than or equal to] [s.sub.y] 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 [[[s.sub.x]]] and [[[s.sub.y]]] without knowing the secret key.

[s.sub.x] and [s.sub.y] are signed integers. They can be expressed as binary numbers [s.sub.x] = [m.sup.0.sub.x][m.sup.1.sub.x] ... [m.sup.k.sub.x] and [s.sub.y] = [m.sup.0.sub.y] [m.sup.1.sub.y] ... [m.sup.k.sub.y] and [m.sup.0.sub.x], [m.sup.1.sub.y] are sign bits of [s.sub.x], [s.sub.y] respectively. Through the Boolean circuit, we can calculate [s.sub.x] - [s.sub.y] = [m.sup.0.sub.x][m.sup.1.sub.x] ... [m.sup.k.sub.x] - [m.sup.0.sub.y][m.sup.1.sub.y] ... [m.sup.k.sub.y]. We can use two's complement to achieve binary subtraction. For example,

[mathematical expression not reproducible] (35)

Specifically,

[mathematical expression not reproducible] (36)

Therefore, 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 [[s.sub.x]] and [[s.sub.x]], GTB protocol is to show [s.sub.x] [greater than or equal to] [s.sub.y] or [s.sub.x] < [s.sub.y]. The overall steps of GTB are shown as follows.

Step 1. We execute the subtraction circuit to calculate the ciphertexts of [s.sub.x] - [s.sub.y].

[mathematical expression not reproducible] (37)

The input of our FFHE scheme is binary bit; therefore, the ciphertext is

[mathematical expression not reproducible] (38)

and [m.sup.0.sub.z] is the sign bit of [s.sub.z].

Step 2. We need to check whether the signs of [s.sub.x] and [s.sub.y] are consistent.

[mathematical expression not reproducible] (39)

same_sign is the ciphertext for 1, when the signs of [s.sub.x] and [s.sub.y] are the same, and same.sign is the ciphertext for 0, when the signs of [s.sub.x] and [s.sub.y] are different.

Step 3.

[mathematical expression not reproducible] (40)

We define GTB protocol as GTB([[s.sub.x]], [[s.sub.y]]) = Gtb. Gtb is the ciphertext for 0, when [s.sub.x] [greater than or equal to] [s.sub.y], and Gtb is ciphertext for 1, when [s.sub.x] < [s.sub.y].

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 [[s.sub.x]] and [[s.sub.y]], the EB protocol is to show whether [s.sub.x] = [s.sub.y]. The overall steps of EB protocol are shown as follows.

Step 1. We execute GTB protocol to check [s.sub.x] > [s.sub.y] or [s.sub.x] < [s.sub.y].

[[g.sub.1]] = GTB ([[s.sub.x]], [[s.sub.y]]),

[[g.sub.2]] = GTB ([[s.sub.y]], [[s.sub.x]]), (41)

Step 2.

[mathematical expression not reproducible] (42)

We define EB protocol as EB([[s.sub.x]], [[s.sub.y]]) = [[g.sub.0]]. Notice that if [g.sub.0] = 1, then [s.sub.x] = [s.sub.y]. Otherwise, [s.sub.x] = [s.sub.y].

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 significant of a floating-point number. Given a ciphertext of the significant [[s.sub.x]] and two ciphertexts of the exponents [mathematical expression not reproducible], where [e.sub.x] [greater than or equal to] [e.sub.y]. The overall steps of LS protocol are shown as follows.

Step 1. For i in [0, 1, ..., [e.sub.max]] ([e.sub.max] is an extremal exponent as described in Section 3.2),

[mathematical expression not reproducible]. (43)

We define LS protocol as

[mathematical expression not reproducible] (44)

We 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 [mathematical expression not reproducible]. The ciphertexts are [[x]] = ([[s'.sub.x]], [[s.sub.x]], [[e.sub.x]]) and [[y]] = ([[s'.sub.y]], [[s.sub.y]], [[e.sub.y]]) respectively. The overall steps of FAdd protocol and FMult protocol are shown as follows.

Floating-Point Number Addition Protocol

Step 1. We need to check whether the signs of x and y are consistent.

[mathematical expression not reproducible] (45)

same_sign is the ciphertext for 1, when [s'.sub.x] = [s'.sub.y], and same_sign is the ciphertext for 0, when [s'.sub.x] [not equal to] [s'.sub.y]. Supposing that [s'.sub.x] = [s'.sub.y], the sign bit of x + y is [s'.sub.x] * [s'.sub.y].

Step 2. If [s'.sub.x] [not equal to] [s'.sub.y], the sign of x + y is the same as the sign of the larger between [absolute value of x] and [absolute value of y], specifically, the sign bit of x + y is [s'.sub.d] as follows:

[mathematical expression not reproducible] (46)

Step 3. We calculate the sign of the addition of x and y.

[mathematical expression not reproducible] (47)

Step 4. When [s'.sub.x] [not equal to] [s'.sub.y], the significant of x + y is as follows:

[mathematical expression not reproducible] (48)

Therefore, we calculate the final significant of the addition of x and y.

[mathematical expression not reproducible] (49)

It shows that [s.sub.+] is k+l binary bits, and the precision of the result is k+l.

Step 5. If [mathematical expression not reproducible], it shows that the exponent of x + y is [mathematical expression not reproducible], it shows that the exponent of x + y is max{[e.sub.x], [e.sub.y]}. The construction is as follows:

[mathematical expression not reproducible] (50)

We calculate the exponent of the addition of x and y.

[mathematical expression not reproducible] (51)

Step 6. Finally, we need to keep the result significant k bits.

[mathematical expression not reproducible] (52)

Therefore, [s.sup.*.sub.+] is k binary bits. The result of addition can be represented as([s+], [s;], [e+]), specifically, FAdd(([[s'.sub.x]], [[s.sub.x]], [[e.sub.x]]), ([[s'.sub.y]], [[s.sub.y]], [[e.sub.y]])) = ([[s'.sub.y]], [[s.sup.*.sub.+]], [[e.sub.+]]).

As above, the precision is still k. Floating-point addition does not add additional relative error. For subsequent operations, the precision is still k, and the relative error [E.sub.rel(x+y) [less than or equal to] 0.5 x [2.sup.1-k] as in Section 3.2.

Floating-Point Number Multiplication Protocol

Step 1. First, we calculate the sign of the multiplication of x and y.

[mathematical expression not reproducible] (53)

Step 2. Then, we calculate the exponent.

[[e.sub.x]] = [[e.sub.x]] [direct sum] [[e.sub.y]] (54)

Step 3. Finally, we calculate the significant.

[mathematical expression not reproducible] (55)

It shows that [s.sub.x] is 2k binary bits, and the precision of the result is 2k.

Step 4. Thereafter, we need to keep the result significant k bits.

[mathematical expression not reproducible] (56)

Therefore, [s.sup.*.sub.x] is k binary bits. The result of multiplication can be represented as ([[s'.sub.x]], [[s.sup.*.sub.x]], [[e.sub.x]], specifically,

[mathematical expression not reproducible]. (57)

As above, the precision is still k. According to Section 3.2, the upper bound of the relative error for multiplication will be twice the original, [E.sub.rel(x x y) [less than or equal to] 2 x 0.5 x [2.sup.1-k]. That is, after the n-layer multiplication operation, the upper bound will be [2.sup.n] x 0.5 x [2.sup.1-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 Sections 5 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). Let f(%) be an analytic function, homomorphic encryption scheme that satisfies function homomorphism if

Dec (sk, f' (Enc (pk, x))) = f (x) (58)

where f' is a corresponding function operating over ciphertexts.

Using Taylor series, our FFHE can homomorphically evaluate analytic functions f(%) 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 function f(%) that is infinitely differentiable at a real or complex number a is the power series:

[mathematical expression not reproducible] (59)

which can be written in the more compact sigma notation as

[[infinity].summation over (n=0)] [f.sup.(n)] (a)/n! [(x - a).sup.n] (60)

where n! denotes the factorial of n and [f.sup.(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 - a).sup.0] and 0! are both defined to be 1. When a=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 variable x 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. Let a=0 below.

Example 10. reciprocal

Description: calculate the reciprocal of x, that is, 1/x, without revealing the value of x.

Taylor series:

[mathematical expression not reproducible] (61)

Convergent domain: [mathematical expression not reproducible]

The precision of floating-point numbers in our FFHE is k. If [absolute value of [DELTA]] < [2.sup.-k], the Taylor polynomial cannot reduce the precision. Specifically, the degree n must satisfy

n > -k/log (x - 1) (62)

Approximate calculation of the reciprocal with the Taylor series provides a method for calculating division.

Example 11. exponent

Description: calculate the exponent of x, that is, ex. Taylor series:

[mathematical expression not reproducible] (63)

Convergent domain: -[mathematical expression not reproducible]

Let x = 1, then e = 1 + 1 + 1/2! + ... + 1/n!, and the error [absolute value of [DELTA]] < e/(n + 1)! < 3/(n + 1)!, let n =10, e = 2.718282, the error will not exceed [10.sup.-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 of v, the convergent domain of v is (0, 2). Suppose v = [(-1).sup.s'] x s x [2.sup.e-k]; we can the transform the formula as

1/x = 1/x x [2.sup.-t] = 1/[(-1).sup.s'] x s x [2.sup.e-t-k] x [2.sup.-t] (64)

Let [x.sup.*] = x x [2.sup.-t] [member of] (0, 2), and the exponent of [x.sup.*] is e - 1. Then, 1/(x x [2.sup.-t]) can be rewritten as the Taylor series as above within the convergent domain. The product of the Taylor series and [2.sup.-t] is the approximate value of 1/v, 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 increasing n, 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. Table 2 compares our FFHE scheme with [2-4,6].

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 to [??]([[lambda].sup.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 [??]([[lambda].sup.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 x 0.5 x [2.sup.1-k], as does the operation on plaintext of a floating-point number.

https://doi.org/10.1155/2018/2363928

Data Availability

The data used to support the findings of this study are available from the corresponding author upon request.

Conflicts of Interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (61572263, 61502251, and 61502243), the University Natural Science Research Project of Jiangsu Province (14KJB520031), and Postdoctoral Science Foundation Project of China (2016M601859).

References

[1] D. G. Feng, M. Zhang, Y. Zhang, and Z. Xu, "Study on cloud computing security," Journal of Software, vol. 22, no. 1, pp. 71-83, 2011.

[2] M. Van Dijk, C. Gentry, S. Halevi, and V Vaikuntanathan, "Fully homomorphic encryption over the integers," in Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 24-43, Springer, Berlin, Germany, 2010.

[3] J. H. Cheon, J. S. Coron, J. Kim et al., "Batch fully homomorphic encryption over the integers," in Annual International Conference on the Theory and Applications of Cryptographic Techniques, vol. 7881 of Lecture Notes in Computer Science, pp. 315-335, Springer, Berlin, Germany, 2013.

[4] J.-S. Coron, A. Mandal, D. Naccache, and M. Tibouchi, "Fully homomorphic encryption over the integers with shorter public keys," in Annual Cryptology Conference, pp. 487-504, Springer, Heidelberg, Germany, 2011.

[5] J.-S. Coron, D. Naccache, and M. Tibouchi, "Public key compression and modulus switching for fully homomorphic encryption over the integers," in Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 446-464, Springer, Berlin, Germany, 2012.

[6] W. J. Xiong, Y. Z. Wei, and H. Y. Wang, "An improved fully homomorphic encryption scheme over the integers," Journal of Cryptologic Research, vol. 3, no. 1, pp. 67-78, 2016.

[7] R. A. Popa, C. M. S. Redfield, N. Zeldovich, and H. Balakrishnan, "CryptDB: protecting confidentiality with encrypted query processing," in Proceedings of the 23rd ACM Symposium on Operating Systems Principles (SOSP '11),pp. 85-100, October 2011.

[8] R. A. Popa, C. M. S. Redfield, N. Zeldovich, and H. Balakrishnan, "CryptDB: Processing queries on an encrypted database," Communications of the ACM, vol. 55, no. 9, pp. 103-111, 2012.

[9] W. K. Wong, B. Kao, D. W. L. Cheung, R. Li, and S. M. Yiu, "Secure query processing with data interoperability in a cloud database environment," in Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD '14), pp. 1395-1406, ACM, June 2014.

[10] K. Xue, S. Li, J. Hong, Y. Xue, N. Yu, and P. Hong, "Two-cloud secure database for numeric-related SQL range queries with privacy preserving," IEEE Transactions on Information Forensics and Security, vol. 12, no. 7, pp. 1596-1608, 2017

[11] P. Paillier, "Public-key cryptosystems based on composite degree residuosity classes," in Proceedings of the 18th Annual International Conference on the Theory and Applications of Cryptographic Techniques, vol. 547, pp. 223-238, Springer, 1999.

[12] N. P. Smart and F. Vercauteren, "Fully homomorphic encryption with relatively small key and ciphertext sizes," in International Workshop on Public Key Cryptography, pp. 420-443, Springer, Berlin, Germany, 2010.

[13] C. Gentry, S. Halevi, and N. P. Smart, "Better bootstrapping in fully homomorphic encryption," in International Workshop on Public Key Cryptography, pp. 1-16, Springer, Heidelberg, Germany, 2012.

[14] X. Liu, R. Lu, J. Ma, L. Chen, and B. Qin, "Privacy-preserving patient-centric clinical decision support system on Naive Bayesian classification," IEEE Journal of Biomedical and Health Informatics, vol. 20, no. 2, pp. 655-668, 2016.

[15] R. L. Rivest, A. Shamir, and L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, ACM, 1983.

[16] C. Gentry, "Fullyhomomorphic encryption using ideal lattices," Proceedings of the Annual ACM Symposium on Theory of Computing, vol. 9, no. 4, pp. 169-178, 2009.

[17] C. Gentry, A Fully Homomorphic Encryption Scheme, Stanford University, 2009.

[18] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, "(Leveled) fully homomorphic encryption without bootstrapping," in Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 309-325, ACM, 2012.

[19] N. J. Higham, Accuracy and Stability of Numerical Algorithm, Society for Industrial and Applied Mathematics, Philadelphia, Pa, USA, 2nd edition, 2002.

[20] R. L. Rivest, L. Adleman, and M. L. Dertouzos, "On data banks and privacy homomorphisms," Foundations of Secure Computation, vol. 4, no. 11, pp. 169-180, 1978.

[21] C. Gentry and S. Halevi, "Implementing Gentry's fully homomorphic encryption scheme," in Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 129-148, Springer, Heidelberg, Germany, 2011.

[22] J. W. Bos, K. Lauter, J. Loftus, and M. Naehrig, "Improved security for a ring-based fully homomorphic encryption scheme," in IMA International Conference on Cryptography and Coding, pp. 45-64, Springer, Heidelberg, Germany, 2013.

[23] C. Gentry, A. Sahai, and B. Waters, "Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based," in Advances in Cryptology-CRYPTO 2013, pp. 75-92, Springer, Berlin, Germany, 2013.

[24] Z. Li, C. Ma, L. Zhang, and W. Zhang, "Two types LWE-based multi-bit lattice-based encryption schemes," Netinfo Security, no. 10, pp. 1-17, 2017

[25] Z. G. wang, C. G. Ma, and X. Q. Shi, "Research on full homomorphic encryption scheme based on binary LWE," Netinfo Security, no. 7, pp. 41-50, 2015.

[26] H. Wang, "Identity-based distributed provable data possession in multi-cloud storage," IEEE Transactions on Services Computing, vol. 8, no. 2, pp. 328-340, 2015.

[27] H. Wang, "Proxy provable data possession in public clouds," IEEE Transactions on Services Computing, vol. 6, no. 4, pp. 551-559, 2013.

[28] H. Wang, D. He, and J. Han, "VOD-ADAC: anonymous distributed fine-grained access control protocol with verifiable outsourced decryption in public cloud," IEEE Transactions on Services Computing, 2017

[29] H. Wang, D. He, J. Yu, and Z. Wang, "Incentive and unconditionally anonymous identity-based public provable data possession," IEEE Transactions on Services Computing, 2016.

[30] S. Arita and S. Nakasato, "Fully homomorphic encryption for point numbers," Cryptology ePrint Archive Report 2016/402, 2016, http://eprint.iacr.org/2016/402.

[31] J. Fan and F. Vercauteren, "Somewhat practical fully homomorphic encryption," Cryptology ePrint Archive Report 2012/144, 2012, http://eprint.iacr.org/2012/144.

[32] J. H. Cheon, A. Kim, M. Kim et al., "Floating-point homomorphic encryption," Cryptology ePrint Archive Report 2016/421, Cryptology ePrint Archive, 2016, http://eprint .iacr.org/2016/421.

[33] A. Costache, N. P. Smart, S. Vivek et al., "Fixed point arithmetic in she schemes," Cryptology ePrint Archive Report 2016/250, 2016, http://eprint.iacr.org/2016/250.

[34] X. Liu, R. H. Deng, W. Ding, R. Lu, and B. Qin, "Privacy-preserving outsourced calculation on floating point numbers," IEEE Transactions on Information Forensics and Security, vol. 11, no. 11, pp. 2513-2527, 2016.

[35] Y. Chen and P. Q. Nguyen, "Faster algorithms for approximate common divisors: breaking fully-homomorphic-encryption challenges over the integers," in International Conference on the Theory and Applications of Cryptographic Techniques, pp. 502519, Springer, Berlin, Germany, 2012.

[36] M. J. Coster, A. Joux, B. A. LaMacchia, A. M. Odlyzko, C.P. Schnorr, and J. Stern, "Improved low-density subset sum algorithms," Computational Complexity, vol. 2, no. 2, pp. 111-128, 1992.

Shuangjie Bai (iD), (1) Geng Yang (iD), (1,2,3) Jingqi Shi (iD), (1) Guoxiu Liu, (1) and Zhaoe Min (1)

(1) College of Computer Science, Nanjing University of Posts and Telecommunication, Nanjing 210003, China

(2) Key Laboratory of Broadband Wireless Communication & Sensor Networks Technology of Ministry of Education, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

(3) Jiangsu Key Laboratory of Big Data Security & Intelligent Processing, Nanjing, Jiangsu 210023, China

Correspondence should be addressed to Geng Yang; yangg@njupt.edu.cn

Received 29 January 2018; Revised 19 May 2018; Accepted 5 June 2018; Published 24 July 2018

Academic Editor: Roberto Di Pietro
Table 1: Performance comparison of somewhat homomorphic encryption
scheme.

Scheme             Size of pk                Size of sk

DGHV [2]     [??]([[lambda].sup.10])   [??]([[lambda].sup.2])
[3]          [??]([[lambda].sup.8])    [??]([[lambda].sup.4])
[4]          [??]([[lambda].sup.7])    [??]([[lambda].sup.2])
[5]          [??]([[lambda].sup.5])    [??]([[lambda].sup.2])
[6]          [??]([[lambda].sup.7])    [??]([[lambda].sup.4])
RSHE         [??]([[lambda].sup.6])    [??]([[lambda].sup.4])

Scheme          Expansion rate of           Computational
                   ciphertext                complexity

DGHV [2]     [??]([[lambda].sup.5])      O([[lambda].sup.5])
[3]          [??]([[lambda].sup.3])      O([[lambda].sup.3])
[4]          [??]([[lambda].sup.5])      O([[lambda].sup.4])
[5]          [??]([[lambda].sup.5])      O([[lambda].sup.3])
[6]          [??]([[lambda].sup.3])      O([[lambda].sup.3])
RSHE         [??]([[lambda].sup.3])      O([[lambda].sup.3])

Table 2: Performance comparison of fully homomorphic encryption
scheme.

Scheme           Size of pk                Size of sk

DGHV [2]   [??]([[lambda].sup.13])   [??]([[lambda].sup.7])
[3]        [??]([[lambda].sup.13])   [??]([[lambda].sup.9])
[4]        [??]([[lambda].sup.8])    [??]([[lambda].sup.3])
[6]        [??]([[lambda].sup.7])    [??]([[lambda].sup.35])
FFHE       [??]([[lambda].sup.6])    [??]([[lambda].sup.5])

Scheme        Expansion rate of           Computational
                 ciphertext                complexity

DGHV [2]   [??]([[lambda].sup.5])      O([[lambda].sup.5])
[3]        [??]([[lambda].sup.3])      O([[lambda].sup.3])
[4]        [??]([[lambda].sup.5])      O([[lambda].sup.4])
[6]        [??]([[lambda].sup.3])      O([[lambda].sup.3])
FFHE       [??]([[lambda].sup.3])      O([[lambda].sup.3])

Scheme     Process floating-point       Process analytic
              numbers operation        function operation

DGHV [2]             No                        No
[3]                  No                        No
[4]                  No                        No
[6]                  No                        No
FFHE                 Yes                       Yes
COPYRIGHT 2018 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2018 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Bai, Shuangjie; Yang, Geng; Shi, Jingqi; Liu, Guoxiu; Min, Zhaoe
Publication:Security and Communication Networks
Geographic Code:4EUGE
Date:Jan 1, 2018
Words:10428
Previous Article:WS N: Wireless Secure SDN-Based Communication for Sensor Networks.
Next Article:Improved Malware Detection Model with Apriori Association Rule and Particle Swarm Optimization.
Topics:

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |