💻 computer science

GPIR: Enabling Practical Private Information Retrieval with GPUs

GPIR is a GPU-accelerated Private Information Retrieval system that overcomes memory bottlenecks in multi-client batching through a stage-aware hybrid execution model and optimized data layouts, achieving up to 297.2x higher throughput than state-of-the-art implementations.

Original authors: Hyesung Ji, Hyunah Yu, Jongmin Kim, Wonseok Choi, G. Edward Suh, Jung Ho Ahn

Published 2026-05-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hyesung Ji, Hyunah Yu, Jongmin Kim, Wonseok Choi, G. Edward Suh, Jung Ho Ahn

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Secret Shopper" Problem

Imagine you are at a massive library (the Database) and you want to borrow a specific book without the librarian knowing which book you picked. If you just ask for "Book #500," the librarian knows exactly what you want.

Private Information Retrieval (PIR) is a magic trick that lets you ask for a book without revealing the number. However, doing this magic trick is incredibly hard for the librarian. To keep your secret, the librarian has to look at every single book in the library, perform complex math on them, and then hand you the result.

For a long time, this was too slow to be useful. The librarian (the server) would get exhausted from the math and the walking around the library.

The Problem: The "Batching" Trap

To make this faster, the library decided to hire a team of librarians (using GPUs, which are super-fast computer chips designed for graphics) and let them handle many shoppers at once (called batching).

The authors of this paper discovered that while batching helps, it creates two new, weird problems that break the system:

The "Filing Cabinet" Mismatch (RowSel):
- The Issue: The math the librarians need to do changes depending on the task. Sometimes they need to look at books row-by-row; other times, they need to look at them column-by-column.
- The Analogy: Imagine the books are stacked in a way that is perfect for reading the titles (Row-by-Row), but the librarians need to count the pages (Column-by-Column). To do the counting, they have to stop, take every book out, rearrange the whole stack, count, and then put them back. This "rearranging" wastes a huge amount of time.
- The Fix: The authors redesigned the library so the books are already stacked in the perfect way for counting, eliminating the need to rearrange them constantly.
The "Too Much Stuff" Wall (ExpandQuery & ColTor):
- The Issue: When you ask for many books at once, the amount of "scratch paper" (temporary data) the librarians need to use explodes.
- The Analogy: Imagine the librarians have a small, super-fast desk (the L2 Cache) where they keep the papers they are currently working on. If they only have one shopper, the desk is fine. But if 32 shoppers arrive at once, the desk gets cluttered. The papers fall off the desk, and the librarians have to run to the slow, distant storage room (the DRAM) to pick them up. This running back and forth slows everything down to a crawl.
- The Fix: The authors realized that sometimes it's better to have the librarians work on one step at a time (using the fast desk), and other times it's better to have them finish an entire task before moving to the next (keeping the papers on the desk longer). They built a smart system that automatically switches between these two styles depending on how crowded the desk is.

The Solution: GPIR (GPU-Powered PIR)

The authors built a new system called GPIR that fixes these problems. Think of it as a "Smart Librarian Manager" that does three main things:

The Hybrid Manager: It watches the "desk space." If the desk is small and crowded, it switches to a strategy that keeps data on the desk. If the desk is big enough, it switches to a strategy that does more math at once. This prevents the librarians from running to the storage room.
The Re-Stacker: It rearranges the books (data) so they are already in the perfect order for the math, so no time is wasted shuffling them around.
The Assembly Line: It uses a technique called "pipelining." Imagine the librarians are doing three tasks: A, B, and C. Instead of waiting for Task A to finish for everyone before starting Task B, they start Task B for the first group while the second group is still doing Task A. This keeps the line moving constantly.

The Results: How Fast is it?

The paper tested this system on powerful computers (like the NVIDIA RTX 5090).

Speed: It is up to 297 times faster than the previous best system.
Scale: It can handle huge libraries (4GB of data) without slowing down, even when many people are asking for books at the same time.
Teamwork: They also showed that if you connect multiple computers together, the system scales up almost perfectly, handling even bigger libraries without getting stuck.

Summary

The paper says: "We took a privacy technology that was too slow to be practical, found out that trying to speed it up by doing many things at once actually broke it in two specific ways, and then fixed those breaks with smart data organization and scheduling. Now, it's fast enough to actually use in the real world."

Technical Summary: GPIR: Enabling Practical Private Information Retrieval with GPUs

Problem Statement

Private Information Retrieval (PIR) enables clients to retrieve records from a server-hosted database without revealing the specific record accessed. While lattice-based homomorphic encryption (HE) provides strong privacy guarantees, deploying PIR at scale is hindered by intense server-side computation and memory traffic. Modern protocols, such as OnionPIRv2, involve three phases: ExpandQuery (expanding a query into encrypted indices), RowSel (encrypted row selection), and ColTor (recursive column tournament).

Although GPUs offer massive parallelism suitable for these operations, existing GPU implementations face critical bottlenecks when multi-client batching is employed to achieve high throughput. The paper identifies two primary architectural challenges:

The Cache-Capacity Wall: Multi-client batching expands the working sets of ExpandQuery and ColTor beyond the GPU's L2 cache capacity. This causes transient working-set spikes (due to digit decomposition operations) to become persistent bottlenecks, forcing excessive DRAM traffic and collapsing performance.
Data Layout Conflicts: The RowSel phase reduces to large-scale matrix-matrix multiplications (GEMMs). However, standard HE data layouts are optimized for Number-Theoretic Transforms (NTTs) and are $p$ -major (polynomial-major). This layout is inefficient for the tiling strategies required by high-performance GEMMs, creating a structural mismatch that limits GPU utilization even when arithmetic intensity is high.

Methodology

The authors present GPIR, a GPU-accelerated PIR system that rethinks kernel design, data layout, and execution scheduling to address these bottlenecks.

1. Stage-Aware Hybrid Execution Model

For the ExpandQuery and ColTor phases, GPIR dynamically switches between two kernel granularities based on the working set size relative to the L2 cache:

Operation-Level Kernels: Used when the working set fits within the L2 cache. These kernels execute primitive operations (e.g., NTT, digit decomposition) separately, maximizing occupancy by exploiting fine-grained parallelism (limb-wise and coefficient-wise partitioning).
Stage-Level Kernels: Used when the working set exceeds L2 capacity. These kernels fuse all operations within a single stage (e.g., NTT, decomposition, and accumulation) into one invocation. This retains intermediate transient data in on-chip registers or shared memory, avoiding the "cache-capacity wall" and minimizing DRAM traffic, even at the cost of reduced parallelism.

2. Layout-Aware RowSel Optimizations

To resolve the conflict between NTT-driven layouts and GEMM requirements, GPIR introduces:

Transposed-Layout Design: The system explicitly transposes data to enable $k$ -major or $m/n$ -major layouts suitable for efficient GEMM tiling. This allows for larger tile sizes and better memory coalescing, shifting RowSel from a memory-bound to a compute-bound regime.
Fine-Grained Pipelining: To mitigate the overhead of data transposition, GPIR partitions the $p$ -dimension (polynomial points) and RNS primes. By launching transposition and GEMM kernels in separate CUDA streams and utilizing CUDA Graphs, the system overlaps transposition latency with computation, preventing serialization bottlenecks.

3. Scalable Multi-GPU Execution

GPIR extends to multi-GPU systems to scale both query throughput and database capacity:

DB Sharding: The database is partitioned across GPUs to increase aggregate memory capacity.
All-Gathering Expanded Cts: For the ExpandQuery phase, the system distributes the workload and then all-gathers the expanded ciphertexts across GPUs. This leverages high-bandwidth interconnects (e.g., NVLink) to minimize communication overhead while scaling throughput.
Response Aggregation: Partial results from ColTor are merged with negligible communication cost.

Key Contributions

Architectural Analysis of Batched PIR: The paper characterizes the "cache-capacity wall" in batched PIR, demonstrating how batching shifts bottlenecks from memory bandwidth to DRAM traffic for ExpandQuery and ColTor, while exposing data layout inefficiencies in RowSel.
Stage-Aware Hybrid Execution: A dynamic execution model that selects kernel granularity (operation-level vs. stage-level) based on the working set size, effectively balancing occupancy and DRAM traffic reduction.
Layout-Aware RowSel: A transposed-layout design with fine-grained pipelining that resolves the structural mismatch between NTT and GEMM data access patterns, significantly improving computational throughput.
Multi-GPU Scaling Strategies: Novel coordination strategies for PIR that scale throughput and database capacity with negligible communication overhead, utilizing DB sharding and high-bandwidth interconnects.

Results

Evaluated on an NVIDIA RTX 5090 and H100 GPUs with database sizes ranging from 1 GB to 4 GB:

Throughput: GPIR achieves up to 297.2× higher throughput than PIRonGPU, the state-of-the-art open-source GPU implementation.
Speedup over Baseline: Compared to a baseline implementation based on PIRonGPU with multi-client batching, GPIR achieves a 1.84–2.23× speedup in end-to-end execution time.
DRAM Reduction: The hybrid execution strategy reduces DRAM transactions by up to 1.83× for ExpandQuery and 1.52× for ColTor compared to operation-level kernels.
Multi-GPU Scaling:
- Throughput Scaling: On H100 with NVLink, GPIR achieves near-linear scaling, reaching 3.76× speedup with four GPUs.
- DB Scaling: When scaling the database from 4 GB to 16 GB across four GPUs, GPIR maintains or slightly improves query throughput (up to 1.09×), demonstrating that capacity scaling does not incur proportional performance degradation.

Significance

The paper argues that while multi-client batching is essential for high-throughput PIR, it fundamentally reshapes performance bottlenecks on GPUs. Naïve application of existing GPU kernels fails to address the resulting "cache-capacity wall" and data layout conflicts. By introducing architecture-aware software designs—specifically stage-aware hybrid execution and layout-aware optimizations—GPIR demonstrates that lattice-based single-server PIR can be made practical for large-scale, privacy-preserving database services on modern accelerator platforms. The work highlights that achieving practical PIR requires not just raw computational power, but careful management of memory hierarchies and data movement patterns specific to the PIR workflow.