Scheduling general purpose encrypted computation on multicore platform
Date
2023
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
In cloud computing, outsourcing computation-intensive tasks to cloud servers is a common practice for those companies and users with limited computational resources. If the data computed upon is sensitive, however, providing it to a cloud server would expose it to various security risks. Fully homomorphic encryption (FHE) allows a user to outsource computation to a cloud server while preserving the privacy of their personal data. Specifically, the user does not need to provide unencrypted values (called plaintexts) or decryption keys to the server, as FHE allows operations to be performed directly on encrypted data (called ciphertexts). While desirable, a major drawback of these encrypted operations is that they can be orders of magnitude slower than their plaintext counterparts. Moreover, the ciphertexts contain some noise for security purposes, and the amount of noise in a ciphertext grows as more operations are performed. Therefore, each ciphertext can only withstand a limited number of operations before accumulated noise renders decryption impossible. To reduce such noise and allow for unlimited computations, an operation known as bootstrapping is needed. Notably, bootstrapping is significantly slower than encrypted arithmetic operations (e.g., multiplication and addition), which makes it a main performance bottleneck while evaluating FHE programs. ☐ The allocation and scheduling of bootstrapping operations has not been well investigated, in part due to the complexity of the problem and the difficulty in finding an optimal solution. To bridge this gap, this master thesis makes three contributions. First, it formally formulates the bootstrapping scheduling problem by clearly defining the constraints that a FHE program must satisfy to confine the noise growth within a safe limit. It then develops two Integer Programming (IP) models to enforce these constraints in an optimal fashion. The first model minimizes the number of bootstrapping operations in an FHE program, while the second model optimizes the execution time of the FHE program. Since solving these IP models optimally may take exponential time, this thesis also presents a faster heuristic method for choosing bootstrap points for a target FHE program to satisfy the noise constraints and mapping the FHE program to a multi-core system in polynomial time. Last but not least, this thesis also introduces FHE-Runner, developed to faithfully map the generated FHE schedule to a multi-core system for evaluation. Experiments with realistic benchmarks shows that the proposed heuristic provides as much as a 3.22× speedup compared to the baseline method.
Description
Keywords
Compilation, Cybersecurity, Fully homomorphic encryption, Scheduling, Integer programming