An Efficient Homomorphic Encryption Protocol for Multi-User Systems

Date Added: Feb 2012
Format: PDF

The authors have presented a novel non-circuit based homomorphic encryption algorithm. Their scheme is fully homomorphic, but it is not semantic secure. The security of their homomorphic encryption scheme is equivalent to the well known large integer factorization problem (which is also the security basis for RSA), but it requires a chosen bound on the plaintext attack. Even though Gentry's and the subsequent solutions are semantic secure, their time complexity is too high for practical use. Also, its circuit based approach suffers from a significant overhead. Their scheme yields a very practical time complexity for encryption, decryption, and computation on ciphertexts.