Paper 2012/193

An Efficient Homomorphic Encryption Protocol for Multi-User Systems

Liangliang Xiao, Osbert Bastani, and I-Ling Yen

Abstract

The homomorphic encryption problem has been an open one for three decades. Recently, Gentry has proposed a full solution. Subsequent works have made improvements on it. However, the time complexities of these algorithms are still too high for practical use. For example, Gentry’s homomorphic encryption scheme takes more than 900 seconds to add two 32 bit numbers, and more than 67000 seconds to multiply them. In this paper, we develop a non-circuit based symmetric-key homomorphic encryption scheme. It is proven that the security of our encryption scheme is equivalent to the large integer factorization problem, and it can withstand an attack with up to m ln⁡poly⁡(λ) chosen plaintexts for any predetermined m, where λ is the security parameter. Multiplication, encryption, and decryption are almost linear in mλ, and addition is linear in mλ. Performance analyses show that our algorithm runs multiplication in 108 milliseconds and addition in a tenth of a millisecond for λ=1024 and m=16. We further consider practical multiple-user data-centric applications. Existing homomorphic encryption schemes only consider one master key. To allow multiple users to retrieve data from a server, all users need to have the same key. In this paper, we propose to transform the master encryption key into different user keys and develop a protocol to support correct and secure communication between the users and the server using different user keys. In order to prevent collusion between some user and the server to derive the master key, one or more key agents can be added to mediate the interaction.