Improved packing for fully homomorphic encryption with reverse multiplication friendly embeddings

• Main Author: Sim, Jun Jie
• Other Authors: Wang Huaxiong
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2024
• Subjects: Mathematical Sciences; Fully homomorphic encryption; Reverse multiplication friendly embeddings
• Online Access: https://hdl.handle.net/10356/173909
• Institution: Nanyang Technological University

The proliferation of digital devices has led to an explosion of data created each day and it is expected that the amount of data generated to increase exponentially as technology advances. While this vast amount of data can provide key revelations and significant findings for businesses, there is a rising trend of individuals lobbying for proper management of this data. This is because this data can reveal highly confidential and deeply personal information. Developments in quantum computing have led cryptographers to review existing protocols that will be vulnerable when quantum computers are practical. There is an ongoing effort by NIST to develop a post-quantum cryptographic standard. Lattice cryptography has emerged as a prime candidate for two reasons. Currently, there are no known algorithms that demonstrate speedups on quantum computers and it was also proven that the worst-case problems used in lattice cryptography can be reduced to average-case problems. It is also possible to construct other utility-based encryption schemes from lattice cryptography like fully homomorphic encryption. This thesis is motivated by the use of fully homomorphic encryption to ensure data privacy and security. Our main contribution improves the packing capacity of a fully homomorphic encryption ciphertext. The packing capacity of a ciphertext refers to the ability to pack multiple messages into a single ciphertext, amortizing the cost of ciphertext operations and hence improving the efficiency of the encryption scheme. We describe how reverse multiplication friendly embeddings can be integrated into the plaintext algebra of a fully homomorphic encryption ciphertext and provide two extensions that enhance the efficiency of our modified ciphertext. Subsequently, we extend our techniques to the bootstrapping process of fully homomorphic encryption. The bootstrapping process is computationally the most expensive function in fully homomorphic encryption. We modified the bootstrapping algorithm to be compatible with reverse multiplication friendly embeddings. Our experiments show that we can achieve an improvement of up to 20× against a standard fully homomorphic encryption ciphertext. Experimental performance of the modified bootstrapping algorithm suggests that careful parameter selection is crucial to working with a reverse multiplication friendly embeddings augmented ciphertext.