Circuit ORAM과 실제 성능

Wang, Chan, Shi가 2015년에 제안한 회로 ORAM은 대역폭 오버헤드를 최소화하는 동시에 안전한 계산 프레임워크(가블드 회로 및 비밀 공유)에서 쉽게 구현되도록 설계되었습니다. 핵심 혁신은 실패 확률을 무시할 수 있는 수준으로 유지하면서 버킷 크기를 Z = 2개 블록으로 줄인 것입니다(Path ORAM에서는 Z = 5). 이를 통해 대역폭을 절반으로 줄였습니다. 축출 절차도 작은 부울 회로로 표현할 수 있도록 다시 설계되었습니다.

Z = 5인 경로 ORAM에서는 블록을 경로에 무작위로 할당할 때 발생하는 문제를 수용하기 위해 버킷마다 여러 블록을 배치하여 임시 저장 공간 초과 확률을 제어합니다. 회로 ORAM은 무작위 축출 대신 결정론적 축출 절차(깊이 우선 축출)를 사용하면 Z = 2로 충분하다는 것을 증명합니다. 따라서 동일한 보안 매개변수를 사용할 때 경로 ORAM에 비해 서버 저장 공간과 통신 오버헤드를 절반으로 줄일 수 있습니다.

회로 ORAM은 효율적인 부울 회로로 표현할 수 있는 축출 절차를 갖도록 특별히 설계되었습니다. 안전한 계산 프로토콜(가블드 회로, SPDZ)에서는 ORAM 접근 자체를 비가시적으로 평가해야 하며, 계산을 수행하는 서버는 어떤 메모리 위치에 접근했는지 알 수 없어야 합니다. 회로 ORAM의 단순한 결정론적 축출 회로는 경로 ORAM의 축출 절차보다 가블드 회로로 변환하기가 훨씬 효율적입니다.

B바이트 크기의 블록 N개로 이루어진 데이터베이스에서 회로 ORAM은 접근마다 2 * log N * B바이트를 필요로 합니다(Z = 2개 블록씩 버킷 하나의 경로를 읽고 기록). 4KB 블록 N = 2^20개인 경우 접근마다 160KB가 필요하며, 이는 경로 ORAM의 400KB(Z=5)와 비교됩니다. 일반적인 매개변수에서 평문 대비 대역폭 오버헤드는 약 40배로, 경로 ORAM의 100배에서 감소합니다.

Oblix(Misra, Schlegel, Sherwood, Tsudik, 2018)는 회로 ORAM을 사용하여 고수준 자료 구조의 망각 버전을 구축합니다. 여기에는 망각 연결 리스트, 망각 맵(해시 테이블), 망각 우선순위 큐가 포함됩니다. 이러한 구조를 사용하면 접근 패턴을 공개하지 않고 동적 데이터에 대해 계산할 수 있습니다. Oblix는 Intel SGX 엔클레이브 내부에서 실행되며, 안전한 비공개 집합 교집합과 비공개 데이터베이스 질의를 대상으로 합니다.

TaoStore(Sahin, Zhu, Gunter, Borisov, 2016)는 여러 ORAM 요청을 병렬로 처리하고 경로 축출을 일괄 처리하여 높은 처리량의 비동기 접근을 지원하도록 경로 ORAM을 확장합니다. 동일한 경로에 대한 접근을 결합함으로써 TaoStore는 동기식 ORAM 구성보다 초당 요청 수 기준으로 훨씬 높은 처리량을 달성하므로, 많은 클라이언트가 동시에 사용하는 클라우드 저장 서버에 적합합니다.

Obladi(Crooks, Park, Alvisi, Iyengar, 2018)는 경로 ORAM 위에 완전한 트랜잭션 저장 시스템을 구축합니다. Obladi는 암호화되고 접근 패턴을 숨기는 저장소에서 ACID 트랜잭션을 지원합니다. 또한 지연 실행을 도입합니다. 트랜잭션을 에폭 단위로 일괄 처리한 다음, 각 에폭에서 어떤 특정 레코드에 접근했는지 숨기는 방식으로 실행합니다. Obladi는 클라이언트와 신뢰할 수 없는 클라우드 저장소 백엔드 사이에서 신뢰할 수 있는 프록시로 실행됩니다.

AWS에 배포하고 인터넷을 통해 블록에 접근하는 클라이언트가 사용하는 1GB ORAM(4KB 블록 262,144개)의 경우, 경로 ORAM의 접근당 지연 시간은 약 50~200ms입니다(log N = 18개 버킷에 접근하는 데 필요한 왕복 시간이 지배적입니다). 버킷을 병렬로 가져오면 이 시간을 줄일 수 있습니다. ORAM이 RAM에 있는 로컬 SGX 애플리케이션에서는 접근당 지연 시간이 1~10ms 범위이므로, 많은 안전한 계산 애플리케이션에서 허용할 수 있는 수준입니다.

ORAM의 대역폭 부담은 접근 패턴에 크게 좌우됩니다. 1MB 블록을 사용하는 1TB 클라우드 저장소 ORAM에서는 한 번 접근할 때 약 25MB를 전송합니다(log N = 25개 수준에 따른 25배 부담). 작은 블록(4KB)을 사용하면 접근당 절대적인 전송 바이트 수는 줄어들지만 상대적인 부담은 커집니다. ORAM을 배포하는 조직은 대역폭이 20~50배 증폭되는 상황을 예산에 반영하고, 네트워크 연결과 클라우드 외부 전송 비용에도 이를 고려해야 합니다.

접근 패턴의 비공개성을 보장하는 ORAM의 대안은 신뢰할 수 있는 하드웨어입니다. Intel SGX 또는 AMD SEV는 적절한 방어 기법을 적용하면 호스트 OS조차 계산이나 메모리 접근 패턴을 관찰할 수 없는 신뢰 실행 환경을 제공합니다. 그러나 ORAM이 없는 SGX는 여전히 하드웨어에 페이지 수준 접근 패턴을 노출하므로, 완전한 보호를 위해서는 SGX 내부에 ORAM이 필요합니다. 순수한 ORAM과 비교하면 신뢰할 수 있는 하드웨어는 대역폭 부담을 줄여 주지만, 하드웨어 제조업체와 공급망을 신뢰해야 합니다.

다음 조건에 해당할 때 ORAM이 적합합니다. 공격자가 서버 측 접근 패턴을 관찰할 수 있고(클라우드 제공업체, 공동 테넌트), 데이터의 민감성이 20~50배의 대역폭 부담을 감수할 만한 가치가 있으며, 접근 패턴 자체가 민감한 정보를 드러낼 수 있어야 합니다. 대부분의 애플리케이션에서는 신중한 키 관리와 함께 표준 암호화를 사용하는 것으로 충분합니다. ORAM은 의료 데이터 분석, 비공개 기계 학습, 금융 거래 시스템, 법 집행 데이터베이스와 같은 높은 보안 수준이 필요한 상황을 위한 특수 도구입니다.

Circuit ORAM은 버킷 크기를 Z=2로 줄이고(경로 ORAM의 Z=5와 비교), 결정적인 깊이 우선 축출을 통해 대역폭을 절반으로 줄입니다. 이는 혼합 회로 기반 안전한 계산 내부에서 사용하도록 설계되었습니다. 일반적인 매개변수에서 실제 부담은 대역폭 40배 증폭입니다. 운영 환경의 시스템으로는 Oblix(SGX와 접근 패턴 은닉 데이터 구조), TaoStore(고처리량 일괄 ORAM), Obladi(트랜잭션 ORAM)가 있습니다. SGX만으로는 페이지 수준 접근 패턴이 노출되므로 SGX 내부에 ORAM을 적용해야 합니다.