Qingquan Tan
School of Cyber Science and Engineering, Wuhan University, Wuhan, China

Chenkai Zeng
School of Cyber Science and Engineering, Wuhan University, Wuhan, China

Qi Feng
School of Cyber Science and Engineering, Wuhan University, Wuhan, China

Cong Peng
School of Cyber Science and Engineering, Wuhan University, Wuhan, China

Weijia Wang
School of Cyber Science and Technology, Shandong University, Qingdao, China

Debiao He
School of Cyber Science and Engineering, Wuhan University, Wuhan, China

Keywords: Private Information Retrieval, Distributed Point Function, GPU, Acceleration

Abstract

Private Information Retrieval (PIR) enables a client to retrieve a database record without revealing the queried index. Among existing constructions, DPFbased PIR (DPF-PIR) is attractive due to its low communication cost and ease of deployment. However, its server-side computation remains a bottleneck because both computation and memory access scale linearly with the database size. In this work, we present a GPU-accelerated design for DPF-PIR that significantly improves the efficiency of its two dominant components: vector generation and inner product evaluation. For vector generation, we analyze the binary tree expansion of DPF evaluation and develop a GPU-oriented execution strategy that reduces redundant memory accesses and alleviates memory conflicts. For inner product evaluation, we identify that database access dominates runtime and follows a probabilistic access pattern. Based on this observation, we propose a memory-efficient distribution-aware access optimization with thread-level access coalescing, significantly reducing memory traffic. We further leverage CUDA primitives for efficient reduction and optimize batch processing by improving GPU cache utilization.We conduct extensive experiments on two distinct implementations: 1) non-pipelined DPF-PIR, which trades higher memory for low latency, and 2) pipelined DPF-PIR, which reduces memory usage and supports larger batch sizes. Across database sizes from 219 to 224, our non-pipelined PIR improves throughput by 8.20–9.39x over state-of-the-art GPU solutions (Lam et al. ASPLOS 2024) on RTX 4090, while the pipelined version achieves a 1.14–1.87x throughput increase with up to 99% lower memory usage. Compared with high-performance preprocessing PIRs, our solution also achieves at least a 2.27x throughput increase. Our GPU-accelerated design is of independent interest beyond database querying, such as maliciously-secure protocols, secure look-up table evaluation, private read/write for digital currencies, etc.