💻 computer science

SPIDER: Two Server Functionality for the Cost of Zero

This paper introduces SPIDER, a novel single-server Private Information Retrieval (PIR) scheme that achieves privacy on standard database interfaces without server cooperation by transforming a stateful client-side protocol (baseSPIDER) that offers improved constant factors and conceptual simplicity over existing solutions.

Original authors: Ofir Dvir, Kali Hale, Javin Zipkin, Divyakant Agrawal, Dahlia Malkhi

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ofir Dvir, Kali Hale, Javin Zipkin, Divyakant Agrawal, Dahlia Malkhi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are at a massive, public library (the Server) that holds millions of books. You want to borrow one specific book without the librarian knowing which one you picked. If you just ask for "Book #4,592," the librarian knows exactly what you want. If you ask for every single book in the library to hide your choice, you'd have to carry a mountain of books home, which is impractical.

This is the problem of Private Information Retrieval (PIR). The paper introduces two new solutions, baseSPIDER and SPIDER, to solve this.

Here is how they work, using simple analogies:

The Core Idea: The "Redacted" Puzzle

Both solutions rely on a clever trick involving hints and XORing (a math operation that acts like a secret code where two things cancel each other out).

Think of a "hint" as a mystery box containing a random selection of books. The client (you) knows exactly which books are in the box and what their combined "secret code" is.

The Setup (Pre-processing): Before you even go to the library, you download the entire library's catalog and create thousands of these mystery boxes. You store the "secret code" for each box in your pocket.
The Request: You want Book #4,592. You find a mystery box that contains Book #4,592.
The Trick: You tell the librarian, "Please give me all the books in this box except for Book #4,592."
- The Catch: The librarian doesn't know which book you are hiding. To them, you just asked for a random list of books.
The Reveal: The librarian hands you the remaining books. You take your secret code for the full box and combine it with the books you just got. Because of the math, the books you got cancel out, leaving you with only the one book you actually wanted.

The Two Versions

The paper presents two versions of this system, depending on how cooperative the library is.

1. baseSPIDER: The "Helpful Librarian"

This version works when the librarian is willing to do a tiny bit of extra work.

How it works: You ask for the mystery box minus your target book. The librarian takes all those books, mixes them together (XORs them) into a single, tiny piece of paper, and hands it to you.
The Benefit: You only download one tiny piece of paper, no matter how big the books are. This is incredibly fast and efficient, especially if the books are huge (like movies or large data files).
The Catch: The librarian must be willing to mix the books for you. If the library has a strict policy of "we only hand out books, we never mix them," this doesn't work.

2. SPIDER: The "Strict Librarian" (The Default Server)

This is the paper's big breakthrough. It works even if the librarian is uncooperative and refuses to do any mixing. They only follow a rule: "If you give me a list of numbers, I will hand you the books at those numbers, one by one."

How it works: You ask for the mystery box minus your target book. Instead of mixing them, the librarian hands you every single book in that list, one by one.
The Trade-off: You have to download more data (the whole list of books) instead of just one mixed piece.
The Magic: Because you already have the "secret code" for the full box in your pocket, you can mix the books yourself on your computer. You get your target book, and the librarian still has no idea which one you wanted.
Why it matters: This allows you to use PIR on any existing website or database (like Wikidata) without needing to ask them to install special privacy software. You just use their standard "give me book #X" interface.

The "Continuous Refresh" Feature

One of the cleverest parts of the paper is how they handle the fact that you can't use the same mystery box twice (if you use it twice, the librarian might figure out your pattern).

The Problem: Once you use a box, it's "spent." You need new boxes.
The Solution: In the SPIDER version, because you are downloading all the books from the list anyway, you use those downloaded books to build new mystery boxes while you are at it.
The Analogy: It's like going to the library, getting a stack of books, reading the one you wanted, and then using the other books in the stack to build a new mystery box for your next visit. You never have to stop and download the whole library again; you just keep recycling the books you already have.

Summary of Claims

baseSPIDER is the fastest way to get private data if the server is willing to help mix the data. It is faster than previous methods, especially for large files.
SPIDER is the first method that works on any standard server that doesn't want to help. It requires you to download a bit more data, but it removes the need for special server software.
Both methods allow you to keep asking questions privately without the server knowing what you are looking for, using a system of "mystery boxes" and "secret codes" that refreshes itself as you go.

The paper does not claim these methods are for medical records, voting, or specific future technologies; it strictly focuses on the mathematical and engineering improvements for retrieving data privately from a single server.

Technical Summary: SPIDER and baseSPIDER

Problem Statement

The paper addresses the challenge of deploying Private Information Retrieval (PIR) in two distinct but critical web environments:

Scalability for Large Entries: Modern web servers serve massive objects (images, videos, large records). Existing stateful single-server PIR schemes often suffer from high constant factors in communication and computation, which become prohibitive when database entries ( $\beta$ ) are large.
The Default-Server Constraint: Most recent efficient single-server PIR schemes require a "cooperative" server that performs specific operations (e.g., XORing retrieved items) or maintains PIR-specific metadata. However, real-world web services (e.g., Wikidata, standard content delivery networks) are "default" servers: they offer only standard read-only, index-based access, cannot be modified, and provide no specialized APIs. Existing PIR solutions cannot operate in this uncooperative setting without violating the server's business model or technical constraints.

Methodology

The paper introduces two protocols: baseSPIDER (for cooperative servers) and SPIDER (for default servers). Both rely on a stateful client that performs a one-time preprocessing phase to store "hints" for future queries.

1. Core Mechanism: Multiset-Based Hints

Unlike prior works (e.g., PIANO, RMS) that partition the database into shards, baseSPIDER and SPIDER utilize a new hint construction based on multisets.

Hint Generation: During preprocessing, the client samples $m$ hints. Each hint is a multiset of $k \approx \sqrt{n}$ indices selected uniformly at random from all possible $\sqrt{n}$ -multisets over the database of size $n$ .
Compact Storage: Instead of storing the full list of indices, the client stores a 64-bit seed and the precomputed XOR of the corresponding database entries. The seed allows deterministic reconstruction of the multiset via a "stars-and-bars" bijection.
Redaction Property: The key insight is that if a uniformly chosen multiset has one element removed (redacted), the remaining $(k-1)$ -multiset is distributed uniformly and independently of the removed element. This ensures that the server cannot distinguish which element was the target of the query.

2. baseSPIDER (Cooperative Server)

Operation: The client selects a hint containing the target index $i$ , "redacts" it by removing $i$ from the multiset, and sends the remaining $k-1$ indices to the server.
Server Role: The server computes the XOR of the entries at these $k-1$ indices and returns a single value.
Recovery: The client XORs the server's response with the stored hint (which contains the XOR of all $k$ entries) to recover the target entry $i$ .
Hint Replenishment: To prevent the server from inferring access patterns over time, used hints are discarded. The client maintains a pool of hints and uses a replacement strategy (swapping a used index into a random surviving hint) to maintain coverage without bias.

3. SPIDER (Default Server)

Transformation: SPIDER adapts baseSPIDER to require no server-side computation beyond standard retrieval.
Operation: Instead of asking the server to XOR the entries, the client requests the raw entries corresponding to the redacted indices.
Client Role: The client performs the XOR operation locally.
Continuous Refresh: Because the client downloads $k-1$ entries per query, it can use these raw entries to construct new hints in the background, enabling continuous querying without a distinct, heavy preprocessing phase.

Key Contributions

Optimized Communication for Large Entries (baseSPIDER):
- baseSPIDER achieves the asymptotically optimal communication complexity of $\tilde{O}(\sqrt{n} \cdot \beta)$ while improving constant factors.
- It reduces the per-query communication from $2 \cdot \beta$ (in the state-of-the-art RMS-24) to exactly $1 \cdot \beta$ . This is a significant practical improvement for databases with large entries.
- It offers a conceptually simpler design compared to prior sharding-based approaches.
First Single-Server PIR for Default Servers (SPIDER):
- SPIDER is the first construction to achieve PIR privacy on a server that performs no PIR-specific operations and maintains no PIR-specific state.
- It requires only standard indexed retrieval APIs.
- While it incurs higher client computation (XORing $\sqrt{n}$ entries) and higher per-query download ( $\sqrt{n} \cdot \beta$ ), it enables PIR on existing, unmodified web infrastructure.
General Transformation:
- The paper demonstrates that the transformation from a cooperative to a default-server setting can be applied broadly to other recent PIR schemes (PIANO-23/24, RMS-24, WR-25), adapting them to the default-server paradigm.

Results and Evaluation

Complexity Analysis:
- Communication: baseSPIDER achieves $1 \cdot \beta$ per query (amortized $\sqrt{n} \cdot \beta$ ). SPIDER achieves $\sqrt{n} \cdot \beta$ per query (amortized $\sqrt{n} \cdot \beta$ ).
- Storage: Client storage is $O(\sqrt{n} \cdot \log n \cdot \beta)$ for both schemes.
- Computation: Server computation is $O(\sqrt{n})$ per query (dominated by I/O). Client computation involves $O(\sqrt{n})$ XORs per query in SPIDER.
Experimental Findings:
- In the cooperative setting, baseSPIDER outperforms RMS-24 in end-to-end latency, particularly as entry size ( $\beta$ ) increases, due to the halving of network traffic.
- Hint search latency (linear scan) is a bottleneck for small entries but becomes negligible compared to network and I/O latency for large entries.
- SPIDER was successfully integrated with Wikidata, demonstrating that the scheme works on a real-world, non-cooperative SPARQL endpoint without modifying the server.

Significance and Claims

The paper claims that SPIDER and baseSPIDER address the two primary remaining barriers to practical PIR deployment on the open web:

Performance: By improving constant factors, baseSPIDER makes PIR viable for large-scale data retrieval where bandwidth is a critical constraint.
Deployability: By removing the need for server cooperation, SPIDER enables privacy-preserving retrieval on the "default" web, where servers are uncooperative and cannot be modified.

The authors note that while SPIDER trades off optimal per-query communication for server compatibility, it enables "uninterrupted, continuous querying" by leveraging the downloaded data for hint replenishment. The work establishes that high-performance, private retrieval is possible even under the strictest constraints of the modern web, provided the client is stateful and willing to perform additional local computation.