VIPIR: A Versatile GPU Framework for Integrating Private Information Retrieval Protocols

Jongmin Kim, Hyesung Ji, Jean-Luc Watson, Charles Gouert, G. Edward Suh, Jung Ho AhnarXiv 2026 · arXiv

TL;DR

VIPIR is a versatile GPU acceleration framework for Private Information Retrieval (PIR) that co-designs cryptographic protocols alongside hardware execution strategies. By introducing a novel, highly parallelized ring-packing method (ExpPack) and optimizing mixed-integer matrix multiplications on Tensor Cores, VIPIR achieves orders-of-magnitude higher throughput than prior systems. Crucially, it eliminates the database bloating that typically exhausts GPU memory, making large-scale, low-latency private data retrieval practical.

What Problem Does This Paper Address?

Private Information Retrieval (PIR) allows a client to fetch a record from a remote database without the server learning which record was requested. To guarantee perfect privacy without relying on trusted hardware, the server must linearly scan the entire database for every single query. This process relies heavily on Homomorphic Encryption (HE), which allows the server to compute on encrypted data.

However, scaling PIR to large databases faces a harsh hardware dichotomy:

  1. Scalar-HE approaches suffer from ciphertext bloating, resulting in massive client-server communication overhead.
  2. Poly-HE approaches reduce communication but cause plaintext bloating, expanding the database size by roughly 4×.

For GPUs, which offer the massive memory bandwidth needed for linear scans but have strictly limited DRAM capacity compared to CPU servers, this 4× database expansion is a fatal bottleneck. Prior GPU-based PIR systems quickly run out of memory (OoM) or bottleneck on slow host-to-device transfers.

Methods

VIPIR resolves these bottlenecks through a hardware-protocol co-design approach:

  • Unified Analytical Model: The authors reframe PIR as a progressive compression process, allowing them to combine the best elements of scalar-HE and poly-HE.
  • New Protocol Designs: They introduce two new protocols: Double-packing (applying data compression twice to minimize communication) and a Hybrid protocol (using scalar-HE for the initial database scan to avoid bloating, then switching to poly-HE for subsequent steps).
  • ExpPack (Expansion-Based Ring Packing): A GPU-friendly packing technique. Instead of the client sending a massive array of ciphertexts (which bottlenecks communication), the client sends a single 96KiB ciphertext. The GPU then expands this on-the-fly into thousands of independent sub-operations, unlocking massive parallelization across hundreds of GPU streaming multiprocessors.
  • Tensor Core GEMM Acceleration: PIR database scans require multiplying an INT8 database by INT32 ciphertexts. Since standard GPU integer pipelines are slow for this, VIPIR decomposes the INT32 matrix into four INT8 matrices using NVIDIA's byte-permutation (prmt) instruction, allowing the entire operation to run on high-throughput Tensor Cores.
  • Memory-Capacity-Aware Streaming: To prevent intermediate data from overwhelming GPU memory during large batches, VIPIR uses stream-wise buffering to reuse memory allocations sequentially without sacrificing parallel execution.

Datasets

The framework was evaluated using simulated databases structured to mimic large-scale lookups (e.g., key-value stores or block-chain anonymization layers). The database sizes tested were 1GiB, 4GiB, 16GiB, and 64GiB, each containing 1 billion records.

The baseline comparisons included open-source CPU and GPU implementations of state-of-the-art PIR protocols, such as Spiral, OnionPIRv2, HintlessPIR, YPIR, InsPIRe, and ShiftPIR.

Key Insights and Ideas

  • PIR as Compression: Viewing PIR protocols through the lens of data compression exposes why previous methods failed on GPUs and reveals the exact mathematical transition points where a hybrid protocol can bypass database bloating.
  • Hacking Tensor Cores for Cryptography: Cryptographic workloads often require wide integer types (like INT32 or INT64). VIPIR proves that instead of waiting for native wide-integer Tensor Cores, researchers can efficiently decompose these types at the byte level to exploit existing INT8 matrix math pipelines.
  • Trading Compute for Communication: In modern networks, bandwidth is often the bottleneck. ExpPack intentionally increases the server's computational burden (via on-the-fly ciphertext expansion) to drastically reduce the network footprint, a trade-off that modern GPUs are perfectly equipped to handle.

Key Results

VIPIR was evaluated on an NVIDIA H100 NVL (94GB) GPU:

  • Throughput: VIPIR achieved 163.1 to 232.8 queries per second (QPS) on a 64GiB database, outperforming the state-of-the-art GPU baseline (ShiftPIR) by 652.6× to 931.3×.
  • Latency: For a 64GiB database, VIPIR executed queries in just 33.0–33.5 ms. This is remarkably close to the absolute hardware limit: simply streaming 64GiB of raw data out of the H100's High Bandwidth Memory (HBM) takes 19.7 ms.
  • Memory Efficiency: While prior poly-HE protocols suffered from Out-of-Memory failures on a 16GiB database due to the 4× bloating factor, VIPIR successfully processed a full 64GiB database entirely within the GPU's memory.

Limitations and Future Work

  • Multi-GPU Scaling Limits: While VIPIR demonstrates near-linear speedups when scaling from one GPU to two GPUs using NVLink, the authors note that evaluating performance across larger clusters (4 or 8+ GPUs) remains an area for future engineering work.
  • Communication Overhead vs. CPU: In certain configurations (like OnionPIRv2), VIPIR's communication cost was higher than its CPU counterpart, though the authors note this can be mitigated in the future by integrating PRNG seed-matching techniques.

Summary updated

Abstract

While private information retrieval (PIR) enables private database services by fully concealing access patterns, it simultaneously requires high computational throughput, large memory capacity, and substantial memory bandwidth. We introduce VIPIR, a versatile GPU framework that co-designs PIR protocols with GPU acceleration. We develop a unified analytic model showing that state-of-the-art PIR protocols fall into two categories with complementary limitations, and propose two protocols that flexibly combine techniques across these categories, overcoming the limitations of both classes. These protocols incorporate a GPU-friendly data compression method called expansion-based ring packing (ExpPack), which offers a high degree of parallelism and minimal communication cost. VIPIR applies further optimizations to core operations, including number-theoretic transforms (NTTs) and various matrix-matrix multiplications (GEMMs). Notably, we develop a tensor-core-based execution method for database multiplication by interpreting it as a mixed-integer-type GEMM. We also design memory-efficient scheduling methods that minimize intermediate buffers and enable multi-GPU scaling under memory capacity constraints. Overall, VIPIR achieves orders-of-magnitude higher throughput than prior PIR systems while reducing communication and memory overheads, making large-scale PIR practical.
BibTeX
@misc{kim2026vipir,
  author = {Jongmin Kim and Hyesung Ji and Jean-Luc Watson and Charles Gouert and G. Edward Suh and Jung Ho Ahn},
  title = {{VIPIR: A Versatile GPU Framework for Integrating Private Information Retrieval Protocols}},
  year = {2026},
  eprint = {2606.11536},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.11536},
}

Loading related content...

Figure