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

문제 정의

현대의 시맨틱 검색(Semantic Search)과 검색 증강 생성(RAG)은 밀집 벡터 임베딩(Dense Vector Embeddings)에 의존합니다. 그러나 최근 연구에 따르면, 이러한 임베딩은 소스 텍스트로 높은 정밀도로 역전될 수 있음이 입증되었습니다(예: Vec2Text는 약 97%의 BLEU 점수 달성). 이는 치명적인 취약점을 생성합니다. 즉, 벡터 데이터베이스가 유출되면 그 밑에 있는 문서들이 사실상 노출되는 것입니다.

기존의 방어책은 두 가지 극단에 치우쳐 있으며, 둘 다 산업 규모의 배포에는 부적합합니다:

1. 완전 동형 암호(Fully Homomorphic Encryption, FHE): 암호학적으로는 견고하지만, 수백만 개의 문서를 검색하기에는 계산 비용이 너무 높습니다.
2. 차분 프라이버시(Differential Privacy, DP): 노이즈를 추가하면 의미 있는 프라이버시 보호를 제공하기 전에 검색 순위 품질이 크게 저하됩니다.

본 논문은 $10^6$개의 문서 규모에서 프라이버시, 검색 정확도, 그리고 지연 시간(Latency) 사이의 균형을 맞추는 중간 경로의 필요성을 다룹니다.

방법론

저자들은 정적인 문서 컬렉션과 동적인 사용자 쿼리를 다르게 취급하는 **비대칭 하이브로 아키텍처(Asymmetric Hybrid Architecture)**를 제안합니다. 이 시스템은 제한된 위협 모델(Restricted Threat Model) 하에서 작동합니다: 신뢰할 수 있는 클라이언트, 정직하지만 호기심 많은(Honest-but-curious) 서버, 그리고 비적응적 공격자(Secret Rotation에 대한 사전 지식 없이 기성 도구를 사용하는 공격자)를 상정합니다.

1. 문서 보호 (정적 측면)

문서 벡터는 암호화 대신 기하학적 변환을 통해 보호됩니다:

• SVD 절단(SVD Truncation): 중심화된 문서 코퍼스는 특이값 분해(SVD)를 사용하여 저차원 부분 공간($k = d/2$)으로 투영됩니다. 이 절단은 상대적 재구성 오차($\sigma_{rec}$)를 최소 0.10 이상으로 보장하도록 선택되었으며, 이는 정보 손실의 대리 지표 역할을 합니다.
• 비밀 회전(Secret Rotation): 절단된 벡터는 비밀스러운 Haar-uniform 무작위 직교 행렬 $R$에 의해 곱해집니다. 이 회전은 $R$을 보유하지 못한 공격자로부터 기저(Basis)의 방향을 숨깁니다.
• 공개 제품 양자화(Public Product Quantization, PQ): 클라이언트가 서버로 쿼리를 보내지 않고도 로컬에서 후보군을 필터링(Stage 1)할 수 있도록 회전된 공간에서 PQ 인덱스(Codebook + Codes)가 훈련됩니다. 저자들은 이 PQ 산물(Artifact)이 이웃 구조를 유출하는 "손실 압축된 뷰(Lossy compressed view)"임을 명시하며, 이를 노출된 채널로 간주합니다.

2. 쿼리 보호 (동적 측면)

쿼리는 암호학적으로 보호됩니다:

• CKKS 암호화: 클라이언트는 회전된 쿼리 벡터를 CKKS 동형 암호 스킴을 사용하여 암호화합니다.
• 암호문-평문(ct-pt) 재순위화: 서버는 암호화된 쿼리와 평문 상태의 회전된 문서 벡터 사이의 내적을 계산하여 짧게 추려진 후보군(예: 상위 40개)의 재순위화를 수행합니다.
• 최적화: 암호문-암호문(ct-ct) 곱셈을 피함으로써, 시스템은 비용이 많이 드는 재선형화(Relinearization) 단계를 생략할 수 있습니다. 이를 통해 서버는 서브 세컨드(Sub-second) 지연 시간 내에 유사도 점수를 계산할 수 있습니다.

3. 파라미터 선택

저자들은 수동 튜닝 대신, 보안 테이블(tc128)과 정확도 허용 범위를 충족하면서 지연 시간을 최소화하는 구성을 선택하기 위해 CKKS 파라미터(다항식 모듈러스 차수, 계수 모듈러스 체인, 스케일)에 대한 재현 가능한 오프라인 마이크로 벤치마크를 수행합니다.

주요 기여

이론적 측와:

• 보조정리 1 (Lemma 1): 본 논문은 이미지가 절단된 부분 공간에 제한된 모든 디코더에 대해 $L_2$ 재구성 오차의 타이트한 하한(Tight lower bound)을 증명합니다. 이는 투영을 통해 손실되는 정보를 공식적으로 정량화하지만, 저자들은 이것이 *투영 경계(Projection bound)*이지 일반적인 역전 보안 정리(Inversion-security theorem)는 아니라고 명시합니다.
• 경험적 가설 1 (Empirical Hypothesis 1): 저자들은 재구성 오차 대리 지표($\sigma_{rec}$)와 기성 역전 공격의 BLEU 점수 사이의 관계를 공식화하고, 이를 수치적으로 검증하여 관계를 입증했습니다.

경험적 및 엔지니어링 측면:

• 규모 평가: 다섯 가지 현대적 텍스트 인코더(multilingual-E5 및 BGE-M3 포함)를 사용하여 100만 개 문서 코퍼스(러시아어 위키피디아)에 대한 실험을 수행했습니다.
• 지연 시간: 시스템은 $10^6$개의 문서에 대해 엔드 투 엔드 쿼리 지연 시간을 1초 미만(p95 $\approx$ 370ms)으로 안정적으로 유지합니다.
• CKKS 최적화: 선택된 구성($N_{poly}=8192$, 특정 모듈러스 체인)은 동일한 보안 경계를 유지하면서 표준 TenSEAL 설정보다 1.7배 빠른 속도 향상을 제공합니다.
• 노이즈 제거 효과: 차원이 $d \ge 768$인 검색 훈련된 인코더의 경우, SVD 절단은 꼬리 부분의 특이 방향(Trailing singular directions)에 있는 노이즈를 필터링함으로써 오히려 랭킹 메트릭(Acc@1, NDCG)을 약간 개선하는 선형 디노이저(Linear denoiser) 역할을 합니다.

결과 및 보안 분석

본 논문은 의도된 위협 모델과 더 강력한 공격자 모두에 대해 시스템을 엄격하게 테스트합니다:

• 비적응적 공격자 대상: 제한된 모델(알려지지 않은 $R$, 기성 Vec2Text 사용) 하에서, 비밀 회전은 BLEU 점수를 노이즈 수준($\approx 0.007$)으로 낮추어 텍스트 복구를 효과적으로 방지합니다.
• 기지 평문 공격자(Known-Plaintext Attackers) 대상: 만약 공격자가 약 $k$(유지된 차원)개의 (원본 텍스트, 회전된 벡터) 쌍을 보유하고 있다면, 직교 프로크루스테스(Orthogonal Procrustes) 방법을 사용하여 비밀 회전 $R$을 복구할 수 있습니다. 일단 $R$이 알려지면, 보호 기능은 SVD 절단만 남게 됩니다.
• 참조 코퍼스 유출: 보호된 컬렉션이 공개되거나 유출된 참조 코퍼스와 겹치는 경우, 공격자는 복구된 회전을 사용하여 정확한 문단 조회를 수행할 수 있습니다.
• PQ 산물 유출: 공개 PQ 코드는 회전된 벡터와 약 95%의 코사인 유사성을 유지하며 대부분의 top-10 이웃을 보존합니다. 이는 PQ 산물이 구조적 정보를 유출하는 노출된 채널임을 확인시켜 줍니다.

인코더 의존성: "디노이징" 이점은 검색 훈련된 인코더에 국한됩니다. 컴팩트한 모델(예: e5-small)이나 패러프레이즈 증류 모델은 $k=d/2$ 절단 시 정확도 저하를 겪습니다.

의의 및 주장

본 논문은 배포 가능한 제품이나 시스템 엔지니어링 보고서라기보다 과학적 연구로서 자리매김합니다. 그 의의는 다음과 같습니다:

1. 경계 정의: 위협 모델을 명확히 한정합니다. 저자들은 쿼리 기밀성(via CKKS)은 암호학적이지만, 문서 보호(via S/SVD + Secret Rotation)는 경험적 난독화(Empirical obfuscation)라고 주장합니다. 즉, 문서 레이어가 적응적 또는 기지 평문 공격자에게 암호학적으로 안전하다고 주장하지 않습니다.
2. 트레이드오프 정량화: 프라이버시, 정확도, 지연 시간 사이의 균형 잡힌 운영 지점을 제시합니다. 또한 특정 유형의 인코더의 경우, 프라이버시를 보존하는 절단이 우연히 검색 품질을 개선할 수 있음을 보여줍니다.
3. 재현성: 결정론적인 암호 파라미터 선택 방법을 제공하며 모든 스크립트와 구성을 공개합니다.

저자들이 인정한 한계점:

• 문서 프라이버시는 암호학적이지 않으며, 기지 평문 또는 적응적 공격에 취술합니다.
• 액세스 패턴(어떤 문서가 재순위화되는지)과 PQ 코드는 노출됩니다.
• 시스템은 정확도를 유지하기 위해 특정 클래스의 인코더($d \ge 768$, 검색 훈련됨)에 의존합니다.
• 주요 미결 과제는 회전된 공간에 특화되어 훈련된 **엔드 투 엔드 학습 디코더(End-to-end learned decoder)**에 대한 강건성이며, 본 연구에서는 이에 대한 완전한 평가가 이루어지지 않았습니다.

결론적으로, 이 논문은 시맨틱 검색을 위한 고성능 하이브리드 접근 방식을 제시하며, 프라이버시 부담을 쿼리 측(암호학적)과 문서 측(기하학적 난독화)으로 분산시키고, 기하학적 난독화 레이어의 실패 모드를 투명하게 정량화합니다.