SHARD: 정렬 저항성을 갖춘 개인정보 보호형 밀집 검색을 위한 셀 키 기반 잔차 분할

밀집 임베딩 (Dense embeddings)은 의미론적 검색 (Semantic search)과 RAG의 근간을 이루지만, 벡터 저장소 (Vector store)가 유출될 경우 이를 보유한 누구에게나 기초 텍스트의 상당 부분이 노출됩니다. 이를 가능하게 하는 공격들 (Few-shot alignment, Zero-shot inversion, Unsupervised cross-space translation)은 한 가지 공통된 약점을 공유합니다. 즉, 보호된 저장소가 알려진 기하학적 구조로 정렬될 수 있는 단일한 전역 기하학 (Single global geometry)을 가진다는 점입니다. 일반적인 경량 방어 기법인 비밀 전역 회전 (Secret global rotation)도 예외는 아닙니다. 공격자가 알려진 쌍 (Known pairs)을 통해 서브스페이스 차원 (Subspace dimension) 정도의 정보를 확보하면, 직교 프로크루스테스 (Orthogonal Procrustes)를 통해 이를 복구할 수 있습니다.

우리는 이러한 취약한 축을 제거하는, 검색 성능을 보존하는 임베딩 변환 방식인 Shard를 소개합니다. 중심화된 임베딩 (Centred embedding)은 짧은 공개 접두사 (Public prefix, 1단계 검색용)와 별도의 비밀 키(Secret keys) 하에 C개의 셀(Cells)로 분할된 개인 잔차 (Private residual)로 나뉩니다. 잔차는 CKKS 하에서 재순위화 (Reranked)되며, 이때 키가 상쇄되어 내적 (Inner product) 값이 정확하게 유지됩니다. 단일 파라미터 C를 통해, Shard는 기존의 전역 선형 베이스라인 (Global-linear baseline, C=1)부터 문서별 마이크로 키 (Per-document micro-keys, C=N) 방식까지 설계를 조절할 수 있습니다.

재순위화가 전체 차원 (Full-dimensional)에서 이루어지기 때문에, Shard는 절반 크기의 SVD 절단 (Half-SVD truncation)이 포기하게 되는 원시 공간의 nDCG@10 성능을 그대로 반환합니다. 또한 잔차가 셀 단위로 로컬 키가 지정되어 있기 때문에, 확산된 알려진 평문 유출 (Diffuse known-plaintext leak) 상황에서 이를 공통 프레임으로 다시 매핑하려면 몇 개의 암호화된 쿼리에 대해 대략 C배 더 많은 앵커 (Anchors)가 필요합니다 (C=256일 때 중앙값 기준 200개에서 102,400개로 증가). 짧은 공개 접두사는 이웃 구조 (Neighbour structure)를 훨씬 적게 유출하며, 마이크로 키 제한은 연결 불가능하고 갱신 가능한 템플릿을 통해 잔차 그래프를 제로로 만듭니다. 이 장벽은 학습된 (Learned), 비선형 (Non-linear), 비지도 (Unsupervised) 정렬기들에 대해 유효하며, 유틸리티가 일치하는 노이즈 방어 기법이 거의 모든 탐색을 비익명화(De-anonymises)하는 상황에서도 Shard는 아무것도 비익명화하지 않습니다.

우리는 한계점에 대해서도 명확히 밝힙니다. 셀 내부에서는 키가 상쇄되며, 표적 공격자는 약 $d_{priv}$개의 앵커만 필요하고, 중첩된 참조 코퍼스 (Overlapping reference corpus)는 여전히 접두사를 통해 정보를 유출할 수 있습니다. Shard는 공격을 인지하는 기하학적 방어 (Attack-aware geometric defence)이지, 암호학적 보장 (Cryptographic guarantee)은 아닙니다.