Oblivious RAM 문서 원본 보기

[[분류: 소프트웨어 기반 보안]]

== 개요 ==
ORAM은 알고리즘의 Input-output의 결과는 유지하면서, 메모리 접근 패턴을 숨기는 기법을 말한다. ORAM은 프로그램의 실행에서 공격자가 메모리 접근 패턴을 가지고 유의미한 공격을 할 수 있음에 착안하여, 메모리접근 위치를 모르게 하거나, 패턴을 랜덤화 시키는 등의 방법을 통해서 메모리를 보호한다.

[[Turing machine]](TM)은 Input에 따라서 TM의 헤드가 같은 순서로 움직이는 경우 Oblivious라고 한다. ORAM은 보호된 CPU와 물리적 RAM 사이의 인터페이스에 위치한 알고리즘으로, CPU에는 일반적인 RAM처럼 동작하면서도 CPU의 실제 메모리 접근 패턴에 대한 정보를 물리적 RAM으로부터 숨기는 방식으로 작동한다. 즉, '''RAM에 동일한 횟수로 메모리 접근을 수행하는 두 프로그램의 메모리 접근 분포는 서로 구별할 수 없게'''한다.

== 방식 ==
; Trivial construction
: 트리비얼 ORAM 시뮬레이터 구성은 각 읽기 또는 쓰기 연산마다 배열의 모든 요소를 읽고 쓰는 방식이다. 이때 실제로 의미 있는 동작은 해당 연산에서 지정한 주소에 대해서만 수행된다. 즉, 이 방식은 메모리의 모든 위치를 연산마다 순차적으로 탐색하는 구조이다. 이러한 방식은 메모리 크기를 n이라 할 때, 각 연산에 대해 Ω(n)의 시간 오버헤드를 발생시킨다.

이외에도 Oblivious ram을 구현하기 위한 많은 소프트웨어적인 방법이 있으며, 하드웨어적인 방법도 있다.