Practical Fully Homomorphic Encryption and Applications - Cyber
Abstract
Efficient fully homomorphic encryption and applications to private search and information retrieval Delaram Kahrobaei1, Ha T. Lam2, and Vladimir Shpilrain3 1 City University of New York dkahrobaei@gc.cuny.edu 2 Infoshield hlam@gc.cuny.edu 3 City University of New York shpil@groups.sci.ccny.cuny.edu Given society’s dependence on information technology, the commercial impact of a variety of cryptographic products is clear. Homomorphic encryption, in particular, allows companies and individuals to protect the privacy of their data in various electronic interactions, especially those carried out in a shared public infrastructure such as a Cloud. We have developed a fully homomorphic encryption algorithm that is by far more efficient than the existing solutions. The most widely known existing solution to the homomorphic encryption problem is due to Craig Gentry [3], and the relevant software is currently being developed by IBM [4]. This solution relies in its security on the closest vector problem in a lattice. This problem has the property of “random self-reducibility”, which basically means that it is about as hard on average as it is in the worst case. While this property is indeed a good evidence of security, the resulting homomorphic encryption algorithm is too inefficient to be practical. Very informally, the reason is that, to provide semantic security, encryption has to be randomized, but on the other hand, if encryption is homomorphic, then zero should be mapped to zero by the encryption function. To resolve this conflict, the ciphertext zero is “masked” by “noise”. The problem now is that during any computation on encrypted data, this “noise” tends to accumulate and has to be occasionally reduced by recryption (also known as bootstrapping), a process that produces the equivalent ciphertext but with no noise. Recryption is an expensive procedure, its cost can only be balanced with a decrease in the depth of the functions that can be computed on encrypted data. There were other proposals for (fully) homomorphic encryption following Gentry’s, see e.g. [1], [2] (the latter is actually very simple conceptually), but they all still involve “bootstrapping”. Our approach to homomorphic encryption [5] is based on the use of noncommutative groups or rings and isomorphisms between them. We show that recovering the private (decryption) key from the public key in our protocol is at least as hard as the problem of factoring integers. The latter problem has been under a lot of scrutiny over the last decades, but it still resists all attempts at efficient solution in general. Thus, we believe that our approach to homomorphic encryption is competitive with Gentry’s as far as security is concerned. At the same time, our algorithm is orders of magnitude more efficient than Gentry’s
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 12, 2016
- Source ID
- N000141512164
Entities
People
- Delaram Kahrobaei
Organizations
- Office of Naval Research
- Research Foundation of The City University of New York
- United States Navy