A Probabilistic Homomorphic Encryption Algorithm over Integers - Protecting Data Privacy in Clouds

With a practical homomorphic encryption algorithm, cloud service providers can operate on users´ encrypted data without having to decrypt the data. Currently only one fully homomorphic encryption algorithm and some of its variants are available in literature, first developed by Graig Gentry in 2009. Unfortunately, these algorithms are not practical because of their prohibitively expensive computing cost. This paper presents an efficient homomorphic encryption algorithm which allows both arithmetic additions and multiplications on cipher texts until the data exceeds the size of the decryption key. The proposed encryption algorithm is probabilistic because every time encrypting a same plaintext it will produce a different cipher text. This probabilistic feature is useful in hiding the equality relationship among encrypted data. In this paper, we also discuss the algorithm´s security weakness, which is vulnerable to some attacks. However, in some applications, the algorithm is extremely useful. This paper describes an application of a shared encrypted storage in clouds that the algorithm can be used to protect data privacy from outside attackers. At the end of the paper, we analyze the efficiency of the algorithm, and compare them to the best implementation of the Gentry-like algorithms.