PaperlayerView exact revision on arXiv

Source-linked AI summary

FRAG: Toward Federated Vector Database Management for Collaborative and Secure Retrieval-Augmented Generation

Dongfang Zhao

arXiv:2410.13272v1cs.CRcs.DB

TL;DR

FRAG addresses the challenge of collaborative RAG when mutually distrusted parties cannot share raw vector data or queries and existing privacy methods impose substantial overhead. It combines single-key homomorphic encryption with multiplicative caching for encrypted federated ANN search, and reports IND-CPA security proofs plus scalability and efficiency evaluations. Its scope includes a semi-honest model without a non-collusion assumption.

  • Problem

    Mutually distrusted organizations need collaborative ANN retrieval for RAG without exposing their data or queries, while existing MPC and homomorphic-encryption approaches can incur high overhead and complex key management.

    Source: §1.2 · pp. 1–2

  • Method

    FRAG combines Single-Key Homomorphic Encryption for encrypted federated vector operations with Multiplicative Caching for reusable encrypted intermediate values.

    Source: §5.1 · p. 5, §9 · p. 12

  • Results

    FRAG’s SK-MHE and Multiplicative Caching protocols are stated to be IND-CPA secure assuming the underlying homomorphic encryption is IND-CPA secure.

    Source: §5.3 · p. 6, §6.3 · p. 8

  • Takeaways & Limitations

    FRAG provides a framework for privacy-preserving collaborative ANN search across distributed encrypted vector databases while targeting efficiency comparable to centralized RAG.

    Source: §1.4 · p. 2, §9 · p. 12

    The security model is semi-honest and explicitly does not assume non-collusion among parties.

    Source: §3.2 · p. 4

Abstract

from arXiv · show

This paper introduces \textit{Federated Retrieval-Augmented Generation (FRAG)}, a novel database management paradigm tailored for the growing needs of retrieval-augmented generation (RAG) systems, which are increasingly powered by large-language models (LLMs). FRAG enables mutually-distrusted parties to collaboratively perform Approximate $k$-Nearest Neighbor (ANN) searches on encrypted query vectors and encrypted data stored in distributed vector databases, all while ensuring that no party can gain any knowledge about the queries or data of others. Achieving this paradigm presents two key challenges: (i) ensuring strong security guarantees, such as Indistinguishability under Chosen-Plaintext Attack (IND-CPA), under practical assumptions (e.g., we avoid overly optimistic assumptions like non-collusion among parties); and (ii) maintaining performance overheads comparable to traditional, non-federated RAG systems. To address these challenges, FRAG employs a single-key homomorphic encryption protocol that simplifies key management across mutually-distrusted parties. Additionally, FRAG introduces a \textit{multiplicative caching} technique to efficiently encrypt floating-point numbers, significantly improving computational performance in large-scale federated environments. We provide a rigorous security proof using standard cryptographic reductions and demonstrate the practical scalability and efficiency of FRAG through extensive experiments on both benchmark and real-world datasets.

1 Introduction

RAG systems use vector databases to retrieve external knowledge for LLM responses, but collaborative retrieval is constrained by privacy and regulatory concerns. FRAG addresses this gap with encrypted federated ANN search, simplified key management, multiplicative caching, and reported efficiency close to centralized RAG.

1.1 Background

  • RAG combines LLM generation with vector-embedding retrieval to produce more informed and contextually rich responses.Source: §1.1 · p. 1

1.2 Motivation

  • Privacy regulations and proprietary data prevent organizations from freely sharing raw data despite potential benefits from collaboration.Source: §1.2 · pp. 1–2
  • Traditional MPC and homomorphic encryption can impose high computational and key-management overheads in real-time federated RAG.Source: §1.2 · p. 2

1.3 Proposed Work

  • FRAG enables mutually-distrusted parties to perform collaborative ANN searches over encrypted queries and distributed vector databases without exposing data or queries.Source: §1.3 · p. 2
  • SK-MHE uses one shared encryption key to simplify key exchanges while supporting secure encrypted vector operations and IND-CPA security.Source: §1.3 · p. 2
  • Multiplicative Caching reuses precomputed encrypted intermediate values to reduce homomorphic-operation costs in large-scale, real-time ANN searches.Source: §1.3 · p. 2

1.4 Contributions

  • The paper reports rigorous security analysis and experiments showing privacy-preserving performance comparable to centralized RAG systems.Source: §1.4 · p. 2

2 Related Work

Related work covers vector databases, federated retrieval, secure aggregation, encryption, secret sharing, MPC, and provable security. FRAG is positioned as addressing privacy and performance limitations that remain in federated vector search.

2.1 Vector Databases

  • Vector database systems support large-scale ANN search, but many lack flexible handling of non-vector queries or mixed workloads.Source: §2.1 · pp. 2–3
  • Existing vector-search solutions often lack efficient privacy mechanisms for federated settings where cryptographic overhead matters for real-time systems.Source: §2.1 · p. 3

2.2 Federated Learning and Retrieval

  • Federated learning and retrieval keep data local or avoid raw-data sharing, but prior methods generally do not address vector databases in RAG systems.Source: §2.2 · p. 3

2.3 Secure Aggregation and Poisoning Attacks

  • Secure aggregation literature commonly uses semi-honest models, while related work also studies malicious participants and poisoning attacks.Source: §2.3 · p. 3

2.4 Homomorphic Encryption and Secret Sharing

  • Homomorphic encryption enables computation on encrypted data, whereas threshold secret sharing distributes reconstruction authority across multiple shares.Source: §2.4 · p. 3

2.5 Multi-Party Computation

  • MPC supports private joint computation but can face scalability and performance limitations for high-dimensional ANN search.Source: §2.5 · p. 3

2.6 Provable Security

  • CPA security formalizes resistance to distinguishing new ciphertexts from chosen plaintext-ciphertext queries, with negligible adversarial success probability.Source: §2.6 · p. 3

3 Problem Statement

FRAG targets ANN search across encrypted, distributed vector databases owned by mutually distrusting parties. Its requirements combine privacy against semi-honest and colluding parties with IND-CPA security and performance comparable to plaintext search.

3.1 System Model

  • Each of n mutually distrusting parties maintains an encrypted database of high-dimensional vectors and encrypted query vectors.Source: §3.1 · pp. 3–4

3.2 Threat Model

  • Security must hold in a semi-honest threat model where parties follow the protocol but may inspect received information.Source: §3.2 · p. 4
  • The model does not assume non-collusion, so guarantees must remain valid when subsets of parties collude.Source: §3.2 · p. 4

3.3 Research Problem

  • The system must search across all encrypted databases and return k nearest matches without revealing parties’ vectors or queries beyond the final result.Source: §3.3 · p. 4
  • FRAG must minimize encryption, query-processing, communication, and aggregation overhead to approach centralized plaintext ANN performance.Source: §3.3 · p. 4, §3.4 · p. 4

3.4 Technical Challenges

  • The technical challenges are efficient encrypted homomorphic operations, scalable key management, and performance optimization.Source: §3.4 · p. 4

4 FRAG Overview

FRAG distributes encrypted ANN retrieval across local vector databases using SK-MHE and Multiplicative Caching. Encrypted queries and results remain protected through distribution, local search, aggregation, and final decryption before LLM integration.

4.1 System Architecture

  • Each FRAG node stores encrypted high-dimensional embeddings in a local vector database for federated retrieval.Source: §4.1 · p. 4
  • SK-MHE lets nodes compute encrypted dot products and distances with a shared key, avoiding decryption during collaborative retrieval.Source: §4.1 · p. 5
  • Multiplicative Caching precomputes encrypted scalar values so nodes can accelerate repeated encrypted scalar and vector multiplications.Source: §4.1 · p. 5

4.2 Query Workflow

  • Encrypted queries are submitted and distributed to nodes, which retrieve relevant encrypted vectors and perform local ANN searches.Source: §4.2 · p. 5
  • Cached encrypted scalar products reduce repeated encryptions during federated ANN computation.Source: §4.2 · p. 5
  • Nodes transmit encrypted local results to an aggregator, which combines them into an encrypted response for decryption by the querying user.Source: §4.2 · p. 5
  • After decryption, retrieved results can be supplied to LLMs to generate context-aware augmented responses.Source: §4.2 · p. 5

5 Single-Key Multiparty Homomorphic Encryption (SK-MHE)

SK-MHE encrypts and splits vector ciphertexts across mutually distrusted parties, who compute and aggregate homomorphically before the querying party decrypts. The section establishes correctness, IND-CPA security under an IND-CPA-secure underlying scheme, and O(mn) computational and communication complexity.

5.1 Protocol Description

  • SK-MHE encrypts each data vector element, splits ciphertexts into shares distributed to parties, and keeps homomorphic computation and aggregation in the encrypted domain.The querying party supplies an encrypted query; parties compute on their shares, aggregate encrypted results, and the querying party decrypts with the private key.Source: §5.1 · p. 5

5.2 Correctness Analysis

  • The decrypted result equals the correct plaintext computation, with homomorphic products producing encrypted vi·qi terms whose aggregate is decrypted as the sum over all elements.Correctness follows because homomorphic operations preserve the computation and share aggregation reflects the corresponding operations on the original data.Source: §5.2 · p. 6

5.3 Security Analysis

  • The protocol is IND-CPA secure assuming the underlying homomorphic encryption scheme is IND-CPA secure.The proof reduces any non-negligible distinguishing advantage against SK-MHE to breaking the underlying scheme’s IND-CPA security.Source: §5.3 · pp. 6–7

5.4 Complexity Analysis

  • The protocol has total time complexity O(mn), exchanges O(mn) messages, and requires two communication rounds.Encryption is O(m), splitting and homomorphic operations are O(mn), aggregation is O(n), and decryption is O(1).Source: §5.4 · p. 7

6 Multiplicative Caching

The Multiplicative Caching Protocol precomputes encrypted scaling factors for vector operations, then performs encrypted products and aggregation while preserving correctness, IND-CPA security, and linear complexity.

6.1 Protocol Description

  • Precomputed encrypted scaling factors are reused during query processing to reduce redundant homomorphic computation for floating-point vector operations.For each v_i, cache[i] = Enc(Δ_i) is created during preprocessing and combined with encrypted data and query values during the query phase.Source: §6.1 · p. 7

6.2 Correctness Analysis

  • The protocol returns the exact scalar product of the original plaintext vectors after homomorphic aggregation and normalization by the scaling factors.The cached factors preserve precision while the final decrypted result remains mathematically consistent with the expected scalar product.Source: §6.2 · p. 8

6.3 Security Analysis

  • The protocol is IND-CPA secure assuming the underlying homomorphic encryption scheme is IND-CPA secure.A distinguisher with non-negligible advantage would yield a reduction breaking the underlying scheme, contradicting its security assumption.Source: §6.3 · p. 8

6.4 Complexity Analysis

  • The protocol has total time complexity O(m), with O(m) messages exchanged across two communication rounds.Encryption, homomorphic operations, and aggregation each take O(m) over m vector elements.Source: §6.4 · pp. 8–9

7 System Implementation

The implementation combines SK-MHE and multiplicative caching within FedML-based distributed infrastructure, using TenSEAL, CKKS, MPI, and Redis for encrypted federated ANN retrieval.

7.1 SK-MHE Implementation

  • SK-MHE enables encrypted ANN searches across mutually distrustful nodes, with FedML and MPI supporting distributed communication and secure aggregation.TenSEAL and CKKS implement encrypted vector multiplication and addition, while only the query owner decrypts the final aggregated result.Source: §7.1 · p. 9

7.2 Multiplicative Caching Implementation

  • Redis stores encrypted scalar values for reuse, reducing online computation by retrieving precomputed values during encrypted query processing.Redis clustering distributes cached values across nodes, and TTL-based invalidation removes stale entries in dynamic environments.Source: §7.2 · p. 9

7.3 Integration into FRAG

  • The integrated FRAG pipeline broadcasts encrypted queries, performs local homomorphic operations, aggregates encrypted responses, and reveals the k nearest neighbors only after decryption by the querying node.Nodes collaborate without exposing plaintext datasets or query vectors, while the modular design supports independently optimized SK-MHE and MC components.Source: §7.3 · pp. 9–10

8 Evaluation

FRAG was evaluated on distributed vector-search infrastructure, with experiments covering setup, SK-MHE overhead, and multiplicative-caching performance. Results show competitive secure computation and MC speedups across real-world datasets, while exposing scaling trade-offs.

8.1 Experimental Setup

  • The experiments used 10 distributed machines, FAISS databases, 1 million 768-dimensional embeddings, and encrypted storage with SK-MHE.Docker and Kubernetes supported containerization, orchestration, and node scalability.Source: §8.1 · p. 10

8.2 SK-MHE Performance

  • SK-MHE primitives run faster on MNIST and FMNIST, whereas CIFAR-10 and SVHN take longer because encryption and verification become more complex.The measured primitives are Split, Merge, and Verify.Source: §8.2 · p. 10, Figure 2 · p. 11
  • SK-MHE adds overhead, particularly during aggregation, but remains competitive with the non-encrypted FedAvg baseline across MNIST, FMNIST, CIFAR-10, and SVHN.The comparison measures distribution, aggregation, and baseline times in seconds.Source: §8.2 · p. 10, Figure 3 · p. 11

8.3 Performance of Multiplicative Caching (MC)

  • MC caching scales with thread count until improvements plateau beyond 32 threads, where context-switching overhead causes degradation.This evaluation cached 200,000 plaintexts using 1 to 96 threads.Source: §8.3 · p. 11, Figure 5 · p. 11
  • MC’s per-message time remains relatively constant as plaintext messages increase from 40 to 120, indicating overhead is primarily independent of message count.The pivot-scaling experiment separately found computational time increases as cached pivots grow from 4 to 64.Source: §8.3 · pp. 11–12, Figure 6 · p. 12
  • MC outperformed CKKS and non-caching approaches on Covid-19, Bitcoin, and Human Gene #38, achieving dataset-dependent speedups from 1.46× to 2.61×.The reported Human Gene #38 speedup was 1.46×, while Covid-19 reached 2.61× and Bitcoin 2.60×.Source: §8.3 · p. 12, Figure 8 · p. 12

9 Conclusion

FRAG enables secure and efficient distributed approximate k-nearest-neighbor searches over encrypted vector databases. Its SK-MHE and MC protocols support privacy-preserving collaboration and reduce computation for large-scale real-world datasets.

9 Conclusion

  • FRAG enables secure distributed approximate k-nearest-neighbor searches over encrypted vector databases without exposing sensitive data.The system targets federated environments with mutually distrusted parties.Source: §9 · p. 12
  • SK-MHE simplifies key management while supporting secure computation over encrypted vectors, and MC caches frequently used scalar values to reduce computation time.The conclusion reports practical feasibility on synthetic and real-world datasets including Covid-19, Bitcoin, and Human Gene #38.Source: §9 · p. 12

Related papers

Loading 2410.13272v1…