기술 요약: SHARD – 정렬 저항성을 갖춘 프라이빗 밀집 검색을 위한 셀 기반 키잉 잔차 분할 (Cell-Keyed Residual Splitting)

1. 문제 정의

밀집 임베딩(Dense embeddings)은 현대적인 시맨틱 검색과 검색 증강 생성(RAG)의 기초입니다. 그러나 최근의 몇 가지 공격 사례가 보여주듯, 벡터 저장소가 유출되면 그 밑바탕이 되는 텍스트까지 사실상 노출되는 것과 다름없습니다. 이러한 공격들은 퓨샷 정렬(few-shot alignment), 제로샷 역전(zero-shot inversion), 그리고 비지도 교차 공간 변환(unsupervised cross-space translation)을 포함합니다. 이 공격들은 기존의 경량 방어 기법이 가진 근본적인 약점인, 보호된 벡터 저장소가 **단일 전역 기하 구조(single global geometry)**를 가진다는 점을 악용합니다.

현재의 방어 기법들은 대개 "전역 선형(global-linear)" 접근 방식에 의존합니다. 즉, SVD 절단을 통해 임베딩을 압축하고, 단일한 비밀 직교 회전을 적용하며, 인덱싱을 위해 곱 양자화(Product Quantization, PQ)를 사용하는 방식입니다. 논문은 이 방식이 취약하다고 주장하는데, 왜냐하면 어떤 단일 전역 기하 구조라도 알려진 참조 공간으로 정렬될 수 있기 때문입니다. 공격자가 직교 프로크루스테스(Orthogonal Procrustes)를 통해 약 $k = d/2$개의 알려진 평문 쌍을 사용하여 비밀 회전 값을 복구하면, 보호 체계는 무너지고 텍스트의 거의 정확한 복구가 가능해집니다. 나아가, 표준 방어 기법들은 트레이드오프에 직면합니다. 차분 프라이버시(Differential Privacy, DP)는 의미 있는 수준의 프라이버시를 제공하기 전에 검색 순위(ranking)의 효용성을 파괴하며, 동형 암호(Fully Homomorphic Encryption, FHE)는 대규모 top-$k$ 검색을 수행하기에는 계산 비용이 너무 높습니다.

2. 방법론: Shard 구성

본 논문은 왜곡을 가리는 대신 "전역 정렬의 약한 축(weak axis)"을 제거하도록 설계된 검색 보존 임베딩 변환인 Shard를 소개합니다. Shard는 임베딩 공간을 두 가지 구성 요소로 분할하고 각 요소에 서로 다른 보호를 적용합니다.

1. 공개 접두사 ($u$): 임베딩은 중심화(centered) 및 회전됩니다. 상위 $d_{pub}$개의 주성분(고분산 방향)이 짧은 공개 접두사를 형성합니다. 이는 공용 PQ 인덱스를 통한 1단계 조기 검색(Stage-1 ANN)에 사용됩니다.
2. 프라이빗 잔차 ($r$): 나머지 차원($d_{priv} = d - d_{pub}$)은 프라이빗 잔차를 형성합니다.
   • 셀 기반 키잉 분할 (Cell-Keyed Splitting): 잔차 공간은 $C$개의 거친 셀(공개 접두사 $u$에 의해 정의됨)로 분할됩니다.
   • 로컬 키 (Local Keys): 각 셀 $c$에는 고유한 비밀 직교 키 $H_c$(Householder 반사의 곱)가 할당됩니다.
   • 저장: 서버는 접두사 $u_i$와 키잉된 잔차 샤드 $z_i = H_{c(i)} r_i$를 저장합니다.
   • 쿼리 처리:
     • 1단계: 클라이언트는 공개 접두사 $u_q$를 사용하여 로컬에서 후보군 리스트를 추출합니다.
     • 2단계 (재정렬/Reranking): 각 후보에 대해, 클라이언트는 쿼리 잔차 $r_q$를 CKKS(동형 암호) 하에서 $H_{c(i)} r_q$로 암호화합니다. 서버는 암호문-평문 모드에서 내적 $\langle H_{c(i)} r_q, H_i \rangle$를 계산합니다.
     • 정확한 복구: $H_c$는 직교 행렬이므로, 키가 상쇄됩니다: $\langle H_c r_q, H_c r_i \rangle = \langle r_q, r_i \rangle$. 서버는 원래 잔차의 정확한 내적 값을 갖는 암호화된 점수를 반환합니다.

파라미터 $C$는 전역 베이스라인($C=1$, 하나의 전역 키)과 문서당 마이크로 키($C=N$, 문서당 하나의 키) 사이를 보간합니다.

3. 주요 기여

본 논문은 이전 연구(특히 저자들의 이전 전역-선형 하이브리드 시스템)와 비교하여 다음과 같은 구체적인 기여를 합니다.

• 셀 기반 키잉 잔차 분할: 단일 전역 기하 구조를 $C$개의 로컬 키 기반 부분 공간으로 대체하여, 단일 정렬 공격이 전체 저장소를 복구하는 것을 방지하는 구성을 제시합니다.
• 전차원 재정렬 (Full-Dimensional Reranking): 차원 축소된 공간에서 재정렬을 수행하는 SVD 절단 베이스라인과 달리, Shard는 전차원 공간(접두사 + 잔차)에서 재정렬을 수행하여 절단으로 인해 손실된 원본 검색 품질을 복구합니다.
• 확장 가능한 정렬 저항성: 본 논문은 확산된 알려진 평문 정렬 공격의 비용이 약 $C$ 배만큼 증가한다는 스케일링 법칙을 입증합니다. 네이티브 프레임을 복구하는 데 필요한 앵커(anchor)의 수는 $O(d)$가 아닌 $O(C \cdot d_{priv})$가 됩니다.
• 공개 정보 유출 감소: 절반의 공간 대신 짧은 접두사($d_{pub} \ll d$)만을 노출함으로써, 공개 인덱스가 누설하는 이웃 구조를 현저히 줄입니다.
• 공격 인지적 평가: Shard를 더 강력한 공격자 군(learned-linear, 비선형 MLP, 비지도 공격자)에 대해 평가하고, 이를 왜곡 기반 방어(DP 노이즈)와 비교하여 키잉(keying)이 노이즈보다 우수한 저항성을 제공함을 입증했습니다.

4. 실험 결과

BEIR, MIRACL, 그리고 100만 개의 문서로 구성된 러시아어 위키피디아 코퍼스 상의 5가지 인코더(multilingual-E5 및 BGE-M3 포함)에서 추출된 캐시된 임베딩을 대상으로 실험을 진행했습니다.

• 효용성 (nDCG@10): Shard는 원본 공간의 랭킹 상한선(ceiling)을 복구합니다. SVD 절단이 nDCG@10에서 2~8 포인트의 하락을 유발했던 BEIR 태스크에서, Shard는 공개 채널의 너비를 1/4에서 1/2 수준으로 줄이면서도 원본 베이스라인과 일치하는 성능을 보였습니다 (예: 원본 0.637 vs Shard 0.638).
• 정렬 저항성:
  • 전역 베이스라인: 약 200개의 앵커로 복구됨 (d=384 기준).
  • Shard ($C=64$): 약 25,600개의 앵커 필요.
  • Shard ($C=256$): 약 102,400개의 앵커 필요 (중앙값).
  • 공격자 강건성: 학습된 선형(learned-linear), 비선형 MLP, 비지도 공격자는 표준 직교 프로크루스테스 공격보다 더 나은 성능을 보이지 못했으며, 단일 셀에 대한 $d_{priv}$ 앵커 임계값을 넘어서지 못했습니다.
• 공개 인덱스 유출: 공개 접두사는 베이스라인보다 훨씬 적은 이웃 구조를 드러냈습니다. $d/4$ 접두사에 대해, NN-overlap@10은 0.76(베이스라인)에서 0.55(Shard)로 감소했습니다.
• 마이크로 키 한계: $C=N$(문서당 키)일 때, 잔차 그래프 유출은 0.00으로 떨어지며, 시스템은 연결 불가능(unlinkable) 상태가 됩니다 (re-keying AUC $\approx 0.5$).
• DP 노이즈와의 비교: 왜곡 인식 DP 방어는 $\sigma=0$(노이즈 없음)일 때만 Shard의 효용성과 일치했으며, 이때 탈익명화(de-anonymization)는 100%였습니다. 탈익명화를 줄이기 위해 노이즈를 추가하면 효용성이 Shard의 성능 아래로 떨어졌습니다. Shard는 0%의 탈익명화율을 달성하면서도 높은 효용성을 유지했습니다.
• 관찰된 한계점:
  • 표적 공격 (Targeted Attacks): 특정 피해자의 셀에 앵커를 집중시키는 표적 공격자의 경우, $C$와 관계없이 약 $d_{priv}$개의 앵커만 있으면 됩니다.
  • 중첩 참조 (Overlap Reference): 공격자가 중첩되는 참조 코퍼스를 보유하고 있다면, 공개 접두사(비록 단일 전역 키로 키잉되었더라도)를 통해 탈익명화가 가능합니다.
  • 액세스 패턴: 베이스라인과 마찬가지로, Shard는 액세스 패턴(어떤 문서가 재정렬되는지)을 숨기지 않습니다.

5. 의의 및 주장

본 논문은 Shard를 **공격 인지적 기하 방어(attack-aware geometric defense)**로 규정하며, 이것이 저장된 문서들에 대한 암호학적 보증(cryptographic guarantee)이 아님을 명시적으로 밝힙니다.

• 핵심 성과: Shard는 "단일 전역 기하 구조"의 취약점을 제거함으로써 프라이버시와 정확도 사이의 트레이드오프를 변화시킵니다. 이를 통해 (확산된 공격자에게는 정렬을 계산 비용이 많이 들게 만들면서) 정확한 전차원 재정렬(효용성 보존)을 가능하게 합니다.
• 설계 철학: 이 연구는 임베딩 프라이버시의 목표를 왜곡 대리물($\sigma_{rec}$)을 최적화하는 것에서 특정 공격 표면(정렬 및 인덱스 유출)에 대응하여 하드닝(hardening)하는 것으로 전환합니다.
• 제한적 주장: 저자들은 Shard가 하지 못하는 것에 대해 명확히 밝힙니다:
  • 단일 셀에 집중하는 표적 공격으로부터 보호하지 못합니다.
  • 공개 접두사 키가 복구될 경우 중첩된 참조 코퍼스를 통한 탈익명화를 방지하지 못합니다.
  • 액세스 패턴을 숨기지 못합니다.
  • 비밀 회전은 암호학적 프리미티브가 아니라 경험적인 난독화 계층입니다.

결론적으로, Shard는 $C$라는 파라미터를 통해 튜닝 가능한 변환 패밀리를 제공하며, 이는 액세스 패턴과 참조 중첩 문제를 처리하기 위해 다른 프리미티브(예: PIR)와 결합되어 사용될 때 현대적인 정렬 공격에 대한 실질적이고 측정 가능한 방어책을 제공합니다.