Implementation and efficiency analysis of the amortized bootstrapping

• Grant number: 24/06478-4
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: August 01, 2024
• End date: July 31, 2025
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Hilder Vitor Lima Pereira
• Grantee: Gustavo Esteche Araujo
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

Fully Homomorphic Encryption (FHE) is an important cryptographic primitive that allows functions to be evaluated on encrypted data. However, each operation on encrypted data adds some noise to the resulting ciphertext, which cannot exceed a certain limit, otherwise, decryption becomes impossible. To overcome this restriction, an operation called bootstrapping is necessary, as it reduces the noise included on ciphertexts. Improving the bootstrapping algorithm is essential for the adoption of FHE in real projects, as it is the most expensive part of this type of cipher. This undergraduation research aims to implement the homomorphic multiplication of the newest amortized bootstrapping algorithm, which was proposed by Liu and Wang (Eurocrypt 2023) and has the potencial to make FHE much more efficient. Note that homomorphic multiplication is the main operation of this algorithm. This implementation will use the Sage language, then it will be translated and optimized for a more efficient language, such as Rust or C++. This research project also aims to provide a library available under a free license, containing the implementation of the proposed homomorphic multiplication for use in any application that wishes to use the GSW homomorphic cipher with slots. After the implementation is finished, the noise growth due to such homomorphic multiplications will be analyzed, allowing for a more precise estimation of the parameters to be used in the homomorphic cipher. Additionally, the implementation will provide insights into the execution time of this bootstrapping, since homomorphic multiplications dominate the algorithm's execution time. The results have the potential to contribute to the research in homomorphic encryption, particularly aiming to guide future research on amortized bootstrapping.