Homomorphic Encryption (HE) is a new cryptographic topic that allows untrusted parties to compute over encrypted data. This new encryption scheme is v... Encryption - Public key - Silicon - Lattices - Switches - cryptography - cryptographic techniques - encrypted data - encrypted query - Dijk-Gentry-Halevi-Vaikutanathan - Brakerski-Gentry-Vaikunathan - BGV fully homomorphic encryption schemes - cryptographic topic - encryption scheme - cloud scenario - lattice based encryption - DGHV fully homomorphic encryption schemes - HE - FHE - DGHV - BGV - BV - LWE

80 downloads 963 Views 342KB Size

On DGHV and BGV Fully Homomorphic Encryption Schemes Khalil Hariss1,2

Maroun Chamoun2

Abed Ellatif Samhat1

1 Lebanese University-Faculty of Engineering- CRSI, Hadath, Lebanon Saint Joseph University-Faculty of Engineering-CMTI, Mar Roukoz, Lebanon [email protected]; [email protected]; [email protected]

2

scheme of BGV is homomorphic for a limited number of circuit depth. Modulus switching is a new technique used to make the scheme fully homomorphic and supports an unlimited circuit depth. But DGHV and BGV are not practical for real world applications due to storage overhead. The rest of this paper is decomposed as follow: In section II, we introduce the properties of FHE as well as the definition of the asymmetric homomorphic encryption scheme. In section III, we present in detail DGHV scheme in both symmetric and asymmetric scenarios. BV-BGV schemes are discussed in section IV. Finally, we conclude this paper by a comparison between DGHV and BV-BGV in section V.

Abstract—Homomorphic Encryption (HE) is a new cryptographic topic that allows untrusted parties to compute over encrypted data. This new encryption scheme is very famous in a cloud scenario, because it leverages cryptographic techniques in the cloud by allowing it to store encrypted data, and to process encrypted query over it. In this paper, we consider two important HE schemes: Dijk-Gentry-Halevi-Vaikutanathan (DGHV) and, Brakerski-Gentry-Vaikunathan (BV-BGV). The first one is based on computing over real integers while the other one is based on LWE (Lattice based Encryption). We present a detailed explanation of both schemes showing their efficient techniques including Bootstrapping and Modulus switching and we finally draw several conclusions. Keywords—HE, FHE, DGHV, BGV, BV, LWE.

I.

INTRODUCTION

Homomorphic Encryption (HE) is a modern cryptographic technique that will be used for cloud systems. HE provides privacy and protection in the cloud setting. Users storing their encrypted data at the cloud side, can send encrypted queries to the cloud and the latter is able to perform encrypted queries over encrypted data. In addition to cloud querying, HE can be used in a lot of real world modern applications such as eVoting, Spam filters, Attribute Based Encryption (ABE)[1], Data aggregation [2], etc. Fig. 1 shows an implementation of HE in real world applications. In 1978, Rivest et al.[3] introduced the notion of Privacy Homomorphism that allows partial computations over encrypted data. Since this date, designing and implementing a Fully Homomorphic Encryption (FHE) scheme that allows full computation over encrypted data, became a big challenge for researchers and cryptographers. Several works had considered the design and implementation of such scheme. Pallier Encryption Scheme [4] is an additive homomorphic encryption scheme that allows only add operations over encrypted data, Domingo Ferrer Crypto-system [5], [6] is a FHE scheme based on polynomial calculations. MORE, Enhanced MORE [7], [8] and PORE [9], are FHE schemes based on linear equations. The most valued work was introduced by Craig Gentry in 2009 [10], [11]. Several works followed Gentry’s contribution and the most two important schemes are: The DGHV which is an asymmetric encryption scheme based on the computation over real integers ([12], [13]). The basic DGHV scheme provides the homomorphic behavior for a limited circuit depth. Bootstrapping ([12], [13]) is a technique introduced in the literature to make the scheme fully homomorphic and supports unlimited circuit depth. Another important Encryption scheme is the BGV scheme ([16][17]). It is based on the hardness of Learning With Error (LWE). The basic

Fig. 1. Homomorphic implementation

II.

HOMOMORPHIC ENCRYPTION

We give in this section an explanation about homomorphic encryption mainly for an asymmetric scenario. A. Homomorphic Scheme An asymmetric homomorphic encryption scheme ԑ is defined by 4 functions: - KeyGenH(): generates pair of keys, public key pk and secret key sk. - EncryptH(pk,Si): outputs a cipher-text ψi, where Si is a plaintext. - DecryptH(sk, ψi): outputs the plain text Si, where ψi is a cipher-text. - EvaluateH: This function takes as input the public key pk, a circuit ܥand a tuple of cipher-texts ߖ ߖ ൌ ሺ߰ଵ ǡ ߰ଶ ǡ ߰ଷ ǡ ǥ Ǥ Ǥ ǡ ߰௧ ሻǤ

1

The evaluation function outputs a cipher-text ߰. ߰ ൌ ݁ݐܽݑ݈ܽݒܧᡅ ሺ݇ǡ ܥǡ ߖሻ The scheme is homomorphic if ߰ ൌ ݐݕݎܿ݊ܧᡅ ሺ݇ǡ ܥሺߨଵ ǡ ߨଶ ǡ ߨଷ ǡ ǥ Ǥ ǡ ߨ௧ ሻሻ.

ܿଵ ܿ כଶ ൌ ሺݍଵ ݍଶ ʹݎଶ ݍଵ ݍଵ ݉ଶ ʹݍଶ ݎଵ ݉ଵ ݍଶ ሻ ʹሺʹݎଵ ݎଶ ݉ଶ ݎଵ ݉ଵ ݎଶ ሻ ݉ଵ ݉ଶ Ǥ

(1)

B. Homomorphic Properties As written in equation (1), we are computing any function ݂, that the circuit ܥperforms, over the encrypted data. Any function ݂ can be written as Boolean function. Any Boolean is written as a polynomial form and since any polynomial form is a set of addition and multiplication operations, to build a FHE scheme we should satisfy the two following homomorphic properties: 1) Addition: ܿ݊ܧᡅ ሺ݇ǡ ݔଵ ሻ ܿ݊ܧᡅ ሺ݇ǡ ݔଶ ሻ ൌ ܿ݊ܧᡅ ሺ݇ǡ ݔଵ ݔଶ ሻ (2) 2) Multiplication: ܿ݊ܧᡅ ሺ݇ǡ ݔଵ ሻ ܿ݊ܧ כᡅ ሺ݇ǡ ݔଶ ሻ ൌ ܿ݊ܧᡅ ሺ݇ǡ ݔଵ ݔ כଶ ሻ (3) Where ݔଵ ǡ ݔଶ are two plain-texts ሼͲǡͳሽ and EncH(pk,x) is the Encryption function.

Decryption works as long as ʹሺʹݎଵ ݎଶ ݉ଶ ݎଵ െ ݉ଵ ݎଶ ሻ߳ൣ ൗʹ ǡ ൗʹ൧Ǥ This scheme seems to be “Somewhat homomorphic”, it can be used to evaluate circuits with limited depth. To make the scheme fully homomorphic by reducing the noise level, bootstrapping is a new technique ([12], [13]) introduced in the literature. B. Asymmetric scheme: 1) Secret parameters: The DGHV scheme is built based on the symmetric scheme given in section A, using six different parameters as follow and Table I shows the different values: λ: Security parameter used by KeyGen. γ: is the bit length of the integer in the public key. η: is the bit length of the secret key. ρ: is the bit length of the noise. τ: is the number of integer in the public key. ߩᇱ ǣ Secondary noise parameter.

III. DGHV SCHEME This scheme is built upon integers, the first step to build DGHV is to consider the following symmetric scheme: A. Symmetric scheme:

TABLE I.

1) The basic symmetric scheme The secret key is an odd integer, chosen from some interval ߳ሾʹఎିଵ ǡ ʹఎ ሻ where η is the bit length of the secret key. The cipher-text of a plain-text ݉߳ሼͲǡͳሽ is given by:

ܿ ൌ ݐݕݎܿ݊ܧሺǡ ݉ሻ ൌ ݍ ʹ ݎ ݉

(4)

ݐݕݎܿ݁ܦሺǡ ݉ሻ ൌ ሺܿ݉݀ሻ݉ʹ݀

(5)

݉ᇱ ՚ ሾܿ െ උܿൗඇሿଶ

(6)

2) Homomorphic behavior: Suppose that we have two plain-texts݉ଵ ǡ ݉ଶ , with two cipher-texts respectively ܿଵ ൌ ݍଵ ʹݎଵ ݉ଵ , ܿଶ ൌ ݍଶ ʹݎଶ ݉ଶ Ǥ a) Addition: ܿͳ ܿʹ ൌ ൫ ͳݍ ʹݍ൯ ʹሺ ͳݎ ʹݎሻ ݉ͳ ݉ʹ (7) long

as

value ჯሺ ߣሻ ߩǤ ˁሺߣ݈݃ଶ ߣሻ ჯ(ߟ ଶ ߣ) γ + ჯ(݈ߣ݃ሻ ρ+ ჯሺ ߣሻ

2) Scheme Construction: For a specific ሺߟܾ݅ݏݐሻ odd positive integer , we use the following distribution over γ-bit integers: ఊ ܦఊǡఘ ሺሻ ൌ ሼ݄ܿ ݍ݁ݏ՚ Ժ תቂͲǡ ʹ ൗቁǡ ݎ՚ Ժ תሺെʹఘ ǡ ʹఘ ሻǣ ݔݐݑݐݑൌ ݍ ݎሽ ݊݁ܩݕ݁ܭሺߣሻ: The secret key is an odd η-bit integer: ՚ ሺʹԺ ͳሻ תሾʹఎିଵ ǡ ʹఎ ሻǤ For the public key, sample ݔ ՚ ܦఊǡ for ݅ ൌ Ͳǡ ǥ ǥ ǡ ߬. Relabel so that ݔ is the largest. Restart unless ݔ is odd and ݎ ሺݔ ሻis even. The public key is ݇ൌ ݔۃ ǡ ݔଵ ǡ ǥ Ǥ Ǥ ǡ ݔఛ ۄ. Choose a random subset ݐݕݎܿ݊ܧሺ݇ǡ ݉߳ሼͲǡͳሽሻǤ ఘᇲ ఘᇲ ሼͳǡʹǡ ܵ ك ǥ Ǥ ǡ ߬ሽ and a random integer ݎin ൫െʹ ǡ ʹ ൯ǡ and output

The decryption works as long as the noise ݎis much smaller than Ǥ Computing the decryption equation is also possible by the following equation:

as

SECURITY PARAMETERS

parameter ρ η γ τ ߩᇱ

Where the integers ݍǡ ݎare chosen randomly in some other intervals, such that ʹ ݎis smaller than ൗʹ in absolute value. In this scheme, the cipher-text is an integer whose residue ݉݀has the same parity of the plaintext ݉Ǥ

Decryption works െ ݎଶ ሻ߳ሾ ൗʹ ǡ ൗʹሿ.

(8)

ܿ ՚ ሾ݉ ʹ ݎ ʹ

ʹሺݎଵ

ఢௌ

ݔ ሿ

(9)

௫బ

݁ݐܽݑ݈ܽݒܧሺ݇ǡ ܥǡ ܿଵ ǡ ܿଶ ǡ ǥ Ǥ Ǥ ǡ ܿ௧ ሻǣ Given the (binary) circuit ܥ with ݐinputs, and ݐciphertexts ܿ ǡ apply the (integer) addition and multiplication gates of ܥto the cipher-texts, performing all the operations over the integers, and return the resulting integer.

b) Multiplication:

2

ሼͳǡʹǡ͵ǡ ǥ ǡ ߆ሽ of size θ with σఢௌ ݕ ൎ ͳൗ ሺ݉ʹ݀ሻ. We also replace the secret key by the indicator vector of the subset ܵ. In more details, we modify the encryption scheme from section B as follows: a) ݊݁ܩݕ݁ܭ. : Generates כ ݇ݏൌ and כ ݇as before. Set ݔ ՚ ቔʹ ൗቓ, choose at random a Θ bit vector with hamming weight θ, ݏԦ ൌ ݏۃଵ ǡ ݏଶ ǡ ǥ Ǥ ǡ ۄ ௵ݏ, and let ܵ ൌ ሼ݅ǣݏ ൌ ͳሽǤ Choose at random integers ݑ ܼ߳ תሾͲǡ ʹାଵ ሻǡ ݅ ൌ ͳǡ ǥ Ǥ Ǥ ǡ ߆, subject to the condition that σఢௌ ݑ ൌ ݔ ሺ݉ʹ݀ାଵ ሻǤ Set ݑ ݕ ൌ ൗʹ and ݕԦ ൌ ሼݕଵ ǡ ݕଶ ǡ ǥ Ǥ Ǥ ǡ ௵ݕሽǤHence each ݕ is a positive number smaller than two, with κ bits of precison after the binary point. Also ሾσఢௌ ݕ ሿଶ ൌ ൫ͳൗ൯ െ ߂ for some ห߂ ห ൏ ʹି . Output the secret key ݇ݏൌ ݏԦ and public key ݇ൌ ሺ כ ݇ǡ ݕԦሻǤ b) ݐݕݎܿ݊ܧand ݁ݐܽݑ݈ܽݒܧǣ Generate a cipher-text ܿ כ as before. Then for ݅߳ሼͳǡʹǡ͵ǡ ǥ Ǥ ǡ ߆ሽ, set ݖ ՚ ሾܿ כǤ ݕ ሿଶ , keeping only ݊ ൌ ۀߠ ݈݃ڿ ͵bits of precision after the binary point for each ݖ . Output both ܿ כand ݖԦ ൌ ݖۃଵ ǡ ݖଶ ǡ ǥ Ǥ Ǥ ǡ ۄ ௵ݖ. c) ݐݕݎܿ݁ܦǣ outputs

ݐݕݎܿ݁ܦሺ݇ݏǡ ܿሻǣ Output ݉ᇱ ՚ ሺܿ݉݀ሻ݉ʹ݀Ǥ (10) Remark: Decryption can also be written as: ݉ᇱ ՚ ሾܿ െ උܿൗඇሿଶ . 3) Homomorphic properties: The homomorphic properties of the asymmetric scheme is interpreted as in section (A.2) for the symmetric one. C. Making the scheme fully homomorphic: 1) Bootstrapping: A bootstrappable encryption scheme is an encryption scheme that can evaluate its own decryption circuit [ ܦ12][13]. We apply equation (1) on the encryption scheme, but instead of using the circuit ܥǡ we use the decryption circuit ܦǤ Suppose that ԑ is bootstrappable with plaintext space ܲwhich is ሼͲǡͳሽ, and the circuit ܥis Boolean. And we have a ciphertext ߰ଵ that encrypts π under ݇ଵ which we want to refresh. Suppose that we can decrypt it homomorphically, and we also have ݇ݏଵ the secret key for ݇ଵ . ݇ݏଵ is encrypted under a തതതതതത second public key ݇ଶ : let ݇ݏ ଵఫ be the encrypted secret key bits. Consider the following algorithm.

തതതതതത ܴ݁ܿݐݕݎᡅ ൫݇ଶ ǡ ܦᡅ ǡ ݇ݏۃ ଵఫ ۄǡ ߰ଵ ൯Ǥ ோ

തതതതത ܵ݁߰ݐ ଵఫ ՚ ݐݕݎܿ݊ܧ൫݇ଶ ǡ ߰ଵ ൯

݉ᇱ ՚ ሾܿ כെ ہ ݏ ݖ ۀሿଶ Ǥ

(11)

തതതതതത തതതതത ܱ߰ݐݑݐݑଶ ՚ ݁ݐܽݑ݈ܽݒܧᡅ ሺ݇ଶ ǡ ܦᡅ ǡ ݇ݏۃۃ ଵఫ ۄǡ ߰ۃଵఫ )ۄۄ

d) Lemma: For every cipher-text ሺܿ כǡ ݖԦሻ that is generated by evaluating a cicuit ܥ, it holds that σ ݏ ݖ is within ͳൗͶ of an integer.

Above, ݁ݐܽݑ݈ܽݒܧtakes as input the bits of ݇ݏଵ and ߰ଵ , each encrypted under ݇ଶ . Then ԑ is used to evaluate the decryption circuit homomorphically. The output ߰ଶ is thus an encryption under ݇ଶ of ݐݕݎܿ݁ܦᡅ ሺ݇ݏଵ ǡ ߰ଵ ሻ ൌ ߨ. Applying the decryption circuit ܦᡅ removes the error vector associated to the first cipher-text, but ݁ݐܽݑ݈ܽݒܧᡅ simultaneously introduces a new vector error. Intuitively, we have made progress as long as the second error vector is shorter. Bootstrapping is possible if decryption can be expressed as an arithmetic circuit of low depth.

e) Proof: Fix a public and secret keys, generated with respect to security parameter λ, with ሼݕ ሽ௵ୀଵ the rational numbers in the public key and ሼݏ ሽ௵ୀଵ the secret key bits. Recall that the ݕ Ԣ ݏwere chosen so that ሾσ ݏ ݕ ሿଶ ൌ ൫ͳൗ൯ െ ߂ with ห߂ ห င ʹି . Fix an electric circuit ܥ, and ݐcipher-texts ሼܿ ሽ௧ୀଵ that encrypt the inputs to ܥ, and denote ܿ כൌ ݁ݐܽݑ݈ܽݒܧሺ݇ǡ ܥǡ ܿଵ ǡ ܿଶ ǡ ǥ ǡ ܿ௧ ሻ, we need to establish that כ උܿ ൗඇ ൌ ہ ۀ ݅ݖ ݅ݏሺ݉ʹ݀ሻ (13)

2) Squashing the decryption circuit Squashing the decryption circuit is a transformation applied over the decryption circuit to make it an arithmetic circuit of low depth [11][12],[13]. In this transformation, we add to the public key some extra information about the secret key, and we use extra information to “post process” the cipher-text. The post-processed cipher-text can be decrypted more efficiently than the original cipher-text, thus making the scheme bootstrappable. But this requires a larger cipher-text, and also introducing another hardness assumption. Let κ, θ, Θ be three more parameters, which are function of λ. ߛߟ We use κ= ൗߩᇱ , θ=λ and Θ=ჯሺߢǤ ߣሻǤ For a secret key כ

݅

Where the ݖᇱ s are computed as ሾܿ כǤ ݕ ሿଶ with only ۀߠ ڿ+3 bits of precision after the binary point, so ሾܿ כǤ ݕ ሿଶ ൌ ݖ െ ߂ with ȁ߂ ȁ င ͳൗͳߠ . We have: כ כ ቂ൫ܿ ൗ൯ െ ݏ ݖ ቃ ൌ ቂ൫ܿ ൗ൯ െ ݏ ሾܿ כǤ ݕ ሿଶ ݏ ߂ ቃଶ ଶ

כ

݇ݏൌ and a public key ݇from the original somewhat homomorphic scheme ᡅ. We add to the public key a set

(12)

ఢௌ

כ ܿכ ൌ ൫ ൗ൯ െ ܿ Ǥ ቂ ݏ ݕ ቃ ݏ ߂ ൨ ଶ ଶ

ݕԦ ൌ

ሼݕଵ ǡ ݕଶ ǡ ǥ ǥ ǡ ௵ݕሽ

of rational numbers in ሾͲǡʹሻ with κ bits of precision, such that there is a sparse subset ܵ ؿ

כ

ൌ ቂ൫ܿ ൗ൯ െ ܿ כǤ ሺͳൗ െ ߂ ሻ ݏ ߂ ቃ

ଶ

3

ൌ ቂܿ כǤ ߂ ݏ ߂ ቃ

We denote the sum ݇ݍൌ σ݅ܤൌͳ ݇ݏǡ݅ ݇ݖǡ݅ , is obtained by adding ܤ numbers, only one being non-zero. The decryption equation is now

ଶ

We claim that the final quantity inside the brackets has magnitude at most ͳൗͺ. By definition, since ܿ כis a valid כ ciphertext output, the value ܿ ൗis within ͳൗͺ of an integer. Together, these facts imply the lemma.

ఏ כ

݉ ՚ ܿ െ ہሺݍ ሻ݀݉ ۀሺʹሻ

Where the ݍ ’s are rational in ሾͲǡʹሻ with n bits of precision after the binary point. Based on decryption equations above, decryption can be written as:

ଵ

ൌ ͳൗͳǤ To establish the claim, observe that ȁ σ ݏ ߂ ȁငθ. ଵఏ Regarding ܿ ߂ כ ǡrecall that the output cipher-text ܿ כis obtained by evaluating the circuit ܥon the cipher-text ܿ As listed in [12], for any polynomial ܲ that implements the cicuit ᇲ ܥ, for any α≥1, if ܲԢs input have magnitude at most ʹఈሺఘ ାଶሻ , ఈሺఎିସሻ its output has magnitude at most ʹ . In particular, when ܲԢs input are fresh ciphertext, which have magnitude at most ʹఊ ǡ ܲ’s output cipher-text ܿ כhas magnitude at most ᇲ ʹఊሺఎିସሻȀሺఘ ାଶሻ ൏ ʹିସ Ǥ Thus, หܿ ߂ כ ห ൏ ͳൗͳ and the claim follows.

௵ כ ݉ ൌ ሾܿ െ ቔܿ ൗቓሿଶ ൌ ሾܿ כെ ሾہ ݏ ݖ ۀሿଶ כ

The same equation can be written as: ௵ כ

݉ ൌ ሾܿ ሿଶ ْ ሾہ ݏ ݖ ۀሿଶ ୀଵ

(17)

The parity of ݉ is related to the parity of ܿ כand the parity of ہσ௵ୀଵ ݏ ݖ ۀ, during bootstrapping we should conserve the parity of ہσ௵ୀଵ ݏ ݖ ۀǤ We show a toy implementation of bootstrapping using low values just to clarify the ideas. Suppose that we have ߆ ൌ Ͷ and ߠ ൌ ʹ. In this case we have ܤൌ ߆ൗߠ ൌ ʹ, and precision bit: ݊ ൌ ͳ. ݏԦ ൌ ሾܾଵ ܾଶ ܾଷ ܾସ ሿ, ሺሺܾଵ ൌ ͳܾܽ݊݀ଶ ൌ Ͳሻ or (ܾଵ ൌ Ͳܾܽ݊݀ଶ ൌ ͳሻሻǤ ሺሺܾଷ ൌ ͳܾܽ݊݀ସ ൌ Ͳሻ or (ܾସ ൌ Ͳܾܽ݊݀ଷ ൌ ͳሻሻ. ݖൌ ሾሾͳͲሿǡ ሾͲͳሿǡ ሾͳͳሿǡ ሾͲͳሿ]. Let us try to evaluate the decryption circuit using the secret key ݏԦ without encryption. ݏଵ ൌ ሾݏଵଵ ݏଵଶ ሿ ൌ ሾܾଵ ǡ ܾଶ ሿ ݏଶ ൌ ሾݏଶଵ ݏଶଶ ሿ ൌ ሾܾଷ ǡ ܾସ ሿ ݖଵ ൌ ሾݖଵଵ ݖଵଶ ሿ ൌ ሾሾͳͲሿǡ ሾͲͳሿሿ ݖଶ ൌ ሾݖଶଵ ݖଶଶ ሿ ൌ ൣሾͳͳሿǡ ሾͲͳሿ൧Ǥ ܵ ݉ݑൌ σఏୀଵ σୀଵ ݏǡ ݖǡ ൌ σଶୀଵ σଶୀଵ ݏǡ ݖǡ = ܾଵ ݖଵଵ ܾଶ ݖଵଶ ܾଷ ݖଶଵ ܾସ ݖଶଶ . ͳ݉ݑݏൌ ܾଵ ݖଵଵ ܾଶ ݖଵଶ ൌ ሾܾଵ ǡ ܾଶ ሿ (ܾଵ is the real part, ܾଶ is the decimal part). ʹ݉ݑݏൌ ܾଷ ݖଶଵ ܾସ ݖଶଶ ൌ ሾܾଷ ǡ ܾଷ ܾସ ሿ (ܾଷ is the real part, ܾଷ ܾସ is the decimal part). To add ͳ݉ݑݏand ʹ݉ݑݏ, we apply the binary addition listed in lemma 7 of [14]. The result is ݉ݑݏൌ ͳ݉ݑݏ ʹ݉ݑݏൌ ሾܾଵ ܾଷ ǡ ܾଶ ܾଷ ܾସ +ܾଵ ܾଷ ሿ (ܾଵ ܾଶ is the real part and ܾଶ ܾଷ ܾସ +ܾଵ ܾଷ is the decimal part). The parity of ۀ݉ݑݏہൌ ہσ ݏ ݖ ۀis given by ሾܾଵ ܾଷ ܾଶ ܾଷ ܾସ ܾଵ ܾଷ ሿଶ Let us repeat the same procedure, but this time we evaluate the decryption circuit using the encryption of the secret key ݏԦ. For simplicity suppose that the largest public key ݔ is ݍ .

After Squashing the decryption circuit, the latter have the form given in equation (12).σఢௌ ݏ ݖ is implemented as given in Fig. 2.

Fig. 2. Multiplication after Sqaushing

In [14][15] a multiplication with lower computational complexity than the one given in Fig. 2 is explained. In this new implementation the secret key ݏԦ is divided in θ boxes of ܤൌ ߆ൗߠ bits each, such that each box has a single 1-bit in it. This enables to obtain a grade-school addition algorithm that requires ܱሺߠ ଶ ሻ multiplications of bits instead of ܱሺ߆Ǥ ߠሻ. The secret key ݏԦ is divided into ݏǡ the ith secret key bit in box ݇, where ͳ င ݇ င ߠ and ͳ င ݅ င ܤ. In this case we have this equation: ఏ

(16)

ୀଵ

3) Practical Example of Bootstrapping and Squashing:

݉ ՚ ܿ כെ ہሺ ݏǡ ݖǡ ሻ݀݉ۀሺʹሻ

(15)

ୀଵ

(14)

݁ݏଵ ൌ ܿ݊ܧሺݏଵ ሻ ൌ ሾݍଵ ʹݎଵ ܾଵ ǡ ݍଶ ʹݎଶ ܾଶ ሿ ݁ݏଶ ൌ ܿ݊ܧሺݏଶ ሻ ൌ ሾݍଷ ʹݎଷ ܾଷ ǡ ݍସ ʹݎସ ܾସ ሿ ݎ ߳ሾെʹఘ ǡ ʹఘ ሿ ݅߳ሼͳǡʹǡ͵ǡͶሽ

ୀଵ ୀଵ

4

ܾ ܾଵଶ ǥ Ǥ ǥ Ǥ ܾଵ ܾଵ ۍଵଵ ې Ǥ ǥ Ǥ ܾଶ ܾۍ ۑଶ ې ܾ ܾ ێଶଵ Ǥ Ǥଶଶ ǥ ǥ ێǤ ۑሺǡሻ ǤǤ Ǥ ǥǤǤ ܤൌێ ୀଵ ୀଵ ୀଵ ୀଵ ۑൌ ܴ߳ ۑ ێ ǥ ǥ Ǥ Ǥ ǥ ǥ Ǥ Ǥ Ǥ ሺݍଵ ʹݎଵ ܾଵ ሻݖଵଵ ሺݍଶ ʹݎଶ ܾଶ ሻݖଵଶ ێ ێ ۑǤۑ ܾۏ ے ǥ Ǥ Ǥ ǥ Ǥ Ǥ ܾ ܾۏଵ ܾଶ ሺݍଷ ʹݎଷ ܾଷ ሻݖଶଵ ሺݍସ ʹݎସ ܾସ ሻݖଶଶ Ǥ ے ܮሺܤሻ is an additive sub-group of ܴ Ǥ ͳ݉ݑݏ ൌ ሺݍଵ ʹݎଵ ܾଵ ሻݖଵଵ ሺݍଶ ʹݎଶ ܾଶ ሻݖଵଶ The rank of the lattice is ݊ and its dimension is ݉, we say ൌ ሾݍଵ ʹݎଵ ܾଵ ǡ ݍଶ ʹݎଶ ܾଶ ሿ that the lattice is full rank if ݊ ൌ ݉. ʹ݉ݑݏ =ሺݍଷ ʹݎଷ ܾଷ ሻݖଶଵ ሺݍସ ʹݎସ ܾସ ሻݖଶଶ 2) Two bases are equivalent when they generate the same ൌ ሾݍଷ ʹݎଷ ܾଷ ǡ ሺݍଷ ݍସ ሻ ʹሺݎଷ ݎସ ሻ ܾଷ ܾସ ሿ. lattice. Also to add ͳ݉ݑݏ ǡ ʹ݉ݑݏ ǡ we apply the same binary Two bases ܤଵ and ܤଶ are equivalent if and only if ܤଶ ൌ ܤଵ ܷ, addition listed in lemma 7 of [14] and the result is where ܷ is a unimodular matrix, ݐ݁ܦሺܷሻ ൌ ା ିͳ Ǥ Two bases ܤଵ and ܤଶ are equivalent, ݐ݁ܦሺܤଵ ሻ ൌ ା ݉ݑݏہ ۀൌ ہ ݁ݏ ݖ ۀൌ ሾͳ݉ݑݏ ʹ݉ݑݏ ሿ௫బ ൌ ିݐ݁ܦሺܤଶ ሻǡ |ݐ݁ܦሺܤଵ ሻȁ ൌ ȁݐ݁ܦሺܤଶ ሻȁǤ ሾሺݍଵ ݍଷ െ ݇ଵ ݍ ሻ ʹሺݎଵ ݎଷ ሻ ܾଵ ܾଷ ሺݍଶ ݍଷ 3) Determinant of a lattice ݍସ െ ݇ଶ ݍ ݍଵ ݍଷ ʹݎଷ ݍଵ ܾଶ ݍଵ ʹݍݎଷ ܾଵ ݍଷ ሻ ܮሺܤሻ ൌ ݐ݁ܦሺܮሻ ൌ ȁݐ݁ܦሺܤሻȁ. ʹሺݎଷ ݎସ ݎଵ ݎଷ ݎଵ ܾଷ ܾଵ ݎଷ ݎଶ ܾଶ ܾଷ ܾସ 4) Fundamental parallelepiped: ଶ ܾଵ ܾଷ ሿ ൌ ሾ݉ݑݏଵ ݉ݑݏ ], Such that ݎ ߳ሾെʹఘ ǡ ʹఘ ሿ, We define the fundamental parallelepiped by: ݅߳ሼͳǡʹǡ͵ǡͶሽ. ܲሺܤሻ ൌ ሼߙଵ ܾଵ ߙଶ ܾଶ ߙଷ ܾଷ ఏ

ଶ

ଶ

ܵ݉ݑ ൌ ݁ݏǡ ݖǡ ൌ ݁ݏǡ ݖǡ ൌ

ܿ݅ݐݔ݁ݐݎ݄݁௦ =݉ݑݏہ ۀ+ሾܿכሿʹ

ڮǤ Ǥ ߙ ܾ ǡ ߙ ߳ሾͲǡͳሻሽ ݐ݁ܦሺܮሻ ൌ ݐ݁ܦሺܤሻ ൌ ݈ݒ൫ܲሺܤሻ൯Ǥ

(18)

5) Bad base vs Good base:

The parity of ܿ݅ݐݔ݁ݐݎ݄݁௦ in equation (18) is preserved based on equation (17), the fresh cipher has lower noise than ܿ כbecause during bootstrapping the secret key bits are encrypted by sampling the noise from ሾെʹߩ ǡ ʹߩ ሿ, while the initial cipher-text is obtained by sampling the noise from Ԣ

(20)

Ԣ

ቂെʹߩ ǡ ʹߩ ቃǡ given thatߩ ൏ ߩᇱ as given in TABLE I. IV. BV, BGV SCHEMES The BV [16] (Brakerski-Vaikunathan) and BGV [17] (Brakerski-Gentry-Vaikunathan) consist of applying the DGHV over Lattices. They are two encryption schemes based on the hardness of LWE (Learning With Error) [18][19]. LWE is a lattice based encryption scheme. We first explain the Lattice based encryption scheme [20], then LWE and finally we will introduce the BV, BGV schemes.

Fig. 3. Good base Vs Bad base

A. Lattices Definition [20]:

If we carefully compare the two bases given in Fig. 3, we can see that two bases generate the same lattice, but the first one is considered as good base because it is formed of small vectors while the other one is a bad basis because it is formed of large vectors.

1) Given ݊ linearly vectors in ܴ ሼܾଵ ǡ ܾଶ ǡ ܾଷ ǡ ǥ Ǥ ǡ ܾ ሽǡ a lattice of basis ሼܾଵ ǡ ܾଶ ǡ ܾଷ ǡ ǥ Ǥ Ǥ ǡ ܾ ሽ is defined as linear combination of the ݊ vectors [20].

ܽଵ ܾଵ ܽଶ ܾଶ ܽଷ ڮǥ ǥ ܽ ܾ ܾଶଵ ܾଷଵ ܾଵଵ ܾ ܾ ܾ ǥ ܽଵ ଵଶ Ǥ ܽଶ ଶଶ Ǥ ܽଷ ଷଶ Ǥ ܾଶ ܾଵ ܾଷ ܾଵ ܾ ǥ ܽ ଶ Ǥ ܾ

6) Succesive Minima and Minskowski’s Theorem We define ߣଵ ሺܮሻ as the length (Euclidean Distance) of the shortest non zero vector in ܮ. More generally, ߣ ሺܮሻ denotes the smallest radius of a ball containing ݇ linearly independent vectorsሺͳ င ݇ င ݊ሻǤ An explanation of successive minima is given briefly in Fig. 4, where ߣଵ ሺܮሻ and ߣଶ ሺܮሻ are drawn.

(19)

The matrix representation is given by ܮሺܤሻ ൌ ܣǤ ܤwhere ܣൌ ሾܽଵ ܽଶ ǥ Ǥ ܽ ሿܼ߳ ሺଵǡሻ ǡ

5

from a sample of the form ሺܽ ǡ ݏۃǡ ܽ ۄ ݁ ሻ, ܽ are uniformly chosen from ܼ and ݁ a noise distribution over ܼ Ǥ Given the following security parameters, ݊ǣDimension, ݍ ʹǣmodulus, ߙ ͳ اerror rate, we define two different problems: Search Problem: find ܼ߳ݏ given a noisy random inner products ܽͳ ՚ ܼ݊ ݍǡ ܾͳ ൌ ݏۃǡ ܽͳ ۄ ݁ͳ

Fig. 4. Succesive Mininma

ଵൗ .

ଵൗ ଵ ငξ݊ሺݐ݁ܦሺܮሻሻ ൗ Ǥ

ܽ ՚ ܼ ǡ

ܾ ൌ ݏۃǡ ܽ ۄ ݁

(21)

2) LWE matrix form Suppose that we have ܽଵଵ ܽ ܣൌ ሾܽଵ ܽଶ ǥ ܽ ሿ ൌ ଵଶ Ǥ ܽଵ

(22)

ሺଵǡሻ

ݏ௧ ൌ ሾݏଵ ݏଶ ǥ Ǥ Ǥ ݏ ሿܼ߳

7) Some lattice problems - ܸܵܲ ǣ Shortest Vector Problem: For ݄ ͳ, given a basis ܤ of ܮൌ ܮሺܤሻ, find ܮ߳ݖsuch that Ͳ ് หȁݖȁห င ݄Ǥ ߣଵ ሺܮሻǤ

ܽଶଵ ܽଶଶ Ǥ ܽଶ

Ǥ ܽଵ Ǥ ܽଶ ሺǡሻ Ǥ ϵܼ Ǥ Ǥ ܽ ሺଵǡሻ

, ݁ ௧ ൌ ሾ݁ଵ ݁ଶ ǥ Ǥ Ǥ ݁ ሿܼ߳

The LWE matrix form of the Equation (23) can be written as ሺଵǡሻ

ܾ ௧ ൌ ݏ௧ ܣ ݁ ௧ ϵܼ

- ܸܲܥ ǣ Closest Vector Problem: For ݄ ͳ, given a basis ܤ of ܮൌ ܮሺܤሻǡ find ܮ߳ݖsuch that หȁ ݐെ ݖȁห င ݄Ǥ ݀݅ݐݏሺݐǡ ܮሻǤ

(24)

Equation (24) is lattice equation, where ݏ௧ ܣforms the lattice points. In lattice base encryption scenario, ݁ ௧ can be considered as the plaintext, and decryption is a ܸܲܥ problem that consists of finding the closest lattice point to ܾ ௧ .

- Using good basis, Babai’s algorithm [20] resolves the ܸܲܥ with ݄ ൌ ʹ

(23)

Decision problem: distinguish ሺܽ ǡ ܾ ሻcalculated in equation (23) from a uniform ሺܽ ǡ ܾ ሻǤ

Minkowski’s second theorem: for any full-rank lattice ܮof rank ݊, ሺςୀଵ ߣ ሺܮሻሻ

ܾଶ ൌ ݏۃǡ ܽଶ ۄ ݁ଶ …

Errors ݁ ՚ ߯=Gaussian over ܼq, param ߙݍ.

Minkowski’s first theorem: for any full-rank lattice ܮof rank ݊, ߣଵ ሺܮሻ င ξ݊ሺݐ݁ܦሺܮሻሻ

ܽଶ ՚ ܼ ǡ

ൗ ଶ.

(i.e. finding ܮ߳ݖsuch that หȁ ݐെ ݖȁห င ʹ ൗଶ Ǥ ݀݅ݐݏሺݐǡ ܮሻሻǤ

C. BV-BGV schemes

8) Lattice based encryption A simple asymmetric encryption scheme using Lattice is as follows: - Secret Key: Secret Key is chosen as a good basis of the lattice ܮሺܤሻǤ - Public Key: Public Key is chosen as a bad basis of the lattice ܮሺܤሻǤ - It is easy to generate the bad basis from the good one, but the inverse is hard. - Encryption consists of creating a problem (such as ܸܲܥ ሻ where it is hard to resolve it using the bad basis, but resolving it with good basis is simple (using Babai’s algorithm with good basis). - Example: to encrypt, we write the message as a vector ݁, we randomly choose ܮ߳ݖ, we need ݔൌ ݖ ݁, decryption is finding ܮ߳ݖclose to ݔǤ

1) Basic Scheme The BV and BGV are two homomorphic encryption schemes that are similar, but differ a little during the modulus switching phase. The BV was published by the authors of [16] in 2011, while the BGV was published by the authors of [17] in 2012. The two schemes consist of applying the DGHV over Lattices. The hardness of these two schemes is based on the hardness of LWE. We will suppose that the scheme for now is a symmetric scheme, that works over the bit level. The secret key is ሺǡଵሻ ሺǡଵሻ ܼ߳ݏ and the cipher-text is ܼܿ߳ Ǥ Decryption is given by this equation ܾ ൌ ᇣᇧᇧᇧᇧᇧᇧᇧᇤᇧᇧᇧᇧᇧᇧᇧᇥ ቀ൫ݏۃǡ ܿ݀݉ۄሺݍሻ൯݉݀ሺʹሻቁ ௩௧

=ሺ൫ሺݏǤ ܿሻ݉݀ሺݍሻ൯݉݀ሺʹሻሻ ᇣᇧᇧᇧᇧᇧᇧᇧᇤᇧᇧᇧᇧᇧᇧᇧᇥ

(25)

௧௫

B. Learning With Error (LWE) 1) LWE is a machine learning problem[18] [19], where we need to solve a hard problem, we have to learn the values of ݏ

Decryption works only if the noise is small enough: ൫ሺݏǤ ܿሻ݉ݍ݀൯ <<ߙݍ.

6

TABLE II.

The cipher-text ܿ is close to an orthogonal space to ݏ, and the plain-text is encoded in the parity of distance.

Nb of multiplications Ͳ ͳ ʹ ….. ݇

2) Building the homomorphic scheme The scheme is an instance of Error Correcting Code (ECC), addition is valid as long as the noise is small. The question is, how we can build the multiplicative homomorphic given that cipher-texts are vectors? To build the homomorphic multiplication, we use tensor product given in the next equation: ܯൌ ݒ ٔ ݑൌ ሼܯ ൌ ൫ݑ ݒ ൯ሽ

(27)

ܿ݁ܦ௦ᇲ ሺܿ ᇱ ሻ ൌ ܿ݁ܦ௦ כሺܿ כሻ

(28)

(30)

To achieve key switching, we have to publish an encryption ሾǡሿ matrix ܼ߳ܯ defined by:

To clarify this scheme, we consider a tensor product with dimension 2, the secret key is ݏൌ ሾݏଵ ݏଶ ሿ and two vectors of cipher-texts ݑൌ ሾݑଵ ݑଶ ሿand ݒൌ ሾݒଵ ݒଶ ሿ.

ܯሺ כ ݏ՜ ݏሻ , ܿԢ ൌ כܿܯሺሾ݉ǡ ͳሿ ൌ ሾ݉ǡ ݊ሿሾ݊ǡ ͳሿሻǤ ݉൏݊

(31)

The different secret keys and cipher-texts are given by ሺ כ ݏൌ ሾͳȁݐሿ ϵܼ , ܿ ܼ߳ כ ) and ሺ ݏᇱ ൌ ሾͳȁ ݐᇱ ሿԖܼ ǡܿ ᇱ ܼ߳ ሻ

ݏۃǡ ۄݑൌ ሺݏଵ ݑଵ ݏଶ ݑଶ ሻ and ݏۃǡ ۄݒൌ ሺݏଵ ݒଵ ݏଶ ݒଶ ሻ ݑଵ ݒଵ ݑଵ ݒଶ ܯൌ ݒ ٔ ݑൌ ൛ܯ ൌ ൫ݑ ǡ ݒ ൯ൟ ൌ ቂ ݒ ݑ ݒ ݑቃ ଶ ଵ ଶ ଶ ݒ ݑ ݒ ݏ ݑ ଵ ଵ ଵ ଶ ଵ ݏܯݏ௧ ൌ ሾݏଵ ݏଶ ሿ ቂ ݒ ݑ ݒ ݑቃ ቂ ݏቃ ൌ ଶ ଵ ଶ ଶ ଶ

The matrix ܯis published as shown in Fig. 5, ሾଵǡሿ

ݏᇱ ܼ߳

ǡ

ሾǡሿ

ܼ߳ܯ

ሾଵǡሿ ݏᇱ ܯൌ െ ݐᇱ ܣ ʹ݁ כ ݏ ݐᇱ ܣൌ ሺʹ݁ ݏሻܼ߳ ܿ݁ܦ௦ᇲ൫ᇲ ൯ ൌ ൫ሺ ݏᇱ ܿ ᇱ ሻ݉݀ሺݍሻ൯݉݀ሺʹሻ ݏᇱ ܿ ᇱ ൌ ݏᇱ ܿܯൌ ሺʹ݁ כ ݏሻܿ כൌ ʹሺ݁ܿ כሻ ሺ כ ܿ כ ݏሻ

ݏଵ ݑଵ ݒଵ ݏଵ ݏଶ ݑଶ ݒଵ ݏଵ ݏଵ ݑଵ ݒଶ ݏଶ ݏଶ ݑଶ ݒଶ ݏଶ . We can simply verify that ݏܯݏ௧ ൌ ݏۃǡ ݏۃۄݑǡ ۄݒ The key point is that we prefer to deal with vectors rather than matrices. ݑଵ ݒଵ ݑଵ ݒଶ ݒ ٔ ݑൌ ቂ ݒ ݑ ݒ ݑቃ, we take ܿ כൌ ݐܿ݁ݒሺݒ ٔ ݑሻ ൌ ଶ ଵ ଶ ଶ ሾݑଵ ݒଵ ݑଵ ݒଶ ݑଶ ݒଵ ݑଶ ݒଶ ሿǤ ݏଵ ݏଵ ݏଵ ݏଶ ݏ ٔ ݏൌ ቂ ݏ ݏ ݏ ݏቃ, we take כ ݏൌ ݐܿ݁ݒሺݏ ٔ ݏሻ ൌ ଶ ଵ ଶ ଶ ሾݏଵ ݏଵ ݏଵ ݏଶ ݏଶ ݏଵ ݏଶ ݏଶ ሿǤ

Fig. 5. Matrix M: key switching

We can simply verify that כ ܿۃǡ ۄ כ ݏൌ ݏۃǡ ݏۃۄݑǡ ۄݒൌ ݏܯݏ௧ Ǥ ܿ݁ܦሺܿ כሻ ൌ ሺ כ ܿۃǡ ݀݉ۄ כ ݏሺݍሻሻ݉݀ሺʹሻ

݇

݊ʹ

To resolve the problem listed above, the key switching technique is introduced [16][17], we have a cipher-text ܿ כwith respect to an extended secret key כ ݏൌ ݐܿ݁ݒሺݏ ٔ ݏሻǡthe main purpose of key switching is to build a low dimension ciphertext ܿ ᇱ with respect to a low dimension key ݏᇱ such that

If the noise level is low after the multiplication operation, decryption can be written as: ൫ݏሺݒ ٔ ݑሻ ݏ௧ ݉݀ሺݍሻ൯݉݀ሺʹሻ ൌ ൫ሺݏۃǡ ݏۃۄݑǡ ۄݒሻ݉݀ሺݍሻ൯݉݀ሺʹሻ

Cipher dimension ݊ ͳ ʹ ݊ ൌ ݊ʹ ʹ ݊Ͷ ൌ ݊ʹ ….

(26)

It is easy to demonstrate that: ݏሺݒ ٔ ݑሻ ݏ௧ ൌ ݏۃǡ ݏۃۄݑǡ ۄݒൌ ሺݏǤ ݑሻሺݏǤ ݒሻ

HOMOMORPHIC MULTIPLICATION GROWTH

The refresh mechanism would work if: ሺሺ ݏᇱ ܿ ᇱ ሻ݉݀ሺݍሻሻ݉݀ሺʹሻ ൌ ሺሺ כ ܿ כ ݏሻ݉݀ሺݍሻሻ݉݀ሺʹሻǤ and ሺ݁ܿ כሻshould be small, but it is not small because ܿ ܼ߳ כ Ǥ To overcome this , we represent ܿ כwith higher dimension but with lower values. Thus ܿ כis represented in its binary form

(29)

Equation (29) holds as long as the noise כ ܿۃǡ ݀݉ۄ כ ݏሺݍሻ is quite small. The problem is that the dimension grows exponentially each time we multiply two cipher-texts homomorphically using tensor product, as shown in TABLE II.

ܿ כൌ ሾܿ כሿǡ ܿ כis the ݅ ௧ entry of ܿ כand can be written כ כ as ܿ כൌ σିଵ ୀ ʹ ܿ , ܿ ߳ሼͲǡͳሽ Let ܾ ൌ ൣܿ כଵ ܿ כଶ ܿ כଷ ǥ ǥ Ǥ ܿ כ ൧ͳ င ݆ င ݈ െ ͳ

7

(32)

we introduce the Modulus switching technique, that is based on switching into another modulus (different than )ݍbut we are still able to decrypt. The key challenge is that we have a cipher-text ܿ with respect to a secret key ݏ, we will build a new cipher-text ܿ ᇱ for some ൏ ݍsuch that

ܿ כൌ σିଵ ୀ ʹ *ܾ כ ۄ כ ܿ כ ݏۃൌ σିଵ ୀ ʹ ܾۃ ǡ ۄ ݏ

ൌ ʹ ܾۃ ǡ ۄ כ ݏ ʹଵ ܾۃଵ ǡ ۄ כ ݏ ʹ ڮିଵ ܾۃିଵ ǡ ۄ כ ݏ.

(33)

൫ܿۃǡ ݀݉ۄݏሺሻ൯݉݀ሺʹሻ ൌ ሺ ܿۃᇱ ǡ ݀݉ۄݏሺݍሻሻ݉݀ሺʹሻ

If we suppose that ܿ ככൌ ሾܾ ܾଵ ǥ ǥ Ǥ ܾିଵ ሿ and ככ ݏൌ ሾʹ ʹ כ ݏଵ כ ݏǥ ǥ Ǥ Ǥ ʹିଵ כ ݏሿ, we can simply verify that ככ ݏۃǡ ܿ ۄ ככൌ כ ݏۃǡ ܿ ۄ כ

Let ൏ ݍbe odd integers, ܿǡ ܼ߳ݏ , such that: ݍ ݍ |ܿۃǡ ݀݉ۄݏሺݍሻȁ ൏ ൗʹ െ ൗ ȁȁݏȁȁ (40) Let ܿ ᇱ ൌ ݀݊ݎ ሺ ൗ ݍc), where ݀݊ݎ ሺǤ ሻrounds each entry up or down such that ܿ ᇱ ൌ ܿሺ݉ʹ݀ሻ, then we have

We publish in this case the matrix ܯǣ ܯሺ ככ ݏ՜ ݏᇱ ሻ such that ᇱ

ככ

ܿ ൌ ܿܯ ሺݏ݅݊݅ݏ݄݊݁݉݅݀݁ݐሾ݉ǡ ͳሿ ൌ ሾ݉ǡ ݊ כሺ݈ െ ͳሻሿሾ݊ כሺ݈ െ ͳሻǡ ͳሿ)

ݏԢ ܯൌ െݐԢ ܣ ʹ݁ ככݏ ݐԢ ܣൌ ʹ݁ ככݏ ݏᇱ ܿ ᇱ ൌ ݏᇱ ככ ܿܯൌ ሺʹ݁ ככ ݏሻܿ ככൌ ʹሺ݁ܿ ככሻ ሺ ככ ܿ ככ ݏሻ

(34)

(35)

ሺ ܿۃᇱ ǡ ݀݉ۄݏሺሻሻ݉݀ሺʹሻ ൌ ൫ܿۃǡ ݀݉ۄݏሺݍሻ൯݉݀ሺʹሻ

(42)

ଶ

Level Somewhat Homomorphic Encryption Scheme (SWHE) means that we are working level by level. For a circuit of depth ݀, we generate ݀ random secret keys ݏ ൌ ሾͳȁݐ ሿܼ , Ͳ င ݅ င ݀ െ ͳ. For each level ݅ of the circuit, we have to publish a public key ሾǡሿ ܯ in ܼ , for level 0 we publish ܯ ൌ ܯሺͲ ՜ ݏ ሻ and for ככ any level ݅ we publish ܯ ൌ ܯሺݏିଵ ՜ ݏ ሻ.

െݍ ݍ ȁȁݏȁȁ ൏ ܿۦǡ ۧݏെ ݇ݍ ʹ

If we multiply the inequality by we obtain the following:

ି ଶ

ȁȁݏȁȁ ൏ ܿۦǡ ۧݏെ ݇ ൏ െ หȁݏȁห ି

ܿۦᇱ ǡ ۧݏെ ݇ ϵ ሾ

ଶ

ଶ

ି

หȁݏȁห , െ หȁݏȁห ሿ ฺ ܿۦᇱ ǡ ۧݏെ ݇ ϵ ሾ , ሿ ଶ

ଶ

ଶ

This proves equation (41).

ݏ ܯ ൌ ʹ݁

Given that ܿۦǡ ݍ݀݉ۧݏൌ ܿۦǡ ۧݏെ ݇ ݍand

(36)

ܿۦᇱ ǡ ݀݉ۧݏൌ ܿۦᇱ ǡ ۧݏെ ݇ for the same ݇Ǥ

Encryption scheme is given by the following equation:

ሺ݇ݍሻ݉ ʹ݀ൌ ሺ݇ሻ݉ʹ݀ǡ

ܾ ܿ݊ܧሺܾሻ ൌ ܯ ݎ ͲǤ , ݎis a random vector (37) Ͳ inሼͲǡͳሽ

ǡ ݍare both odd.

ᇱ

ܿ ൌ ܿሺ݉ʹ݀ሻ. ܿۦᇱ ǡ ݀݉ۧݏሺʹሻ ൌ ܿۦǡ ݀݉ۧݏሺʹሻ ฺ ሺ ܿۦᇱ ǡ ۧݏെ ݇ሻ݉݀ሺʹሻ ൌ ሺܿۦǡ ۧݏെ ݇ݍሻ݉݀ሺʹሻ ൫ܿۦǡ ݀݉ۧݏሺݍሻ൯݉݀ሺʹሻ ൌ ൫ ܿۦᇱ ǡ ݀݉ۧݏሺሻ൯݉݀ሺʹሻǤ

Decryption at level ݅ is given by the following equation: ܿ݁ܦሺܿǡ ݅ሻ ൌ ൫ݏۃ ܿ ݀݉ۄሺݍሻ൯݉݀ሺʹሻ

(41)

For ܿۃǡ ݀݉ۄݏሺݍሻ, we can always find a ݇ such that െݍ ݍ ܿۃǡ ۄݏെ ݇ ߳ݍቂ ǡ ቃ ʹ ʹ |ܿۃǡ ݍ݀݉ۄݏȁ ൏ െ ȁȁݏȁȁ ฺ

3) Leveled Somewhat Homomorphic Scheme

ככ ݏ ܯ ൌ ʹ݁ ݏିଵ

| ܿۃᇱ ǡ ݀݉ۄݏሺሻȁင ȁܿۃǡ ݀݉ۄݏሺݍሻȁ ȁȁݏȁȁ

In this case we can say that: ൫ሺ ככ ܿ ככ ݏሻ݉݀ሺݍሻ൯݉݀ሺʹሻ ൌ ሺሺ ݏᇱ ܿ ᇱ ሻ݉݀ሺݍሻሻ݉݀ሺʹሻ Because ݁ܿ ככis small enough.

(39)

And this proves equation (42). As we said before BV and BGV are similar, but they differ in the modulus switching phase, the difference is that with BV ݍ ا , while in BGV ൏ ݍ. During the implementation we start with a large modulus ݍ , small noise ߤ ൏൏ ݍ Ǥ After ͳ௦௧ multiplication, noise grows to ݍ ߤଶ ߤ ଶ ǡwe switch to ݍଵ ؆ ൗߤ, noise is reduced to ൗߤ ؆ ߤ. After next multiplication layer, noise again grows to ߤ ଶ , we ݍ switch to ݍଶ ؆ ଵൗߤ to reduce it back to ߤǤ A practical example is given in TABLE III. where we started with initial modulus ݍ ൌ ߤ ହ , we can deduce how the modulus switching allowed us to evaluate deeper circuit depth. Without

(38)

By applying this SWHE, we can directly add cipher-texts at the same level, while during multiplication, we multiply ሺܿଵ ǡ ݅ሻ and ሺܿଶ ǡ ݅ሻ, we compute the extended cipher-texts ܿ כൌ ݐܿ݁ݒሺܿଵ ǡ ܿଶ ሻǡ then we calculate the doubly extended ܿ ככ, and we calculate the fresh cipher-text ܿ ᇱ ൌ ככ ܿܯǤ 4) Making the scheme fully homomorphic: The noise at level ݅ is given by ሺܿݏ ሻ݉݀ሺݍሻ. Noise level gets doubled and squared by multiplication. But in this way we can homomorphically evaluate a limited depth circuit as long as the noise is lower than ݍ. To evaluate deeper circuit,

8

[6]

modulus switching we stopped at level 3, while with modulus switching we stopped at level 4. TABLE III.

MODULUS SWITCHING VS NO MODULUD SWITCHING

With modulus switching Noise Modulus Fresh Ciphertexts Level 1 Level 2 Level 3 Level 4

[7]

Without modulus switching Noise Modulus

ߤ

ߤହ

ߤ

ߤହ

ߤ ߤ ߤ ࣆ

ߤସ ߤଷ ߤଶ ࣆ

ߤଶ ߤସ ࣆૡ

ߤହ ߤହ ࣆ

[8]

[9]

[10]

V. CONCLUSION In this paper, we investigated two important FHE asymmetric schemes: DGHV and BV-BGV. The first one is based on computing over real integers, while the other one is based on LWE (Lattice based Encryption). The two encryption schemes are not practical for real world applications due to storage overhead because for example as listed in [14], the public key size of DGHV is 802 MB even after applying public key compression. One main advantage of the BV-BGV over the DGHV is the modulus switching technique: a cipher-text refresh mechanism in DGHV (squashing and bootstrapping) takes 14 minutes, while modulus switching is very simple to be achieved [14]. On the other hand bootstrapping can extend the circuit evaluation to unlimited circuit depth, while the modulus switching extends it to a limited number but larger than the original scheme. Future work will focus on the designing and implementing of a secure FHE scheme practical for real world applications and especially for Cloud applications.

[11]

[12]

[13]

[14]

[15]

REFERENCES [1]

[2]

[3]

[4]

[5]

[16]

Dan Boneh and Craig Gentry and Sergey Gorbunov and Shai Halevi and Valeria Nikolaenko and Gil Segev and Vinod Vaikuntanathan and Dhinakaran Vinayagamurthy, Fully Key-Homomorphic Encryption, Arithmetics Circuiy ABE, and Compact Garbled Circuits, Cryptology ePrint Archive, Report 2014/356, 2014,http://eprint.iacr.org/2014/356. T. D. Ramotsoela and G. P. Hancke, "Data aggregation using homomorphic encryption in wireless sensor networks," 2015 Information Security for South Africa (ISSA), Johannesburg, 2015, pp. 1-8.doi: 10.1109/ISSA.2015.7335058 R. Rivest, A. Shamir, and L. Adelman, A method for obtaining digital signatures and public-key cryptosystems, Communication of the ACM 21 (2): 120126, 1978. M. Nassar, A. Erradi, and Q. Malluhi, Pallier’s Encryotion:Implementation and clouds applications Applied Research in Compuer Science and Engineering (ICAR), 2015 International Conference on, Beirut, 2015, pp. 1-5 .doi:10.1109/ARCSE.2015.7338149. Joseph Domingo Ferrer, A new privacy homomorphism and applications Information Processing Letters, Volume 60, Isssue 5, 9 December 1996, pages 277-282.

[17]

[18]

[19]

[20]

9

Joseph Domingo Ferrer, A Provably Secure Additive and Multiplicative Privacy Homomorphism, Universitat Rovira I Virgli, Dept. of Computer Engineering and Maths, ISC ’02 Proceedings of the 5th International Conference on information Security, Pages 471-483, Springer-Verlag London UK, 2002. Xiao, Liangliang and Bastani, Osbert and Yen, ILing An Efficient Homomorphic Encryption Protocol for Multi-User Systems Citeseer, IACR Cryptology ePrint Archive, volume 2012, year 2012, pp. 193, year 2012. Khalil Hariss, Hassan Noura, Abed Ellatif Samhat, Fully Enhanced Homomorphic Encryption algorithm of MORE approach for real world applications, Journal of Information Security and Applications, Volume 34, 2017, Pages 233-242, ISSN 2214-2126, http://dx.doi.org/10.1016/j.jisa.2017.02.001. Kipnis, Aviad and Hibshoosh, Eliphaz, Efficient Methods for Practical Fully Homomorphic Symmetric-key Encrypton, Randomization and Veriﬁcation IACR Cryptology ePrint Archive, volume 2012, pp. 637, year 2012. Craig Gentry PhD Thesis “A FULLY HOMOMORPHIC ENCRYPTION SCHEME” Stanford University, Department of Computer Science, September 2009. Craig Gentry.2009. Fully homomorphic encryption using ideal lattices. In Proceedings of the forty-first annual ACM symposium on Theory of Computing (STOC’09). ACM, New York, NY, USA, 169178:https://doi.org/10.1145/1536414.1536440 M. van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan, Fully Homomorphic Encryption over the integers, EURO-CRYPT2010 (LNCS) vol.6110, pp. 24-43. Jean-Sébastien Coron, Avradip Mandal, David Naccache, and Mehdi Tibouchi. 2011. Fully homomorphic encryption over the integers with shorter public keys. In Proceedings of the 31st annual conference on Advances in cryptology (CRYPTO'11), Phillip Rogaway (Ed.). Springer-Verlag, Berlin, Heidelberg, 487-504. Jean-Sébastien Coron, David Naccache, and Mehdi Tibouchi. 2012. Public key compression and modulus switching for fully homomorphic encryption over the integers. In Proceedings of the 31st Annual international conference on Theory and Applications of Cryptographic Techniques (EUROCRYPT'12), David Pointcheval and Thomas Johansson (Eds.). Springer-Verlag, Berlin, Heidelberg, 446-464. DOI=http://dx.doi.org/10.1007/978-3-642-29011-4_27. Craig Gentry, Shai Halevi, Implementing Gentry’s FullyHomomorphic Encryption scheme, Cryptology ePrint Archive, Report 2010/520, 2010, http://eprint.iacr.org/2010/520. Zvika Brakerski and Vinod Vaikuntanathan. 2011. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In Proceedings of the 31st annual conference on Advances in cryptology (CRYPTO'11), Phillip Rogaway (Ed.). Springer-Verlag, Berlin, Heidelberg, 505-524. Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. 2012. (Leveled) fully homomorphic encryption without bootstrapping. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS '12). ACM, New York, NY, USA, 309-325. DOI=http://dx.doi.org/10.1145/2090236.2090262. oded Regev. 2005. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (STOC '05). ACM, New York, NY, USA, 84-93. DOI: http://dx.doi.org/10.1145/1060590.1060603 Chris Peikert, Lattice-Based Cryptography: Short Integer Solution (SIS) and Learning With Errors (LWE), Georgia Institute of Technology David A. Madore, Réseaux euclidiens et cryptographie, Journées Télécom-UPS, Le numérique pour tous, Télécom ParisTech, 29 mai 2015.