Efficient Privacy-Preserving Retrieval Augmented Generation with Distance-Preserving Encryption

Huanyi Ye, Jiale Guo, Ziyao Liu, Kwok-Yan Lam

TL;DR

This paper introduces ppRAG, a novel framework for secure Retrieval-Augmented Generation (RAG) that allows users to leverage cloud storage for their private data without compromising privacy. It achieves this through a new encryption scheme, CAPRISE, which enables efficient similarity search on encrypted data while defending against various privacy attacks.

What Problem Does This Paper Address?

Large Language Models (LLMs) are powerful, but they often suffer from outdated knowledge or "hallucinations." Retrieval-Augmented Generation (RAG) addresses this by allowing LLMs to access external knowledge bases. However, when individuals or small organizations need to store large amounts of private data in the cloud for RAG, privacy becomes a major concern. Traditional RAG systems assume a trusted environment, but outsourcing data to untrusted cloud providers introduces risks. Specifically, the vector embeddings used for similarity search can be vulnerable to attacks that reconstruct original text (Vec2Text) or reveal relationships between documents (Vector Analysis). Furthermore, repeated queries can expose sensitive usage patterns (Query Analysis). Existing privacy-preserving RAG solutions often rely on computationally expensive encryption methods, making them impractical for real-world use.

Methods

The core of ppRAG is a new symmetric encryption scheme called Conditional Approximate Distance-Comparison-Preserving Symmetric Encryption (CAPRISE). Unlike previous methods that might preserve all pairwise distances between encrypted data, CAPRISE is designed to only preserve the distance comparisons between an encrypted query embedding and the encrypted database embeddings. This is crucial for enabling similarity search for retrieval. By not preserving the distances among the database embeddings themselves, CAPRISE effectively obfuscates the internal structure of the data, thus defending against vector analysis attacks.

To further enhance privacy, ppRAG incorporates Differential Privacy (DP) via a mechanism called DistanceDP. Before encrypting a query embedding, it's perturbed with calibrated noise. This makes it difficult for the cloud server to infer sensitive patterns from query frequency or similarity scores, mitigating query analysis risks.

The overall ppRAG framework operates in three phases:

  1. Upload: User encrypts local files and their corresponding embeddings using AES and CAPRISE, respectively, and uploads them to the cloud.
  2. Retrieve & Generate: User encrypts a query embedding using CAPRISE and sends it to the cloud. The cloud performs a similarity search on encrypted embeddings and returns the top-k encrypted files. These are then decrypted locally.
  3. Augment & Prompt: The retrieved content is combined with the original query to augment the prompt for the LLM.

Datasets

The paper uses the MS MARCO dataset for evaluation. The embedding model used is gtr-t5-base. No new benchmarks were introduced.

Key Insights and Ideas

  • Selective Distance Preservation is Key: The insight that preserving all pairwise distances in encrypted embeddings is not necessary for retrieval and can actually be a privacy vulnerability is central. CAPRISE's focus on query-to-database distances is a clever way to balance functionality and privacy.
  • CAPRISE vs. ADCPE: The paper clearly illustrates how CAPRISE offers stronger privacy against vector analysis than ADCPE by intentionally breaking inter-database distance relationships, while still maintaining retrieval accuracy.
  • Differential Privacy for Query Obfuscation: The integration of DistanceDP is a practical step to address the often-overlooked threat of query analysis, which can reveal user behavior even with encrypted data.
  • Efficiency Gains: The significant improvement in encryption throughput compared to existing methods like RemoteRAG highlights the practicality of CAPRISE for real-world applications.

Key Results

  • Vec2Text Attack Defense: CAPRISE significantly reduces the reconstructability of encrypted embeddings, dropping the BLEU score from over 83.021 (without encryption) to 12.425 (with CAPRISE), demonstrating strong privacy against embedding inversion.
  • Vector Analysis Defense: CAPRISE consistently achieves a lower Attack Success Rate (ASR) than ADCPE across various embedding sizes, indicating superior obfuscation of internal embedding structures.
  • Efficiency: CAPRISE achieves a throughput of approximately 2,339 vectors per second, which is a 9x improvement over RemoteRAG's approximately 250-300 vectors per second for similar embedding sizes. The encryption overhead adds less than 19% to the embedding time.
  • Query Privacy: The DistanceDP mechanism ensures (ε, δ)-differential privacy for query embeddings, protecting against query analysis attacks.

Limitations and Future Work

  • Parameter Calibration: The encryption parameter β in CAPRISE and the perturbation range in DistanceDP are crucial for balancing privacy and retrieval accuracy. These parameters may need dataset-specific calibration, and the paper suggests future work on developing adaptive parameter selection strategies.
  • Trade-off Management: The paper acknowledges the inherent trade-off between privacy and retrieval accuracy. A larger perturbation radius for DP enhances privacy but can increase retrieval noise and computational cost. Future research could focus on systematically studying and optimizing this trade-off.

Summary updated

Abstract

Retrieval-Augmented Generation (RAG) has emerged as a key technique for enhancing response quality of large language models (LLMs) without incurring high computational cost. It works by retrieving knowledge and fact from external databases, augmenting the prompt with the retrieved data, and enabling the LLM to generate more accurate responses. In traditional architectures, RAG services are provided by a single entity that hosts the dataset and issues queries within a trusted local environment. However, individuals or small organizations often lack the resources to maintain data storage servers, leading them to rely on outsourced, cloud-based storage for scalability. This dependence on untrusted third-party services introduces significant privacy risks, particularly when handling private and sensitive data. Embedding-based retrieval mechanisms, commonly used in RAG systems, are especially vulnerable to privacy leakage such as vector-to-text reconstruction attacks and structural leakage via vector analysis. Several privacy-preserving RAG techniques have been proposed to address such vulnerabilities; however, most existing approaches rely on partially homomorphic encryption, which incurs substantial computational overhead and limits their practicality in real-world deployments.To address these challenges, we propose an efficient privacy-preserving RAG framework (ppRAG) tailored for untrusted cloud environments that defends against vector-to-text attack, vector analysis, and query analysis. At its core, we propose Conditional Approximate Distance-Comparison-Preserving Symmetric Encryption (CAPRISE) that encrypts embeddings while still allowing the cloud to compute similarity between an encrypted query embedding and the encrypted database embeddings. CAPRISE preserves only the relative distance ordering between the encrypted query and each encrypted database embedding, without exposing inter-database distances, thereby enhancing both privacy and efficiency. To further mitigate query analysis risks, we introduce differential privacy by perturbing the query embedding prior to encryption, preventing the cloud from inferring sensitive patterns from query frequency. Experimental results show that ppRAG achieves efficient processing throughput, high retrieval accuracy, strong privacy guarantees, making it a practical solution for resource-constrained users seeking secure, cloud-augmented LLMs.
BibTeX
@inproceedings{ye2025efficient,
  author = {Huanyi Ye and Jiale Guo and Ziyao Liu and Kwok-Yan Lam},
  title = {{Efficient Privacy-Preserving Retrieval Augmented Generation with Distance-Preserving Encryption}},
  booktitle = {FLLM},
  year = {2025},
  url = {https://openreview.net/forum?id=GErc99W42d},
}
Figure