arXiv CS open access

High-Throughput Private Information Retrieval with on-CPU Accelerators

Gyuyeong Kim · arxiv_cs

arXiv CS · Papers

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

High-Throughput Private Information Retrieval with on-CPU Accelerators

arXiv:2611.02376v1 [cs.OS] 2 Nov 2026

Gyuyeong Kim Yonsei University

Abstract

A PIR system can improve throughput through cross-client batching [48, 53], which combines multiple clients’ queries into one matrix multiplication over the database. Batching reduces memory traffic per query but leaves computation unchanged, eventually shifting the bottleneck to computation. This limits throughput gains on CPUs, whose vector instructions multiply only a few integer pairs at a time (e.g., 16 pairs of 32-bit integers with AVX-512). Recent systems use GPUs [33, 35, 62], including their tensor cores, or dedicated accelerators [36] to overcome this bottleneck. However, these devices require additional hardware and limit the database to the memory of each device. Therefore, we ask: Can a commodity CPU server achieve high PIR throughput without a discrete accelerator? To answer this question affirmatively, we present AltoPIR, the first PIR system that leverages the capability of on-CPU matrix accelerators. An on-CPU matrix accelerator, such as Intel AMX [31], is a unit inside each CPU core that multiplies small matrices of low-precision numbers, including 8-bit integers, much like a small tensor core. It is an attractive vantage point for a PIR batch for three reasons. First, the server work of a batch consists of two matrix products. The scan multiplies the database by the encrypted queries, and packing compresses each result into a short response with a key that the client sends. Once every 32-bit encrypted value is split into four bytes, called limbs, both products run on the accelerator. The accelerator performs far more multiply-adds per cycle than vector instructions such as AVX-512. Second, the built-in accelerator reads data from the CPU server’s memory, which is far larger and cheaper per byte than the memory of a discrete accelerator. Lastly, because recent server CPUs already include it, we can deploy AltoPIR easily without additional hardware. Unfortunately, two characteristics of an on-CPU accelerator make it hard to leverage for PIR. First, the accelerator holds only a few small operand registers, called tiles, while a GPU keeps large blocks of operands in registers and shared memory. The accelerator runs at its full rate only when new tiles come from the L1 cache. However, a batch touches far more data

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.1× higher throughput than existing CPU-based solutions and serves databases larger than a GPU’s memory.

Introduction

Private information retrieval (PIR) lets a client retrieve a database record without revealing its choice to the server [15, 39]. It enables leaked-password checks [2, 43], unsafe-link checks [37], private web search [26], and private communication [3, 5]. Most PIR schemes require the server to scan the entire database for each query [7], making throughput critical to the cost of serving many concurrent users. Such databases can be large, for example billions of leaked passwords [43], and the server keeps the whole database in main memory. Earlier schemes reduce this cost using a client-side hint, a database digest that each client must download and update as the database changes [17, 27, 70]. This overhead is difficult to amortize for users with short sessions. Therefore, recent work has shifted toward hintless PIR [50, 51, 53], which eliminates this client state by moving the hint-related work to the server. 1

Database

than the caches hold, and a larger batch leaves less cache space for each query. Furthermore, every result must be rebuilt exactly from its limb products. Second, the cores that feed the accelerator must also parse every request and assemble every response, and the accelerator remains idle while they do so. These characteristics pose four technical challenges, which AltoPIR addresses with one placement rule and four mechanisms. Both products multiply a large shared operand (the database or a public matrix) by small per-client operands (encrypted queries or keys). The rule is to keep the small operands in the caches and reuse each piece of the shared operand across all clients, reading it from memory only once per batch. The query-blocked scan (§3.2) and column-group packing (§3.3) apply this rule to the two products. Both recombine their limb products inside the core instead of writing them to memory. Stable placement keeps the scan equally fast after every restart and for large batches (§3.4). Lastly, the in-place engine validates each request in its receive buffer and completes each response in one vector pass (§3.5), freeing CPU cycles to feed the accelerator. We implement a prototype of AltoPIR on a commodity server and evaluate it against the state-of-the-art PIR systems [50, 51, 53, 65]. AltoPIR provides better throughput than the fastest of these systems by 24.2× to 50.1× on databases of 1 GB to 64 GB. Furthermore, AltoPIR keeps its advantage in real applications, under random request arrivals, and beside co-located jobs. In summary, this work makes the following contributions:

Record 0 Record 1 Record 2 Record 3 A 0 1 0 0 B 0 0 0 1 C 1 0 0 0

2.1

E(Record 1) E(Record 3) E(Record 0)

A B C

Packing (client keys)

Encrypted one-hot Scan output, one ciphertext per byte query vectors

Short responses

Figure 1: Three PIR queries answered as one matrix product. Every entry of the query vectors is encrypted. 105

Expected gain Actual gain

104

4 2 1.00 0 1

1.49

1.68

1.72

Clients per Batch

Thr ughput (QPS)

Gain of Batching

(a) Batching efficiency of YPIR [53]

AMX Mem ry AVX-512 VNNI b und

AMX b und

103 102

VNNI b und

Batch Size

256

(b) AMX and AVX-512 VNNI

Figure 2: Existing CPU batching gains far less than expected, while AMX keeps gaining where VNNI stops. that each client downloads [17, 27], the server packs these ciphertexts into a few compact ones with a packing key that the client sends. The server still computes the hint. However, it keeps the hint and derives from it a public matrix for this step, called the packing matrix. Server work as byte matrix products. Both steps of the server are matrix products. In the scan, the database, a matrix of bytes, is multiplied by the query vectors, and packing multiplies the packing key of the client by the packing matrix. The scan reads the whole database. In contrast, the packing matrix has 8,192 rows (one per value of the packing key), one column per byte of a record, and 32-bit entries. Its size depends only on the record size, not on the number of records. For 32 KB records, it takes 1 GB. GPU-based systems that use tensor cores split every 32-bit value x into four bytes, called limbs, with x = x0 + 28 x1 + 216 x2 + 224 x3 . For example, the value 258 has the limbs 2, 1, 0, and 0, because 258 = 2 + 28 . These systems run the scan [35, 62] or both products [62] as 8-bit integer products. In the scan, each database entry is already a byte. Therefore, multiplying it by a 32-bit query value takes four limb products, which are added back with these weights modulo 232 . In packing, both operands have 32-bit entries. Therefore, every product takes 16 limb products, which are added back modulo a 32-bit prime. A short per-request step, called the tail, then combines the two results into the response.

• We identify the matrix accelerators built into server CPUs as a platform for batched PIR without a discrete accelerator. • We design AltoPIR, which places the two products of a batch in the caches of a CPU core and answers requests in place with a vector tail. • We evaluate AltoPIR against four state-of-the-art schemes and show that it outperforms the fastest of them.

Each byte read once serves all clients

Background and Motivation Private Information Retrieval

PIR by example. A PIR protocol hides from the server which record a client fetches [15]. The schemes that we consider build this from a linearly homomorphic encryption scheme, which lets the server multiply encrypted numbers by plain numbers and add them without decrypting [27]. Figure 1 shows the idea with a database of four records. To fetch record 1, client A sends the query vector (0, 1, 0, 0) with every entry encrypted. The server multiplies each record by the matching encrypted entry and adds up the results, which decrypt to record 1. Because every entry looks random to the server, it must touch every record for every query. This scan yields one ciphertext per byte of the record. Recent schemes are hintless [42, 50, 51, 53]. Instead of a digest of the database

2.2

Limitations of Existing Solutions

A single query performs few multiply-adds per database byte. As a result, its scan is limited by memory bandwidth. Cross2

Table 1: Comparison to existing approaches.

Platform

CPU

GPU

High throughput Readily deployable Commodity CPU server Large database support

✗ ✓ ✓ ✓

✓ ✓ ✗ ✗

AMX-Lib

Scan Tail

27 ms 0

Fou tiles loaded Two tiles loaded

N AMX w rk

125 ms

Ideal

✓ ✓ ✓ ✓

100

100100 75

50 0

Time per Batch (ms)

(a) One batch of AMX-Lib

95 58

77 6 11

16 KB (L1)

512 KB 1.5 MB 64 MB (L2) (L2) (Mem.)

(b) Rate of tile multiplications

Figure 3: AMX-Lib leaves the accelerator idle for most of a batch. In (b), operand tiles from the L2 cache or memory keep the accelerator below its peak rate.

client batching [48, 53] stacks independent clients’ query vectors into a matrix without changing any message (Figure 1). This lets one database read serve many queries, reducing memory traffic per query while leaving the arithmetic work unchanged. Therefore, batching improves throughput only when the CPU has spare compute capacity. Existing CPU systems quickly exhaust this capacity because they operate directly on 64- or 32-bit integers. One AVX-512 instruction multiplies only 8 or 16 such pairs, versus 64 pairs of 8-bit integers. For example, YPIR [53] reports at most 1.4× batching gains. In our testbed server, YPIR processes eight clients only 1.72× faster than one at a time (Figure 2 (a)). These schemes also pack each client’s response separately. Recent systems use GPUs (VIPIR [35], SandwichPIR [62], GPIR [33]) or a dedicated accelerator (IVE [36]) to increase compute capacity. However, they require additional hardware, and each accelerator holds only as much of the database as fits in its memory. For example, one A30 GPU has 24 GB [58], whereas the server CPU supports several terabytes of DRAM [29].

2.3

Packing

ASIC CPU ✓ ✗ ✗ ✗

Rest

% of AMX Peak

At peak

YPIR [53], SandwichPIR [62], InsPIRe [50], GPIR [33], IVE ReinsPIRe [51] VIPIR [35] [36] AltoPIR

2.4

A Straightforward Design Is Not Enough

An on-CPU matrix accelerator works like a small tensor core. Therefore, a straightforward solution would be to port the GPU data flow of recent GPU solutions and run each product with the faster of the vendor libraries oneDNN [64] and oneMKL [30]. Figure 3 (a) shows that AMX-Lib, our optimized CPU port of SandwichPIR’s data flow, keeps the accelerator busy for only 22% of a batch of 128 queries on a 1 GB database. We call this ratio the utilization of the accelerator. The idle time has three causes. First, the accelerator holds only eight tile registers. Operand tiles from the L2 cache allow only 58% to 75% of its peak rate, and those from memory only 6%, as Figure 3 (b) shows. Second, the library products suit the shapes of a PIR batch poorly. The scan runs at 34% of the peak rate and reads the database from memory 2.6 times. Packing writes all 16 limb products of every output to memory. Third, request handling and the per-request tail take 37 ms, more than the products would need at the peak rate.

Why On-CPU Accelerators for PIR?

Matrix accelerators in CPU cores. An on-CPU matrix accelerator is a unit built into a CPU core that multiplies small matrices held in dedicated registers. Such accelerators already ship in recent processors, for example Intel AMX [31, 57], the Matrix-Multiply Assist of IBM Power10 [54], and Arm SME [6]. They also support 8-bit integer multiplication with 32-bit accumulation, which AltoPIR uses to multiply database bytes by the byte limbs of encrypted queries. Our prototype uses Intel AMX, which has eight tile registers of 1 KB, each holding a matrix of 16 rows of 64 bytes. One tile instruction multiplies two such matrices and adds the 16 × 16 result to a third tile. Per cycle, the peak 8-bit multiply-add rate of AMX is higher than that of AVX-512 VNNI by 8×. Figure 2 (b) runs AltoPIR on 16 cores with a 1 GB database of 32 KB records, once with AMX and once with AltoPIR-VNNI. Even with VNNI, the throughput gains only 6.0× from batching and then stays near 400 QPS. In contrast, AMX keeps gaining and outperforms it by up to 5.0×. Comparison to existing work. Table 1 compares AltoPIR with existing approaches. AltoPIR meets all four requirements by leveraging the capability of an on-CPU matrix accelerator.

2.5

Technical Challenges

An on-CPU accelerator speeds up PIR only when the system is designed around it. In this context, removing the three aforementioned costs poses four technical challenges. • C1: One pass over the database with query limbs in the core. The database should stream once past the query limbs of all queries, but those of a batch do not fit in the L2 cache (§3.2). • C2: Reducing packing products without collecting them. The reduction needs all 16 limb products of an entry, but those of a batch take hundreds of megabytes (§3.3). • C3: Large batches with stable query limbs. The scan should keep its speed as the batch grows and across processes, but a larger batch fits fewer records of query limbs in the L2 cache (§3.4). • C4: Many requests with little work per request. Copying each request and running its tail one coefficient at a time takes longer than the products would at the peak rate (§3.5). 3

Oﬄine state, built once

Packing matrix in four planes

Tiled database

First response rows Response buﬀers

Clients Requests

Reader threads

Waiting requests form the next batch Front end on other cores

✓ ✗ ✓ Validate in place

Query-blocked scan

Block in L2 cache

Response

Column-group packing

Vector tail

Writer threads

Engine on the cores of one socket, one batch at a time Responses

Figure 4: AltoPIR architecture. The engine answers each batch of waiting requests in four steps (§3.1).

AltoPIR Design

3.1

Overview

for neither a fixed size nor a timer. At a low arrival rate, a timer would add its wait to every query. At a high rate, the next batch fills up during the current one anyway. Therefore, batches stay small at a low rate and grow toward the maximum as the rate grows. The engine answers a batch in the four numbered steps of 1 It checks every request the figure, each on all of its cores. ⃝ frame where the frame arrived, without copying or decoding 2 It runs the scan it, and drops malformed frames (§3.5). ⃝ (§3.2 and §3.4). The scan reads the database from memory once and multiplies it by the query limbs held in the L2 cache. 3 It It recombines the limb sums before they leave the core. ⃝ runs packing (§3.3). Packing reads the packing matrix from memory once and multiplies it by the packing keys held in the L3 cache. It recombines the limb products of each output 4 It runs a tail with while they are still in the L2 cache. ⃝ vector instructions for each client (§3.5). The tail reads the two products and writes the response bytes into one of several rotating buffers. Writer threads send each response from that buffer, and the client decrypts it.

AltoPIR answers the queries of many independent clients together on the matrix accelerators of one CPU socket. It follows the hintless scheme of SandwichPIR [62], which defines what the server computes for each query. The design of AltoPIR decides how a CPU computes these responses quickly. Two characteristics of the accelerator shape this design. First, the accelerator has few operand registers, but each core has megabytes of private L2 cache. Therefore, the key decision is which operand to stream from memory and which to keep in cache. Each product has one large shared operand (the database or packing matrix) and small per-client operands. AltoPIR reads the shared operand only once per batch, minimizing memory traffic, and reuses the per-client operands from cache, a block at a time in the scan. Second, the same cores also handle every request and response. Therefore, AltoPIR neither copies nor decodes requests, and it builds each response with vector instructions. Figure 4 shows the architecture of AltoPIR. Offline state. When the database is loaded, AltoPIR builds the three pieces of offline state at the top of Figure 4. First, it stores the database in tile order, in which every tile that the accelerator loads lies contiguously in memory. Second, it precomputes the packing matrix and splits its 32-bit entries into four byte planes. The first plane holds the lowest byte of every entry, the second plane holds the next byte, and so on, each in tile order. Third, it precomputes the first row of every response ciphertext, which is the same for all clients. All three depend only on the database and the public parameters. Because they are built once, a batch neither changes any layout nor recomputes anything that does not depend on the clients. Life of a request. A client sends one request that holds its encrypted query vector and its packing key. On the left of Figure 4, reader threads append arriving requests to a bounded queue, and a request that finds it full receives a busy reply. When the engine finishes a batch, it takes every waiting request, up to a maximum batch size, as the next batch. It waits

3.2

Query-Blocked Scan

The scan should read each database tile from memory once per batch and multiply it by all queries’ limbs, four bytes per 32-bit value (§2.1). However, the batch’s query limbs exceed L2 capacity, and the four limb products must be recombined exactly. Running general matrix products and recombining afterward would poorly utilize the accelerator for PIR batch shapes and write all limb sums to memory. Our observation is that each record uses only its corresponding query entries. For example, record 2 in Figure 1 uses only the third entry from clients A, B, and C. Therefore, the scan processes one block of records at a time, keeping only that block’s query limbs in L2. This reads each database tile once and recombines limb products before results leave the core. We call this a query-blocked scan. Blocking the queries. Figure 5 follows one block from left to right. For a block of records, the L2 cache holds the four limbs of every query of the batch, which we call the query-limb block. The database tiles of the same records then stream from 4

Tile registers Query tiles of Tiled Query-limb block 4 queries × 4 limbs (half of L2) database L2 cache

Database tiles of one group

Next group of 32 columns

L1 cache After every block Limb 0 ×20 Limb 1 ×28 + Limb 2 ×216 24 Limb 3 ×2

Products of one group

Reduce 32 outputs

Caches

Keys (L3)

Block of sums (L2)

Memory

Matrix slices (L2)

Packing matrix in tile order, read once (a) One column group at a time

Four accumulator tiles Added to one 32-bit of limb sums sum per output

Matrix limb 0 1 2 3 0 0 1 2 3 1 1 2 3 4 2 2 3 4 5 3 3 4 5 6 Equal numbers, equal weight

Figure 5: Query-blocked scan. The database streams past a block of query limbs in the L2 cache, and the limb sums are recombined in the core without reaching memory. memory past the query-limb block, one group of 32 columns at a time. Inside the core, each step loads two database tiles and two query tiles, and each query tile holds the four limbs of four queries. The step adds their four products into four accumulator tiles, which keep one limb sum per output, query, and limb. This 2 × 2 blocking uses all eight tile registers. The opposite order would keep a group of database columns in the core and stream the query limbs past it. It would then read the query limbs from memory once per group, which is far more traffic than reading the database once. Recombining each block. After every block, the engine stores the accumulator tiles into a small buffer in the L1 cache, as on the right of Figure 5. It multiplies the four limb sums of each output by their weights, 20 , 28 , 216 , and 224 , and adds them to one 32-bit sum per output and query. These sums overflow 32 bits but stay exact. This is because the scheme computes the scan modulo 232 , and a 32-bit integer that wraps around performs exactly this reduction. For example, a sum that reaches 232 + 5 keeps 5, which is its correct value modulo 232 . Therefore, the engine can cut the records into blocks anywhere. Only the 32-bit sums, a quarter of the size of the limb sums, ever leave the core. After the last block, one rounding step switches each sum from modulus 232 to the prime modulus of packing. Choosing the block length. A longer block recombines less often. However, all of its query limbs must stay in the L2 cache, the largest cache that a core does not share, next to the database tiles in flight. Therefore, AltoPIR gives the query limbs half of the L2 cache and the database tiles an eighth, and neither pushes the other out. For example, a core with an L2 cache of 2 MB gives 1 MB to the query limbs. With 128 queries of four limbs each, every record needs 512 bytes of query limbs, and a block holds 2,048 records. A 1 GB database of 32 KB records then takes 16 blocks, and each block streams 64 MB of the database past the same 1 MB of query limbs.

3.3

Core

Key limb

Memory

Add equal-weight products into 7 sums Weight each sum into one 64-bit total Fold the upper 32 bits back in, twice Subtract the prime once if needed (b) Reducing one output exactly

Figure 6: Column-group packing. (a) Each core reduces one group of 32 columns while its limb products are in the L2 cache. (b) The 16 limb products of an output share seven weights. products in memory. It multiplies each client’s packing key by a matrix with one column per record byte. Each pair of 32-bit entries yields 16 differently weighted limb products. Wrap-around cannot reduce them, because the prime is not a power of two. A naive approach would store all limb products in an array and reduce them in a separate pass. However, this moves hundreds of megabytes to and from memory, leaving the accelerator idle. Instead, AltoPIR assigns column groups to cores. Each core then holds all 16 limb products of its outputs and reduces them immediately. We call this columngroup packing. Reading the packing matrix once. Packing follows the placement rule of the scan. This is because the packing matrix is shared by all clients and large, while each packing key holds only 8,192 values whatever the number of records. For example, with 32 KB records, the packing matrix takes 1 GB, while the keys of 128 clients take 4 MB. Therefore, AltoPIR reads the packing matrix from memory once per batch and keeps the keys of the batch in the shared L3 cache. The keys of a large batch exceed the L2 cache of a core, and every core reads all of them. Recombining per column group. Figure 6 (a) follows one core. Each core owns a range of groups of 32 columns of the packing matrix. Inside a core, the roles of the two operands turn around. For one group, the core keeps slices of the four byte planes in its L2 cache, and the keys stream past them from the L3 cache. The core collects the 16 limb products of each client and column as 32-bit sums in a block in its L2 cache. When the group is done, it reduces the 32 outputs of every client and moves on to the next group. A split along the key would instead leave partial results of each output on several cores, which would have to combine them through memory. With the split by columns, the large array of the naive approach never exists.

Column-Group Packing

Packing should reduce each output’s limb products exactly modulo the prime without storing the batch’s intermediate 5

Query buﬀer Panel of the block

L2 cache sets, ﬁlled evenly (a) Contiguous panel, 2 MB pages

one array per group of four queries, with the query limbs of all records in record order. With 128 queries over 32,768 records, each of the 32 arrays would take 512 KB, and the 32 KB pieces of one block would lie exactly 512 KB apart. On 2 MB pages, these pieces would all fall into the same quarter of the sets and evict each other, while the other three quarters stay idle. On 4 KB pages, the overlap would depend on the physical pages that each process receives. AltoPIR instead stores each block of query limbs as one contiguous panel in a buffer backed by 2 MB pages, as Figure 7 (a) shows. A panel of 1 MB fills each of the 2,048 sets with exactly eight lines. On 2 MB pages, the virtual address alone decides the set of every line. Therefore, the panel covers every set the same way in every process. Padding the stride, the usual fix, would also avoid the pile-up. However, a good padding depends on the sets and ways of each cache, while a panel covers the sets evenly on any cache. Client chunks. If all clients of a batch formed one block, a larger batch would fit fewer records in the half of the L2 cache reserved for query limbs. For example, doubling the batch would halve the block length. The scan would then run twice as many blocks, and each block would recombine twice as many clients. As a result, the recombination work would grow fourfold. AltoPIR instead splits a large batch into client chunks of 128 clients and runs the scan once per chunk. The block length then stays fixed, and the recombination work grows only linearly with the batch size. For example, 512 clients over 32,768 records form four chunks that each recombine 128 clients over 16 blocks, as Figure 7 (b) shows. Without chunks, the scan would run 64 blocks that each recombine 512 clients. Each chunk reads the database once more. This costs little, because a chunk of 128 clients already makes the scan bound by the accelerator rather than by memory. Chunks matter only when the maximum batch size exceeds 128. Packing is not chunked, because it has no block that shrinks with the batch.

512 clients in chunks of 128, blocks of 2,048 records

4 passes of 16 blocks, each recombines 128 (b) Example of client chunks

Figure 7: Placement of the scan. (a) A contiguous panel fills every set of the L2 cache evenly. (b) Client chunks keep the block length fixed for large batches. Exact reduction modulo the prime. Reducing right away is cheap because of two properties, shown in Figure 6 (b). First, the weight of a limb product depends only on the sum of the positions of its two limbs. Each cell of the grid in the figure shows this sum for one key limb and one matrix limb. For example, key limb 1 times matrix limb 2 has the same weight, 224 , as key limb 2 times matrix limb 1. Therefore, the 16 products of an output fall into seven groups of equal weight. The engine adds up each group and multiplies only seven sums by their weights. Second, the prime is 232 − 12,287, just below 232 . Therefore, 232 equals 12,287 modulo the prime, and the part of a sum above 32 bits folds back in as only 12,287 times its value. For example, 3 · 232 + 7 folds into 3 · 12,287 + 7 = 36,868. As a result, the weighted total of an output fits in one 64-bit lane. Two folds of its upper half and one conditional subtraction of the prime give the exact result, as the four steps of the figure show. All of these steps are vector operations on registers. Therefore, the reduction needs neither a division nor a pass through memory.

3.4

Stable Placement and Client Chunks

The scan should run at the same speed in every process and for every batch size. Otherwise, the same system could run at a different rate after every restart, or slow down when its batches grow. Two effects stand in the way of this goal. First, the scan reuses its query limbs from the L2 cache for a whole block. Therefore, its speed depends on where these limbs land in the cache. Second, a larger batch reuses each database byte for more queries. However, its query limbs take more of the L2 cache, which shortens the block and adds recombination work. The key idea is to make the cache footprint of the scan independent of both the physical pages of the process and the batch size. AltoPIR achieves this with contiguous panels for the first effect and client chunks for the second, as Figure 7 shows. Contiguous panels. A cache stores each line in one of a fixed number of sets, which some bits of its address choose. For example, an L2 cache of 2 MB with 16 ways has 2,048 sets of 64-byte lines, and addresses that lie a multiple of 128 KB apart fall into the same set. A strawman layout would keep

3.5

In-Place Engine and Vectorized Tail

Request handling should not stall the accelerator, which finishes the products of a batch faster than the cores can handle its requests. A request carries a query vector and two keys, one for packing and one for the tail. A typical path would copy each request into library formats and build each response in working buffers. Each copy is a pass through memory. The tail adds an inverse number-theoretic transform (NTT) and four other steps for every client and output polynomial. The NTT is an FFT over integers modulo the prime. A scalar implementation would spend tens of instructions per coefficient. Overlapping this work with another batch would gain little, because both share the cores. The key observation is that the products can read the query vector and keys as they arrive. Therefore, a request needs only to be checked, never decoded or copied. Similarly, the tail of each output needs only its 6

parts of the two products and fits in the L1 cache. As a result, AltoPIR validates requests in place and runs one vectorized tail per output. Validating requests in place. AltoPIR answers requests in the frames where they arrive. The engine checks the lengths, the headers, and the range of every key value of the received frames. It runs these checks with vector instructions, in parallel over the whole batch. A frame that fails a check is removed from the batch and receives an error status. For example, if one frame of a batch of 128 carries a key value at or above the prime, the engine answers the other 127. The check accepts and rejects exactly the frames that a conventional decoder does. The scan, packing, and tail then read the query vectors and keys directly from the frames. Their intermediate results live in buffers that the engine allocates once and reuses for every batch. One vectorized tail per output. The tail runs as one parallel loop over all pairs of a client and an output polynomial. For example, a batch of 128 clients with 32 KB records gives 2,048 pairs, because each response holds 16 polynomials of 2,048 coefficients. For each pair, the tail adds the keydependent term to the packing output, applies the inverse NTT, adds the scan output, switches the modulus, and writes the bits of the second ciphertext row into the response buffer of the client. All intermediate values of one pair fit in tens of kilobytes and stay in the L1 cache. A staged tail that runs each step over the whole batch would instead write every intermediate polynomial to memory and read it back once per step. Every step works on eight coefficients at a time with AVX-512 instructions. Every reduction modulo the prime uses the two folds of packing instead of a division.

3.6

state costs about the same for one changed record as for many. Therefore, updates are best applied in groups. Key-value lookups. Many applications look up records by key, while the scheme fetches them by index. A lookup by key reduces to fetching by index [14]. Each pair is stored in one of two records chosen by public hash functions, as in cuckoo hashing [60]. A client fetches both records and keeps the one that holds its key. Therefore, every lookup sends two queries whether or not the key is present, and the server learns nothing new. However, lookups then run at half the query rate, and the hashing leaves some records empty. Inserting a pair may move a few other pairs, each a record update. Other on-CPU accelerators. Arm and IBM processors also ship matrix accelerators (§2.3) with other tile shapes and register counts. The techniques of AltoPIR rely only on three properties of the accelerator, which multiplies 8-bit integers into 32-bit sums, holds its operands and sums in a few registers, and loads them from the caches. On such an accelerator, the tile shape sets the data layout, the register count sets the scan blocking, and the L2 cache size sets the block length and client chunks. However, an accelerator that takes operands from vector registers changes how the scan holds the query limbs. Furthermore, cores that share one accelerator [10] compete for it. A portable PIR system is our future work. Other matrix-shaped schemes. Other hintless schemes also reduce most of their server work to integer products with an operand that all clients share. However, their operands are often wider than the 32-bit values of SandwichPIR. When the modulus is a power of two, the query-blocked scan applies to such products as well, with more byte limbs per value and wider accumulators per block. A scheme with a prime modulus could instead reduce each output inside the core, as column-group packing does for its prime. However, the extra limb products cost more at small batches. Furthermore, a whole scheme gains only if its per-client steps are batched too, as AltoPIR does for packing.

Discussion

Security. AltoPIR keeps the threat model of SandwichPIR [62], whose scheme it follows. The server is honest but curious about which records the clients fetch. AltoPIR does not protect the database from the clients. Because AltoPIR computes exactly the responses of this scheme, its security analysis carries over. Batching reveals nothing new, because the server already sees which requests arrive together, and the batch time depends only on public sizes. A malformed request cannot change another response, because each response goes only into the buffer of its own request. Removing a malformed request changes only the number of requests. Database updates. When a record changes, the offline state that AltoPIR derives from the database changes too. This state comes from the hint, which is linear in the database. Therefore, changing one record adds one outer product to the hint. The rest of the state depends on the hint but not on the number of records. AltoPIR recomputes it from the updated hint while it rewrites only the changed records. Meanwhile, AltoPIR answers batches with the old state. Clients need no action, because they keep no state. However, recomputing the

Implementation

We build AltoPIR on top of the public code base of SandwichPIR [62], from which it takes the parameters, key generation, and message formats of the scheme. The engine of AltoPIR is new and consists of about 600 lines of C++ with AMX and AVX-512 intrinsics and OpenMP. The server, client, and benchmark programs of AltoPIR add about 1,500 lines of Rust. The scan uses TDPBUUD for unsigned limb products. Packing uses TDPBUSD with the packing matrix stored as signed bytes, which lets AltoPIR-VNNI read the same layout with VPDPBUSD. The tiled database, the packing matrix, and the query panels each have their own mapping with 2 MB pages, while small per-batch buffers use 4 KB pages. AltoPIR keeps freed memory in the C allocator with mallopt, which saves the next batch from faulting it in again. It binds the engine threads and all memory to one socket. It speaks a 7

1 GB

8 GB

Database Size

(a) Queries per second

101

42.6×

24.2×

103

Throughput (QPS)

42.6×

102 101

AltoPIR AltoPIR (B=1)

105

24.2×

103

AltoPIR Batching bound

Throughput (GB/s)

Throughput (QPS)

104

Valar ReinsPIRe

102 101

1 GB

100

8 GB

Database Size

(b) Database bytes per second

5.1

16 32 64

Database Size (GB)

InsPIRe YPIR+SP

102 101 100

10−1

8 16 32 64

Database Size (GB) (b) 1 core

Figure 9: AltoPIR keeps its advantage at every database size. YPIR+SP runs only on one core. records). Every query comes from a new client with fresh keys and a random index, and every response is decrypted and compared with the record. AltoPIR follows the parameters of the public SandwichPIR implementation, with ring dimension 2048, modulus 232 − 12,287, plaintext modulus 256, and packing keys with four 9-bit gadget digits. For these parameters, SandwichPIR reports at least 128 bits of security. On 64 GB, each existing scheme uses its fastest configuration on 32 GB. Measurement. A ready batch gives the system a batch of requests that have already arrived. Its throughput is the number of requests divided by the time from the received request bytes to the serialized response bytes. We run each configuration in at least three processes after a warmup and report the median of the per-process medians. In the arrival experiments, the four clients send requests at Poisson times for 20 seconds over eight connections. A request that finds 512 requests waiting receives a busy reply. The latency runs from the scheduled send time to the receipt of the full response. In these experiments, the engine of AltoPIR runs on 15 cores, and all reader and writer threads share the single remaining core. At 64 GB, the setup of AltoPIR and of existing schemes borrows memory of the other socket, and we move all pages back before they serve.

length-prefixed binary protocol over TCP, with one reader and one writer thread per connection on a core of the same socket that the engine does not use. The client uses the original library and is compiled for AVX2, because our client machines lack AVX-512. All programs are built with rustc 1.95.0 and GCC 13.3.

(a) 16 cores

Figure 8: AltoPIR answers far more queries than existing hintless schemes. Black marks show each existing scheme at 1 GB if its pass over the database took no time. YPIR+SP runs only on one core.

ReinsPIRe Valar Throughput (QPS)

YPIR+SP InsPIRe

Evaluation Methodology

Testbed. We use a server with two Intel Xeon Silver 4514Y processors and 256 GB of DDR5 memory. Each processor has 16 cores, 2 MB of L2 cache per core, and 30 MB of L3 cache. Four client machines with Intel Core i5-12600K processors connect to the server through a 100 GbE switch. All machines run Ubuntu 24.04 with Linux 6.17. Unless specified, every system runs on the 16 cores of one socket and allocates its memory on that socket. Compared schemes. We compare AltoPIR with the official implementations of the state-of-the-art hintless schemes ReinsPIRe [51], InsPIRe [50], Valar [65], and YPIR+SP [53], and of the hint-based SimplePIR [27] as a reference. Each runs with the parameters of its official implementation, with about 128 bits of security by its authors’ estimates, except Valar, whose authors make no such claim. We run each in its fastest configuration, and YPIR+SP runs only on one core. ReinsPIRe uses the 54-bit modulus of its paper and a 64-bit index that its implementation needs at 32 GB. We also compare AltoPIR-VNNI, which runs AltoPIR with AVX-512 VNNI instructions instead of AMX, and AMX-Lib, our optimized AMX system from §2.4. As a GPU-based system, we run SandwichPIR [62] on one NVIDIA A30 GPU with 24 GB of memory in a CloudLab server [19]. It runs back-to-back batches at its best batch size, which lets the GPU run at its highest clock. Workloads and parameters. The databases hold 32 KB records and range from 1 GB (215 records) to 64 GB (221

5.2

Main Results

Throughput on 1 GB and 8 GB databases. Figure 8 shows that AltoPIR outperforms every existing scheme, and the fastest of them, ReinsPIRe, by 24.2× and 42.6× for 1 GB and 8 GB databases, respectively. This is because AltoPIR batches both products of the scheme on the accelerator, while the existing schemes batch at most the scan and run packing for each client. The black marks show that, even with a free pass over the database, AltoPIR would still outperform the highest of these marks by 3.71× because of the per-client steps of these schemes. Counting the database once per answered query, Figure 8 (b) shows that AltoPIR exceeds the memory bandwidth of the socket by more than an order of magnitude. Therefore, packing must be batched as well as the 8

Scheme

Down

SimplePIR 64 YPIR+SP 686 InsPIRe 392 Valar 280 ReinsPIRe 270 AltoPIR 192

211a 120 96 152 94 112

(ms) 1 core 16 cores (QPS)

(s)

57.3 52 40.3 33.1 63.5 18.0

499 14.9 28.5 3.0 101 13.4

76.5 384 315 205 155 123

p50 p99 6400 1600 32 GB 400 8 GB 100 1 GB 25 10 100 1000

Tput Offline

– – – – 315 28.3 20.6 57.3 155 83.2 13.9 2,013

Latenc (ms)

Comm. (KB) Client Latency (ms)

Throughput (QPS)

(a) Latency of AltoPIR

102

8 16 Database Size (GB)

Doe( no) fi)

103

128

256

VNNI

400

100

500

1000

1500

Throughput (QPS)

(b) Maximum batch size and VNNI (1 GB)

SandwichPIR (GPU)

of a CPU server reaches several terabytes. AltoPIR also outperforms AMX-Lib by 1.68× to 2.00× at every size. Therefore, AltoPIR complements GPU-based systems on CPU servers and on databases beyond the memory of one GPU. Latency under load. Figure 11 (a) shows the latency of AltoPIR when requests arrive at Poisson rates. Without a busy reply, AltoPIR achieves higher throughput than the best existing scheme by 21× to 42× on every database size of Figure 11 (a). With a 100 ms target for the 99th-percentile latency, AltoPIR sustains a higher load than AltoPIR-VNNI by 7.5× on 1 GB, as Figure 11 (b) shows. Therefore, the gain of batching holds under random arrivals.

104 Doe( no) fi)

Throughpu) (QPS)

AMX-Lib (CPU)

1600

Figure 11: Latency of AltoPIR under Poisson arrivals. The latency stays low until the load nears saturation.

a Each client also downloads a 211 MB hint in advance.

Al)oPIR (CPU)

P99 Latency (ms)

Table 2: Comparison on a 1 GB database.

Figure 10: AltoPIR and AMX-Lib against SandwichPIR on one NVIDIA A30 GPU. The GPU answers more queries per second, but the two largest databases do not fit in its memory. scan. Latency, communication, and client cost. Table 2 compares the cost of one query on a 1 GB database. AltoPIR achieves the lowest latency among the hintless schemes on both one core and 16 cores. The client of AltoPIR needs the least time and uploads the fewest bytes among the hintless schemes. Therefore, AltoPIR raises the throughput without making a single query slower or more costly for its client. Impact of database size. Figure 9 (a) shows that the advantage of AltoPIR over the fastest existing scheme grows with the database size, from 24.2× at 1 GB to about 50× from 16 GB on. The advantage grows because packing and the tail take about half of a batch of AltoPIR on 1 GB, and neither grows with the database. In contrast, ReinsPIRe spends most of each query in its pass over the database. From 16 GB on, the scan takes over 90% of a batch of AltoPIR as well, and the advantage stops growing. On one core, AltoPIR with one query per batch also outperforms the fastest existing scheme by 1.26× to 2.32×, as Figure 9 (b) shows. Therefore, the larger the database, the more servers AltoPIR saves. Comparison with GPU-based systems. Figure 10 shows that SandwichPIR on the GPU achieves higher throughput than AltoPIR by 2.9× to 5.1×. This is expected from the rated multiply-add rate and memory bandwidth of the GPU [58], which exceed those of one processor by 4.1× and 5.5×, respectively. Databases of 32 GB and 64 GB do not fit in the 24 GB memory of the GPU, while AltoPIR serves them. This limit is not specific to the A30, because even the largest single GPUs hold a few hundred gigabytes, while the main memory

5.3

Real Applications

Leaked-password checks. A client can check whether its password has leaked without revealing it [43]. We place the SHA-1 hashes of the 2.07 billion leaked passwords of Have I Been Pwned [28] in 217 buckets of 88 KB (11 GB), and a check fetches the bucket of its hash. Both applications run with random records of their shape. Their latency adds the transfer time on the mobile network that SandwichPIR assumes, 112.07 Mbps down and 14.68 Mbps up [62]. Figure 12 (a) shows that AltoPIR achieves higher throughput than ReinsPIRe, the fastest existing scheme, by 36.1×. When 64 checks arrive at once, AltoPIR achieves better latency than the existing schemes by 13.3× to 17.6× on a mobile network, as Figure 12 (b) shows. This is because AltoPIR answers all 64 requests together, faster than ReinsPIRe by 33.9×. Therefore, many users can check their passwords at the same time without a long wait. Unsafe-link checks. A browser can check whether a link is a known phishing link without revealing the link [37]. The database holds the 1.1 million phishing links and domains of Phishing.Database [61] in 214 buckets of 4 KB (64 MB). A check sends six requests, for the link, its host, and its parent domains, with random requests padding every link to six. Figure 12 (c) shows that AltoPIR provides better throughput than ReinsPIRe by 16.4×. When 64 links arrive at once, AltoPIR answers all 384 requests faster than ReinsPIRe by 14.6×, as Figure 12 (d) shows. Therefore, AltoPIR also helps 9

104

Server

Lookups per Second

AltoPIR 0.61

103

36×

Valar

101

InsPIRe InsPIRe Valar ReinsPIRe AltoPIR

(a) Passwords: lookups per second

9.53 10.84 0

Download

Decode

104

8.16

ReinsPIRe

102

100

Upload

Lookups per Second

Query gen.

16×

1.36 7.92 →

InsPIRe

100

(b) Passwords: 64 lookups at once

1.11

ReinsPIRe Valar

102

Latency (s)

0.51

AltoPIR

InsPIRe Valar ReinsPIRe AltoPIR

Latency (s)

(d) Links: 64 lookups at once

Figure 12: Results with two real applications. AltoPIR answers more lookups per second and keeps a lookup fast when 64 lookups arrive at once over a mobile network. Table 3: Where the gain over ReinsPIRe comes from.

System

QPS

Ratio

QPS

Ratio

ReinsPIRe AltoPIR-VNNI AltoPIR

83.2 401 2,013

1.0× 4.8× 24.2×

11.5 93.8 492

1.0× 8.1× 42.6×

1 0

il k L n e R N ib NaivoneDN oneMKAMX-L +Ta +Pac +Sca Al+oPI

il k n −Ta −Pac −Sca

Figure 13: Every stage of AltoPIR adds to the speedup over AMX-Lib. Bars right of the line remove one stage from +Scan.

small databases that need several requests per lookup.

5.4

1 GB, 128 q,eries 1 GB, 32 q,eries 8 GB, 128 q,eries

1.98 1.74 1.76

8 GB

Speedup

1 GB

Deep Dive

Table 4: Isolated scans of 128 queries. AltoPIR is the fastest and reads the database about once. DRAM reads are relative to the database size and L2 misses to AltoPIR.

Sources of the gain. Table 3 separates the gain over ReinsPIRe into the batching design of AltoPIR and the matrix accelerator. Without the accelerator, AltoPIR-VNNI is already better than ReinsPIRe by 4.8× and 8.1× on 1 GB and 8 GB, respectively. This is because it batches both the scan and packing. AMX then raises the throughput by another 5.0× and 5.2×, respectively, because the vector units run out of compute at small batches. Therefore, AltoPIR needs both its design and the accelerator. A processor without AMX still gains from the design through AltoPIR-VNNI. Contribution of each mechanism. We replace one stage of AMX-Lib at a time with the corresponding stage of AltoPIR, as Figure 13 shows. Every stage adds to the speedup. Together, they make AltoPIR faster than AMX-Lib by 1.98× and 1.76× on 1 GB and 8 GB, respectively. Packing gains the least, because oneDNN already computes its products at about the rate of AltoPIR. AltoPIR raises the accelerator utilization from 22% to 43% on 1 GB. When AMX-Lib uses 2 MB pages for every buffer, AltoPIR still outperforms it by 1.97× and 1.75× on 1 GB and 8 GB, respectively. Scan against library kernels. Table 4 compares the scan of AltoPIR with four library scans, each run alone. The scan of AltoPIR is faster than the fastest library scan by 1.15× and 1.6× on 1 GB and 8 GB, respectively, although every scan keeps the AMX unit busy for the same cycles. This is because the library scans read the database from memory two to five times, while AltoPIR reads it about once. The table reports the fastest run of each library scan, which favors the libraries.

Time (ms)

DRAM reads

Scan

1 GB 8 GB

1 GB

oneDNN oneMKL brgemm brgemm, AltoPIR order AltoPIR, spilled sums AltoPIR, no prefetch AltoPIR

39.9 33.5 47.6 37.3 31.0 31.2 29.1

8 GB misses

377 2.16× 2.65× 363 2.56× 3.02× 357 3.39× 4.68× 359 1.74× 2.49× 236 1.97× 1.88× 242 – – 224 1.19× 1.17×

4.18× 2.89× 6.38× 4.91× 1.53× 1.01× 1.00×

Therefore, the libraries lose on memory traffic rather than on their use of the accelerator. Feeding the accelerator. We rerun the kernels of AltoPIR with operand tiles held at fixed addresses, which removes the cost of loading them but gives wrong results. Figure 14 (a) shows that the scan of AltoPIR reaches 46% of the peak AMX rate and packing 42%. Fixed operands raise them to 72% and 87%. This means that loading tiles from the L2 cache explains most of the gap of packing and about half of that of the scan. Figure 14 (b) shows that the block length of AltoPIR gives the highest scan rate, because shorter blocks recombine more often and longer ones overflow the L2 cache. Therefore, the remaining gap to the peak rate lies in feeding operand tiles from the L2 cache, not in the memory bandwidth. Placement of the scan. Figure 15 (a) shows that the contigu10

50 25 0

53 57 60 72 46

Scan

Per query Batched 32

20 0

Thr ughput (QPS)

Client Both

% of AMX Peak

100

AltoPIR Sha ed

1,024 2,048 4,096 8,192

(a) Operand tiles held fixed

(b) Block length of the scan

Memory (× DB Size)

2.0 1.5 1.0 0.5 0.0

Panel, 4 KB Panel, 2 MB

Scan per Query (μs)

Rel. Scan Time

Figure 14: Loading operand tiles from the L2 cache limits the products of AltoPIR (1 GB, 128 queries). (a) Shared, Client, and Both hold those tiles at one address, and hatches skip the recombination. (b) The block length that AltoPIR chooses is the fastest.

Strided, 4 KB Strided, 2 MB

One pass Chunks of 128

300 200

256 queries

(a) Query layout and page size

128

256

1000 100 10

AltoPIR AltoPIR, serving

8 4 2 1

ReinsPIRe Valar

InsPIRe YPIR+SP

Sim lePIR Database size

4 8 16 32 64 Database Size (GB) Figure 17: Memory divided by the database size. Two copies of the database make up most of the peak of AltoPIR, and it frees one of them after setup (dashed).

100

128 queries

neDNN, 1 call Alt PIR

16 64 256 1024 Batch Size Figure 16: The query-blocked scan also speeds up the online step of ReinsPIRe. Per query is the data flow of ReinsPIRe, and Batched uses AVX-512.

Block Length (Record )

Packing

Batched, IFMA neDNN, 13 calls

512

Queries per Batch

(b) Scan time per query

Figure 15: Contiguous panels keep the scan fast, and client chunks keep large batches efficient. Times in (a) are relative to AltoPIR.

Setup Time (s)

800

ous panels of AltoPIR are faster than strided query tiles on 2 MB pages by 1.82× to 1.86×. This is because a strided block uses only a quarter of the sets of the L2 cache. The panels take the same time on either page size. Strided tiles on 4 KB pages are as fast here, but their placement depends on the physical pages of the process [34]. Figure 15 (b) shows that, with client chunks, the scan time per query grows by only 7% from 128 to 512 queries per batch. With one pass, it grows by 25%, because the block length shrinks to 512 records. Therefore, the scan speed of AltoPIR depends neither on the physical pages of the process nor on the batch size. Generality to other schemes. To check that the techniques of AltoPIR are not specific to SandwichPIR, we apply the queryblocked scan to the dominant online step of ReinsPIRe. This step multiplies 16-bit database entries by 52-bit query values modulo 252 . Figure 16 shows that, at their best batch sizes, this scan achieves higher throughput than the data flow of ReinsPIRe by 31.5× and than the best data flow with oneDNN products by 1.6×. With more byte limbs per query value, it is slower than oneDNN below 16 queries per batch. A complete ReinsPIRe would still be limited by its per-client steps to 542 QPS. Therefore, the scan of AltoPIR carries over to other hintless schemes, and their per-client steps decide how much of this gain they keep. Memory usage. Figure 17 shows that the ratio of the peak

600

DB build Precomputation Tile order

400 200 0

8 16 32 64 Database Size (GB) Figure 18: Setup time of AltoPIR. Almost all of it is spent in the library of the scheme.

memory of AltoPIR to the database size falls from 8.0 at 1 GB to 2.1 at 64 GB. This is because the peak holds two copies of the database during setup and about 6 GB of state that does not depend on the number of records. At 64 GB, this ratio is close to those of the existing schemes. After setup, AltoPIR frees the row-order copy. Therefore, the memory of one socket is enough to serve a 64 GB database, and only the setup needs more. Setup time. Figure 18 shows that the setup time of AltoPIR grows almost linearly with the database size, from 13.4 s for 1 GB to 598 s for 64 GB. Almost all of it builds the database in the format of the scheme and precomputes the offline state in the library of the scheme, while the tile layout of AltoPIR takes at most 4.0 s. Therefore, AltoPIR adds almost nothing to the setup cost of the scheme, and a service pays this cost once per database rather than for every update. Database updates. Table 5 shows the time to apply record updates with the rank-one update of the hint. Changing one 11

8 GB

2.6 s 3.4 s 13.1 s

2.6 s 3.6 s 89 s

% of AMX Pea

1 changed record 64 changed records Setup from scratch

1 GB

60 40

Silver 4514Y Gold 5512U

20 0

1,024 2,048 4,096 8,192

Block Length (Records)

Throughput (QPS)

Linear

Al(oPIR

2 soc e(s

AVX-512 job

Memory s(ream

(a) Block length of the scan

3000

Prediction Gold 5512U Silver 4514Y

1 4 8 12 16 20 24 28

Cores

(b) Throughput on 1 GB

Figure 20: On another processor, the same block length gives the highest scan rate, and AltoPIR follows the throughput predicted before the runs.

1000 300 100

online work of the server with a digest that each client stores [17, 27, 70], while hintless schemes move this digest to the server [42, 50, 51, 53] or use no hint [18, 45, 49]. Unlike batch PIR for one client [4, 32, 46, 56], cross-client batching answers independent clients with one product over the database [48, 53], like the shared scans of database systems [21, 25, 71]. AltoPIR makes this batching effective on CPUs. Pantheon [2] and Femur [69] serve key-value lookups one query at a time, while AltoPIR batches key lookups as index queries. Accelerators and matrix arithmetic. Other PIR systems add GPUs [24, 33, 35, 40, 41, 68], computational storage [12, 44], or a dedicated accelerator [36] to every server, while AltoPIR serves the database from the memory of the host. SandwichPIR [62], whose scheme AltoPIR follows, runs both products on GPU tensor cores, while AltoPIR runs on CPU matrix accelerators that hold few operands and share their cores with request handling. Matrix units also run mixtureof-experts inference [11] and build wide products from 8bit products, combining the partial products in a separate step [38,59,62,66] or inside one GPU kernel [35,47]. AltoPIR instead combines them after every block of records in the L2 cache. GEMM libraries block one product for the caches [20, 22, 64, 67], while AltoPIR sizes the blocks of both products for one cache budget. Vector libraries [8], latency-aware batch sizing [16, 23, 63], and overload control [13] could replace parts of the engine of AltoPIR.

Cores Figure 19: Throughput grows nearly in proportion to the number of cores up to eight. Separate points show two sockets and eight cores beside another job.

record takes 2.6 s on both 1 GB and 8 GB databases, far less than a setup from scratch. This is because only the hint depends on the changed records, at about 18 ms per record, while the rest of the state takes a fixed 2.4 s to recompute. Afterward, the state and the responses equal those of a fresh instance of AltoPIR set up on the updated database. Therefore, a service can apply small updates within seconds. Core scaling. Figure 19 shows that AltoPIR scales almost linearly up to eight cores and reaches 0.78 of linear scaling at 16 cores. This is because the AMX clock drops from 3.40 GHz with one busy core to 2.49 GHz with 16. A second socket with its own copy of the database raises the throughput by 2.03×. When the other eight cores run an AVX-512 job or stream memory at 135 GB/s, AltoPIR on eight cores keeps 81% or 78% of its throughput. Therefore, AltoPIR scales with the number of sockets and can share a socket with other jobs. Robustness on another processor. We also run AltoPIR on a CloudLab server [19] with an Intel Xeon Gold 5512U, a processor of the same generation as the main one but with 28 cores. With the same 2 MB L2 cache per core, the rules of AltoPIR give the same block length. Figure 20 (a) shows that this block length again gives the highest scan rate. Figure 20 (b) shows that, at every core count, the throughput stays within 10% of the throughput that we predicted from the main processor before the runs. From 16 to 28 cores, the throughput grows by only 1.35×, because the AMX clock falls from 3.18 GHz to 2.39 GHz when all 28 cores are busy. Therefore, AltoPIR carries over to another processor, and its throughput follows the cores and the clock of the accelerator.

4000 3000 2000 1000 0

Throughput (QPS)

Table 5: Time to apply record updates. Updating a few records costs much less than building the offline state again.

Conclusion

We presented AltoPIR, the first PIR system built on the matrix accelerators inside server CPUs. AltoPIR splits encrypted values into bytes for the accelerator, reads the database once per batch, and keeps each core fed from its caches. On a commodity server without added devices, it outperforms the fastest existing hintless scheme by 24.2× to 50.1× on databases of 1 GB to 64 GB. We believe that the accelerators built into server CPUs can make PIR, and other privacy systems whose work reduces to integer matrix products, practical on the servers.

Related Work

PIR schemes and batching. Lattice-based schemes made PIR practical [1, 4, 9, 52, 55]. Hint-based schemes cut the 12

Acknowledgement

[11] Hongtao Chen, Weiyu Xie, Boxin Zhang, Jingqi Tang, Jiahao Wang, Jianwei Dong, Shaoyuan Chen, Ziwei Yuan, Chen Lin, Chengyu Qiu, Yuening Zhu, Qingliang Ou, Jiaqi Liao, Xianglin Chen, Zhiyuan Ai, Yongwei Wu, and Mingxing Zhang. KTransformers: Unleashing the full potential of CPU/GPU hybrid inference for MoE models. In Proc. of ACM SOSP, pages 1014–1029, 2025.

This research was sponsored by the National Research Foundation of Korea (NRF) grants funded by the Ministry of Science and ICT (No. RS-2025-00522990). Gyuyeong Kim is the corresponding author.

References

[12] Zehao Chen, Honghui You, Qian Wei, Hang Lu, Lei Ju, and Zhaoyan Shen. SmartPIR: A private information retrieval system using computational storage devices. In Proc. of IEEE/ACM MICRO, pages 1749–1762, 2025.

[1] Carlos Aguilar-Melchor, Joris Barrier, Laurent Fousse, and Marc-Olivier Killijian. XPIR: Private information retrieval for everyone. Proceedings on Privacy Enhancing Technologies, 2016(2):155–174, 2016.

[13] Inho Cho, Ahmed Saeed, Joshua Fried, Seo Jin Park, Mohammad Alizadeh, and Adam Belay. Overload control for µs-scale RPCs with Breakwater. In Proc. of USENIX OSDI, pages 299–314, 2020.

[2] Ishtiyaque Ahmad, Divyakant Agrawal, Amr El Abbadi, and Trinabh Gupta. Pantheon: Private retrieval from public key-value store. Proc. VLDB Endow., 16(4):643– 656, 2022.

[14] Benny Chor, Niv Gilboa, and Moni Naor. Private information retrieval by keywords. Technical Report CS0917, Technion, Department of Computer Science, 1997.

[3] Ishtiyaque Ahmad, Yuntian Yang, Divyakant Agrawal, Amr El Abbadi, and Trinabh Gupta. Addra: Metadataprivate voice communication over fully untrusted infrastructure. In Proc. of USENIX OSDI, pages 313–329, 2021.

[15] Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan. Private information retrieval. Journal of the ACM, 45(6):965–981, 1998.

[4] Sebastian Angel, Hao Chen, Kim Laine, and Srinath Setty. PIR with compressed queries and amortized query processing. In Proc. of IEEE S&P, pages 962–979, 2018.

[16] Daniel Crankshaw, Xin Wang, Giulio Zhou, Michael J. Franklin, Joseph E. Gonzalez, and Ion Stoica. Clipper: A low-latency online prediction serving system. In Proc. of USENIX NSDI, pages 613–627, 2017.

[5] Sebastian Angel and Srinath Setty. Unobservable communication over fully untrusted infrastructure. In Proc. of USENIX OSDI, pages 551–569, 2016.

[17] Alex Davidson, Gonçalo Pestana, and Sofía Celi. FrodoPIR: Simple, scalable, single-server private information retrieval. Proceedings on Privacy Enhancing Technologies, 2023(1):365–383, 2023.

[6] Arm Limited. Arm architecture reference manual supplement, the scalable matrix extension (SME), for Armv9-A. Document DDI0616, issue B.a, https://deve loper.arm.com/documentation/ddi0616/latest, 2023.

[18] Leo de Castro, Kevin Lewi, and G. Edward Suh. WhisPIR: Stateless private information retrieval with low communication. Cryptology ePrint Archive, Paper 2024/266, 2024.

[7] Amos Beimel, Yuval Ishai, and Tal Malkin. Reducing the servers’ computation in private information retrieval: PIR with preprocessing. Journal of Cryptology, 17(2):125–151, 2004.

[19] Dmitry Duplyakin, Robert Ricci, Aleksander Maricq, Gary Wong, Jonathon Duerig, Eric Eide, Leigh Stoller, Mike Hibler, David Johnson, Kirk Webb, Aditya Akella, Kuangching Wang, Glenn Ricart, Larry Landweber, Chip Elliott, Michael Zink, Emmanuel Cecchet, Snigdhaswin Kar, and Prabodh Mishra. The design and operation of CloudLab. In Proc. of USENIX ATC, pages 1–14, 2019.

[8] Fabian Boemer, Sejun Kim, Gelila Seifu, Fillipe D. M. de Souza, and Vinodh Gopal. Intel HEXL: Accelerating homomorphic encryption with Intel AVX512-IFMA52. In Proc. of ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography (WAHC), pages 57–62, 2021. [9] Alexander Burton, Samir Jordan Menon, and David J. Wu. Respire: High-rate PIR for databases with small records. In Proc. of ACM CCS, pages 1463–1477, 2024.

[20] Evangelos Georganas, Kunal Banerjee, Dhiraj Kalamkar, Sasikanth Avancha, Anand Venkat, Michael Anderson, Greg Henry, Hans Pabst, and Alexander Heinecke. Harnessing deep learning via a single building block. In Proc. of IEEE IPDPS, pages 222–233, 2020.

[10] Feiyang Chen and Haibo Chen. SMEPilot: Characterizing and optimizing LLM inference with scalable matrix extensions. arXiv:2606.16332, 2026.

[21] Georgios Giannikis, Gustavo Alonso, and Donald Kossmann. SharedDB: Killing one thousand queries with one stone. Proc. VLDB Endow., 5(6):526–537, 2012. 13

[22] Kazushige Goto and Robert A. van de Geijn. Anatomy of high-performance matrix multiplication. ACM Transactions on Mathematical Software, 34(3):12:1–12:25, 2008.

[34] Richard E. Kessler and Mark D. Hill. Page placement algorithms for large real-indexed caches. ACM Transactions on Computer Systems, 10(4):338–359, 1992. [35] Jongmin Kim, Hyesung Ji, Jean-Luc Watson, Charles Gouert, G. Edward Suh, and Jung Ho Ahn. VIPIR: A versatile GPU framework for integrating private information retrieval protocols. arXiv preprint arXiv:2606.11536, 2026.

[23] Arpan Gujarati, Reza Karimi, Safya Alzayat, Wei Hao, Antoine Kaufmann, Ymir Vigfusson, and Jonathan Mace. Serving DNNs like Clockwork: Performance predictability from the bottom up. In Proc. of USENIX OSDI, pages 443–462, 2020. [24] Daniel Günther, Maurice Heymann, Benny Pinkas, and Thomas Schneider. GPU-accelerated PIR with clientindependent preprocessing for large-scale applications. In Proc. of USENIX Security, pages 1759–1776, 2022.

[36] Sangpyo Kim, Hyesung Ji, Jongmin Kim, Wonseok Choi, Jaiyoung Park, and Jung Ho Ahn. IVE: An accelerator for single-server private information retrieval using versatile processing elements. In Proc. of IEEE HPCA, pages 1–15, 2026.

[25] Stavros Harizopoulos, Vladislav Shkapenyuk, and Anastassia Ailamaki. QPipe: A simultaneously pipelined relational query engine. In Proc. of ACM SIGMOD, pages 383–394, 2005.

[37] Dmitry Kogan and Henry Corrigan-Gibbs. Private blocklist lookups with Checklist. In Proc. of USENIX Security, pages 875–892, 2021. [38] Tomonori Kouya. Ozaki scheme II is fast on CPUs too: Multiple-precision matrix multiplication on Intel AMX-INT8 and Arm SVE2-i8mm. arXiv:2609.27831, 2026.

[26] Alexandra Henzinger, Emma Dauterman, Henry Corrigan-Gibbs, and Nickolai Zeldovich. Private web search with Tiptoe. In Proc. of ACM SOSP, pages 396–416, 2023.

[39] Eyal Kushilevitz and Rafail Ostrovsky. Replication is not needed: Single database, computationally-private information retrieval. In Proc. of IEEE FOCS, pages 364–373, 1997.

[27] Alexandra Henzinger, Matthew M. Hong, Henry Corrigan-Gibbs, Sarah Meiklejohn, and Vinod Vaikuntanathan. One server for the price of two: Simple and fast single-server private information retrieval. In Proc. of USENIX Security, pages 3889–3905, 2023.

[40] Maximilian Lam, Jeff Johnson, Wenjie Xiong, Kiwan Maeng, Udit Gupta, Yang Li, Liangzhen Lai, Ilias Leontiadis, Minsoo Rhu, Hsien-Hsin S. Lee, Vijay Janapa Reddi, Gu-Yeon Wei, David Brooks, and G. Edward Suh. GPU-based private information retrieval for on-device machine learning inference. In Proc. of ACM ASPLOS, pages 197–214, 2024.

[28] Troy Hunt. Pwned passwords. https://haveibeenpwned .com/Passwords, 2026. Accessed October 2026. [29] Intel. Intel Xeon Silver 4514Y processor: Specifications. https://www.intel.com/content/www/us/en/products/s ku/237557/intel-xeon-silver-4514y-processor-30mcache-2-00-ghz/specifications.html, 2026. Accessed October 2026.

[41] Ryan Lehmkuhl, Alexandra Henzinger, and Henry Corrigan-Gibbs. Distributional private information retrieval. In Proc. of USENIX Security, pages 3377–3396, 2025.

[30] Intel. oneAPI math kernel library (oneMKL). https: //www.intel.com/content/www/us/en/developer/tools/ oneapi/onemkl.html, 2026. Accessed October 2026.

[42] Baiyu Li, Daniele Micciancio, Mariana Raykova, and Mark Schultz-Wu. Hintless single-server private information retrieval. In Proc. of CRYPTO, pages 183–217, 2024.

[31] Intel Corporation. Intel 64 and IA-32 architectures software developer’s manual, combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4. Order Number 325462093US, https://www.intel.com/content/www/us/en/deve loper/articles/technical/intel-sdm.html, 2026.

[43] Lucy Li, Bijeeta Pal, Junade Ali, Nick Sullivan, Rahul Chatterjee, and Thomas Ristenpart. Protocols for checking compromised credentials. In Proc. of ACM CCS, pages 1387–1403, 2019.

[32] Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Batch codes and their applications. In Proc. of ACM STOC, pages 262–271, 2004.

[44] Jilan Lin, Ling Liang, Zheng Qu, Ishtiyaque Ahmad, Liu Liu, Fengbin Tu, Trinabh Gupta, Yufei Ding, and Yuan Xie. INSPIRE: In-storage private information retrieval via protocol and architecture co-design. In Proc. of ACM/IEEE ISCA, pages 102–115, 2022.

[33] Hyesung Ji, Hyunah Yu, Jongmin Kim, Wonseok Choi, G. Edward Suh, and Jung Ho Ahn. GPIR: Enabling practical private information retrieval with GPUs. In Proc. of ACM ICS, pages 1193–1205, 2026. 14

[45] Chenyang Liu, Xukun Wang, and Zhifang Zhang. VIA: Communication-efficient single-server private information retrieval. In Proc. of IEEE S&P, pages 1503–1521, 2026.

[59] Hiroyuki Ootomo, Katsuhisa Ozaki, and Rio Yokota. DGEMM on integer matrix multiplication unit. International Journal of High Performance Computing Applications, 38(4):297–313, 2024.

[46] Jian Liu, Jingyu Li, Di Wu, and Kui Ren. PIRANA: Faster multi-query PIR via constant-weight codes. In Proc. of IEEE S&P, pages 4315–4330, 2024.

[60] Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. Journal of Algorithms, 51(2):122–144, 2004. [61] Phishing.Database. Phishing.Database: Phishing domains and links. https://github.com/PhishingDatabase/Phishing.Database, 2026. Accessed October 2026.

[47] Denghui Lu, Alexander Maeder, Mathieu Luisier, and Alexandros Nikolaos Ziogas. EmuGEMM: Fused tensor core kernels for precision emulation in matrix multiplication. In Proc. of SC, 2026. To appear, arXiv:2606.25453.

[62] Sidaarth Sabhnani and David J. Wu. From lattices to tensor cores: Accelerating private information retrieval. Cryptology ePrint Archive, Paper 2026/1816, 2026.

[48] Wouter Lueks and Ian Goldberg. Sublinear scaling for multi-client private information retrieval. In Proc. of Financial Cryptography and Data Security (FC), pages 168–186, 2015.

[63] Haichen Shen, Lequn Chen, Yuchen Jin, Liangyu Zhao, Bingyu Kong, Matthai Philipose, Arvind Krishnamurthy, and Ravi Sundaram. Nexus: A GPU cluster engine for accelerating DNN-based video analysis. In Proc. of ACM SOSP, pages 322–337, 2019.

[49] Ming Luo, Feng-Hao Liu, and Han Wang. Faster FHEbased single-server private information retrieval. In Proc. of ACM CCS, pages 1405–1419, 2024. [50] Rasoul Akhavan Mahdavi, Sarvar Patel, Joon Young Seo, and Kevin Yeo. InsPIRe: Communication-efficient PIR with server-side preprocessing. In Proc. of IEEE S&P, pages 1463–1482, 2026.

[64] UXL Foundation. oneAPI deep neural network library (oneDNN). https://github.com/uxlfoundation/oneDNN, 2026. Accessed October 2026.

[51] Rasoul Akhavan Mahdavi, Sarvar Patel, Joon Young Seo, and Kevin Yeo. ReinsPIRe: High-throughput, lowcommunication PIR with server preprocessing. Cryptology ePrint Archive, Paper 2026/1934, 2026.

[65] Valar Group. IPIR+SP: YPIR+SP private information retrieval (PIR) with InsPIRing packing algorithm. https: //github.com/valargroup/ipir-sp, 2026.

[52] Samir Jordan Menon and David J. Wu. Spiral: Fast, high-rate single-server PIR via FHE composition. In Proc. of IEEE S&P, pages 930–947, 2022.

[66] Joris van der Hoeven and Marc Mezzarobba. Multi-limb integer matrix multiplication using AMX and AVX512IFMA instructions. HAL preprint hal-05641903v2, http s://hal.science/hal-05641903v2, 2026.

[53] Samir Jordan Menon and David J. Wu. YPIR: Highthroughput single-server PIR with silent preprocessing. In Proc. of USENIX Security, pages 5985–6002, 2024.

[67] Field G. Van Zee and Robert A. van de Geijn. BLIS: A framework for rapidly instantiating BLAS functionality. ACM Transactions on Mathematical Software, 41(3):14:1–14:33, 2015.

[54] José E. Moreira et al. A matrix math facility for Power ISA processors. arXiv:2104.03142, 2021.

[68] Zihan Wang, Lutan Zhao, Ming Luo, Zhiwei Wang, Haoqi He, Wenzhe Lv, Xuan Ding, Dan Meng, and Rui Hou. ShiftPIR: An efficient PIR system with gravity shifting from client to server. In Proc. of ACM CCS, pages 1143–1157, 2025.

[55] Muhammad Haris Mughees, Hao Chen, and Ling Ren. OnionPIR: Response efficient single-server PIR. In Proc. of ACM CCS, pages 2292–2306, 2021. [56] Muhammad Haris Mughees and Ling Ren. Vectorized batch private information retrieval. In Proc. of IEEE S&P, pages 437–452, 2023. [57] Nevine Nassif et al. Sapphire Rapids: The nextgeneration Intel Xeon scalable processor. In Proc. of IEEE ISSCC, pages 44–46, 2022.

[69] Jiaoyi Zhang, Liqiang Peng, Mo Sha, Weiran Liu, Xiang Li, Sheng Wang, Feifei Li, Mingyu Gao, and Huanchen Zhang. Femur: A flexible framework for fast and secure querying from public key-value store. Proc. ACM Manag. Data, 3(3):162:1–162:29, 2025.

[58] NVIDIA. NVIDIA A30 tensor core GPU datasheet. https://www.nvidia.com/content/dam/en-zz/Solutions /data-center/products/a30-gpu/pdf/a30-datasheet.pdf, 2022. Accessed October 2026.

[70] Mingxun Zhou, Andrew Park, Wenting Zheng, and Elaine Shi. Piano: Extremely simple, single-server PIR with sublinear server computation. In Proc. of IEEE S&P, pages 4296–4314, 2024. 15

[71] Marcin Zukowski, Sándor Héman, Niels Nes, and Peter Boncz. Cooperative scans: Dynamic bandwidth sharing in a DBMS. In Proc. of VLDB, pages 723–734, 2007.

High-Throughput Private Information Retrieval with on-CPU Accelerators

Analyze & explore related research in Conceptio

Related documents