Billion-Scale Nearest-Neighbor Search under Fully Homomorphic Encryption on a Single GPU, Balancing Leakage and Cost
본 논문은 순위 감소(rank reduction)와 계층적 라우팅(hierarchical routing)을 결합하여 실용적인 지연 시간을 달성하고, 시드 기반 패딩(seeded padding)을 통해 이와 관련된 기하학적 누출을 정량화 및 완화함으로써 완전 동형 암호 하에서 십억 규모의 최근접 이웃 탐색을 위한 GPU 가속 시스템을 제시한다.
원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기
당신에게 수십억 장의 사진이 들어 있는 도서관이 있고, 당신은 주머니 속에 있는 사진과 가장 비슷하게 생긴 것을 찾고 싶다고 상상해 보십시오. 보통 컴퓨터는 일치하는 것을 찾기 위해 모든 사진을 하나하나 스캔하겠지만, 만약 당신의 질문(사진)이 사적인 것이라 컴퓨터에게 보여줄 수 없다면 어떻게 될까요? 만약 그 도서관이 당신이 신뢰하지 않는 낯선 사람의 소유라면 어떨까요? 이것이 바로 연구자들이 해결하고자 했던 문제입니다. 그들은 컴퓨터가 질문되는 내용이 무엇인지 전혀 알지 못한 채로 거대한 비밀 데이터베이스를 검색할 수 있는 방법을 원했습니다. 이를 위해 그들은 '완전 동형 암호(fully homomorphic encryption)'라고 불리는 방법을 사용하는데, 이는 마치 당신의 질문을 투명한 잠긴 상자 안에 넣는 것과 같습니다. 컴퓨터는 상자를 열지 않고도 상자 안에서 계산을 수행할 수 있으며, 결과 또한 여전히 잠긴 상태로 반환됩니다. 오직 열쇠를 가진 당신만이 최종 상자를 열어 답을 확인할 수 있습니다. 수년 동안 이 아이디어는 수학적 연산이 매우 무거웠기 때문에 방대한 양의 데이터를 처리하기에는 너무 느렸습니다.
한 연구팀은 이제 단 하나의 그래픽 카드(GPU)로 10억 개의 항목에 대해 이를 가능하게 하는 시스템을 구축했습니다. 그들은 서버가 쿼리(질문)를 전혀 보지 못한 상태에서 13.9억 개의 항목이 담긴 데이터베이스에서 가장 유사한 이미지를 찾아냈습니다. 이 시스템은 속도를 높이기 위해 두 가지 주요 기술을 사용합니다. 첫째, 이미지를 단순화합니다. 사진의 모든 미세한 세부 사항을 비교하는 대신, 시스템은 검색을 시작하기 전에 각 이미지의 설명을 더 짧고 단순한 버전으로 축소합니다. 이는 수학적 계산을 훨씬 가볍게 만듭니다. 둘째, 모든 사진을 다 살펴보지 않습니다. 대신, 먼저 일반적인 동네를 가리키고, 그다음 특정 거리, 마지막으로 몇 채의 집을 가리키는 지도와 같은 계층 구조를 사용합니다. 컴퓨터는 선택된 영역 내의 사진들만 확인하고 나머지는 건너뜁니다. 이를 통해 시스템은 데이터가 잠긴 상자 안에 있음에도 불구하고 빠르게 정답을 찾아낼 수 있습니다.
결과는 이 접근 방식이 놀라울 정도로 잘 작동한다는 것을 보여줍니다. 13.9억 개의 이미지 데이터셋에서 이 시스템은 상위 10개 결과 안에 정답을 90%의 확률로 찾아냈습니다. 인터넷에는 거의 동일한 사진의 약간 다른 복사본들이 많다는 점을 고려하여 유사 중복(near-duplicates)을 허용했을 때, 성공률은 95%로 뛰었습니다. 전체 과정은 단일 그래픽 카드에서 검색당 약 6초가 소요되었습니다. 이는 데이터가 사전에 준비되어 있다면 실생활에서 사용할 수 있을 만큼 빠른 '배포 가능한 속도(deployable speed)'입니다. 연구진은 또한 9,600만 차원의 벡터가 담긴 또 다른 10억 개 규모의 컬렉션에서도 이 시스템을 테스트하여, 단 2.3초 만에 90%의 성공률을 달고했습니다. 이 수치들은 수십억 개의 암호화된 항목을 단 한 대의 기기에서 검색하는 것이 더 이상 이론적인 꿈이 아님을 증명합니다.
하지만 연구진은 이 속도가 프라이버시 측면에서 어떤 비용을 치르는지 신중하게 측정했습니다. 서버는 질문이나 답을 보지는 못하지만, 컴퓨터가 어떤 데이터 그룹을 살펴보는지에 대한 패턴은 볼 수 있습니다. 이러한 접근 패턴은 데이터베이스 자체에 대한 단서를 드러낼 수 있습니다. 어떤 그룹들이 함께 요청되는지를 관찰함으로써, 관찰자는 데이터가 어떻게 조직되어 있는지 보여주는 지도의 약 72%를 재구성할 수 있습니다. 또한 서로 다른 두 검색이 같은 그룹을 요청한다면, 두 검색이 비슷한 것을 찾고 있다는 것을 추측할 수도 있습니다. 이를 해결하기 위해 연구진은 컴퓨터가 실제 그룹과 함께 추가적인 가짜(fake) 그룹들을 요청하여 진정한 패턴을 숨기는 방법을 시도했습니다. 만약 가짜 그룹이 매번 바뀐다면 영리한 공격자가 여러 번의 검색을 비교하여 진실을 알아낼 수 있습니다. 하지만 가짜 그룹이 고정되어 있고 항상 동일하다면, 공격자는 이를 제거할 수 없습니다. 이 '시드(seeded)' 패딩 방식은 정보 유출을 약 35배 줄여, 데이터베이스 지도의 복구율을 72%에서 단 2%로 떨어뜨렸습니다.
연구팀은 또한 데이터를 작은 코드로 나누는 '곱 양자화(product quantization)'와 같은 다른 빠른 방법들도 탐구했습니다. 그들은 암호화된 상태에서는 이 방법이 잘 작동하지 않는다는 것을 발견했습니다. 이 방법은 표준 암호화 검색보다 성능이 떨어지거나 데이터 구조에 대한 정보를 너무 많이 유출했습니다. 따라서 그들은 이 방법을 사용하는 대신, 데이터 설명을 축소하고 계층적 지도를 사용하는 더 단순한 방식에 집중하기로 결정했습니다. 이 선택은 프라이버시가 우선순위일 때는 때때로 복잡한 방법보다 단순한 접근 방식이 더 낫다는 핵심적인 발견을 강조합니다.
시스템은 사용자가 암호화된 질문을 서버로 보내는 방식으로 작동합니다. 암호화된 데이터베이스를 보유한 서버는 잠긴 데이터에 대해 수학적 연산을 수행합니다. 서버는 먼저 몇 천 개의 넓은 카테고리를 확인하고, 그다음 몇 천 개의 더 구체적인 그룹으로 범위를 좁힌 뒤, 마지막으로 해당 그룹 내의 실제 이미지들에 대한 점수를 매깁니다. 모든 단계에서 서버는 암호화된 점수를 반환합니다. 사용자는 이 점수를 복호화하여 다음에 어떤 그룹을 살펴볼지 결정하고 새로운 요청을 보냅니다. 서버는 사용자의 결정이나 최종 답을 결코 볼 수 없습니다. 이 주고받는 과정은 상위 10개의 매치가 발견될 때까지 계속됩니다. 연구진은 사용자가 최종 결과를 복호화하거나 네트워크를 통해 데이터가 이동하는 시간을 제외하고, 데이터를 로드하고 점수를 매기는 데 걸리는 시간을 측정했습니다. 그들은 시간이 수학적 계산 자체가 아니라, 암호화된 데이터를 컴퓨터 메모리로 로드하는 과정에 의해 지배된다는 것을 발견했습니다.
프라이버시 위험 분석에서 연구진은 정보 유출이 검색되는 특정 데이터의 문제가 아니라, 검색 경로(routing)의 특성임을 보여주었습니다. 데이터베이스에 얼굴이 들어 있든 일반적인 이미지가 들어 있든, 접근 패턴은 동일한 양의 구조적 정보를 드러냈습니다. 그들은 보호 조치가 없다면 관찰자가 데이터의 그룹화를 거의 완벽하게 복구할 수 있음을 입증했습니다. 고정 그룹 패딩을 사용하면 이 복구가 크게 감소했지만, 완전히 사라지지는 않았습니다. 트레이드오프(trade-off)는 명확합니다. 접근 패턴을 숨기려면 시스템은 꼭 필요한 것보다 더 많은 데이터를 가져와야 하며, 이는 검색 시간을 증가시킵니다. 연구진은 이 비용을 관리할 수 있지만, 얼마나 많은 프라이버시가 필요한지와 시스템이 얼마나 빨리 실행되어야 하는지 사이의 균형이 필요함을 보여주었습니다.
이 연구는 대규모 규모에서 프라이버시가 보장된 검색을 실용적으로 만드는 데 있어 중요한 진전을 의미합니다. 이는 당신이 몇 초의 지연을 수용하고 정교하게 관리된 프라이버시 비용을 감수한다면, 의도를 드러내지 않고도 10억 개의 항목을 검색할 수 있음을 증명합니다. 이 시스템은 마법이나 검증되지 않은 이론에 의존하지 않습니다. 대신 확립된 수학과 영리한 엔지니어링을 사용하여 실제 문제를 해결합니다. 연구진은 속도와 정확성을 위한 정확한 설정값을 포함하여, 이 시스템을 구축하고 운영하는 방법에 대한 완전한 가이드를 제공했습니다. 또한 그들은 특히 정보가 누출되는 부분에 관한 한계를 명확히 밝힘으로써, 정보가 무엇을 숨기고 무엇을 드러내는지에 대해 투명하게 공개함으로써 프라이-데이터 검색의 현실적인 경로를 제시했습니다.
연구 분야의 논문에 파묻히고 계신가요?
연구 키워드에 맞는 최신 논문의 일일 다이제스트를 받아보세요 — 기술 요약 포함, 당신의 언어로.