1. 문제 정의 (Problem)

현대 데이터 서비스는 클라우드 및 엣지 환경에서 운영되며, 많은 클라이언트는 로컬 자원이 부족하여 직접 데이터베이스에 접근하지 못하고 프록시 (예: Cloudflare, 금융 자문가 등) 를 통해 간접적으로 접근합니다. 이 과정에서 다음과 같은 주요 문제들이 발생합니다.

• 프록시를 통한 쿼리 의도 유출: 클라이언트가 프록시를 통해 요청할 때, 프록시는 요청 구조와 메타데이터를 관찰하여 클라이언트가 어떤 데이터를 찾고 있는지 추론할 수 있습니다.
• 기존 OT 의 한계:
  • 위임 부재: 기존 OT 는 수신자가 직접 쿼리 인덱스를 계산하고 송신자와 직접 상호작용해야 하므로, 자원이 부족한 클라이언트가 무거운 연산을 프록시에 위임할 수 없습니다.
  • 다중 수신자 및 병합 데이터베이스 문제: 클라우드 제공자가 여러 조직의 데이터를 병합하여 저장할 경우, 기존 OT 는 데이터베이스의 전체 크기나 수신자의 접근 패턴과 같은 민감한 메타데이터를 유출합니다.
  • 고정 크기 응답의 부재: 응답 크기를 상수로 유지하는 프로토콜은 일반적으로 수신자가 전체 데이터베이스의 암호화된 사본을 로컬에 저장해야 하므로, 저장 공간이 제한된 경량 클라이언트에는 부적합합니다.
  • 정보이론적 보안의 비실용성: 정보이론적 보안 (Information-Theoretic Security) 을 제공하는 기존 OT 는 다중 송신자, 잡음 채널, 또는 완전히 신뢰할 수 있는 초기화 설정을 요구하여 실제 배포가 어렵습니다.

2. 방법론 및 제안 시스템 (Methodology & Oblivis Framework)

Oblivis 는 두 가지 주요 계열로 구성된 모듈형 프레임워크입니다.

2.1 설정 중심 (Setting-Oriented) 프로토콜

프록시 기반의 위임과 프라이버시 보호를 위한 세 가지 새로운 OT 원시 (Primitive) 를 제공합니다.

1. 위임 쿼리 OT (Delegated-Query OT, DQ-OT):
   • 수신자의 선택 인덱스 $s$를 두 개의 프록시 ($P_1, P_2$) 에 비밀 공유 (Secret Sharing) 합니다.
   • 두 프록시가 순차적으로 부분 쿼리를 계산하고 정렬하여 송신자 ($S$) 에게 전송합니다.
   • 최종 쿼리는 수신자가 직접 Naor-Pinkas OT 를 수행한 것과 구조적으로 동일하지만, 어느 프록시도 실제 인덱스 $s$를 알지 못합니다.
2. 위임 미지 쿼리 OT (Delegate-Unknown-Query OT, DUQ-OT):
   • 수신자 자체가 쿼리 인덱스를 모르는 경우 (예: 제 3 자 쿼리 발행자가 인덱스를 결정) 에 사용됩니다.
   • 송신자가 메시지에 공개적으로 알려진 구조 (예: 특정 마커) 를 부여하고, 수신자는 복호화 후 구조를 가진 메시지만을 선택하여 인덱스 없이도 올바른 데이터를 획득합니다.
3. 위임 쿼리 다중 수신자 OT (DQMR-OT):
   • 병합된 클라우드 데이터베이스 환경에서 사용됩니다.
   • 송신자는 모든 수신자 쌍에 대한 응답을 생성하지만, 프록시가 특정 수신자 ($v$) 에 해당하는 한 쌍만 필터링하여 전달합니다.
   • 이를 통해 수신자는 데이터베이스의 전체 크기 ($z$) 를 알 수 없으며, 송신자는 어느 수신자가 어떤 레코드를 요청했는지 알 수 없습니다.

2.2 성능 중심 (Performance-Oriented) 구성 요소

• 상수 크기 응답을 위한 범용 컴파일러:
  • 임의의 $n$개 중 1 개를 선택하는 OT 를 변환하여, 수신자가 다운로드하는 응답 크기를 $O(n)$에서 $O(1)$로 줄입니다.
  • 가법 동형 암호 (Additive Homomorphic Encryption) 를 사용하여 수신자가 선택 벡터를 암호화하여 송신자에게 보내고, 송신자가 이를 응답에 곱하여 합산함으로써 단일 레코드만 추출되도록 합니다.
• 초고속 OT (Supersonic OT):
  • 정보이론적 보안을 달성하면서도 다중 송신자, 잡음 채널, 신뢰할 수 있는 초기화 설정 없이 동작합니다.
  • 공개키 암호화를 사용하지 않고, 제어된 스왑 (Controlled-Swap) 메커니즘과 일회용 패드 (One-Time Pad) 를 활용합니다.
  • 송신자와 수신자가 공유한 키를 기반으로 메시지를 암호화하고, 프록시가 이를 스왑하여 필터링하는 방식으로 동작합니다.

3. 주요 기여 (Key Contributions)

1. 새로운 OT 패러다임 제시: 프록시 기반의 위임, 숨겨진 쿼리, 다중 수신자 프라이버시를 동시에 지원하는 최초의 OT 프레임워크를 제안했습니다.
2. 공식적 보안 증명: 시뮬레이션 기반의 보안 모델 (Simulation-based Paradigm) 하에서 모든 프로토콜이 반-정직한 (Semi-honest) 적대자에 대해 안전함을 수학적으로 증명했습니다.
3. 고효율 정보이론적 OT (Supersonic OT):
   • 공개키 연산을 배제하여 매우 빠른 속도를 달성했습니다.
   • 현대 노트북에서 1 회 전송당 0.53ms, Raspberry Pi 4 에서 1.36ms의 실행 시간을 기록했습니다.
   • 기존 고효율 OT 에 비해 92 배, OT 확장 (OT Extension) 에 비해 2.6 배~106 배의 속도 향상을 달성했습니다.
4. 실제 구현 및 평가: C++ 로 구현하여 다양한 하드웨어 (MacBook, Raspberry Pi) 에서 성능을 검증하고, 경량 장치에서도 원활하게 작동함을 입증했습니다.

4. 실험 결과 (Results)

• 성능 비교:
  • Supersonic OT vs Base OT: Simplest OT [18] 대비 92.8 배 빠른 속도를 보였습니다.
  • Supersonic OT vs OT Extension: 200 회 호출 시 IKNP OT 확장 대비 106 배, 100,000 회 호출 시 2.6 배 빠른 성능을 보였습니다. (대규모 호출에서는 IKNP 가 우세할 수 있으나, 일반적인 범위에서 Supersonic 이 우월함)
• 하드웨어 호환성: Raspberry Pi 4 와 같은 제한된 하드웨어에서도 1,000 회 호출 시 3.26ms 의 실행 시간을 유지하며 확장성이 입증되었습니다.
• 보안성: 정보이론적 보안을 제공하여 양자 컴퓨터 공격에도 안전하며 (Post-Quantum Secure), 신뢰할 수 있는 제 3 자나 잡음 채널 없이도 구현 가능합니다.

5. 의의 및 결론 (Significance)

Oblivis 프레임워크는 클라우드 및 엣지 컴퓨팅 환경에서 프라이버시 보호된 데이터 검색의 새로운 기준을 제시합니다.

• 실용성: 기존 이론적 OT 의 복잡한 요구사항 (다중 서버, 신뢰 초기화 등) 을 제거하고, 단일 프록시와 경량 클라이언트 환경에 최적화되어 실제 배포가 가능합니다.
• 프라이버시 강화: 금융, 의료 등 민감한 데이터가 처리되는 환경에서, 프록시조차도 사용자의 쿼리 의도나 데이터베이스 구조를 알 수 없도록 보장합니다.
• 미래 지향성: 양자 내성 (Post-Quantum) 을 갖춘 정보이론적 보안을 제공하며, 브라우저 기반 배포나 엣지 컴퓨팅 플랫폼과의 통합 등 향후 연구 방향을 제시합니다.

이 연구는 경량 클라이언트가 복잡한 암호학적 연산 없이도 안전하게 데이터를 검색할 수 있는 길을 열어주며, 프라이버시 보호 기술의 실용화를 크게 앞당긴 것으로 평가됩니다.