TL;DR
This paper presents a GPU-accelerated implementation of a computationally private information retrieval (cPIR) scheme based on somewhat homomorphic encryption (SWHE). By optimizing polynomial arithmetic operations for GPUs, they achieve significant speedups (up to 34x) compared to CPU implementations, making private data retrieval more practical.
What Problem Does This Paper Address?
Private Information Retrieval (PIR) schemes allow a client to retrieve data from a server without revealing which data item was requested. While information-theoretic PIR exists, computational PIR (cPIR) offers a more practical approach by relying on the computational difficulty of certain cryptographic problems. Some advanced cPIR schemes leverage the power of homomorphic encryption, particularly Somewhat Homomorphic Encryption (SWHE), which allows computations on encrypted data. However, these SWHE-based cPIR schemes often suffer from high computational costs, making them impractical for real-world applications. This paper aims to bridge this gap by significantly accelerating an existing SWHE-based cPIR scheme using Graphics Processing Units (GPUs), which are well-suited for parallel computations.
Methods
The core of this work lies in optimizing the computational bottleneck of the SWHE-based cPIR scheme for GPUs. The authors focus on tailoring the scheme proposed by Doröz et al. to leverage the massive parallelism of GPUs. Key techniques include:
- Custom CUDA Code for Polynomial Arithmetic: They developed optimized CUDA code to handle large-degree and large-coefficient polynomial operations, which are fundamental to the cPIR scheme. This includes modular multiplication/reduction and modulus switching.
- Number Theoretic Transform (NTT): For efficient polynomial multiplication, they employ the NTT, a fast algorithm for computing Discrete Fourier Transforms, which is crucial for speeding up polynomial operations.
- Chinese Remainder Theorem (CRT) Domain Operations: To manage large coefficients and enable parallel processing, polynomials are represented in the CRT domain. This allows complex operations to be broken down into independent operations on smaller polynomials.
- Optimized Modulus Switching: Modulus switching is a critical operation in SWHE to manage noise growth during computations. The paper presents an optimized approach for modulus switching within the CRT domain, reducing the need for expensive inverse-CRT operations.
- GPU Memory Management: Careful management of GPU memory, including pre-allocation and chunking, is used to minimize memory access latencies and overhead.
Datasets
Not discussed in the paper. The paper focuses on implementing and evaluating a PIR scheme on a simulated database.
Key Insights and Ideas
- GPU Parallelism for Cryptography: The paper demonstrates that the inherent parallelism of GPUs can be effectively harnessed to accelerate computationally intensive cryptographic primitives like those used in SWHE-based PIR.
- CRT and NTT Synergy: Combining the CRT for breaking down computations and NTT for fast polynomial multiplication is a powerful strategy for optimizing polynomial arithmetic on GPUs.
- Domain-Specific Optimization: Tailoring the implementation to the specific operations of the cPIR scheme and the architecture of GPUs (e.g., CUDA) is key to achieving significant performance gains.
- Modulus Switching Efficiency: Optimizing modulus switching within the CRT domain is crucial for maintaining performance in SWHE-based schemes, as it directly impacts the number of expensive inverse-CRT operations.
Key Results
The implementation achieves substantial speedups compared to a pure CPU software implementation of the same cPIR scheme:
- Index Comparison: 14-34 times speedup.
- Data Aggregation: 4-18 times speedup.
- Specifically, for a database size of 64K entries, their index comparison implementation is about 33 times faster, and data aggregation is 18 times faster than the previous implementation by Doröz et al.
Limitations and Future Work
- GPU Hardware Dependency: The performance gains are tied to the specific GPU hardware used (NVIDIA GeForce GTX 690). While the techniques are general, actual speedups may vary on different GPU architectures.
- Data Transfer Latency: While efforts are made to hide data transfer latencies, they remain a factor, especially for smaller databases or less frequent operations.
- Future Work: The authors suggest that performance can be further improved with multi-GPU setups, as the algorithm exhibits a high degree of parallelism. Further optimizations for specific operations and broader applicability to other SWHE-based schemes are also implied.
Summary updated