Design of Practical Homomorphic Schemes

Homomorphic encryption schemes allow computing operations directly on the cipher text. A scheme allowing fairly limited number of operations is said to be somewhat homomorphic and if it allows unlimited operations then it is said to be fully homomorphic. Looking at the recent developments in this area, we identify three directions: first is based on Ideal Lattice, second is based on Approximate Greatest Common Divisor (GCD) and the third is based upon Learning with Errors. In the Lattice based direction, Gentry's scheme is a popular fully homomorphic scheme and considered as blueprint for further improvements. However, it has high computation requirements and is unpractical for present day applications. In the last few years, homomorphic schemes have been proposed with (a) lower computational complexity (b) improved bootstrapping (c) reduction in the ciphertext size (d) reduction in the public key size and (e) improved security. Apart from algorithmic aspects, improvements in hardware implementation of homomorphic schemes for practical usage were also reported. This paper presents the theory and applications of homomorphic encryption and the mathematical primitives used for their construction. Schemes based on the above three directions are explained together with their advantages and limitations. Basis for improvement of these schemes are also presented. Finally, practical implementation of a scheme based on approximate GCD is presented along with supporting experimental results.