Accelerating homomorphic encryption for privacy-preserving applications

In the first industrial revolution, steam power transformed production from manual to mechanized. In the second industrial revolution, electric energy is the driving force of mass production. The third industrial revolution witnessed the birth of automatic production from electronics and information technology. Today, it is believed that data is the most essential factor that lays the foundation of the fourth industrial revolution. The recent emergence of new paradigms of automation such as Big Data, Internet of Things, Cloud Computing, Artificial Intelligence, etc. has assisted humanity greatly in collecting, processing, sharing, and exploiting the massive data generated in every second. The disappearance or closing of physical space and time barriers has led to boosted efficiency, higher level of productivity and cost reduction. However, these developments come with the sacrifice of user privacy since intensive collection and sharing user information can significantly increase the chance of data leakage. Recent incidents of data breaches have raised an increasing public concern about whether current practices can completely prevent private information from falling into the hands of unwanted party. Homomorphic encryption, a concept that is regarded as the cryptography holy grail, is considered the most promising solution for privacy preservation for sensitive applications. This concept guarantees data privacy by allowing computation to be performed directly on encrypted data without the need for decryption, and keeping the final result in encrypted form. Thus, only data owners, who are in possession of the secret key, can decrypt the encrypted result. Despite its theoretical elegance and correctness, as well as major advancements since its inception, homomorphic encryption is still far from being practical for large scale deployment due to its computational complexity, and exorbitantly large and massive parameters. Thus, the primary objective of this thesis is to improve the performance of homomorphic encryption. Throughout the history of cryptology, hardware platforms have been successfully used for alleviating performance and bottleneck computations. The limitations of state-of-art hardware implementations of homomorphic encryption are identified and viable solutions are proposed in this research. First of all, a fast residue-to-binary conversion method is presented. To accelerate large integer arithmetic, existing hardware implementation of homomorphic encryption exploit very high cardinality arbitrary moduli sets of residue number system. However, large modulo operation and limited number theoretic property of arbitrary moduli set cause slow residue-to-binary conversion and significantly undermine the gained benefit. The proposed method base-extends from arbitrary moduli set to the special moduli set {2n-1, 2n, 2n+1} before the final conversion. Thanks to the smaller and parallel operations of base extension as well as efficient reverse conversion method for this special three-moduli set, the proposed method is 2.25 ~ 6.8 times faster than existing residue-to-binary converters for the same large arbitrary moduli sets for homomorphic encryption, and can improve the overall speed of existing hardware implementation of homomorphic encryption by 10.2% to 32.08%. Secondly, a custom implementation of Number Theoretic Transform is presented. Number Theoretic Transform is the essential algorithm to accelerate the bottleneck operations in homomorphic encryption. Although efficient implementation of Number Theoretic Transform on various software and reconfigurable hardware platforms has been widely studied, its ASIC design remains unexplored at the time of this research. By optimizing the modulo multiplier designs of Barrett and Montgomery multiplication algorithm, and designing the butterfly circuit around two parallel half-sized dual-port RAMs, the proposed custom architecture substantially cut down the latency and boost the throughput of homomorphic encryption for large parameter sets by 28.38% to 54.85% comparing with previous architectures on reconfigurable hardware. While the performance can be boosted by hardware accelerators, noise growth in homomorphic encryption can increase the ciphertext size and severely limits the performance of homomorphic applications. A method is proposed to prevent the noise growth from affecting the size of the ciphertexts via the homomorphism of residue number systems and fuzziness offered by fuzzy vault construction. For the same application, the proposed method achieves a smaller ciphertext size compared with other homomorphic encryption schemes. For logistic regression model, the CPU implementation of the proposed method can achieve a speedup of 5.34 times over the implementation of an existing scheme on a powerful CPU-GPU platform.Doctor of Philosoph