Path ORAM: 메모리 접근 숨기기

Stefanov, van Dijk, Shi, Fletcher, Ren, Yu, Devadas가 2013년에 제안한 경로 ORAM은 실제 구현에 가장 큰 영향을 준 ORAM 구성 방식입니다. 서버 저장 공간을 버킷으로 이루어진 이진 트리로 구성하며, 각 리프는 데이터 블록을 배치할 위치에 해당합니다. 경로 ORAM은 기본 형태에서 접근마다 O(log^2 N)의 통신 오버헤드를 달성하며, 몇백 줄의 코드로 구현할 수 있을 만큼 구조가 단순합니다.

위치 맵은 각 논리적 블록 주소를 이진 트리의 리프 노드에 매핑하는 클라이언트 측 자료 구조입니다. N개 블록으로 이루어진 데이터베이스와 높이가 L = log N인 트리가 있다면, 위치 맵은 N개의 리프 인덱스로 이루어진 배열입니다. 블록 b에 접근하기 전에 클라이언트는 위치 맵에서 현재 할당된 리프를 조회하고 새로운 무작위 리프를 할당합니다. 이전 리프 경로는 서버에서 읽어 온 후 다시 기록합니다.

임시 저장 공간은 서버에서 읽었지만 아직 다시 기록하지 않은 블록을 일시적으로 보관하는 클라이언트 측의 작은 버퍼입니다(일반적으로 20~40개 블록). 블록을 읽으면 해당 경로에서 제거하여 임시 저장 공간에 배치합니다. 블록에 접근하고 필요하다면 수정한 후, 새로운 경로에 배치할 수 있는 임시 저장 공간의 모든 블록을 다시 기록합니다. 경로에 들어갈 수 없는 블록은 임시 저장 공간에 남습니다.

서버 저장 공간은 L+1개 레벨로 이루어진 완전한 이진 트리입니다(L = log N). 각 노드(버킷)는 Z개의 블록을 보관합니다(일반적으로 Z = 5). 리프는 데이터 블록을 배치할 위치에 해당합니다. 리프 노드가 N개이므로 전체 노드는 2N-1개이고, 전체 서버 저장 공간은 O(NZ)입니다. 각 리프에서 루트까지의 경로에는 log N개의 노드가 있으며 Z*log N개의 블록을 보관할 수 있으므로 경로 축출 전략에 필요한 용량을 제공합니다.

블록 b를 읽는 과정은 다음과 같습니다. (1) 위치 맵에서 b의 현재 리프 l을 조회합니다. (2) b에 새로운 무작위 리프 l'을 할당하고 위치 맵을 갱신합니다. (3) 리프 l에서 루트까지의 경로에 있는 모든 버킷(log N개 버킷)을 읽습니다. (4) 읽은 경로나 임시 저장 공간에서 블록 b를 찾습니다. (5) 새로운 경로 l'에 할당할 수 있는 모든 블록을 다시 기록하고, 남은 버킷 슬롯은 더미 블록으로 채웁니다. 서버에는 매번 무작위 경로를 읽는 것으로 보입니다.

경로 ORAM은 어떤 블록에 접근하는지와 관계없이 모든 접근에서 정확히 하나의 루트-리프 경로를 읽고 기록하므로 접근 패턴 은닉성을 유지합니다. 경로는 블록의 내용이나 주소가 아니라 균일하게 무작위로 할당된 리프에 의해 결정됩니다. 비어 있는 버킷 슬롯은 더미 블록으로 채워 모든 경로의 점유된 슬롯 수가 같도록 합니다. 서버를 관찰하는 공격자는 무작위 경로에 대한 접근만 볼 수 있습니다.

경로 ORAM의 각 접근에서는 하나의 루트-리프 경로를 읽고 기록해야 하며, 이 경로는 각각 Z개의 블록을 포함하는 O(log N)개의 버킷으로 이루어집니다. 블록 크기가 B이고 버킷 크기가 Z이면 각 접근에서 O(Z * log N * B)비트를 전송합니다. 일반적인 매개변수(N = 2^20, Z = 5, B = 4KB)를 사용하면 접근마다 약 400KB가 전송되며, 이는 평문 접근의 4KB와 비교해 100배의 오버헤드입니다. 재귀적 위치 맵을 사용하면 블록 단위 통신량을 O(log^2 N)으로 줄일 수 있습니다.

단순한 위치 맵은 클라이언트에 N개의 항목을 저장해야 하므로 클라이언트 저장 공간이 O(N)이며, 이는 데이터베이스 전체 크기와 같습니다. 재귀적 위치 맵은 위치 맵 자체를 더 작은 ORAM에 재귀적으로 저장하여 클라이언트 저장 공간을 O(log^2 N)으로 줄입니다. ORAM이 임시 저장 공간에 들어갈 만큼 작아지면 재귀가 종료됩니다. 이는 대규모 데이터셋에서 경로 ORAM을 실용적으로 만드는 표준 기법입니다.

경로 ORAM에서는 경로 충돌로 인해 블록을 할당된 경로로 축출할 수 없으면 임시 저장 공간의 크기가 증가합니다. Stefanov 등은 임시 저장 공간이 초과되어 R개 블록을 넘을 확률이 R에 대해 지수적으로 작으며, 표준 분석에서 구체적으로 최대 14 * (0.6002)^R임을 증명했습니다. R = 40으로 설정하면 실패 확률은 약 2^{-38}이 되며, 이 결과는 공격자가 선택한 접근 순서를 포함한 모든 접근 순서에 대해 성립합니다.

경로 ORAM 이전에는 가장 실용적인 ORAM 구성 방식의 오버헤드가 O(log^3 N)이었습니다(Shi 등, 2011, "O((log N)^3) 최악의 경우 비용을 갖는 망각 RAM"). 경로 ORAM은 훨씬 단순한 구조로 이를 O(log^2 N)까지 줄였습니다. 이후의 연구(회로 ORAM, OptORAMa)는 상수와 점근적 한계를 더욱 개선했지만, 단순한 구조 덕분에 경로 ORAM은 여전히 가장 널리 구현되는 구성 방식입니다.

경로 ORAM은 수십 개의 연구 및 상용 시스템에 구현되었습니다. ZeroTrace(Intel SGX + 경로 ORAM), Obladi(클라우드 저장소에서 실행되는 경로 ORAM), Opaque(Apache Spark에서 실행되는 경로 ORAM)가 대표적인 구현입니다. Stanford 보안 계산 그룹은 오픈 소스 C++ 경로 ORAM 구현을 관리합니다. AWS는 개인정보 보호 데이터 분석을 위한 연구 프로토타입인 Nitro Enclaves의 일부로 경로 ORAM을 제공합니다.

경로 ORAM에서 위치 맵은 어떤 역할을 합니까?

경로 ORAM은 서버 저장 공간을 이진 트리로 구성하며, 각 접근에서 하나의 루트-리프 경로를 읽고 기록합니다. 위치 맵은 각 블록에 현재 할당된 리프를 추적하고, 임시 저장 공간은 최근에 접근한 블록을 버퍼링합니다. 모든 접근에서 새로운 무작위 리프 위치를 할당하므로 접근이 무작위화되며, 서버에서 보이는 모든 접근의 분포가 동일해집니다. 접근마다 통신 오버헤드는 O(Z * log N)입니다. 재귀적 위치 맵은 클라이언트 저장 공간을 O(log^2 N)으로 줄입니다. 경로 ORAM은 가장 널리 구현되는 ORAM 구성 방식입니다.