망각 RAM

망각 RAM(ORAM) 시뮬레이터는 결과 알고리즘이 원래 알고리즘의 입출력 동작을 유지하지만 변환된 알고리즘의 메모리 액세스 패턴의 분포는 원래 알고리즘의 메모리 액세스 패턴과는 무관하도록 알고리즘을 변환하는 컴파일러입니다.

ORAM의 사용은 상대방이 실행 중에 메모리의 다양한 위치에 액세스하는 패턴을 관찰하는 것만으로 프로그램 실행 및 처리 중인 데이터의 특성에 대한 중요하지 않은 정보를 얻을 수 있다는 사실에 의해 동기 부여됩니다.상대는 데이터 값이 모두 암호화되어 있어도 이 정보를 얻을 수 있습니다.

이 정의는 보호되지 않은 공유 메모리에서 실행되는 보호된 프로그램 설정 및 원격 서버에 이전에 저장된 데이터에 액세스하여 시스템에서 프로그램을 실행하는 클라이언트 설정에도 적합합니다.이 개념은 1996년 ^[1]Oded Goldreich와 Rafail Ostrovsky에 의해 공식화되었습니다.

정의.

실제 컴퓨터(프로그램)의 수학적 추상화인 튜링 머신(TM)은 같은 길이의 두 입력 중 하나에 대해 테이프 헤드의 움직임이 동일하면 의식하지 못한다고 한다.Pippenger와^[2] Fischer는 실행 $T(n)$ $T(n)$ 이 $T(n)$ T ( $T(n)$ $O(T(n)\log T(n))$ $T(n)$ ) { $displaystyle$ T ( $n$ ) } { displaystyle O ( $t$ ( $n$ ) $O(T(n)\log T(n))$ { $displaystyle$ O ( n ) \ $log$ T $O(T(n)\log T(n))$ ( $n$ ) $O(T(n)\log T(n))$ $（$ $O(T(n)\log T(n))$ ） $O(T(n)\log T(n))$ 보다 현실적인 계산 모델은 RAM 모델입니다.계산의 RAM 모델에는 기본적인 수학, 논리 및 제어 명령을 실행할 수 있는 CPU가 있습니다.CPU는 또한 몇 개의 레지스터와 물리 랜덤 액세스메모리와 관련지어져 명령의 오퍼랜드를 저장합니다.또한 CPU에는 메모리 셀의 내용을 읽고 메모리 셀에 특정 값을 쓰는 명령이 있습니다.ORAM의 정의는 이 모델에서 망각 메모리 액세스의 유사한 개념을 포착합니다.

비공식적으로 ORAM은 CPU의 실제 메모리액세스 패턴에 대한 정보를 물리 RAM에서 숨기면서 CPU의 물리 RAM을 쿼리함으로써 CPU에 대한 RAM과 같은 기능을 하도록 보호된 CPU와 물리 RAM의 인터페이스 알고리즘입니다.즉, RAM에 대한 메모리 액세스 수가 같은 2개의 프로그램의 메모리 액세스 분포는 서로 구별할 수 없다.이 설명은 CPU를 작은 스토리지를 가진 클라이언트로 대체하고 물리 RAM을 큰 스토리지 용량을 가진 리모트서버(클라이언트의 데이터가 상주하는 것)로 대체한 경우에도 유효합니다.

다음 형식(3]에 대한 자세한 내용은 μmula_PI suppose을 위한 특수 디스플레이 스타일(3]을 표시)을 표시할 때 기본 표시한다.사실. ${\mathsf {read}}(l)$ ${\mathsf {read}}(l)$ ${\mathsf {read}}(l)$ ( ${\mathsf {read}}(l)$ style \ $display$ \ $mathsf$ { $read$ ${\mathsf {read}}(l)$ } ( ${\mathsf {read}}(l)$ $l$ ) ${\mathsf {read}}(l)$ ${\mathsf {write}}(l,v)$ ${\mathsf {write}}(l,v)$ ${\mathsf {write}}(l,v)$ e ${\mathsf {write}}(l,v)$ ( ${\mathsf {write}}(l,v)$ , ${\mathsf {write}}(l,v)$ $){$ $display$ style \ $display$ style \ $mathsf$ { $read$ $}$ ( $l$ , $v$ ) ${\mathsf {read}}(l)$ 。 ${\mathsf {read}}(l)$ 서 ${\mathsf {read}}(l)$ ${\mathsf {read}}(l)$ style ${\mathsf {read}}(l)$ \ display $style$ { ${\mathsf {write}}(l,v)$ ${\mathsf {read}}(l)$ $}$ ( l ) ${\mathsf {write}}(l,v)$ ${\mathsf {write}}(l,v)$ ${\mathsf {write}}(l,v)$ $display$ ${\mathsf {write}}(l,v)$ l ) ${\mathsf {write}}(l,v)$ $값$ v( $displaystyle$ $)$ ~ l $(displaystyle$ l $l$ 을 지정합니다.실행 중에 프로그램 $\Pi$ (\ $displaystyle \Pi)$ 에 $\Pi$ 의해 액세스되는 메모리 셀의 시퀀스를 메모리 액세스 패턴이라고 하며, ${\tilde {\Pi }}(n,x)$ ${\tilde {\Pi }}(n,x)$ ( ${\tilde {\Pi }}(n,x)$ , ${\tilde {\Pi }}(n,x)$ $)(\displaystyle$ {\ $Pi }}(n$ , x $)$ 로 나타냅니다 ${\tilde {\Pi }}(n,x)$

다항식 시간 알고리즘 $C$ (\ $displaystyle$ C)는 $C$ 계산 $c(\cdot )$ c $(\displaystyle$ c $(\cdot)$ 와 $c(\cdot )$ 메모리 $m(\cdot )$ m $(\displaystyle$ m $(\$ $cdot$ $m(\cdot )$ 을 가진 ORAM( $n\in N$ RAM $)$ 컴파일러입니다( $C$ $displaystyle$ C $)$ 가 $C$ $n\in N$ 지정된 $n\in N$ 경우). $tyle$ $\Pi$ \Pi $} with$ memory-size $\Pi$ n {\ $displaystyle$ $n$ $}$ 은 $n$ 입력 x {\ $\Pi _{0}(n,x)$ x $x$ {\ $displaystyle$ x} {\ $displaystyle$ $m(n)\cdot n$ x} ${\displaystyle$ $\Pi _{0}(n,x)$ x} {n $m(n)\cdot n$ $}$ {\ $displaystyle$ x $}$ 의 실행 시간을 나타내듯이 메모리 $m(n)\cdot n$ m $m(n)\cdot n$ $\Pi _{0}(n,x)$ ) $\Pi _{0}(n,x)$ $m(n)\cdot n$ $\Pi _{0}$ 0( $n$ $\Pi _{0}(n,x)$ 0 $m(n)\cdot n$ {displaystyle \ $pi}$ { $0}$ { $0}$ 을 $\Pi _{0}$ 출력합니다. $aystyle$ c $(n)\cdot$ T $c(n)\cdot T$ $（$ $T$ \ $displaystyle$ T） $the$ （ $\Pi (n,x)$ , $\Pi (n,x)$ $)$ 의 실행시간이며, 무시해도 될 정도의 $\mu$ (\ displaystyle $\$ $Pi$ ( $n$ , x $)$ 가 $\mu$ 존재하므로 다음 속성이 $유지됩니다.$

정확성: $1-\mu (n)$ $1-\mu (n)$ 의 n개 $(\$ n $\in \mathbb$ { $x\in \{0,1\}^{*}$ $})$ 및 $x\in \{0,1\}^{*}$ $x개$ $displaystyle$ x $\in \{0,1$ 에 대해 $displaystyle 1-\mu(n)$ $\Pi (n,x)=\Pi _{0}(n,x)$ $\Pi (n,x)=\Pi _{0}(n,x)$ , n $\Pi (n,x)=\Pi _{0}(n,x)$ ) $\Pi (n,x)=\Pi _{0}(n,x)$ = DISPLAISPLAY( $\Pi (n,x)=\Pi _{0}(n,x)$ 1 ) $\Pi (n,x)=\Pi _{0}(n,x)$ $x\in \{0,1\}^{*}$
의식하지 않음:임의의 2개의 프로그램 $\Pi _{1},\Pi _{2}$ 1, $\Pi _{1},\Pi _{2}$ 2 $(\$ _{ $1},\Pi$ _{ $2$ $n\in \mathbb {N}$ 의 $(\$ n $\in \mathbb {N})$ 및 $n\in \mathbb {N}$ $x_{1},x_{2}\in \{0,1\}^{*}$ 의 2개의 입력 $x_{1},x_{2}\in \{0,1\}^{*}$ 1, $x_{1},x_{2}\in \{0,1\}^{*}$ $x_{1},x_{2}\in \{0,1\}^{*}$ $x_{1},x_{2}\in \{0,1\}^{*}$ { $,$ $x_{1},x_{2}\in \{0,1\}^{*}$ $x_{1},x_{2}\in \{0,1\}^{*}$ ${\$ { $0},$ {1 $}$ 의 $경우$ ${{Pi$ }} $_{1}(n,$ $x_$ ${1})$ = {{ $tilde {Pi }}_{2}($ ${{\tilde {\Pi }}_{1}}'(n,x_{1})$ , $x_{$ 2}) $}$ ${{\tilde {\Pi }}_{1}}'(n,x_{1})$ ${{\tilde {\Pi }}_{1}}'(n,x_{1})$ 1 ${{\tilde {\Pi }}_{1}}'(n,x_{1})$ 1 1 {\ 1 1 {{ ${{\tilde {\Pi }}_{1}}'(n,x_{1})$ n , ${{\tilde {\Pi }}_{1}}'(n,x_{1})$ 1 ${{\tilde {\Pi }}_{1}}'(n,x_{1})$ ） ${{\tilde {\Pi }}_{1}}'(n,x_{1})$ （ $display$ style ${$ \ $tilde$ { \ Pi $}$ $μstyle$ } ${{\tilde {\Pi }}_{1}}'(n,x_{1})$ $（$ n , $x 1$ ）） μstyle $（$ n ）） {\ $μstyle$ 。 ${\Pi _{1}}'=C(n,\Pi _{1})$ ${\Pi _{1}}'=C(n,\Pi _{1})$ ( $n$ , ${\Pi _{1}}'=C(n,\Pi _{1})$ 1 ) （ \ $displaystyle$ \ $Pi$ _ ${$ 1} ) ${\Pi _{1}}'=C(n,\Pi _{1})$ ${\Pi _{2}}'=C(n,\Pi _{2})$ C ( $n$ , \ $Pi$ ${\Pi _{1}}'=C(n,\Pi _{1})$ _ ${\Pi _{1}}'=C(n,\Pi _{1})$ {1} ) ${\Pi _{2}}'=C(n,\Pi _{2})$ ′ ${\Pi _{2}}'=C(n,\Pi _{2})$ ${\Pi _{2}}'=C(n,\Pi _{2})$ 2 ${\Pi _{2}}'=C(n,\Pi _{2})$ C ( ${\Pi _{2}}'=C(n,\Pi _{2})$ n $,$ ${\Pi _{2}}'=C(n,\Pi _{2})$ ) \ $displaystyle$ \ $Pi$ _ ${2$ } ${\Pi _{2}}'=C(n,\Pi _{2})$ = $C$ ( n , \ $Pi$ _ { $}$ )

위의 정의에서는 통계 보안의 개념을 사용하고 있습니다.컴퓨터 보안의 개념에 대해서도 비슷한 정의를 내릴 수 있다.

ORAM의 이력

ORAM은 Goldreich와 Ostrovsky에^[4] 의해 도입되었습니다.주요 동기는 메모리액세스 패턴을 관찰할 수 있는 상대로부터의 소프트웨어 보호입니다(메모리의 내용은 관찰할 수 없습니다).

이 작업의 주요 결과는 $O(n)$ 컴파일러가 존재하며, ORAM 컴파일러는 O ${O(\log ^{3}n)}$ $n$ 서버 공간을 $O(n)$ 하고 있으며 $,$ $n개의 메모리$ $n$ 을 $n$ 사용하는 프로그램을 인식시키지 못할 때 실행 시간 오버헤드가 $($ ${O(\log ^{3}n)}$ n $)$ { $Displaystyle$ { $O(\log ^{3}}}}}$ 인 ${O(\log ^{3}n)}$ 것입니다.이 작업은 현재까지 진행되고 있는 망각 RAM 구축에 대한 일련의 작업을 시작했다.다양한 ORAM 구성을 비교할 때 고려해야 할 속성이 몇 가지 있습니다.ORAM 구성의 가장 중요한 파라미터는 클라이언트 스토리지의 양, 서버 스토리지의 양, 1개의 메모리에 액세스 할 때의 시간 오버헤드입니다.이러한 속성을 바탕으로 Kushilevitz ^[6]등의 시공이 가장 잘 알려진 ORAM 시공이다.O $)$ { $displaystyle$ O( $1)}$ 클라이언트 $O(1)$ 스토리지, $)$ { $displaystyle$ O( $n)}$ 서버 $O(n)$ 스토리지 $o(\log ^{2}n)$ o( $o(\log ^{2}n)$ 2 $)$ { $displaystyle$ o $(\log ^{2}n)}$ 액세스 $o(\log ^{2}n)$ 오버헤드를 $O(1)$ 합니다.

ORAM 구성의 다른 중요한 속성은 액세스 오버헤드가 상각되었는지 또는 최악의 경우인지를 나타냅니다.이전의 ORAM 구성 중 일부에서는 상각된 접근오버헤드가 양호하지만 최악의 경우 $\Omega (N)$ 접근오버헤드가 $\Omega (N)$ ( $\Omega (N)$ ) \ $displaystyle \ Omega$ ( $N$ ) 。다중 산술적 최악의 경우 계산 오버헤드를 갖는 ORAM 구성 중 일부는 다음과 같습니다.^[6]^[7]^[8]^[9]^[10]의 구성은^[4]^[5]^[1] 랜덤 오라클 모델에 대한 것입니다.여기서 클라이언트는 랜덤 함수처럼 동작하는 오라클에 대한 액세스를 가정하고 반복된 쿼리에 대해 일관된 응답을 반환합니다.또한 단방향 함수의 존재를 가정할 경우 이 오라클은 클라이언트가 저장하는 비밀키인 의사랜덤 함수로 대체될 수 있다는 점에 주목했습니다.그^[11]^[12] 논문은 이 가정을 완전히 제거하는 것을 목표로 했다.의 작성자는^[12] $O(\log ^{3}n)$ O(log $)$ 의 $O(\log ^{3}n)$ 오버헤드(\ $displaystyle$ O $(\log ^{3}n$ 도 달성했습니다.이는 가장 잘 알려진 ORAM 액세스 오버헤드로부터 로그 팩터만 떨어져 있습니다.

이전 연구의 대부분은 보안을 계산적으로 증명하는 데 중점을 두고 있지만, 보안에 대한 보다 강력한 통계적 개념을 사용하는 최신^[3]^[8]^[11]^[12] 연구들이 더 많이 있습니다.

ORAM의 액세스 오버헤드에 관한 기존의 하한 중 하나는 Goldreich 등입니다.^[1]ORAM 액세스 오버헤드의 하한은 $\Omega (\log {n})$ n $\Omega (\log {n})$ )(\ $displaystyle \Omega(\log$ { $n})$ 입니다 $\Omega (\log {n})$ . $n$ 서 n $\displaystyle$ n은 $n$ 데이터 크기입니다.또한 Boyle ^[13]등에 기인하는 ORAM의 접속 오버헤드에 대한 조건부 하한이 있으며, 이 양은 분류 네트워크의 크기와 관련이 있습니다.

ORAM 구성

간단한 구조

읽기 또는 쓰기 조작마다 간단한 ORAM 시뮬레이터 구조는 어레이 내의 모든 요소를 읽고 쓰며, 그 단일 조작으로 지정된 주소에 대해서만 의미 있는 액션을 수행합니다.따라서 간단한 솔루션은 각 작업에 대해 메모리 전체를 스캔합니다.이 방식에서는 각 메모리 동작에 대해 시간 오버헤드가 $\Omega (n)$ ( $\Omega (n)$ ) $\Omega (n)$ \ $displaystyle \ Omega$ ( $n$ ) 。 $여기$ 서 n은 메모리의 크기입니다.

간단한 ORAM 스킴

Jung and^[3] Pass에 의해 구축된 통계적으로 안전한 ORAM 컴파일러의 간단한 버전은 그 정확성 증명에 대한 개요와 함께 아래에 설명되어 있습니다. $입력$ n의 컴파일러와 메모리 $요건$ n의 프로그램 $δ$ 는 동등한 망각 프로그램 $δ$ 를 출력한다.

입력 프로그램 $π$ 이 r 레지스터를 $사용$ 하는 경우 출력 프로그램 $n$ $r+n/{\alpha }+{\text{poly}}\log {n}$ 、 r + $r+n/{\alpha }+{\text{poly}}\log {n}$ / $r+n/{\alpha }+{\text{poly}}\log {n}$ + $r+n/{\alpha }+{\text{poly}}\log {n}$ log $r+n/{\alpha }+{\text{poly}}\log {n}$ n \ $displaystyle$ r + $n$ / { \ $alpha$ } + { \ $text$ { $poly$ } \ $log$ { $n$ } 레지스터가 $r+n/{\alpha }+{\text{poly}}\log {n}$ $r+n/{\alpha }+{\text{poly}}\log {n}$ 합니다. $\alpha >1$ 서 $\alpha >1$ $\alpha >1$ { $displaystyle$ \ $alpha$ > $\alpha >1$ 1 $}$ 은 $\alpha >1$ 파라미터입니다. $O(n{\text{ poly}}\log n)$ 、 $O$ （ $O(n{\text{ poly}}\log n)$ poly $nn$ ） { displaystyle $O$ ( n { \ $text$ { $poly$ } \ $O(n{\text{ poly}}\log n)$ log n $O(n{\text{ poly}}\log n)$ )메모리를 사용하며 $O(n{\text{ poly}}\log n)$ 그 (최악의 경우) $O({\text{poly}}\log n)$ 오버헤드는 $O$ ( $O({\text{poly}}\log n)$ poly $O({\text{poly}}\log n)$ n n ) { \ displaystyle $O$ ( ${ poly$ } \ $log$ n ) $O({\text{poly}}\log n)$ } \ log n } } 입니다.

ORAM 컴파일러는 설명하기가 매우 간단합니다.Suppose that the original program $Π$ has instructions for basic mathematical and control operations in addition to two special instructions ${\mathsf {read}}(l)$ and ${\mathsf {write}}(l,v)$ , where ${\mathsf {read}}(l)$ reads $location$ l 및 ${\mathsf {write}}(l,v)$ ${\mathsf {write}}(l,v)$ ${\mathsf {write}}(l,v)$ e ${\mathsf {write}}(l,v)$ , v ${\mathsf {write}}(l,v)$ )의 값({displaystyle ${mathsf {write}}(l,v)})$ 은 ${\mathsf {write}}(l,v)$ $값$ v를 $l$ 에 씁니다.ORAM 컴파일러는 $δ$ 를 구성할 때 각 읽기 및 쓰기 명령을 서브루틴 Oread 및 Owrite로 대체하고 나머지 프로그램을 동일하게 유지합니다.이 구조는 온라인상의 메모리 요구에도 대응할 수 있다는 점에 주의해 주십시오.

ORAM 컴파일러는 원래 프로그램의 읽기 및 쓰기 명령을 서브루틴 Oread 및 Owrite로 대체합니다.

인식되지 않는 프로그램의 메모리 구성

$d=\log(n/\alpha )$ $δ$ 는 깊이 d $=$ $d=\log(n/\alpha )$ δ ( $d=\log(n/\alpha )$ / α ) { $displaystyle$ d=\ $log(n/\alpha )}$ 의 $d=\log(n/\alpha )$ 완전한 이진 $트리$ T를 메모리에 저장합니다. $T$ 의 각 노드는 $최대$ d의 길이의 이진 문자열로 나타납니다.root은 빈 문자열로, "로 나타납니다. $\gamma$ $"\displaystyle \gamma"$ 로 $\gamma$ 표시되는 노드의 왼쪽 자녀와 오른쪽 자녀는 각각 0 $(\$ _ ${0})$ 및 $\gamma _{0}$ $(\$ _{ $1})$ 입니다 $\gamma _{1}$ .프로그램 $δ$ 는 $δ$ 의 메모리를 블록으로 분할한 것으로 간주하며, 각 블록은 $크기$ α의 메모리 셀의 연속된 시퀀스입니다. $\lceil n/\alpha \rceil$ $\lceil n/\alpha \rceil$ 에는 최대 $\lceil n/\alpha \rceil$ n $\lceil n/\alpha \rceil$ / α 블록 $(\displaystyle \lceil$ n $/\alpha \rceil)$ 이 $\lceil n/\alpha \rceil$ 있습니다.즉, 메모리 $셀$ r은 $b=\lfloor r/\alpha \rfloor$ b $=$ r / α $⌋$ { $displaystyle$ b =\ $lfloor r/\$ alpha \ $loor$ 에 대응합니다.

어느 시점에서도 $T$ 의 블록과 잎 사이에는 관련성이 있습니다. $이$ 관련성을 추적하기 위해 O ( n / $O(n/\alpha )$ ) \ $displaystyle$ O ( $n$ / \ $alpha )$ 레지스터를 $O(n/\alpha )$ $O(n/\alpha )$ 하여P $os$ \ $display style$ Pos $Pos$ 라고 $불리는$ 데이터 구조도 저장합니다.이 데이터 구조에서는 각 $블록$ b에 대해 $b$ 와 $관련된T$ 의 리프가 $Pos(b)$ s ( $Pos(b)$ )\ $display style$ Pos ( $b$ 에 저장됩니다.

$T$ 의 각 노드는 $최대$ K개의 트리플을 가진 어레이를 포함합니다.각 트리플은 ( $(b,Pos(b),v)$ , $(b,Pos(b),v)$ ( $(b,Pos(b),v)$ ) , $(b,Pos(b),v)$ ) { $displaystyle ( b$ , $Pos$ ( $b$ , $v$ 형식입니다. $여기$ 서 b는 블록 $식별자$ , v는 블록의 내용입니다. $여기$ 서 K는 보안 파라미터로 O $O({\text{poly}}\log n)$ log $){$ $displaystyle$ O $({\text{poly}}\log$ n $O({\text{poly}}\log n)$ 입니다.

바이너리 트리 및 위치 맵을 나타내는 망각 프로그램의 메모리 그림.

인식되지 않는 프로그램에 대한 설명

프로그램 $π$ 은 메모리 초기화 및⊥에 등록하는 것으로 시작합니다.Owrite와 Oread의 순서를 설명하면, $「」$ 의 설명이 완료됩니다.서브루틴 Owrite는 다음과 같습니다.서브루틴에 대한 입력은 메모리 $l\in [n]$ l $l\in [n]$ [ $]{$ $displaystyle$ l $\in$ [ $n$ ]및 $l\in [n]$ $위치$ l에 저장되는 값 $v$ 입니다.여기에는 FETCH, PUT_BACK 및 FLUSH의 3가지 주요 단계가 있습니다.

입력:  $위치$  l, 값  $v$

순서 FETCH // 필요한 블록을 검색합니다. $b$   $b\leftarrow \lfloor l/\alpha \rfloor$   $b\leftarrow \lfloor l/\alpha \rfloor$ /  $b\leftarrow \lfloor l/\alpha \rfloor$  \  $displaystyle$  b \  $lfloor$ l /\ $pos\leftarrow Pos(b)$  $b\leftarrow \lfloor l/\alpha \rfloor$ \  $lfloor$ } //  $i\leftarrow l\mod \alpha$ 는 l.  $i\leftarrow l\mod \alpha$  ←  $i\leftarrow l\mod \alpha$ mod $i\leftarrow l\mod \alpha$ α {  $style$  i $\mod$  \alpha $i\leftarrow l\mod \alpha$ } //  $i$ 는  $pos\leftarrow Pos(b)$ p  $i\leftarrow l\mod \alpha$   $displaystyledisplay$  style p  $←$  s )의 l 컴포넌트입니다. $pos=\perp$   $pos=\perp$  s $pos=\perp$ relf {  $displaystyle$  pos = \ $perp$  $}$ 이면 $pos=\perp$   $pos\leftarrow _{R}[n/\alpha ]$   $pos\leftarrow _{R}[n/\alpha ]$  s  $\leftarrow 0$  $pos\leftarrow _{R}[n/\alpha ]$ R [ $n$ / $α ]$  {  $displaystyle$  $pos$  $}$ . // 루트 $P$ 의  $각$   $노드$ 에 대해 t.  $플래그$   $=$  $\leftarrow 0$ 0(\ $displaystyle$ \ $left$   $arrow$  0 $\leftarrow 0$ 으로 $pos$   $설정$ 합니다.pos $}$ 는 $pos$  N이 3중 형식 $(b,pos,x)$  ,  $(b,pos,x)$  , $(b,pos,x)$ x $(b,pos,x)$ ) { $displaystyle ( b$  , $(b,pos,x)$  , $x$  ) { $displaystyle$ ( $b$ ,  $pos$ , $x )}$ 을 $(b,pos,x)$  $(b,pos,x)$  $(b,pos,x)$ 를 $(b,pos,x)$  N에서  $삭제$ 하고 x를  $레지스터$ 에 저장한 후  $업데이트$ 된 N을 T. flag  $←$   $\leftarrow 1$  { $styleft arrow$ 1 $\leftarrow 1$ 에  $씁니다$ . $N$ 을 T로  $되돌립니다$ .절차 PUT_BACK // 업데이트된 블록을 루트에 다시 추가합니다.  $pos'\leftarrow _{R}[n/\alpha ]$   $pos'\leftarrow _{R}[n/\alpha ]$  s  $pos'\leftarrow _{R}[n/\alpha ]$  [ $pos'\leftarrow _{R}[n/\alpha ]$  /  $α ]$  \  $left arrow$  _  ${ R$ } [ n / \ alpha  $]$ . // 플래그  $=1$  \  $display style =$ 1 \ display style $=1$ }인 경우 po s′ \  $display$  x $'$ 로 $pos'$   $설정$ 합니다 $.$ i번째 위치에 있는 v를  $제외$ 하고. $그렇지$  않으면 x{\({ $displaystyle$  x $')$ 를 $x'$  블록으로  $설정$ 하고 v를 i번째 위치에 두고  $'$ 의 블록을 설정합니다.루트에 공간이 남아 있는 경우 T의  $루트$ 에 트리플 $(b,pos',x')$   $(b,pos',x')$ ,  $(b,pos',x')$  s $(b,pos',x')$ " ,  $(b,pos',x')$  "  $displaystyle$  ( b ,  $pos$ ' , x ' )를 추가합니다 $.$ 그렇지 $(b,pos',x')$  않으면 출력 오버플을 중단합니다.순서 FLUSH // 랜덤 패스에 존재하는 블록을 가능한 한 아래로 밀어냅니다. $pos^{*}\leftarrow _{R}[n/\alpha ]$  o  $pos^{*}\leftarrow _{R}[n/\alpha ]$   $pos^{*}\leftarrow _{R}[n/\alpha ]$ [  $pos^{*}\leftarrow _{R}[n/\alpha ]$  / $α$ ] \ left  $화살표 _$ {  $R$ } [ $n$  / \ alpha $pos^{*}\leftarrow _{R}[n/\alpha ]$ ] $pos^{*}\leftarrow _{R}[n/\alpha ]$ } . //  $pos^{*}$   $pos^{*}$  s $pos^{*}$  \  $displaystyle$   $(b'',pos'',v'')$  $^$  { * }  $pos^{*}$  、 $(b'',pos'',v'')$ triple b $(b'',pos'',v'')$ 、 $(b'',pos'',v'')$  s  $(b'',pos'',v'')$  for for for for for for for for for for for for for for for for for for for for 。 $root$ 에서  $pos^{*}$  s로의 패스를 횡단한 노드의 $(b'',pos'',v'')$  , v $(b'',pos'',v'')$ " $pos^{*}$ } $pos^{*}$ 。{  $displaystyle$ pos $pos^{*}$  $^$  $pos^{*}$ { * } 。버킷이 오버플로우 될 것 같으면 p  $pos^{*}$  s" $pos^{*}$ 및 $pos''$  p o s "의  $가장$   $pos^{*}$  공통 프레픽스에 대응하는  $노드N$ 까지 이 트리플을 누릅니다.hen 출력 오버플로우를 중단합니다.

FETCH 단계의 작업은 $트리$ T에서 $위치l$ 을 찾는 것입니다. $p$ $o$ s\ $displaystyle$ posthe $pos$ location l을 $포함$ 하는 블록과 관련된 리프라고 가정합니다.루트에서 $p$ $o$ s $displaystyle$ pos로의 $경로$ 상의 T in $T$ 의 각 $노드$ N에 대해 이 절차는 $N$ 의 모든 트리플을 검토하고 l을 $포함$ 하는 블록에 대응하는 트리플을 찾습니다. $N$ 에서 트리플이 검출되면 $N$ 에서 트리플을 삭제하고 업데이트된N $상태$ 를 다시 씁니다.그렇지 않으면 $노드$ N 전체를 다시 쓸 뿐입니다.

다음 단계에서는 l을 $포함$ 하는 블록을 새로운 $값$ v로 업데이트하고 해당 블록을 트리의 균등하게 랜덤하게 샘플링된 신규 리프와 관련지어 업데이트된 트리플을 $T$ 의 루트에 다시 씁니다.

마지막 단계인 FLUSH는 루트 및 기타 상위 내부 노드에서 메모리 셀을 해제하기 위한 추가 작업입니다.특히 알고리즘은 균등하게 랜덤 $pos^{*}$ p $pos^{*}$ s $pos^{*}$ " $pos^{*}$ {\ $displaystyle$ pos $^{*}}$ 를 선택하고 $pos^{*}$ 부터 p $pos^{*}$ s $pos^{*}$ " " {\ $displaystyle$ pos $pos^{*}$ 에 $pos^{*}$ 이르는 경로를 따라 모든 노드를 최대한 밀어내려고 합니다.어떤 시점에서 버킷이 용량을 초과하려고 하면 오버플로우 출력이 중단됩니다.

서브루틴 Oread는 Owrite와 비슷합니다.Oread 서브루틴의 경우 입력은 메모리 $l\in [n]$ l $l\in [n]$ [ $l\in [n]$ ](\ $displaystyle l\in$ [n $])$ 일 $l\in [n]$ 뿐이며 Owrite와 거의 동일합니다.FETCH 스테이지에서 $위치$ l에 대응하는 트리플이 발견되지 않으면 $위치$ l의 값으로θ를 반환한다.PUT_BACK 단계에서는 새로 샘플링된 균일한 랜덤 리프와 관련지은 후 읽은 블록과 동일한 블록을 루트에 다시 씁니다.

단순 ORAM 방식의 정확성

$C$ 는 위에서 설명한 ORAM 컴파일러를 나타냅니다. $프로그램$ , a $denote$ 、 C $C(\Pi )$ ( $π$ ) \ $displaystyle$ C ( \ $C(\Pi )$ ) $C(\Pi )$ . 、 $\Pi (n,x)$ $\Pi (n,x)$ n , $\Pi (n,x)$ x $\Pi (n,x)$ ) \ $displaystyle \ Pi$ ( $n$ , $x$ )는 $\Pi (n,x)$ n개의 메모리 셀을 $사용$ 하여 $입력x$ 상에서 프로그램 $on$ 를 실행하는 것을 나타냅니다. ${\tilde {\Pi }}(n,x)$ , ${\tilde {\Pi }}(n,x)$ ~ ${\tilde {\Pi }}(n,x)$ ( n ${\tilde {\Pi }}(n,x)$ , x $){$ $displaystyle$ { $tilde$ { Pi $}($ $\Pi (n,x)$ ${\tilde {\Pi }}(n,x)$ , x )은 ${\tilde {\Pi }}(n,x)$ $\Pi (n,x)$ ( $\Pi (n,x)$ , $\Pi (n,x)$ x $){$ $displaystyle \$ Pi ( $n$ , $x$ $\Pi (n,x)$ 의 메모리액세스 패턴을 나타냅니다. $μ$ 는 n $n\in \mathbb {N}$ N $n\in \mathbb {N}$ n \ $displaystyle$ n \ $in$ \ $mathbbb {$ N } $}$ 및 $프로그램$ 에 대해 다음과 같은 함수를 나타냅니다. $\Pi '(n,x)$ $\Pi '(n,x)$ $\Pi '(n,x)$ $\Pi '(n,x)$ , $\Pi '(n,x)$ ) { $displaystyle \Pi$ ' ( $n$ , $\Pi '(n,x)$ x )가 오버플로우를 출력할 확률은 $\mu (n)$ μ ( $\mu (n)$ ) $\mu (n)$ \ $displaystyle \ mu$ ( $n$ ) $\mu (n)$ 。다음 $약어$ 는 C의 설명에서 쉽게 알 수 있습니다.

등가 보조항: $(\$ $displaystyle$ n $\$ $in$ $\mathbb$ { $x\in \{0,1\}^{*}$ $})$ 및 $x\in \{0,1\}^{*}$ $1-\mu (n)$ $,$ 1 $1-\mu (n)$ $x\in \{0,1\}^{*}$ 로 $n\in \mathbb {N}$ . $프로그램$ $Ω$ 을 지정하면 1μ $($ $\Pi '(n,x)$ $displaystyle 1-\mu$ $\Pi '(n,x)$ $n$ $)$ $1-\mu (n)$ )의 $출력$ 입니다 $\Pi '(n,x)$ $\Pi (n,x)$ 를 클릭합니다.

각 Owrite 및 Oread 조작은 랜덤으로 균일하고 독립적으로 선택된T $내$ 의 루트에서 리프 경로를 통과하는 것을 쉽게 알 수 있습니다.이 사실은 같은 수의 메모리액세스를 하는 두 프로그램의 메모리액세스 패턴 분포가 둘 다 오버플로하지 않는 한 구별할 수 없음을 의미합니다.

망각 보조군: 2개의 프로그램 $\Pi _{1}$ 1 { $displaystyle$ \ $Pi$ _ { $\Pi _{1}$ 1 $\Pi _{1}$ } $\Pi _{2}$ $\Pi _{2}$ \ $displaystyle$ \ $Pi$ _ { 2 $\Pi _{2}$ } $\Pi _{2}$ {\ 2개의 $x_{1},x_{2}\in \{0,1\}^{*}$ x $x_{1},x_{2}\in \{0,1\}^{*}$ , x $|{\tilde {\Pi _{1}}}(x_{1},n)|=|{\tilde {\Pi _{2}}}(x_{2},n)|$ $x_{1},x_{2}\in \{0,1\}^{*}$ { $x_{1},x_{2}\in \{0,1\}^{*}$ , $x_{1},x_{2}\in \{0,1\}^{*}$ } ${\$ \ $displaystyle x_{1}$ \ $in$ \ { $0$ , $|{\tilde {\Pi _{1}}}(x_{1},n)|=|{\tilde {\Pi _{2}}}(x_{2},n)|$ \ 1 \ $|{\tilde {\Pi _{1}}}(x_{1},n)|=|{\tilde {\Pi _{2}}}(x_{2},n)|$ }^*} $x_{1},x_{2}\in \{0,1\}^{*}$ such $x_{1},x_{2}\in \{0,1\}^{*}$ 2개의 입력이 주어지면 $|{\tilde {\Pi _{1}}}(x_{1},n)|=|{\tilde {\Pi _{2}}}(x_{2},n)|$ 1 $|{\tilde {\Pi _{1}}}(x_{1},n)|=|{\tilde {\Pi _{2}}}(x_{2},n)|$ ~ $|{\tilde {\Pi _{1}}}(x_{1},n)|=|{\tilde {\Pi _{2}}}(x_{2},n)|$ 이 됩니다 $|{\tilde {\Pi _{1}}}(x_{1},n)|=|{\tilde {\Pi _{2}}}(x_{2},n)|$ $= {\$ $tilde$ { $Pi$ _ {2 $}}($ $x_$ ${2},$ n $|{\tilde {\Pi _{1}}}(x_{1},n)|=|{\tilde {\Pi _{2}}}(x_{2},n)|$ $displaystyle$ ${\tilde {\Pi _{1}'}}(x_{1},n)$ $\mu$ (n ${\tilde {\Pi _{1}'}}(x_{1},n)$ $1-2\mu (n)$ {\displaystyle $1$ ~ ( $1,$ n) {\ $displaystyle$ {{1}} {{ $n}$ 및 ${\tilde {\Pi _{2}'}}(x_{2},n)$ $|{\tilde {\Pi _{1}}}(x_{1},n)|=|{\tilde {\Pi _{2}}}(x_{2},n)|$ $。$

다음 조항에 따라 ORAM 스킴의 올바른 증명서가 완성됩니다.

오버플로우 보조항: $모든$ 프로그램 $δ$ , $모든$ n 및 $입력$ x에 대해 프로그램 $\Pi '(n,x)$ ( n , $\Pi '(n,x)$ ) { $displaystyle \Pi$ ' ( $n$ , $x$ ) } 출력 $\Pi '(n,x)$ 오버플로우 $\mu (n)$ 이 μ $\mu (n)$ ( $\mu (n)$ , x ) \ $displaystyle$ \ $mu$ ( $\mu (n)$ n ) $\mu (n)$ } { $displaystyle$ \ mu ( n ) } 。

계산 및 메모리 오버헤드

각 Oread 및 Owrite 동작 중에 $T$ 의 2개의 랜덤루트부터 리프까지의 패스가 $δ$ 에 의해 완전히 조사됩니다. $O(K\cdot \log(n/\alpha ))$ $O(K\cdot \log(n/\alpha ))$ 에는 O $O(K\cdot \log(n/\alpha ))$ K $O(K\cdot \log(n/\alpha ))$ $O(K\cdot \log(n/\alpha ))$ $O(K\cdot \log(n/\alpha ))$ ( $O(K\cdot \log(n/\alpha ))$ / $O(K\cdot \log(n/\alpha ))$ ) $O(K\cdot \log(n/\alpha ))$ { $displaystyle$ O ( $K$ \ $cdot \ log$ ( $n$ / \ $alpha )$ } 시간이 $O(K\cdot \log(n/\alpha ))$ 걸립니다.이는 계산 오버헤드와 동일하며 $O({\text{poly}}\log n)$ 는 O $O({\text{poly}}\log n)$ 로그 $O({\text{poly}}\log n)$ 이므로 $O$ $O({\text{poly}}\log n)$ 로그 $O({\text{poly}}\log n)$ $O({\text{poly}}\log n)$ $O({\text{poly}}\log n)$ {\ $displaystyle$ O $({\text{poly}\log$ n $O({\text{poly}}\log n)$ 입니다 $O({\text{poly}}\log n)$ .

$π$ is가 사용하는 메모리의 $합계$ 는 T 사이즈와 동일합니다.트리에 저장된 각 트리플에는 $\alpha +2$ α + $\alpha +2$ $displaystyle$ $\alpha +$ $K(\alpha +2)$ ) $\alpha +2$ 워드가 $\alpha +2$ $\alpha +2$ 있습니다.따라서 트리의 노드당 $K(\alpha +2)$ K $(\alpha$ + $K(\alpha +2)$ 2) $K(\alpha +2)$ 워드가 $K(\alpha +2)$ .트리의 노드 총수는 $O(n/\alpha )$ ( $O(n/\alpha )$ / $O(n/\alpha )$ α $){$ $displaystyle$ O ( $n$ / \ $alpha$ ) $O(n/\alpha )$ $O(n{\text{ poly}}\log n)$ 이므로 메모리의 총 사이즈는 $O(nK)$ O $O(n{\text{ poly}}\log n)$ ( $O(nK)$ K $){$ $displaystyle$ $O(nK)$ O ( $n$ $O(nK)$ / $text {$ } \ $log$ )입니다 $O(nK)$ .즉, O ( $O(n{\text{ poly}}\log n)$ $O(n{\text{ poly}}\log n)$ log $O(n{\text{ poly}}\log n)$ ) $그래서$ 메모리의 오버헤드가 $O({\text{poly}}\log n)$ . $\text{poly}\log$ n $O({\text{poly}}\log n)$

레퍼런스

^ ^a ^b ^c ^d ^e Goldreich, Oded; Ostrovsky, Rafail (1996), "Software protection and simulation on oblivious RAMs", Journal of the ACM, 43 (3): 431–473, doi:10.1145/233551.233553, hdl:1721.1/103684, MR 1408562
^ Pippenger, Nicholas; Fischer, Michael J. (1979), "Relations among complexity measures", Journal of the ACM, 26 (2): 361–381, doi:10.1145/322123.322138, MR 0528038
^ ^a ^b ^c Chung, Kai-Min; Pass, Rafael (2013), "A simple ORAM", IACR Cryptology ePrint Archive
^ ^a ^b Goldreich, Oded (1987), "Towards a theory of software protection and simulation by oblivious RAMs", in Aho, Alfred V. (ed.), Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC '87), Association for Computing Machinery, pp. 182–194, doi:10.1145/28395.28416
^ ^a ^b Ostrovsky, Rafail (1990), "Efficient computation on oblivious RAMs", Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC '90), Association for Computing Machinery, pp. 514–523, doi:10.1145/100216.100289
^ ^a ^b Kushilevitz, Eyal; Lu, Steve; Ostrovsky, Rafail (2012), "On the (in)security of hash-based oblivious RAM and a new balancing scheme", Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 143–156, doi:10.1137/1.9781611973099.13, MR 3205204
^ Ostrovsky, Rafail; Shoup, Victor (1997), "Private information storage (extended abstract)", in Leighton, F. Thomson; Shor, Peter W. (eds.), Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing (STOC '97), Association for Computing Machinery, pp. 294–303, doi:10.1145/258533.258606
^ ^a ^b Shi, Elaine; Chan, T.-H. Hubert; Stefanov, Emil; Li, Mingfei (2011), "Oblivious RAM with $O((\log N)^{3})$ worst-case cost", in Lee, Dong Hoon; Wang, Xiaoyun (eds.), Advances in Cryptology – ASIACRYPT 2011 – 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4–8, 2011, Proceedings, Lecture Notes in Computer Science, vol. 7073, Springer, pp. 197–214, doi:10.1007/978-3-642-25385-0_11
^ Goodrich, Michael T.; Mitzenmacher, Michael; Ohrimenko, Olga; Tamassia, Roberto (2011), "Oblivious RAM simulation with efficient worst-case access overhead", in Cachin, Christian; Ristenpart, Thomas (eds.), Proceedings of the 3rd ACM Cloud Computing Security Workshop, CCSW 2011, Chicago, IL, USA, October 21, 2011, Association for Computing Machinery, pp. 95–100, doi:10.1145/2046660.2046680
^ Chung, Kai-Min; Liu, Zhenming; Pass, Rafael (2014), "Statistically-secure ORAM with ${\tilde {O}}(\log ^{2}n)$ overhead", in Sarkar, Palash; Iwata, Tetsu (eds.), Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014, Proceedings, Part II, Lecture Notes in Computer Science, vol. 8874, Springer, pp. 62–81, doi:10.1007/978-3-662-45608-8_4
^ ^a ^b Ajtai, Miklós (2010), "Oblivious RAMs without cryptographic assumptions [extended abstract]", Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), Association for Computing Machinery, pp. 181–190, doi:10.1145/1806689.1806716, MR 2743267
^ ^a ^b ^c Damgård, Ivan; Meldgaard, Sigurd; Nielsen, Jesper Buus (2011), "Perfectly secure oblivious RAM without random oracles", in Ishai, Yuval (ed.), Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 2011, Proceedings, Lecture Notes in Computer Science, vol. 6597, Springer, pp. 144–163, doi:10.1007/978-3-642-19571-6_10
^ Boyle, Elette; Naor, Moni (2016), "Is there an oblivious RAM lower bound?", Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS '16), Association for Computing Machinery, pp. 357–368, doi:10.1145/2840728.2840761, MR 3629839

「」를 참조해 주세요.

[GO96-1] Goldreich, Oded; Ostrovsky, Rafail (1996), "Software protection and simulation on oblivious RAMs", Journal of the ACM, 43 (3): 431–473, doi:10.1145/233551.233553, hdl:1721.1/103684, MR 1408562

[2] Pippenger, Nicholas; Fischer, Michael J. (1979), "Relations among complexity measures", Journal of the ACM, 26 (2): 361–381, doi:10.1145/322123.322138, MR 0528038

[CP13-3] Chung, Kai-Min; Pass, Rafael (2013), "A simple ORAM", IACR Cryptology ePrint Archive

[G87-4] Goldreich, Oded (1987), "Towards a theory of software protection and simulation by oblivious RAMs", in Aho, Alfred V. (ed.), Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC '87), Association for Computing Machinery, pp. 182–194, doi:10.1145/28395.28416

[O90-5] Ostrovsky, Rafail (1990), "Efficient computation on oblivious RAMs", Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC '90), Association for Computing Machinery, pp. 514–523, doi:10.1145/100216.100289

[KLO12-6] Kushilevitz, Eyal; Lu, Steve; Ostrovsky, Rafail (2012), "On the (in)security of hash-based oblivious RAM and a new balancing scheme", Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 143–156, doi:10.1137/1.9781611973099.13, MR 3205204

[OS97-7] Ostrovsky, Rafail; Shoup, Victor (1997), "Private information storage (extended abstract)", in Leighton, F. Thomson; Shor, Peter W. (eds.), Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing (STOC '97), Association for Computing Machinery, pp. 294–303, doi:10.1145/258533.258606

[SCSL11-8] Shi, Elaine; Chan, T.-H. Hubert; Stefanov, Emil; Li, Mingfei (2011), "Oblivious RAM with $O((\log N)^{3})$ worst-case cost", in Lee, Dong Hoon; Wang, Xiaoyun (eds.), Advances in Cryptology – ASIACRYPT 2011 – 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4–8, 2011, Proceedings, Lecture Notes in Computer Science, vol. 7073, Springer, pp. 197–214, doi:10.1007/978-3-642-25385-0_11

[GMOT11-9] Goodrich, Michael T.; Mitzenmacher, Michael; Ohrimenko, Olga; Tamassia, Roberto (2011), "Oblivious RAM simulation with efficient worst-case access overhead", in Cachin, Christian; Ristenpart, Thomas (eds.), Proceedings of the 3rd ACM Cloud Computing Security Workshop, CCSW 2011, Chicago, IL, USA, October 21, 2011, Association for Computing Machinery, pp. 95–100, doi:10.1145/2046660.2046680

[CLP14-10] Chung, Kai-Min; Liu, Zhenming; Pass, Rafael (2014), "Statistically-secure ORAM with ${\tilde {O}}(\log ^{2}n)$ overhead", in Sarkar, Palash; Iwata, Tetsu (eds.), Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014, Proceedings, Part II, Lecture Notes in Computer Science, vol. 8874, Springer, pp. 62–81, doi:10.1007/978-3-662-45608-8_4

[A10-11] Ajtai, Miklós (2010), "Oblivious RAMs without cryptographic assumptions [extended abstract]", Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), Association for Computing Machinery, pp. 181–190, doi:10.1145/1806689.1806716, MR 2743267

[DMN11-12] Damgård, Ivan; Meldgaard, Sigurd; Nielsen, Jesper Buus (2011), "Perfectly secure oblivious RAM without random oracles", in Ishai, Yuval (ed.), Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 2011, Proceedings, Lecture Notes in Computer Science, vol. 6597, Springer, pp. 144–163, doi:10.1007/978-3-642-19571-6_10

[BN16-13] Boyle, Elette; Naor, Moni (2016), "Is there an oblivious RAM lower bound?", Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS '16), Association for Computing Machinery, pp. 357–368, doi:10.1145/2840728.2840761, MR 3629839

[1]

[2]

[4]

[6]

[7]

[8]

[9]

[10]

[5]

[11]

[12]

[3]

[13]

Search

망각 RAM

네임스페이스

더

목차

정의.

ORAM의 이력