CS Paper Radar

High-Throughput Private Information Retrieval with on-CPU Accelerators

Gyuyeong Kim

cs.OS cs.CRcs.DB ·submitted 2026-11-02 01:43 UTC · v1

Abstract

Private information retrieval (PIR) hides which record a client retrieves by scanning the entire database, and batching is an effective technique to improve throughput by sharing this scan across queries. However, existing CPU-based solutions gain little from batching because each query still requires its own multiplications, and vector instructions perform only a few at a time. GPUs and other discrete accelerators can accelerate these computations, but require extra hardware and can constrain database size due to their limited memory capacity. In this paper, we present AltoPIR, the first PIR system that leverages on-CPU matrix accelerators such as Intel AMX. AltoPIR keeps the accelerator fed from the CPU caches, reading each database byte from memory once for all queries in a batch and never writing intermediate products to memory. This enables high-performance PIR through efficient batching without requiring discrete accelerators. Our evaluation shows that AltoPIR achieves up to 50.1x higher throughput than existing CPU-based solutions and serves databases larger than a GPU's memory.

Closest papers

Nearest neighbours by meaning across the whole index.

PMKPIR: Parallel Multi-Keyword PIR with Interleaved Batching for Private Boolean Retrieval

cs.CR ·2026-11-18 ·Rongxi Wang, Guanxiong Ha, Chunfu Jia, Minfen Gao, Hanmiaomiao Wang
similarity 0.66
Abstract

Keyword Private Information Retrieval (Keyword PIR) allows users to retrieve data associated with specific keywords from a database while protecting query privacy. However, existing Keyword PIR schemes supporting boolean retrieval either incur high computational overhead due to multiple database traversals, or fail to support universal boolean computation. We propose PMKPIR, a novel keyword PIR scheme supporting both parallel multi-keyword queries and universal boolean computation. We utilize the single instruction multiple data (SIMD) capability of BFV homomorphic encryption to propose an interleaved batching method, and design IBPIR based on this method, achieving the private matching of multiple keywords in a single database traversal. Furthermore, we design a boolean query processing method, extending the parallel capability of interleaved batching from keyword querying to boolean query computation, to support universal boolean computation and accelerate boolean operations. Building upon IBPIR, we integrate this method to further design PMKPIR. To the best of our knowledge, PMKPIR is the first Keyword PIR scheme to support multi-keyword batch matching within boolean queries. Security analysis demonstrates that, consistent with existing PIR schemes supporting boolean retrieval, PMKPIR preserves the core security guarantees of classic PIR. Compared with state-of-the-art schemes, PMKPIR reduces query time, communication overhead, storage overhead, and peak memory by up to 79.06%, 75.00%, 97.92%, and 80.26%, respectively.

0.43

Amora: Communication-Efficient Private Approximate Nearest Neighbors Search

cs.DB cs.CR ·2026-10-15 ·Qiuhao Wang, Zuowei Chen, Xu Yang, Saiyu Qi, Yong Qi
top venue similarity 0.66
Abstract · Accepted at SIGMOD 2027

Approximate nearest neighbors search (ANNS) over cloud-hosted vector databases raises a critical privacy concern: the query vector, which often encodes sensitive user intent, is exposed to the server. Private ANNS (PANNS) allows a client to retrieve nearest neighbors without revealing its query. The state-of-the-art single-server scheme, Pacmann (ICLR'25), achieves high accuracy via graph-based search with private information retrieval (PIR), but incurs substantial communication overhead because each PIR query retrieves only a single vertex. We present Amora, a communication-efficient PANNS system that applies SimplePIR to a partitioned graph index so that one PIR query is amortized over many vertices. To retrieve as much of the distance and neighbor information the search needs under a limited communication budget, Amora adopts a dual-PIR split layout with two heterogeneous PIR matrices that stay balanced in dimension: VecPIR retrieves inner products for an entire partition of vertices as their distance at once, while NbrPIR retrieves necessary neighbor lists at subgroup granularity for graph traversal. This layout shifts the cost model of PIR query from per-vertex to per-partition, which significantly reduces the communication overhead. To further improve efficiency by reducing the number of scans and query rounds in the PIR database, Amora introduces batch PIR to pack multiple queries into one matrix multiplication, centroid-based pruning to filter unpromising partitions, and TopCand exploration that seeds jump-style graph navigation with the closest vertices from each retrieved partition. We evaluate Amora on five datasets spanning 96 to 1024 dimensions and up to 10 million vectors. Compared to Pacmann, Amora reduces online communication by 93--99% while achieving higher search accuracy.

0.37

Hoss: Fast Oblivious Semantic Search with Heterogeneous GPU-CPU-TEE Architecture

cs.CR ·2026-09-03 ·Jianzhang Du, Weijie Huang, Chenghong Wang, Nicolas Tsagareli, Yukui Luo +2 more
benchmark similarity 0.65
Abstract

Semantic search is widely deployed in modern AI systems, but protecting both data contents and access patterns remains challenging. The current state-of-the-art system, Compass, achieves oblivious semantic search by building an optimized ORAM over HNSW graphs. However, even with aggressive optimizations, it still incurs large overheads. Closing this performance gap is fundamentally difficult: Compass has already removed most cryptographic overheads, leaving ORAM accesses as the dominant cost, which are constrained by well-known Omega(log N) bandwidth lower bounds. Our key insight is that traditional ORAM overhead stems from the assumption of limited private memory, whereas modern GPU TEEs provide large private memory (Pmem) that blinds internal access patterns (Hunt et al., NSDI '23). This shift opens a new design space. We therefore propose Hoss, a first-of-its-kind oblivious semantic search system with a heterogeneous CPU-GPU TEE architecture that supports fast, scalable search with low cost of ownership. In Hoss, the GPU TEE's large Pmem hosts the hot-path HNSW traversal, while the lower layers of the graph, if they exceed GPU capacity, are offloaded to CPU TEEs. The system invokes oblivious primitives only when accessing these lower layers. The availability of large Pmem also enables new optimization opportunities. For example, Hoss features a host-access ORAM mechanism that goes beyond traditional performance constraints and incorporates several data-dependent optimizations that are not possible in prior designs. We implement a prototype of Hoss and benchmark it against Compass. Our results show that Hoss achieves up to 67x speedup while maintaining high recall, with larger gains at scale.

0.17

Hidden in Plain Sight: Privacy-Enhanced Computing Through Register Renaming

cs.AR cs.CR ·2026-11-09 ·Ahmed Nematallah, Stefanos Kaxiras
similarity 0.64
Abstract

Privacy-Enhanced Computing (PEC) is a mechanism to hide program secrets from the outside world without paying the cost of fully-homomorphic encryption. Previous work has developed hardware mechanisms to achieve this goal but they require a dedicated processor enclave where all computations are done, requiring duplicate ALU resources and limiting the performance of PEC-utilizing applications due to not being able to access the full compute resources of the processor (e.g., multiple execution units and vector units), or not being able to execute PEC instructions in parallel and out-of-order. In this work, we introduce HPS-PEC (Hidden in Plain Sight PEC), a novel method of utilizing existing infrastructure in the CPU to achieve PEC with minor modifications to the architecture. We show that, across 25 VIP-Bench benchmarks and with a 7-cycle QARMA-64 cipher, HPS-PEC runs encrypted code at 3.41x the execution time of unprotected native code (geometric mean), of which 1.03x is the cost of data-oblivious code itself, and is 1.26x faster than a Sequestered Encryption (SE) unit while utilizing under a third of its dedicated area. Our method keeps plaintext out of reach of every instruction, as an enclave does given a correctly functioning renamer and register file, which every program already depends on.

0.20

Chimera: Efficient Multi-Vector Retrieval via GPU-CPU Co-Processing

cs.DB ·2026-08-24 ·Yanqi Chen, Juelin Liu, Alexandra Meliou, Xiao Yan
similarity 0.62
Abstract

Multi-vector retrieval has become an important primitive for fine-grained matching in information retrieval, with emerging applications in areas such as recommender systems and bioinformatics. However, its high computational complexity and memory costs make low-latency retrieval difficult. Prior systems have attempted to optimize query latency, but their designs remain CPU-centric. While GPUs offer substantial computational advantages, their limited memory capacity necessitates a heterogeneous architecture in which the dataset resides in host memory and the GPU serves as an accelerator. Existing GPU-based system, PLAID, is bottlenecked by CPU-GPU data movement, as vector data must be transferred from host memory to the GPU at query time. We propose Chimera, a GPU-CPU co-processing system for multi-vector retrieval that eliminates this transfer bottleneck. Chimera stores highly compressed, low-precision quantization codes on the GPU while maintaining high-precision data in CPU memory. At query time, it leverages GPU-resident data for efficient candidate generation and filtering, and further refines results through a GPU-CPU collaborative scoring scheme that completely avoids vector data transfer while enabling computation overlap. Experiments on real-world datasets demonstrate that Chimera significantly outperforms existing approaches, achieving up to 59.5x higher QPS at the same recall level.

0.33

CAROUSEL: GPU-Accelerated Private Vector Search via Homomorphic Sketching

cs.CR ·2026-11-07 ·Sohaib, Divyakant Agrawal, Amr El Abbadi, Soamar Homsi
similarity 0.61
Abstract

Vector search on untrusted infrastructure exposes the \emph{query embedding}, a faithful summary of the user's intent. Fully homomorphic encryption can hide the query, but existing approaches still require a full scan followed by ranking of encrypted scores. Scalable private systems avoid encrypted ranking by either sending scores from a single cluster to the client or moving the search to the client, which must first stream the entire vector index for preprocessing. We present \textsc{Carousel}, which instead scores the full corpus under encryption and compresses the results for client-side ranking. The server scores every vector under encryption, raises the scores to a power that preserves their order by magnitude while suppressing all but a handful, and compresses the resulting sparse vector into a logarithmic number of ciphertexts using homomorphic additions alone. Because every vector is scored, \textsc{Carousel} incurs no recall loss from discarding candidates. Since clients hold no database-dependent state, insertions and deletions take effect immediately at the cost of a single vector write. \textsc{Carousel} searches $1$ billion vectors of BIGANN SIFT1B across multiple GPUs and achieves recall@100 of $0.9715$. At $100$ million SIFT vectors, it achieves recall@100 of $0.9845$ with a query latency of $3.735$ seconds on a single GPU.

0.20

Tile-Based Decompression in Compiled GPU Engines

cs.DB cs.DC ·2026-10-23 ·Antonio Boffa, Ananya Gupta, Hamish Nicholson, Anastasia Ailamaki
top venue similarity 0.61
Abstract · 15 pages, 6 figures, 3 tables. Accepted to PVLDB Vol. 20

Modern GPUs reach record analytical performance only when a query's working set fits within its GPU memory budget, and that budget is under growing pressure: GPUs are partitioned and shared, working sets are outgrowing high-bandwidth memory (HBM), and HBM is a fixed on-device resource whose per-dollar capacity has stagnated across generations. Lightweight compression can relieve this pressure by shrinking both footprint and bandwidth demand, but existing GPU compressed-execution techniques either bind decompression to a specific execution model or materialize decompressed columns in HBM before query execution. We present a compression subsystem for compiled GPU query engines that treats decompression as a first-class physical operator. Compression-specific logic is isolated behind a narrow backend interface, so new GPU-oriented encodings can be added without rewriting downstream operators. We implement the design in Proteus and study where decompressed values should be materialized in the GPU memory hierarchy. Our compiler-integrated shared-memory strategy fuses cooperative tile decompression with tuple-at-a-time query execution inside a single generated GPU kernel, avoiding decompressed-column materialization in HBM. Compared with HeavyDB and Sirius on GPU-resident data, fused on-chip decompression achieves competitive query times while reducing the resident memory footprint by up to 4x and memory-bandwidth consumption by up to 6x.

0.33

PixCrypt: Fast Fine-Grained FHE with Range-Aware Caching

cs.CR ·2026-09-12 ·Chao Wang, Shubing Yang, Xiaoyan Sun, Yan Bai, Jun Dai +1 more
published similarity 0.61
Abstract · 20 pages, 4 figures. Accepted at ICICS 2026

Many analytics tasks require secure computation over encrypted data. In particular, fine-grained data such as pixel-level images require higher precision, as every pixel can directly affect outcomes in tasks like tumor segmentation and anomaly detection. While Multi-Party Computation (MPC) is interactive, Differential Privacy (DP) protects only aggregate values, and Partially Homomorphic Encryption (PHE) lacks multiplicative support, none of them can efficiently handle fine-grained data analytics. Fully Homomorphic Encryption (FHE) uniquely enables arbitrary operations on encrypted pixels but remains computationally expensive, posing significant challenges for both software and hardware accelerators. We present PixCrypt, a caching-based acceleration mechanism for fine-grained fully homomorphic encryption. PixCrypt replaces expensive fresh ciphertext generation with cache retrieval and coefficient-level operations across CKKS, BFV, and BGV, while randomized reconstruction ensures that ciphertexts do not repeat. Its linear noise growth reduces the need for bootstrapping and lowers NTT load, improving hardware accelerator efficiency. This design yields up to 35x faster fine-grained encryption and maintains IND-CPA (Indistinguishability under Chosen Plaintext Attack) security. Experiments on five real-world pixel-level image processing tasks show that PixCrypt significantly improves the practicality of FHE for privacy-preserving analytics.

0.28