Private search lets a user query a server's database without the server learning the query. The simplest form with strong guarantees works like this: the user encrypts a query embedding with homomorphic encryption, a scheme that lets the server compute on encrypted data without decrypting it. The server multiplies that encrypted query against every stored vector and returns encrypted scores. Every record must be touched on every query. If the server skipped some records, the skip pattern would reveal something about the query. For a database of tens to hundreds of gigabytes, the cost of such a query is dominated by reading the database, not by cryptography. The per-record work is a cheap modular multiply-add between one unencrypted record and one encrypted query. The output is a few ciphertexts, far smaller than the input.
That profile of bulk read, cheap arithmetic, and tiny output is exactly what near-data processing was built for. In near-data processing, the storage device computes on data where it sits and ships back only a small result. We propose running the encrypted inner-product scan inside computational SSDs, which are flash drives with an attached programmable chip (an FPGA). The scan would run at the drive's internal flash bandwidth instead of the narrower host link. We also study the one design choice that decides whether this wins: how the database is encoded on flash. The encoding determines how many bytes the scan must read and how much arithmetic the drive must do per byte.
Core Claim
Our claim concerns a specific operation: homomorphic retrieval where the database is unencrypted, the query is encrypted, and every record is scanned. For this operation, the bottleneck is bytes read per query. An array of FPGA-equipped SSDs can therefore serve it with lower energy per query than a host that streams the same data over its I/O link, and at larger scale than any DRAM-resident design. This holds only if the on-flash encoding is chosen to balance two things: the expansion from storing records in a precomputed, transform-ready form, and the arithmetic cost of transforming them on the device.
In a ring-based scheme such as BFV, a record can be stored in one of two forms. The compact form uses small coefficients and forces the drive to run a Number Theoretic Transform, the modular analogue of an FFT, on every record. The precomputed form stores the already-transformed polynomial with full-width coefficients modulo $q$. This makes on-device work a pure pointwise multiply-accumulate, but it multiplies the bytes on flash by an expansion factor $e$. A first-order model makes the tradeoff explicit. With $k$ drives, database size $B$ in its compact encoding, per-drive internal bandwidth $W$, and per-drive transform throughput $F$ in bytes per second of compact data, the per-query scan time is roughly
$$T(e) \approx \max\left(\frac{e\,B}{k\,W},\ \frac{\mathbb{1}[\text{on-device transform}]\,B}{k\,F}\right),$$
where the indicator is 1 only for the compact layout. The better layout is whichever term is smaller. The crossover depends on measurable device constants, so it can be tested directly. Partial layouts are also possible, such as storing a subset of transform stages precomputed or using a mid-width modulus. These trace a curve between the two extremes, and finding the best point on that curve is the core technical contribution.
Relation to Prior Work
Two papers already bring near-data hardware to homomorphic encryption, and they motivate this work by showing that memory traffic, not arithmetic, often limits it. APACHE places accumulation logic inside DRAM banks and transform units on the memory module. It targets key switching, which it measures at I/O demands near 10,000 GB/s, and it reports 10.6–35.5x over ASIC accelerators in simulation. FHEmem puts bit-serial units beside the DRAM arrays inside high-bandwidth memory stacks. It reports 4.0x over SHARP and CraterLake on logistic regression and ResNet-20. Both accelerate deep encrypted computation, including bootstrapping (the expensive noise-refresh step) and key switching, on data that fits in volatile memory of 16–32 GB per stack. Both explicitly leave persistent storage unaddressed. We do the opposite. We target shallow encrypted computation with no bootstrapping over data too large for memory, and we put the logic in flash drives rather than DRAM. We do not claim flash can serve bootstrapping. The 100 TB/s working-set bandwidth that FHEmem cites for homomorphic multiplication rules that out, and this constraint is why we restrict the operation to plaintext-by-ciphertext products.
The device side reuses techniques from computational storage. Kim et al.'s SmartSSD graph search shows that FPGA pipelines next to flash can serve billion-scale nearest-neighbor search at 75.59 queries per second on SIFT1B across four drives. It also shows that hand-written RTL beat high-level synthesis by 7.74x, a lesson we adopt for the multiply-accumulate pipeline. RecSSD puts gather-and-sum aggregation into SSD firmware. Smart-Infinity offloads optimizer updates to drive-side accelerators, and it warns that a single drive saturates its own internal channels, so gains come from arrays. This constrains our design: we plan for multi-drive scaling from the start. All three compute on plaintext. None faces the byte expansion that encryption-compatible encoding imposes, which is the question we study.
The algorithmic competitors avoid full scans altogether. Pacmann runs graph search on the client and fetches neighbors through sublinear private information retrieval. It reports 1.6 s LAN latency on SIFT-100M at 90% of the plaintext search tool NGT's quality. The cost is roughly 60 GB of client preprocessing and a static database. p²RAG uses two non-colluding servers. ppRAG swaps homomorphic encryption for distance-comparison-preserving encryption plus differential privacy, accepting leakage of distance rankings. These papers set the bar a full-scan design must clear, and they mark its niche: single-server, no client preprocessing, updates at write speed, and no leakage beyond the encryption itself. KeyMemRT is relevant because rotation keys consume 20–94% of runtime memory. Our operation needs few rotations, and we measure key footprint to confirm that it fits the SmartSSD's 4 GB of onboard DRAM.
Research Program
We will build a scan engine on Samsung SmartSSDs, the same platform as Kim et al. It has four parts: a BFV parameter set sized for one plaintext-ciphertext multiplication plus accumulation with no bootstrapping; an RTL pipeline for modular multiply-accumulate over packed slots; an optional on-device transform unit; and a layout compiler. The compiler takes an embedding database, quantization width, and drive constants, and emits the on-flash encoding that minimizes $T(e)$. It also partitions records across drives so that each drive returns one partial ciphertext per query, and the host adds these partial results.
Queries are batched so that one flash pass serves many encrypted queries at once. This raises the arithmetic done per byte read, and the model predicts it will shift the best layout toward compact storage. Security needs no new trust assumption. The drive belongs to the server, which already sees the full database in plaintext. The query stays encrypted end to end, and the access pattern is a fixed full scan regardless of the query. We will first validate the analytical model against measured device throughput and then use it to explain the results. A central risk is that the precomputed layout's expansion factor, likely several-fold for 8-bit embeddings under a 60-bit modulus, makes the compact layout mandatory while the FPGA's transform throughput sits below flash bandwidth. In that case the result is a negative finding with an exact limiting constant, and it is still worth reporting.
Baselines
The naive reference is a host CPU scan over commodity NVMe SSDs of the same count and capacity. It uses the same BFV parameters, the same quantized database, and the same batching, with the host running an optimized multiply-accumulate loop in a standard library. This isolates what moving computation into the drive buys when the operation and data are held fixed. Beating it means higher queries per second or lower joules per query at equal drive count.
The strongest same-guarantee competitor is a DRAM-resident scan on a large-memory CPU server, plus a GPU server that streams from SSD. These cover the case where the database fits in memory, and the case where accelerator arithmetic helps once data arrives. Both are tuned with the same effort as our pipeline, and both are compared at matched hardware cost and measured wall power. The file contains no reported number for encrypted full-scan retrieval of this kind. We found no reported result on Lacuna for homomorphic full-scan embedding retrieval throughput, so we will measure this baseline ourselves. We count our system as better if it matches DRAM throughput per dollar while using less energy per query, or if it scales past DRAM capacity where the DRAM baseline cannot run.
The strongest existing private-search system in the file is Pacmann. The reference point it reports is 1.6 s LAN query latency on SIFT-100M at 90% of NGT quality (Pacmann). We will run it on the same SIFT-100M data and network setting and report latency, recall, client preprocessing bytes, and update cost. Beating Pacmann on latency is not required. We count a win if we reach comparable latency with exact recall, zero client preprocessing, and support for inserts.
Two ablations isolate the key ingredient. The first forces each fixed layout, fully compact or fully precomputed, instead of the compiler's choice. The second runs the identical FPGA pipeline with data staged through host memory instead of peer-to-peer from flash, separating the benefit of the accelerator from the benefit of avoiding the host link.
Why not just…?
Why not just put the database in a big server's DRAM? For SIFT-100M-scale data this may well match us on latency, and we treat this as a real threat. The DRAM baseline settles it. Our claim holds only if we win on energy and cost per query at that scale, or if the database, after encryption-friendly encoding expands it, exceeds practical DRAM. SIFT1B is 119 GB raw, so its expanded form is the regime where the distinction should appear.
Why not just use a processing-in-memory accelerator like APACHE or FHEmem? Both are simulated designs whose capacity is bounded by DRAM or high-bandwidth memory stacks. FHEmem explicitly does not handle data beyond stack capacity. They are optimized for bootstrapping and key switching, which our operation does not need. We will estimate from their published architecture what fraction of their silicon a plaintext-by-ciphertext scan would use, but we cannot run them.
Why not just avoid the full scan, as Pacmann does? Sublinear retrieval is asymptotically better, and on a static database with a willing client it may win outright. The price is 60 GB of client-side preprocessing and no updates. Our Pacmann comparison measures both sides of this tradeoff, together with an insertion-heavy workload where preprocessing must be redone.
Why not just compress the plaintext database and scan on the host? Compression reduces bytes over the host link, but it adds decompression work on the host and cannot shrink the full-width precomputed form. We include a compressed host-scan variant and expect it to narrow the gap to our system without closing it.
Proposed Experiments
We will evaluate on three datasets: SIFT-100M, for direct comparison with Pacmann; SIFT1B, to reach the scale where Kim et al. showed plaintext SmartSSD gains; and MS-MARCO embeddings reduced to 192 dimensions as in Pacmann, to test retrieval quality on text. The metrics are queries per second, energy per query, and bytes read per query at one, two, and four drives. We also report exact-scan recall@10 against plaintext search, response size, and onboard key and buffer memory against the 4 GB limit.
Three checks decide the outcome. The first is whether measured scan time follows the $T(e)$ model and whether the compiler's layout beats both fixed layouts at the predicted crossover as batch size varies. The second is whether four SmartSSDs beat the matched host-streaming baseline on energy per query at SIFT1B scale. The third is whether throughput scales roughly linearly with drive count, the condition Smart-Infinity found necessary. If the first check fails, the design principle is wrong. If the second fails while the first holds, the finding becomes a precise statement of which device constant, flash bandwidth or FPGA transform rate, must improve before encrypted retrieval belongs in storage.
References
- APACHE: A Processing-Near-Memory Architecture for Multi-Scheme Fully Homomorphic Encryption
- FHEmem: A Processing In-Memory Accelerator for Fully Homomorphic Encryption
- Accelerating Large-Scale Graph-based Nearest Neighbor Search on a Computational Storage Platform
- RecSSD: near data processing for solid state drive based recommendation inference
- Smart-Infinity: Fast Large Language Model Training using Near-Storage Processing on a Real System
- Pacmann: Efficient Private Approximate Nearest Neighbor Search
- $p^2$RAG: Privacy-Preserving RAG Service Supporting Arbitrary Top-$k$ Retrieval
- Efficient Privacy-Preserving Retrieval Augmented Generation with Distance-Preserving Encryption
- KeyMemRT Compiler and Runtime: Unlocking Memory-Scalable FHE