In the world of privacy-preserving data access, there is a fundamental "linearity barrier." To retrieve a single item from a database without the server knowing which one you picked, the server must—at least in the traditional model—touch every single record in the database.
As Mingxun Zhou, Elaine Shi, and others have noted in papers like Optimal Single-Server Private Information Retrieval, this requirement is a logical necessity for perfect privacy: if the server skips even one record, it learns with 100% certainty that the user was not interested in that record. For a database with millions or billions of entries, this $O(n)$ computational cost makes Private Information Retrieval (PIR) prohibitively slow for real-time applications like DNS lookups Xiao et al. or genomic searching Sá Sousa et al..
Recent research has focused on breaking this barrier, moving from linear scans to sublinear query times ($O(\sqrt{n})$, $O(\log n)$, or even $O(1)$) by rethinking the relationship between the client, the server, and the data.
The Preprocessing Paradigm
The most successful strategy for achieving sublinear time is shifting the heavy lifting to an offline preprocessing phase. In this model, the client and server perform a one-time setup where the client downloads a small amount of "hint" metadata.
In Piano: Extremely Simple, Single-Server PIR with Sublinear Server Computation, Mingxun Zhou and Elaine Shi demonstrate how these hints allow the server to process only a fraction of the database during the actual query. The intuition is that the client’s hints act as a "map" of random parity checks. When a query arrives, the client uses their hint to request a specific set of items that, when combined, reveal only the desired record.
Other frameworks like Pai, introduced by Shuaishuai Li and Yuan Hong, push this to the limit, achieving constant ($O(1)$) online time Encode and Permute that Database!. By encoding and permuting the database during the offline phase, the online retrieval becomes a simple, direct lookup. Alexander Hoover and Sarvar Patel further refined this in Plinko by using Invertible Pseudorandom Functions (iPRFs) to handle database updates efficiently, solving a long-standing weakness of preprocessing-based PIR Plinko: Single-Server PIR with Efficient Updates via Invertible PRFs.
Secure Indexing and Hashing
While PIR focuses on retrieving data by index, "Private Search" aims to find data by content (e.g., "find the nearest neighbor to this vector"). Traditional cryptographic search often defaults back to linear scans to hide the search pattern.
To achieve sublinear performance here, researchers like M. Sadegh Riazi and Beidi Chen developed Secure Locality Sensitive Indexing (SLSI) Sub-Linear Privacy-Preserving Near-Neighbor Search. SLSI uses a probabilistic transformation of Locality Sensitive Hashing (LSH). Instead of checking every record, the system hashes the query and only searches the "buckets" where a match is likely. The "secret sauce" is a mathematical flattening of the hash collision probabilities, which prevents an untrusted server from using the frequency of collisions to triangulate and reveal the original data.
Similarly, Hao Chen and colleagues introduced SANNS, which uses sublinear clustering to scale secure approximate nearest neighbor search to datasets with 10 million entries SANNS: Scaling Up Secure Approximate k-Nearest Neighbors Search. By combining clustering with homomorphic encryption, they avoid the quadratic explosion of distance calculations usually required for encrypted spatial queries Liu et al..
Relaxing Privacy for Practicality
A third direction involves a pragmatic trade-off: if "perfect" obliviousness is too expensive, can we achieve "good enough" privacy with much higher speed?
In Scalable Private Search with Wally, Hilal Asi and Guy N. Rothblum relax the requirement from full obliviousness to $(\epsilon, \delta)$-differential privacy. This allows the system to hide a user's query among a "crowd" of real and fake queries. Because the server no longer needs to be 100% "blind" to which records it touches, it can use more efficient data structures, resulting in a 31x reduction in bandwidth.
This concept of "Weakly-Private Information Retrieval," explored by Hsuan-Yin Lin and others, suggests that by allowing a quantifiable, tiny amount of leakage, we can drastically reduce the access complexity and operational burden on servers Weakly-Private Information Retrieval.
The Path Forward
The field is moving toward unifying these techniques. For instance, Pacmann by Mingxun Zhou and Giulia Fanti combines graph-based search (an indexing technique) with preprocessing-based PIR to achieve sublinear efficiency for nearest-neighbor searches on massive datasets.
By moving away from the "scan everything" mentality and toward intelligent preprocessing, secure indexing, and differential privacy, researchers are transforming PIR from a theoretical "holy grail" into a practical component for modern, high-throughput systems.