A New Additive Homomorphic Encryption based on the co-ACD Problem
We propose an efficient additive homomorphic encryption scheme. In our scheme, an encryption of a message is simply its noisy modular reduction by several different moduli. The security of our scheme relies on the hardness of a new problem, the co-Approximate Common Divisor problem. We analyze its hardness by applying all known attacks and devising dedicated attacks. These analyses are not complete, but give sufficiently plausible evidence for the hardness of this new problem. Our scheme has an advantage in the performance since both of encryption and decryption consist of only several modular multiplications where a modulus is a hard-to-factor integer N or its prime factor, whereas the previous require more expensive modular exponentiations. In fact, our rudimentary implementation demonstrates that our public-key encryption scheme requires about 0.72ms, 4.00μs and 0.40μs for encryption, decryption and an addition of ciphertexts, respectively. It also takes about 40μs to compute an encryption of the mean of 1000 integers of 128-bit from their ciphertexts. To the best of our knowledge, our encryption scheme is the most efficient of those that support an additive homomorphic property. As an application of additive homomorphic encryption, we present how to efficiently evaluate a symmetric polynomial by additionally providing ciphertexts of some powers of messages. We also present a threshold version of our encryption scheme for smooth adoption of our scheme to advanced applications such as private set operations.