Sublinear Indexing for Scalable Encrypted Search

72 concepts61 papers2 proposals

The fundamental challenge of searchable encryption lies in a harsh trade-off between privacy and performance. In a naive encrypted database, searching for a keyword securely requires the server to perform a linear scan ($O(N)$) over every single record. If the server skipped records, it would reveal information about which documents match the query, leaking access patterns. While perfectly secure, this linear scan quickly becomes computationally prohibitive as datasets grow into millions of records.

To break this bottleneck, a major research direction focuses on sublinear indexing for encrypted search. The core intuition is to translate classical database acceleration techniques—such as tree-based pruning, inverted indices, and hierarchical filtering—into the cryptographic domain. By structuring ciphertexts into searchable indices, systems can achieve logarithmic ($O(\log N)$) or constant-time search complexities without decrypting the underlying data.

Tree and Graph Structures for Logarithmic Pruning

In plaintext databases, trees are the gold standard for avoiding exhaustive scans. By organizing data hierarchically, a search algorithm can discard entire branches of irrelevant data at each step. Bringing this concept to encrypted cloud storage, Xingming Sun et al. demonstrated in Dynamic Multi-keyword Top-k Ranked Search over Encrypted Cloud Data that tree-based index structures reduce the computational complexity of multi-keyword ranked searches from linear to logarithmic relative to the document count. As further detailed by the authors in Privacy-preserving Multi-keyword Ranked Search over Encrypted Cloud Data Supporting Dynamic Update, this scaling property ensures that search performance depends primarily on the number of relevant results rather than the size of the entire dataset.

This tree-based pruning paradigm extends across diverse data modalities:

When dealing with network data, graph structures offer similar scaling advantages. In GraSS: Graph-based Similarity Search on Encrypted Query, Duhyeong Kim et al. designed an encryption-friendly graph structure where the time required for each search step remains largely constant regardless of the total number of entries. Consequently, performance scales with the search depth rather than the database volume.

Hierarchical Pipelines and Candidate Pre-Filtering

Fully Homomorphic Encryption (FHE) and Multi-Party Computation (MPC) allow for highly secure, arbitrary computations on encrypted data, but they introduce massive computational overhead. To make these heavy cryptographic tools scalable, researchers employ a multi-layered strategy: use a fast, lightweight sublinear indexing mechanism to prune the database down to a small candidate set, and then apply the expensive cryptographic operations only to that pre-filtered subset.

[ Massive Encrypted Database ] 
             │
             ▼  (Stage 1: Fast Sublinear Index / Pruning)
   [ Small Candidate Set ]
             │
             ▼  (Stage 2: Heavy Cryptography / FHE / MPC)
      [ Exact Matches ]

This hierarchical architecture is highly effective for complex retrieval tasks. Haomiao Tang et al. developed a two-stage framework in Secure and Scalable Face Retrieval via Cancelable Product Quantization that utilizes a rapid indexing stage to filter candidates before executing fine-grained homomorphic encryption for final ranking, yielding a 500x speedup over flat encrypted searches.

In the context of large language models, Yihang Cheng et al. applied this multi-layered approach to Retrieval-Augmented Generation (RAG) in RemoteRAG: A Privacy-Preserving LLM Cloud RAG Service, limiting expensive cryptographic operations to a small candidate set to maintain real-time cloud response times over millions of documents. Similarly, Guy Zyskind et al. adapted inverted file indexing to secure MPC in Don't forget private retrieval: distributed private similarity search for large language models, clustering data into buckets so that queries are only evaluated against relevant clusters, which significantly cuts down communication bandwidth.

Optimizing Cryptographic Workloads via Structural Layouts

Beyond trees, the physical and mathematical layout of the index itself can be optimized to minimize cryptographic overhead. Inverted indices—which map keywords directly to document identifiers—are widely used to achieve sublinear retrieval. Iftekhar Salam et al. demonstrated in Implementation of searchable symmetric encryption for privacy-preserving keyword search on cloud storage that encrypted inverted indices maintain efficient retrieval speeds as the corpus grows, while Mingchu Li et al. showed in Encrypted Searching with Adaptive Symmetric Searchable Encryption Security in Cloud Storage that these indices can be compressed to occupy less storage space than the original raw data corpus.

For more complex query types, specialized layouts prevent performance degradation:

Algorithmic Primitives for Efficient Traversal and Joins

Achieving sublinear complexity often requires moving away from generic cryptographic primitives toward algorithms engineered for specific data access patterns.

When navigating encrypted tree indices, protecting the client's access path from the server is critical. Erik-Oliver Blass et al. introduced Iterative Oblivious Pseudo-Random Functions (iOPRFs) in Iterative Oblivious Pseudo-Random Functions and Applications, which allow a client to traverse a tree path-by-path. This primitive ensures that the server learns nothing about the access pattern while maintaining optimal linear complexity relative to the depth of the tree rather than its total size.

Database join operations traditionally suffer from a quadratic ($O(N^2)$) bottleneck when executed blindly over encrypted tables. To overcome this, Masoumeh Shafieinejad et al. proposed predicate-aware join optimization in Equi-Joins Over Encrypted Data for Series of Queries. By identifying matching join keys only for the rows that satisfy specific selection criteria, the authors enabled hash-based join algorithms on encrypted data, successfully dropping the computational complexity from quadratic to linear.

Similarly, in high-throughput multi-writer streams, Angelo Massimo Perillo et al. introduced Amortized Orthogonality Encryption (AOE) in Secure Selections on Encrypted Multi-writer Streams to achieve linear efficiency for complex conjunctive queries, bypassing the massive quadratic overhead of traditional non-amortized methods.

Key Foundational Work

CryptDB: protecting confidentiality with encrypted query processing (2011) — contributed 4 concept elements to this direction.
Efficient Secure Query Evaluation over Encrypted XML Databases (2006) — contributed 1 concept elements to this direction.
Conjunctive, Subset, and Range Queries on Encrypted Data (2006) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scalable_searchable_encryption_a59aba01,
  title = {scalable searchable encryption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scalable-searchable-encryption/rdr_a59aba016f714e648004aebfc1e10676},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_scalable_searchable_encryption_a59aba01_v1,
  title = {scalable searchable encryption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scalable-searchable-encryption/rdr_a59aba016f714e648004aebfc1e10676/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake