SmartPIR: A Private Information Retrieval System using Computational Storage Devices

Review Form

Reviewer: The Guardian (Adversarial Skeptic)

Summary

The authors present SmartPIR, a system for Private Information Retrieval (PIR) that leverages Computational Storage Devices (CSDs) to mitigate I/O bottlenecks. The core contributions are a protocol and architecture co-design, featuring a "zero-skipping encoding" (ZSE) to handle variable-length data efficiently and an in-storage FHE engine implemented on FPGAs. The system claims significant (10²×~10³×) speedups over CPU-based PIR schemes.

While the motivation is sound and the use of CSDs is pertinent, the paper's central claims rest on a foundation of weak baselines, an insufficient security analysis, and a glossing over of critical implementation details. The work demonstrates a functional prototype but fails to rigorously substantiate its performance advantages and security guarantees against realistic alternatives and threats.

Strengths

1. Problem Identification: The paper correctly identifies two critical, practical bottlenecks in FHE-based PIR systems: the I/O overhead from full database scans and the computational redundancy introduced by padding variable-length data entries. This is a well-articulated motivation.
2. Prototype Implementation: The authors have implemented a full-stack prototype on commercially available CSDs (Samsung SmartSSDs). This is a non-trivial engineering effort and provides a valuable data point on the practical feasibility of such systems, moving beyond pure simulation.
3. Core Concept: The high-level idea of offloading FHE operations to CSDs to co-locate computation and data is a logical and promising direction for alleviating the identified I/O bottleneck.

Weaknesses

1. Grossly Exaggerated Performance Claims: The headline claim of a "10²×~10³× speedup" (Abstract, page 1) is deeply misleading. A close reading of the evaluation in Section 8.2.1 and Figure 8 (page 9) reveals this claim is derived from a comparison against a single-threaded CPU baseline (MulPIR+CPU). Against more credible, parallelized baselines such as MulPIR+CPUs (48 threads) and MulPIR+A100 (a high-end GPU), the speedups are far more modest, typically in the range of 5× to 47×. The abstract and introduction must be revised to reflect the performance against state-of-the-art, parallelized implementations, not a strawman baseline.

2. Insufficient Security Analysis: The security analysis in Section 5.4 (page 7) is cursory and unconvincing. The paper claims "indistinguishable computation" because the skipping pattern is dictated by the static database layout. This argument completely ignores timing side channels. An adversary observing the total execution time could potentially infer properties of the query index if different query paths, despite being functionally identical from the server's perspective, result in different numbers of skipped (i.e., fast-path) vs. non-skipped (slow-path) operations. The execution time of a query is an observable trace. Without a formal proof or at least a rigorous argument that execution time is independent of the query index, the security claim is unsubstantiated.

3. Unfair and Opaque Baselines:

   • The comparison to INSPIRE (Section 8.2.1, page 10) is an apples-to-oranges comparison. INSPIRE is a simulated architecture, and the authors dismiss its superior performance on the uniform (Uni) dataset by claiming it relies on "idealized compute and I/O capabilities." This is a weak defense. The authors should instead explain why their real-world implementation is fundamentally less efficient in this best-case scenario for traditional PIR.
   • A crucial baseline is missing: a direct implementation of the baseline protocol (MulPIR) on the same CSD hardware. Without this, it is impossible to disentangle the performance gains from the SmartPIR protocol (i.e., ZSE) from the gains simply obtained by moving any PIR computation to the CSDs. The authors' "co-design" claim hinges on this, but they provide no evidence to support it.

4. Unaddressed Protocol Overheads: The ZSE protocol (Section 5.1, page 5) requires a "bitwidth-aware sorting of the entries" as a preprocessing step. The cost of this sorting is never analyzed or mentioned in the evaluation. For dynamic databases where entries are frequently added, updated, or deleted, this could introduce significant and recurring overhead, undermining the system's practicality. The paper presents the database as a static artifact, which is not realistic.

5. Missing Hardware Implementation Details: The claim of a "resource-efficient FPGA circuit design" is not sufficiently supported. Table 1 (page 8) shows very high resource utilization (e.g., 85% of BRAMs, 68% of LUTs). High utilization often leads to significant challenges in timing closure and typically necessitates lower clock frequencies. The authors fail to report the clock frequency of their FPGA design, a critical metric for evaluating the efficiency of any hardware accelerator. Without this information, the performance results lack crucial context.

Questions to Address In Rebuttal

1. Please justify the 10²×~10³× speedup claim in the abstract. Provide a revised claim based on a comparison to the multi-threaded CPU (MulPIR+CPUs) or GPU (MulPIR+A100) baselines, which represent the current state-of-the-art.
2. Provide a rigorous security argument for why the data-dependent "zero-skipping" in your ZSE protocol does not leak information about the client's query index through timing side channels. A simple assertion that the pattern is static is insufficient.
3. What is the computational cost of the initial "bitwidth-aware sorting" required by ZSE? How does your system handle database updates (insertions/deletions), and what is the amortized performance cost of maintaining the sorted structure?
4. What is the operating clock frequency of your FPGA design on the Kintex UltraScale+ KU15P? How does this compare to other published FPGA-based FHE accelerators?
5. Please explain the significant performance deficit of SmartPIR compared to the simulated INSPIRE on the Uni dataset. What specific architectural or protocol-level limitations cause this gap?
6. To properly evaluate the benefit of the SmartPIR protocol itself, please provide performance data for the baseline MulPIR protocol implemented on your CSD hardware, or provide a compelling argument for why this comparison is not necessary.

Review Form:

Reviewer: The Synthesizer (Contextual Analyst)

Summary

This paper presents SmartPIR, a full-stack Private Information Retrieval (PIR) system that tackles key performance and scalability bottlenecks in existing Fully Homomorphic Encryption (FHE)-based schemes. The authors correctly identify that as FHE computation is accelerated by hardware like GPUs, the system-level bottleneck shifts to I/O, as the entire database must be read from storage for every query. Furthermore, they highlight the significant computational overhead incurred when handling real-world, variable-length data, which requires padding records to a uniform maximum size.

The core contribution of SmartPIR is a holistic protocol and architecture co-design that moves the computation to the data using commercial Computational Storage Devices (CSDs). This is achieved through three key innovations:

1. An in-storage computing framework that offloads FHE operations to FPGAs embedded within CSDs, fundamentally eliminating the host-storage I/O bottleneck.
2. A novel "Zero-Skipping Encoding" (ZSE) protocol that intelligently handles variable-length data by segregating payload from padding, allowing the system to skip redundant computations on zero-padded data without compromising privacy.
3. A resource-efficient hardware design and load-aware scheduler optimized for the constrained environment of CSDs, enabling high throughput and near-linear scalability across an array of devices.

The authors demonstrate the efficacy of their system with an implementation on commercial SmartSSDs, showing speedups of 100-1000x over state-of-the-art CPU-based PIR systems.

Strengths

1. Excellent Problem Identification and Contextualization: The paper's primary strength lies in its clear-eyed view of the evolving landscape of PIR systems. The authors astutely recognize that the success of prior work in accelerating FHE computation has created a new, dominant bottleneck: data movement. The motivation presented in Section 3 (page 4), particularly with the compelling data in Figure 2, perfectly frames this "Amdahl's Law" moment for the field. This work represents a logical and necessary next step, shifting the focus from purely computational optimization to system-level, I/O-bound optimization.

2. A Powerful Synthesis of Ideas: This is not merely a paper about accelerating FHE on an FPGA. It is a compelling example of co-design, where insights from cryptography (PIR protocols), computer architecture (CSDs, FPGA design), and systems (scheduling, data layout) are synthesized into a single, cohesive solution. Marrying the CSD paradigm with a protocol explicitly designed to be hardware-friendly (ZSE) is the paper's most significant achievement.

3. Addressing a Critical Practical Challenge: The problem of variable-length data is a persistent thorn in the side of many cryptographic protocols, which often assume uniform data structures for simplicity. SmartPIR's ZSE scheme (Section 5.1, page 5) is an elegant solution that directly addresses this practical issue, yielding massive performance gains on realistic, skewed datasets. This significantly enhances the applicability of PIR to real-world use cases like text databases, logs, or user records.

4. Strong Empirical Evidence on Real Hardware: The evaluation is conducted on commercially available SmartSSDs, not a simulator. This lends immense credibility to the performance claims. The demonstrated near-linear scalability with an increasing number of CSDs (Figure 10, page 11) validates the architectural design and its promise for building large-scale, private systems. The comparison against strong baselines, including a high-end A100 GPU, effectively underscores the superiority of the in-storage computing approach for this I/O-bound problem.

Weaknesses

My criticisms are less about fundamental flaws and more about opportunities to further explore the implications of this excellent work.

1. Limited Discussion on Dynamic Data Management: The paper rightly positions itself as superior to LWE-based schemes like SimplePIR for dynamic datasets that require frequent updates (Section 8.5, page 12). However, the cost of updates within the SmartPIR framework itself is not fully explored. The ZSE scheme relies on sorting and partitioning the database based on entry length. A single record update, insertion, or deletion could potentially disrupt this layout, necessitating a costly data re-organization across the CSDs. A discussion of the amortization cost of such updates would provide a more complete picture of the system's performance in truly dynamic environments.

2. Generality of the Hardware Accelerator: The hardware engine is thoughtfully designed with three stages (PMAC, MAC, RAC) that are tightly coupled to the SmartPIR protocol's workflow (Figure 6, page 7). While this specialization is key to its efficiency, it raises questions about its flexibility. How much effort would be required to adapt this hardware to support a different FHE-based protocol (e.g., one with a different retrieval structure or higher multiplicative depth)? A brief discussion on the accelerator's programmability or adaptability would help contextualize it within the broader FHE acceleration landscape.

Questions to Address In Rebuttal

1. Could the authors elaborate on the operational cost of database updates? Specifically, if a new record is inserted or an existing one's length changes significantly, does this trigger a resort and re-partitioning of a large portion of the database shard? How is this re-organization managed, and what is its performance impact?

2. The cost and energy efficiency analysis in Section 8.4 (page 11) is very compelling. Given that CSDs are still a relatively niche technology compared to commodity SSDs and GPUs, could the authors comment on the trajectory of this technology? How does the anticipated maturation and commoditization of CSDs affect the long-term viability and accessibility of the SmartPIR approach?

3. The paper presents a significant leap forward for RLWE-based PIR. How do the authors see this work influencing the broader field of private computation? For example, could the principles of co-designing protocols for in-storage computation be applied to other FHE-heavy applications, such as private machine learning inference or genomic analysis?

Review Form

Reviewer: The Innovator (Novelty Specialist)

---

Summary

This paper presents SmartPIR, a Private Information Retrieval (PIR) system designed to run on Computational Storage Devices (CSDs). The authors identify two primary bottlenecks in existing Fully Homomorphic Encryption (FHE)-based PIR systems: (1) I/O overhead, which becomes dominant when computation is accelerated, and (2) computational inefficiency when handling variable-length data due to mandatory padding.

To address this, the authors propose a co-design of a new protocol and an in-storage architecture. The core claims to novelty appear to be:

1. An in-storage computing framework that offloads FHE operations to an array of commercial CSDs, thereby eliminating the host-SSD I/O bottleneck.
2. A "Zero-Skipping Encoding" (ZSE) protocol that structurally separates payload data from padding, allowing the system to skip redundant computations on the padding.
3. A set of system and architectural optimizations, including a "folding retrieval" mechanism, a resource-efficient FPGA design, and a load-aware scheduler, to make the system scalable and efficient on resource-constrained CSDs.

The paper demonstrates substantial performance gains over CPU- and GPU-based implementations of state-of-the-art PIR schemes.

Strengths

The most significant novel contribution of this work is the Zero-Skipping Encoding (ZSE) protocol (Section 5.1, Page 5). The problem of handling variable-length data in PIR has historically been addressed by brute-force padding, which, as the authors correctly identify, leads to massive computational overhead. The ZSE scheme, with its "horizontal encoding" that segregates padding into distinct, all-zero plaintext vectors, is a genuinely new protocol-level idea for mitigating this issue. This allows for a data-aware computation flow where zero-vectors can be provably skipped without leaking information about the query, directly tackling a fundamental inefficiency in prior art.

The second key strength is the practical realization of in-storage PIR on commercial hardware. While the conceptual groundwork for in-storage PIR acceleration was laid by prior work (e.g., INSPIRE [34]), that work was based on a simulated architecture. This paper presents a full-stack implementation on commercially available SmartSSDs. Moving a complex system like FHE-based PIR from simulation to a functioning hardware prototype is a non-trivial contribution that validates the real-world viability of the in-storage processing paradigm for this domain.

Weaknesses

My primary concern relates to the positioning of the work and the novelty of several constituent components.

1. The Foundational Idea of In-Storage PIR Is Not New: The central premise of offloading PIR computation to near-storage processors to alleviate the I/O bottleneck was previously proposed and explored in INSPIRE [34]. The authors cite INSPIRE as a baseline but do not sufficiently acknowledge that the core concept of an "in-storage private information retrieval" system is prior art. The novelty here lies in the implementation on real hardware and the co-designed protocol for variable-length data, not in the foundational idea of moving PIR computation to storage. The authors should frame their contribution more precisely as the first practical and variable-length-aware implementation of this concept.

2. Several "Novel" Optimizations Are Adaptations of Known Techniques: The paper presents several architectural and protocol-level optimizations that, while effective, are adaptations of existing ideas rather than fundamental innovations.

   • Folding Retrieval (Section 5.2, Page 6): The authors explicitly state they "leverage the idea of folding [6, 7]". Their contribution is the application of this known query-size reduction technique to the specific 3D data structure produced by their ZSE scheme. This is an engineering adaptation, not a new retrieval concept.
   • KeySwitch Hoisting (Section 6.1.2, Page 7): Deferring expensive operations like KeySwitch until after a batch of cheaper operations (like Mult and Add) have accumulated is a known optimization pattern in FHE accelerator design to reduce overhead. While its application here is sound, it does not represent a novel architectural principle.
   • Load-Aware Scheduling (Section 6.2, Page 8): The use of a greedy heuristic to solve a knapsack-like load balancing problem is a standard systems design technique. The novelty is in the metric being balanced (the count of non-zero plaintexts, a direct result of ZSE), but the scheduling algorithm itself is not new.

The paper would be stronger if it more clearly delineated between genuinely new ideas (like ZSE) and the clever engineering that involved adapting existing techniques to their specific system.

Questions to Address In Rebuttal

1. The concept of in-storage PIR was proposed in INSPIRE [34]. Please clarify the conceptual novelty of your work beyond the (admittedly significant) engineering effort of implementing it on real CSDs. Is the primary novelty the ZSE protocol's ability to efficiently handle variable-length data, a specific weakness that INSPIRE did not address?

2. The Zero-Skipping Encoding (ZSE) appears to be the main novel protocol contribution. Could the authors elaborate on any potential performance or security trade-offs introduced by this "horizontal encoding" approach? For instance, does spreading a single database entry across multiple plaintext vectors increase the baseline complexity for retrieving a single, fully-packed entry compared to traditional encoding schemes?

3. The paper presents several architectural techniques (e.g., KeySwitch Hoisting, modular resource reuse). Could the authors please contextualize these with respect to prior work in the FHE hardware acceleration community? Are there specific constraints of the CSD's FPGA that make the application of these known techniques non-trivial and thus a contribution in its own right?