This project applies tools from homomorphic encryption to improve security in cloud services. Cloud computing saves money for companies by allowing them to pay for services only if they need them and just at the time that such services are needed, rather than purchasing and maintaining hardware/software that may see little use. The drive to gain these savings may transform both business and personal computing. This new level of resource sharing and complexity naturally generates new problems related to security and privacy, problems that are both novel and challenging. In the broadest sense, homomorphic encryption allows one to borrow computational power from an untrusted source. If made practical, this has especial implications for cloud computing. The software owner may employ homomorphic encryption in this setting to reduce the threat of reverse engineering and to administer software licenses. When made available over a untrusted cloud, the software is run homomorphically, data is submitted and returned in encrypted form, and the execution of instances is highly robust against malicious users. This project removes the uncertainties in the implementation efficiency of homomorphic encryption schemes and improves it to the point where it becomes practical for use in cloud computing. Specifically, the project centers on three modules: instruction set development for homomorphic computing, processor-specific optimizations for homomorphic schemes, and the investigation of new homomorphic schemes.
Fully homomorphic encryption (FHE) is one of the key technologies that will protect sensitive personal data stored on the cloud in the future. In a nutshell, FHE allows an untrusted party to compute functions directly over encrypted data thereby perfectly preserving the privacy of personal data. Such a powerful technology would, for example, allow companies such as Google to return search results to a user without any knowedge of the terms in the query! Unfortunately, for FHE to become practical, a substantial efficiency bottleneck first needs to be resolved. Addressing this efficiency bottleneck has been the primary aim of this project. During the course of this project we have developed new algorithms, clever optimizations to reduce cryptographic key sizes, and employed new computation platforms to bring the performance of FHE technologies closer to what would be acceptable by real-life applications. In our first effort, we have taken advantage of new platforms such as graphics processors (GPUs) commonly used for computer gaming. Such processors are commonly underutilized in server stations. By developing custom software for the Gentry Halevi FHE we have been able to gain 1-2 orders of speedup of FHE operations over common software implementations. This work not only took advantage of GPUs but also introduced many new optimizations such as taking advantage of special number representations and precomputations to achieve the cited speedup. In the next phase of the project, we developed a new class of FHE algorithms based on the NTRU cipher. To achieve this, we have also tailored and implemented arithmetic operations in GPUs that handle very large degree polynomials. In this endeavor, we have observed similar speedups, i.e. 1-2 orders of magnitude, compared to comparable CPU implementations. By utilizing the NTRU-based library, we were able to evaluate the AES block cipher homomorphically more than 40 times faster than earlier implementations. Furthermore, with a clever specialization technique, we managed to reduce the public evaluation key sizes from several hundred gigabytes down to less than 64 Gigabytes, thereby allowing efficient homomorphic evaluation of complex circuits on common light clients (i.e. non-server platforms). In contrast, earlier FHE implementations required high-end expensive servers with huge memory resources. To assess the suitability of the somewhat homomorphic encryption techniques we developed for private information retrieval (PIR), we devised and implemented a batched PIR scheme. PIR is a standard building block for many cryptographic schemes, and informally it allows a client to retrieve data from a curated database without revealing to the server which data was retrieved. While the computational complexity is high, the bandwidth performance is significantly better than existing techniques. With our PIR work, we demonstrated that, when carefully calibrated, FHE techniques can become as practical as and, in some respects (e.g. bandwidth), even more efficient than traditional multi-party computing techniques. Finally we went beyond CPU and GPU software optimizations and explored the power of custom hardware implemetations. We developed custom design blocks to support large integer arithmetic operations. This arithmetic core was then extended to form the first custom ASIC FHE design to provide a complete implementation of an FHE scheme. Synthesis results showed that it is possible to gain an additional 1-2 orders of speedup over software implementations. At the intellectual level, we determined that the bottleneck in FHE hardware implementations lies in the memory interface. This study further motivates the need for architectural innovations to support FHE evaluation and explores gains that may be obtained using such innovations in custom ASIC hardware. A possible new direction to explore would be to consider specialized cores in multi-core systems where this special core is customized to provide hardware acceleration for FHE evaluation. With this work, we have demonstrated that significant gains can be achieved by carefully studying FHE algorithms from a hardware viewpoint and providing optimized algorithms to support FHE operations on CPUs as well as on computationally more powerful platforms such as GPUs. Furthermore, we demonstrated that an additional two orders of magnitude speedup is possible via innovations at the hardware level.
