Search-Bound Proximity Proofs: Binding Encrypted Geographic Search to Zero-Knowledge Verification

1. 문제 정의 (Problem Statement)

• 배경: 위치 기반 서비스 (LBS) 는 일반적으로 두 단계로 구성됩니다.
  1. 탐색 (Discovery): 사용자가 암호화된 검색 토큰을 사용하여 서버에 가까운 콘텐츠 (예: 지리적 드롭) 를 찾습니다.
  2. 검증 (Verification): 사용자가 특정 콘텐츠에 근접했음을 증명하기 위해 영지식 증명 (ZKP, 예: Groth16) 을 생성하여 잠금을 해제합니다.
• 핵심 문제 (Authorization Provenance Gap): 현재 시스템에서는 이 두 단계가 분리되어 있습니다. 서버가 세션 상태를 삭제한 후, 감사 (Audit) 시점에 어떤 검색 세션에서 생성된 증명인지를 암호학적으로 추적할 수 없습니다.
  • 증명의 공개 입력 (Public Inputs) 에 세션 식별 정보가 포함되어 있지 않기 때문입니다.
  • 이로 인해 **감사 재연결 공격 (Audit Re-association Attack)**이 가능합니다. 공격자는 한 세션에서 생성된 유효한 증명을 가로채어 다른 세션의 권한 토큰과 연결하여, 잘못된 감사 기록을 생성할 수 있습니다.
• 위협 모델: 정직하지만 호기심이 많은 서버 (Honest-but-Curious, HBC) 와 악의적인 클라이언트/네트워크 공격자를 가정합니다.

2. 방법론 (Methodology: SBPP)

저자는 **검색-승인된 증명 (Search-Authorized Proof, SAP)**이라는 새로운 보안 개념을 정의하고, 이를 실현하기 위해 SBPP 프로토콜을 제안합니다.

• 핵심 아이디어: 검색 세션의 비즈 (Nonce) 와 검색 결과 집합의 무결성을 증명 내부의 공개 입력에 암호학적으로 바인딩합니다.

• SBPP 프로토콜 흐름:

  1. 세션 생성: 서버는 고유한 난수 (Nonce, $N$) 와 세션 ID 를 생성하고, 검색 결과 집합에 대한 **머클 트리 (Merkle Tree)**를 구성하여 루트 ($root(R)$) 만 저장합니다.
  2. 증명 생성 (클라이언트): 클라이언트는 선택한 드롭 (Drop) 에 대한 근접 증명을 생성할 때, 다음 요소들을 포함하여 **도전 요약 (Challenge Digest)**을 계산합니다.
     • 세션 Nonce ($N$)
     • 검색 결과 집합의 머클 루트 ($root(R)$)
     • 드롭 ID, 정책 버전 등
     • 이 Digest 를 Groth16 회로의 공개 입력으로 사용합니다.
  3. 검증 및 감사: 서버는 세션 유효성, Digest 일치성, 머클 멤버십 증명을 확인합니다. 세션 상태가 삭제된 후에도, 서버가 발행한 **서명된 영수증 (Signed Receipt)**과 머클 경로를 통해 감사자가 오프라인에서 증명의 출처를 재검증할 수 있습니다.

• 구현 특징:

  • 기존 ZKP 회로 (Groth16) 를 수정하지 않고, 공개 입력 (Public Input) 만을 확장하여 구현 가능합니다.
  • Core SBPP: 세션 Nonce 만 바인딩 (온라인 검증 중심).
  • Full SBPP: Nonce + 머클 루트 + 서명된 영수증 포함 (오프라인 감사 및 결과 집합 무결성 보장).

3. 주요 기여 (Key Contributions)

1. SAP 보안 개념 정의: 검색 세션과 증명 간의 바인딩을 보장하는 세 가지 속성 (P1~P3) 을 정의했습니다.
   • P1 (Authorization Binding): 증명이 생성된 세션과 다른 세션에서 받아들여지지 않음.
   • P2 (Result-set Soundness): 검색 결과 집합에 없는 콘텐츠에 대한 증명이 받아들여지지 않음.
   • P3 (Authorization Provenance): 감사 기록이 증명의 실제 출처를 정확히 식별할 수 있음.
2. 공격 시나리오 제시: "증명 외부 (Proof-external)" 방식 (예: 별도의 토큰 확인) 이 동일한 드롭 파라미터가 여러 세션에 걸쳐 재사용될 때, 감사 재연결 공격에 취약함을 구체적인 공격 사례로 증명했습니다.
3. SBPP 프로토콜 제안: 회로 수정 없이 구현 가능한 실용적인 분해 구조를 제시했습니다.
   • 세션 Nonce, 머클 루트, 서명된 영수증을 독립적인 구성 요소로 분리하여 **속성 수준의 결함 격리 (Property-level Fault Isolation)**를 가능하게 합니다.
4. 광범위한 평가: 합성 데이터와 실제 OpenStreetMap 데이터 (110,776 개 POI) 를 사용하여 9 가지 프로토콜 변형과 모바일 환경에서 성능을 평가했습니다.

4. 실험 결과 (Results)

• 보안성:
  • SBPP 는 모든 공격 클래스 (세션 교체, 재연결, 결과 집합 탈출 등) 를 차단합니다.
  • 특히 **A4b (감사 재연결 공격)**를 방어하는 유일한 솔루션입니다. 기존 방식 (V5-V7) 은 재연결 공격에 취약했으나, SBPP 는 0% 성공률로 방어했습니다.
  • **V8(내부화된 토큰 해시)**과 비교 시, V8 은 보안은 유지하지만 감사 시 실패 원인을 특정하기 어렵습니다. 반면 SBPP 는 Nonce 불일치, 머클 실패, 서명 실패 등을 명확히 구분하여 감사 디버깅을 용이하게 합니다.
• 성능 (Overhead):
  • 프로토콜 경로 오버헤드: GridSE(암호화 검색) 대비 SBPP 는 **약 7% (27 µs)**의 추가 지연만 발생시킵니다.
  • 전체 잠금 해제 시간: ZKP 생성 시간 (모바일 기준 42~125 ms) 에 비해 SBPP 오버헤드는 무시할 수준 (<0.03%) 입니다.
  • 확장성: 50,000 개의 드롭이 있는 경우에도 머클 트리 검증은 1ms 미만의 지연을 보입니다.
  • 모바일 성능: POCO X7 Pro 와 iPhone 16 Pro 에서 모두 실시간 상호작용 가능한 수준 (130ms 이내) 을 달성했습니다.

5. 의의 및 결론 (Significance)

• 감사 가능성의 혁신: 위치 기반 콘텐츠 시스템에서 서버의 세션 상태가 삭제된 후에도, 암호학적 증거를 통해 **"누가, 언제, 어떤 검색 세션을 통해 접근 권한을 얻었는지"**를 forensic(수사) 수준으로 추적할 수 있게 되었습니다.
• 실용성: 기존 ZKP 회로를 변경하지 않고도 구현 가능하여, 기존 시스템 (예: Zairn 플랫폼) 에 쉽게 통합될 수 있습니다.
• 한계 및 향후 작업:
  • SBPP 는 서버가 정직하게 (Honest-but-Curious) 동작한다고 가정합니다. 서버가 검색 결과를 조작하거나 편향된 머클 루트를 서명하는 경우 (악의적인 서버) 는 방어하지 못합니다.
  • 검색 패턴 누출 (SSE Leakage) 은 기존 암호화 검색과 동일하게 유지되므로, 완전한 프라이버시를 위해서는 ORAM 등 추가 기술이 필요합니다.

요약하자면, 이 논문은 암호화된 지리 검색과 영지식 증명을 연결하는 '결합 고리'를 암호학적으로 강화하여, 위치 기반 서비스의 보안 감사와 책임 소재 추적을 혁신적으로 개선한 연구입니다.