Research And Optimize On Fully Homomorphic Encryption Based On The Integers

In the recent years, with the development of cloud computing, secure multi-party computation and wireless sensor networks, security issues related to these technologies has becoming increasingly prominent. There is a crusial but difficult problem in cloud computing as well as secure multi-party computation and wireless sensor networks:how to compute the privacy data without leaking any information. Because of the character of processing directly on the ciphertext, fully homomorphic encryption technology is albe to solve this problem. The research of fully homomorphic encryption has become a subject of great importance in the international cryptographic filed.Fully homomorphic encryption technology based on the integers has simper concept and easier arithmetic. It has been one of the most important research directions of the fully homomorphic encryption system while the DGHV scheme presented in 2010 is the most representative one. Although there has been a major optimization on the algorithm complexity in the DGHV scheme by realizing fully homomorphic encryption with simple modular addition arithmetics and modular multiplication arithmetics, DGHV scheme still has a long way to go because of two main problems:the size of public key is too large for any practical application and the noise of ciphertext grows exponentially when multiplying the ciphertexts, some extremely complicated re-encryption and decryption operations are required frequently so as to suppress the growth of noise. An optimization scheme is proposed in this paper aiming to the above two problems in DGHV scheme. By the proposed scheme, the complexity of fully homomorphic encryption scheme is reduced and operational efficiency is improved accordingly. The main contents and contributions are shown as follows:(1) By studying the public key vector and algorithm structure in the DGHV scheme as well as other two existing public key compression schemes, a new idea to reduce the public key size is proposed where the public key integers used to encrypt the plaintexts are generated by less and shorter public key elements. On the one hand, public key integers in linear form are transformed into several sets of higher order elements when generating secret keys, then the public key integers are generated by multiplying these public key higher-order integers before encrypting plaintexts. The number of public key elements in the public key vector is reduced by this way. On the other hand, the public key higher-order integers are calculated by subtracting the public key higher-order corrections from the pseudo-random numbers initialized by a random seed. Instead of storing the public key higher-order integers directly, there are only the public key higher-order corrections with small length in the public key vector, which reduces the length of public key elements. The proposed HOEC-PKC SWHE scheme in this paper compresses the public key size to O(λ2 logλ). The running time of generating secret keys process and encrypting plaintexts process are optimized as well. According to the definition of permitted circuits, the correctness of presentd scheme is proved. By introducing a more general leftover hash lemma, the proposed scheme is proved to be semantically secure under the assumption of approximate-GCD problem with error-free x0.(2) In order to restrain the growth of noise when homomorphic multiplication, the least significant bit of encryption operation is replaced by the most significant bit. The noise of ciphertexts grows linearly when multiplying the ciphertexts by using some approximate multiple of the square of private key to generating public keys and adopting the ciphertext conversion process. Combined with the public key compress scheme presented previously, a LNC-LHE scheme which can support thousands of multiplications on ciphertexts is proposed. By analyzing the growth of ciphertexts noise in LNC-LHE scheme, the deepest multiplicative operational circuit allowed is calculated and set as a threshold. Compared to the previous schemes, where re-encryption and decryption operations are required as long as there is a homomorphic additive operation or a multiplicative operation, LNC-FHE scheme operates re-encryption and decryption only once until ciphertext noise reaches the threshold. The number of complex bootstrapping operations is decreased greatly, the computing efficiency of the fully homomorphic encryption scheme is improved, and the running time is reduced observably. The correctness and semantic security under the assumption of approximate-GCD problem with error-free x0 are proved as well.