P$^2$RAG: Efficient Privacy-Preserving RAG Service Supporting Arbitrary Top-$k$ Retrieval

P2RAG 기술 요약: 임의의 Top-k 검색을 지원하는 효율적인 개인정보 보호 RAG 서비스

문제 제기
검색 증강 생성 (RAG) 은 대규모 언어 모델 (LLM) 이 외부 지식을 활용할 수 있게 하지만, RAG 서비스를 아웃소싱하면 데이터 소유자 (전용 데이터베이스가 노출됨) 와 사용자 (프롬프트가 공개됨) 모두에게 심각한 개인정보 보호 위험이 발생합니다. 기존 개인정보 보호 RAG(PP-RAG) 시스템은 일반적으로 문제를 안전한 Top-k 검색 작업으로 규정하며, 안전한 정렬 또는 안전한 k-근접 이웃 (k-ANN) 기술에 의존합니다. 그러나 이러한 시스템은 다음과 같은 치명적인 한계를 안고 있습니다:

1. 비유연성: 검색 매개변수 $k$에 대한 임의적이거나 동적인 조정을 지원하지 못하는 경우가 많습니다.
2. 효율성 저하: $k$가 증가함에 따라 성능이 현저히 저하됩니다. 이는 금융, 법률, 의료 분야의 현대적 응용 프로그램과 긴 컨텍스트 LLM 이 최적의 정확도를 달성하기 위해 종종 100~150 이상과 같은 큰 $k$값을 요구하기 때문에 주요 병목 현상이 됩니다.
3. 보안 격차: 일부 기존 접근 방식은 새로운 보안 문제를 제기하거나 악의적인 사용자에게 대한 정보 유출을 엄격하게 제한하지 못합니다.

방법론
저자들은 임의의 Top-k 검색을 효율적으로 지원하도록 설계된 개인정보 보호 RAG 서비스인 P2RAG를 제안합니다. 이 시스템은 서버가 반정직 (honest-but-curious) 이며 비공모 (non-colluding) 인 두 서버 모델에서 작동합니다.

• 시스템 아키텍처:

  • 데이터 소유자: 암호화된 데이터베이스를 두 서버에 아웃소싱합니다. 데이터베이스는 $N$개의 문서 임베딩으로 구성되며, 소수 필드 (prime field) 상의 Shamir 비밀 공유를 사용하여 두 서버 간에 비밀 공유됩니다.
  • 사용자: 두 서버 간에 비밀 공유된 프롬프트 임베딩을 제출합니다.
  • 위협 모델: 서버는 프로토콜을 따르지만 데이터를 추론하려 할 수 있습니다. 사용자는 악의적으로 모델링되어 정보를 추출하기 위해 프로토콜에서 벗어날 수 있습니다. 데이터 소유자는 정직한 것으로 가정합니다.

• 핵심 혁신: 상호작용 이분법 vs 정렬
  기존 시스템이 모든 후보 문서를 정렬하는 것 (안전한 프로토콜에서 계산 비용이 많이 드는 작업) 과 달리, P2RAG는 정렬을 전혀 수행하지 않습니다. 대신, Top-$k$ 집합을 정의하는 거리 임계값 ($d_k$) 을 결정하기 위해 상호작용 이분법을 사용합니다.

  1. 거리 계산: 서버는 Beaver triple 을 사용하여 사용자의 프롬프트와 모든 문서 임베딩 간의 비밀 공유된 코사인 거리 (점곱으로 근사됨) 를 계산합니다.
  2. 이분법 반복: 사용자와 서버는 거리 임계값을 좁히기 위해 상호작용합니다. 각 반복에서 사용자는 임계값 $d_k$를 지정합니다. 서버는 **분산 비교 함수 (DCFs)**를 사용하여 $d_k$보다 거리가 짧은 문서의 수를 셉니다.
  3. 임계값 선택: 사용자는 반환된 개수를 기반으로 $d_k$를 업데이트하여 임계값 내의 문서 수가 목표 $k$에 가까워질 때까지 반복합니다.
  4. 결과 검색: 임계값이 결정되면 서버는 임계값에 해당하는 문서를 나타내는 비밀 공유된 이진 벡터를 생성합니다. 사용자는 단일 서버 개인 정보 검색 (PIR) 을 사용하여 이러한 문서의 인덱스를 검색합니다.

• 보안 메커니즘:

  • 개인정보 보호: 비밀 공유를 통해 어느 서버도 데이터베이스나 프롬프트를 학습하지 못하도록 보장합니다.
  • 악의적 사용자에 대한 방어: 사용자가 과도한 정보를 추출하는 것을 방지하기 위해 P2RAG는 엄격한 제한을 부과합니다:
    • 이분법 반복 횟수를 제한하여 총 개수 유출을 $O(\log^2 N)$으로 제한합니다.
    • 최종 결과 집합 크기를 제한합니다.
    • 검증 메커니즘을 통해 사용자가 합의된 이진 벡터에 해당하는 인덱스만 검색하도록 하여 검색 과정의 조작을 방지합니다.

주요 기여

1. 임의의 Top-k 지원: P2RAG는 정렬 기반 접근 방식에서 발생하는 효율성 저하 없이 임의의 $k$값을 효율적으로 지원하는 최초의 시스템으로, 현대의 긴 컨텍스트 모델이 요구하는 대규모 $k$ 시나리오에 적합합니다.
2. 효율적인 프로토콜 설계: 안전한 정렬을 DCF 를 사용하는 상호작용 이분법으로 대체함으로써, 안전한 프로토콜의 주요 병목 현상인 비교 횟수를 크게 줄였습니다.
3. 강건한 보안: 시스템은 반정직 서버에 대해 데이터 소유자의 데이터베이스와 사용자의 프롬프트를 모두 보호합니다. 또한 악의적인 사용자에게 대한 정보 유출을 엄격하게 제한하기 위한 구체적인 제한 사항과 검증 단계를 도입했습니다.
4. 구현 및 평가: 저자들은 P2RAG 를 구현하고 Apache License 2.0 하에 코드를 공개했습니다.

실험 결과
저자들은 BEIR 데이터셋 (예: 약 171k 개의 문서를 가진 trec-covid) 과 합성 데이터셋을 사용하여 P2RAG 를 평가했습니다.

• 정확도: P2RAG 는 높은 계산 정확도를 달성합니다. $k'$가 16 에서 1024 로 변할 때 재현율 (Recall) 은 1.0 으로 유지되며, 관련성 점수는 검색된 문서가 일반적으로 프롬프트와 관련이 있음을 나타냅니다.
• 성능: P2RAG 는 최첨단 시스템인 PRAG 대비 상당한 속도 향상을 보여줍니다.
  • $k = 16$인 경우, P2RAG 는 3.78 배 더 빠릅니다.
  • 더 큰 $k$(예: $k=1024$) 의 경우, 속도 향상은 322 배까지 증가합니다.
  • 시스템은 문서 수 ($N$) 에 따라 선형적으로 확장되지만, 효율성 저하를 겪는 PRAG 와 달리 $k$가 증가함에 따라 상대적으로 더 빨라집니다.
• 통신: 서버 간 통신은 수백 메가바이트에 달할 수 있으나, 대역폭이 높은 데이터 센터 링크를 통해 관리 가능합니다. 사용자 - 서버 간 통신은 낮게 유지됩니다 (몇 개의 표준 이미지와 유사).

의의 및 주장
이 논문은 P2RAG 가 개인정보 보호 RAG 의 중요한 격차, 즉 대규모 $k$값을 효율적으로 처리하지 못하는 문제를 해결했다고 주장합니다. 저자들은 표준 비보안 RAG 가 더 간단하고 빠르지만, 데이터 개인정보 보호가 엄격한 요구 사항인 의료, 금융, 법률 서비스와 같은 고위험 분야에서는 P2RAG 가 필수적이라고 강조합니다. 이 시스템은 이러한 분야가 전용 데이터베이스나 사용자 쿼리의 기밀성을 훼손하지 않고도 (LLM 정확도를 향상시키는) 대규모 검색 집합을 활용할 수 있게 합니다. 저자들은 겸손하게도 이 시스템이 반정직 비공모 서버 가정에 의존하며, 개인정보 보호가 중요하지 않은 경우에는 표준 비보안 RAG 가 여전히 선택지라고 언급합니다.