Accelerating SWHE based PIRs using GPUs

Wei Dai, Yarkin Doröz, Berk Sunar

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

Abstract

In this work we focus on tailoring and optimizing the computational Private Information Retrieval (cPIR) scheme proposed in WAHC 2014 for efficient execution on graphics processing units (GPUs). Exploiting the mass parallelism in GPUs is a commonly used approach in speeding up cPIRs. Our goal is to eliminate the efficiency bottleneck of the Doröz et al construction which would allow us to take advantage of its excellent bandwidth performance. To this end, we develop custom code to support polynomial ring operations and extend them to realize the evaluation functions in an optimized manner on high end GPUs. Specifically, we develop optimized CUDA code to support large degree/large coefficient polynomial arithmetic operations such as modular multiplication/reduction, and modulus switching. Moreover, we choose same prime numbers for both the CRT domain representation of the polynomials and for the modulus switching implementation of the somewhat homomorphic encryption scheme. This allows us to combine two arithmetic domains, which reduces the number of domain conversions and permits us to perform faster arithmetic. Our implementation achieves 14-34 times speedup for index comparison and 4-18 times speedup for data aggregation compared to a pure CPU software implementation. tion compared to a pure CPU software implementation.
BibTeX
@article{dai2015accelerating,
  author = {Wei Dai and Yarkin Doröz and Berk Sunar},
  title = {{Accelerating SWHE based PIRs using GPUs}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2015},
}

Loading related content...

Figure