💻 computer science

Hybrid privacy-aware semantic search: SVD-truncated document geometry and CKKS-encrypted query reranking under a restricted threat model

This paper proposes a hybrid privacy-aware semantic search framework that combines SVD-truncated geometric obfuscation for static document vectors with CKKS homomorphic encryption for dynamic query reranking, achieving sub-second latency and robust protection against embedding-inversion attacks while maintaining high ranking quality under a defined threat model.

Original authors: Sergey Kurilenko

Published 2026-06-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sergey Kurilenko

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 have a massive library of secret documents, and you want to let people search for them without ever letting the librarian (the server) see the actual text or know exactly what you are looking for.

This paper proposes a clever, two-part trick to solve this problem, but it is very honest about where the trick works and where it might fail. Think of it as a "hybrid" security system that mixes geometry (shapes and angles) with magic math (encryption).

Here is the breakdown in simple terms:

1. The Problem: The "Leaky" Library

Modern search engines turn text into "embeddings"—think of these as unique fingerprints or shadows cast by the text.

The Risk: Researchers have discovered that if someone steals these fingerprints, they can often reconstruct the original secret text with scary accuracy. It's like stealing a shadow and being able to rebuild the 3D object that cast it.
The Old Solutions:
- Option A (Full Encryption): Put every document in an unbreakable safe. Problem: It's so slow that searching a million documents would take hours.
- Option B (Adding Noise): Blur the fingerprints with static. Problem: The blur is so heavy that the search engine can't find the right answers anymore.

2. The New Solution: A Two-Step Dance

The authors propose a middle ground that treats the documents (the library) and the search queries (the user's request) differently.

Step A: Protecting the Documents (The "Geometric" Trick)

The documents are stored on the server, but they are altered before they get there.

Compression (SVD Truncation): Imagine a high-resolution photo. The system throws away the "fine details" (the noise) and keeps only the main shapes. This reduces the file size and, crucially, removes some of the information needed to rebuild the original text.
- The Catch: This isn't magic; it's just data compression. If you throw away too much, the search gets worse. If you throw away too little, the text is still recoverable.
The Secret Spin (Rotation): After compressing the data, the system spins the entire library on a secret axis. Imagine taking a map of a city and rotating it 90 degrees so "North" is now "East."
- The Trick: The server sees the rotated map, but it doesn't know the angle of the spin. To an outsider, the map looks like gibberish.
- The Limit: If an attacker knows the original text of even a few documents (like a "known-plaintext" attack), they can mathematically figure out the secret spin angle and undo the rotation. This is not unbreakable cryptography; it's a puzzle that gets easier if you have a few clues.

Step B: Protecting the Search Query (The "Magic" Trick)

When a user searches, they don't send the question in plain text.

They use CKKS Encryption, a type of "magic math" that allows the server to do calculations on the question without ever seeing the question itself.
The server compares the encrypted question against the rotated documents and returns a list of scores, all while remaining "blind" to what the user asked or what the scores actually mean.
Result: The server follows the rules but learns nothing about the specific query. This part is mathematically secure.

3. The Results: What Works and What Doesn't

The authors tested this on a library of one million documents.

Speed: It is fast! The whole process takes less than a second.
Accuracy: For most modern search models, throwing away half the data (the compression step) actually improved the search results. It acted like a "denoiser," filtering out the messy details and leaving the clear signal.
Security Reality Check:
- The Query: The server cannot see what you searched for. (Secure).
- The Documents: The server can see the compressed, rotated data. If an attacker has a few examples of "Original Text vs. Rotated Fingerprint," they can reverse-engineer the secret spin and read the rest of the library.
- The "Public" Clues: The system uses a public "index" (like a card catalog) to speed things up. The paper admits this index leaks some information about which documents are similar to each other.

4. The Bottom Line

This paper doesn't claim to have built an unbreakable fortress. Instead, it offers a practical trade-off:

For the User: You get fast, private search where the server can't read your mind.
For the Documents: You get a layer of protection that makes it very hard for a casual attacker to read your secrets, but it is not safe against a determined attacker who has a few "cheat codes" (known examples of your data).

The authors' main message: "We have found a sweet spot where the search is fast and accurate, and the query is cryptographically safe. However, the document protection relies on a 'secret spin' that is an obfuscation trick, not a magic shield. If you have a few leaked examples of your data, that trick fails."

They are very clear: Query privacy is cryptographic (unbreakable), but document privacy is empirical (it works until someone figures out the pattern).

Problem Statement

Modern semantic search and Retrieval-Augmented Generation (RAG) rely on dense vector embeddings. However, recent research demonstrates that these embeddings can be inverted back into their source text with high fidelity (e.g., Vec2Text achieving ~97% BLEU). This creates a critical vulnerability: if a vector database leaks, the underlying documents are effectively compromised.

Existing defenses fall into two extremes, both unsuitable for industrial-scale deployment:

Fully Homomorphic Encryption (FHE): Cryptographically sound but computationally prohibitive for searching millions of documents.
Differential Privacy (DP): Adding noise degrades ranking quality significantly before providing meaningful privacy protection.

The paper addresses the need for a middle path that balances privacy, retrieval accuracy, and latency at the scale of $10^6$ documents.

Methodology

The authors propose an asymmetric hybrid architecture that treats the static document collection and the dynamic user query differently. The system operates under a restricted threat model: a trusted client, an honest-but-curious server, and a non-adaptive attacker (using off-the-shelf inversion tools without prior knowledge of the secret rotation).

1. Document Protection (Static Side)

The document vectors are protected via a geometric transformation rather than encryption:

SVD Truncation: The centered document corpus is projected onto a lower-dimensional subspace ( $k = d/2$ ) using Singular Value Decomposition (SVD). This truncation is chosen to ensure a relative reconstruction error ( $\sigma_{rec}$ ) of at least 0.10, serving as a proxy for information loss.
Secret Rotation: The truncated vectors are multiplied by a secret, Haar-uniform random orthogonal matrix $R$ . This rotation hides the orientation of the basis from attackers who do not possess $R$ .
Public Product Quantization (PQ): A PQ index (codebook + codes) is trained in the rotated space to allow the client to perform local candidate filtering (Stage 1) without sending queries to the server. The authors explicitly note this PQ artifact is a "lossy compressed view" that leaks neighborhood structure and is treated as an exposed channel.

2. Query Protection (Dynamic Side)

The query is protected cryptographically:

CKKS Encryption: The client encrypts the rotated query vector using the CKKS homomorphic encryption scheme.
Ciphertext-Plaintext (ct-pt) Reranking: The server performs the reranking of the short-listed candidates (e.g., top 40) by computing the inner product between the encrypted query and the plaintext rotated document vectors.
Optimization: By avoiding ciphertext-ciphertext (ct-ct) multiplication, the system eliminates the need for costly relinearization steps. This allows the server to compute similarity scores in sub-second latency.

3. Parameter Selection

Instead of manual tuning, the authors employ a reproducible offline micro-benchmark over a discrete grid of CKKS parameters (polynomial modulus degree, coefficient modulus chain, scale) to select the configuration that minimizes latency while satisfying security tables (tc128) and accuracy tolerances.

Key Contributions

Theoretical:

Lemma 1: The paper proves a tight lower bound on the $L_2$ reconstruction error for any decoder whose image is constrained to the truncated subspace. This formally quantifies the information lost to the projection, though the authors clarify this is a projection bound, not a general inversion-security theorem.
Empirical Hypothesis 1: They formalize the relationship between the reconstruction error proxy ( $\sigma_{rec}$ ) and the BLEU score of off-the-shelf inversion attacks, validating it numerically.

Empirical & Engineering:

Scale Evaluation: Experiments conducted on a 1-million-document corpus (Russian Wikipedia) using five contemporary text encoders (including multilingual-E5 and BGE-M3).
Latency: The system achieves end-to-end query latency comfortably below 1 second (p95 $\approx$ 370 ms) for $10^6$ documents.
CKKS Optimization: The selected configuration ( $N_{poly}=8192$ , specific modulus chain) yields a 1.7 $\times$ speed-up over standard TenSEAL settings while maintaining the same security bound.
Denoising Effect: For retrieval-trained encoders with dimensions $d \ge 768$ , the SVD truncation acts as a linear denoiser, slightly improving ranking metrics (Acc@1, NDCG) compared to the raw baseline by filtering out noise in trailing singular directions.

Results and Security Analysis

The paper rigorously tests the system against both the intended threat model and stronger adversaries:

Against Non-Adaptive Attackers: Under the restricted model (unknown $R$ , off-the-shelf Vec2Text), the secret rotation reduces BLEU scores to the noise floor ( $\approx 0.007$ ), effectively preventing text recovery.
Against Known-Plaintext Attackers: If an attacker possesses $\approx k$ (the retained dimension) pairs of (original text, rotated vector), they can recover the secret rotation $R$ using Orthogonal Procrustes. Once $R$ is known, the protection reduces to the SVD truncation alone.
Reference Corpus Leakage: If the protected collection overlaps with a public or leaked reference corpus, the attacker can use the recovered rotation to perform exact paragraph lookups.
PQ Artifact Leakage: The public PQ codes preserve $\approx 95\%$ cosine similarity to the rotated vectors and retain most top-10 neighbors, confirming that the PQ artifact is an exposed channel that leaks structural information.
Encoder Dependence: The "denoising" benefit is specific to retrieval-trained encoders. Compact models (e.g., e5-small) or paraphrase-distilled models suffer accuracy degradation with $k=d/2$ truncation.

Significance and Claims

The paper positions itself as a scientific study rather than a deployable product or a systems engineering report. Its significance lies in:

Defining Boundaries: It explicitly delimits the threat model. It claims query confidentiality is cryptographic (via CKKS) but document protection is empirical obfuscation (via SVD + Secret Rotation). It does not claim the document layer is cryptographically secure against adaptive or known-plaintext adversaries.
Quantifying Trade-offs: It provides a measured operating point where privacy, accuracy, and latency are balanced. It demonstrates that for specific encoder types, privacy-preserving truncation can coincidentally improve retrieval quality.
Reproducibility: It offers a deterministic method for selecting cryptographic parameters and releases all scripts and configurations.

Limitations Acknowledged by the Authors:

Document privacy is not cryptographic; it fails against known-plaintext or adaptive attacks.
Access patterns (which documents are reranked) and PQ codes are exposed.
The system relies on a specific class of encoders (retrieval-trained, $d \ge 768$ ) to maintain accuracy.
The primary open question remains the robustness against an end-to-end learned decoder trained specifically on the rotated space, which was not fully evaluated in this study.

In conclusion, the paper presents a practical, high-performance hybrid approach for semantic search that shifts the privacy burden to the query side (cryptographic) and the document side (geometric obfuscation), while transparently quantifying the failure modes of the geometric obfuscation layer.