An Effectively Fully Homomorphic Encryption Over The Integers

Fully Homomorphic Encryption scheme (short in FHE), originally called a privacy homomorphism, allows one to delegate processing of the data, without giving away access to it. It was introduced by Rivest, Adleman and Dertouzous in1978, shortly after the introduction of RSA Encryption scheme [1]. The orig-inally RSA encryption scheme[2]is a multiplicatively homomorphic encryption scheme. Fllowing this ideas, Rivest, Adleman and Dertouzous proposed the Fully Homomorphic Encryption[1]:an encryption scheme eεwith an efficient evaluate algorithm Evaluateε, for any public key pk, any circuit C (not just a multiplication gates in RSA) and any ciphertext ψi←Encryptε(pk, πi), outputs ψ←Evaluateε(pk, C,ψi,...,ψt), a vaild encryption of C(πi,...,πt) under pk.Under this ideas, we can construct a fully homomorphic encryption scheme allows one to process the encrypted data without the decryption key, so it can protect the user’s privacy. This encryption scheme can be efficiently used in cloud computing, privacy query, the Internet of things, Electronic Commerce and other applications, to protect the user’s privacy data. Though the fully homomorphic encryption scheme can be used in cloud computing and other applications, many cryptographers have studied on it, but there are not have a viable construction until now. Until2009, Gentry propose the first fully homomorphic encryption us-ing ideal lattices[3], by using the bootstrappable encryption ideas and the re-encryption technology to construct a fully homomorphic encryption scheme. Following Gentry’s ideas, many cryptographers propose the new fully homo-morphic encryption scheme. Currently three main families of fully homo-morphic encryption scheme are known [8]:first, Gentry’s original scheme using the ideal lattices [3]; second, Dijk’s scheme over the integers[5](short in DGHV); third, Brakerski and Vaikuntanathan’s scheme on the LWE and RLWE problems[9,10].In2010, Dijk and Gentry propose a fully homomorphic encryption scheme over the integers[5], short in DGHV scheme. This scheme using only elemen-tary modular arithmetic over the integers, can encrypt1bite plaintext to a large integer. In the thesis, they reduce the security of the fully homomorphic encryption scheme to the hardness of the approximate-GCD problem[5] and SSIP problems.In2011, Coron and Mandal propose an improvement on the original DGHV scheme as the large public key size. By using the quadratic form in the public key elements instead of a linear form, they reduce the public key size from O(λ10) to O(λ7)[7]. They also prove that the scheme’security remains on a stronger variant of the approximate-GCD problem.In2013, Coron and Lepoint propose another improvement on the original DGHV scheme as the large ciphertext expansion ration. By using the Chinese Remainder Theorem, to encrypt multiple bits into a single ciphertext, extend the fully homomorphic encryption scheme over the integers to batch fully ho-momorphic encryption [8]. Therefor the ciphertext expansion ratio reduced from O(λ5) toO(λ3).In this paper, we show another improvement on the original DGHV scheme as the large ciphertext expansion ratio. By using the knowledge on{0,1}k, can convert k bits plaintext into an integer in (0,...,2k-1), then encrypt the integer, extend the original DGHV scheme to batch fully homomorphic encryption. In the DGHV scheme, the ciphertext has the form c=q· p+2· r+m, can convert to c=q· p+2k· r+m, where pis the secret key, qis a large random integer and r is a small random in-teger (noise). By setting the security parameters λ’of the improvement scheme as λ+k, where Ais the security parameters of the DGHV scheme, can make the improvement scheme sufficing the correctness, then constructing an effectively fully homomorphic encryption over the integers. Comparing with the DGHV scheme encrypted ed kbits, the improvement scheme can reduce the ciphertext size from O{k·λ10) to O{(k+λ)10), as the public key size growing from O(λ10) to O((k+λ)10)and the private key size growing from O(λ2) to O(k+λ2).