Nezapomenutelná RAM - Oblivious RAM - Wikipedia

An zapomnětlivý simulátor RAM (ORAM) je překladač který se transformuje algoritmy takovým způsobem, aby výsledné algoritmy zachovaly vstup -výstup chování původního algoritmu, ale rozdělení z Paměť přístupový vzor transformovaného algoritmu je nezávislý na přístupovém vzoru paměti původního algoritmu. Definice ORAM je motivována skutečností, že protivník může získat netriviální informace o provádění programu a povaze data s nimiž se potýká, pouhým pozorováním vzoru, ve kterém se během jejího provádění přistupuje k různým umístěním paměti. Protivník může získat tyto informace, i když jsou hodnoty dat všechny šifrované. Definice se hodí stejně dobře jako nastavení chráněných programů běžících na nechráněných sdílená paměť stejně jako klient běžící na svém systému přístupem k dříve uloženým datům v a vzdálený server. Koncept byl formulován Oded Goldreich v roce 1987.^[1]

Definice

A Turingův stroj TM je matematická abstrakce skutečného počítače (programu) zapomíná pokud u jakýchkoli dvou vstupů stejné délky zůstávají pohyby hlav pásky stejné. Pippenger a Fischer^[2] dokázal, že každá TM s dobou chodu ${ displaystyle T (n)}$ lze zapomenout a že doba provozu zapomnětlivé TM je ${ displaystyle O (T (n) log T (n))}$ . Realističtější model výpočtu je RAM model. V modelu výpočtu RAM existuje a procesor které mohou provádět základní matematické, logické a řídicí pokyny. CPU je také spojen s několika registry a fyzický náhodný přístup Paměť, kde ukládá operandy svých pokynů. CPU má navíc pokyny ke čtení obsahu paměťové buňky a zápisu konkrétní hodnoty do paměťové buňky. Definice ORAM zachycuje podobný pojem obliviousness přístupů do paměti v tomto modelu.

ORAM je neformálně algoritmus na rozhraní chráněného CPU a fyzické RAM, takže se chová jako RAM pro CPU dotazem na fyzickou RAM pro CPU, zatímco skrývá informace o skutečném vzoru přístupu k paměti CPU z fyzická RAM. Jinými slovy, distribuce přístupů do paměti dvou programů, které zajišťují stejný počet přístupů do paměti RAM, je od sebe nerozeznatelná. Tento popis bude mít smysl, pokud CPU nahradí klient s malým úložištěm a fyzická paměť RAM bude nahrazena vzdáleným serverem s velkou úložnou kapacitou, kde jsou uložena data klienta.

Následuje formální definice ORAMů.^[3] Nechat ${ displaystyle Pi}$ označují program vyžadující paměť velikosti ${ displaystyle n}$ při provádění na vstupu ${ displaystyle x}$ . Předpokládejme to ${ displaystyle Pi}$ má kromě dvou speciálních pokynů také pokyny pro základní matematické a řídicí operace ${ displaystyle { mathsf {číst}} (l)}$ a ${ displaystyle { mathsf {write}} (l, v)}$ , kde ${ displaystyle { mathsf {číst}} (l)}$ přečte hodnotu na místě ${ displaystyle l}$ a ${ displaystyle { mathsf {write}} (l, v)}$ zapíše hodnotu ${ displaystyle v}$ na ${ displaystyle l}$ . Posloupnost paměťové buňky přístupné programem ${ displaystyle Pi}$ během jeho provádění se nazývá jeho vzor přístupu do paměti a je označen ${ displaystyle { tilde { Pi}} (n, x)}$ .

A algoritmus polynomiálního času, ${ displaystyle C}$ je kompilátor Oblivious RAM (ORAM) s výpočetní režií ${ displaystyle c ( cdot)}$ a paměť nad hlavou ${ displaystyle m ( cdot)}$ , pokud ${ displaystyle C}$ daný ${ displaystyle n v N}$ a a deterministický program RAM ${ displaystyle Pi}$ s velikostí paměti ${ displaystyle n}$ výstup programu ${ displaystyle Pi _ {0}}$ s velikostí paměti ${ displaystyle m (n) cdot n}$ takový, že pro jakýkoli vstup ${ displaystyle x}$ , doba provozu ${ displaystyle Pi _ {0} (n, x)}$ je ohraničen ${ displaystyle c (n) cdot T}$ kde ${ displaystyle T}$ je doba běhu ${ displaystyle Pi (n, x)}$ , a existuje a zanedbatelná funkce ${ displaystyle mu}$ takové, že platí následující vlastnosti:

Správnost: Pro všechny ${ displaystyle n in mathbb {N}}$ a jakýkoli řetězec ${ displaystyle x in {0,1 } ^ {*}}$ alespoň s pravděpodobností ${ displaystyle 1- mu (n)}$ , ${ displaystyle Pi (n, x) = Pi _ {0} (n, x)}$ .
Zapomenutí: Pro libovolné dva programy ${ displaystyle Pi _ {1}, Pi _ {2}}$ , jakýkoli ${ displaystyle n in mathbb {N}}$ a jakékoli dva vstupy, ${ displaystyle x_ {1}, x_ {2} in {0,1 } ^ {*}}$ -li ${ displaystyle | { tilde { Pi}} _ {1} (n, x_ {1}) | = | { tilde { Pi}} _ {2} (n, x_ {2}) |}$ , pak ${ displaystyle {{ tilde { Pi}} _ {1}} '(n, x_ {1})}$ je ${ displaystyle mu}$ -blízko k ${ displaystyle {{ tilde { Pi}} _ {2}} '(n, x_ {2})}$ v statistická vzdálenost, kde ${ displaystyle { Pi _ {1}} '= C (n, Pi _ {1})}$ a ${ displaystyle { Pi _ {2}} '= C (n, Pi _ {2})}$ .

Všimněte si, že výše uvedená definice používá pojem statistická bezpečnost. Podobně lze definovat i pojem výpočetní bezpečnost.

Historie ORAMů

ORAM byly zavedeny Goldreich a Ostrovský^[1]^[4]^[5] přičemž klíčová motivace byla uvedena jako ochrana softwaru před protivníkem, který dokáže pozorovat vzorec přístupu do paměti (ale ne obsah paměti).

Hlavní výsledek této práce^[5] je, že existuje kompilátor ORAM, který používá ${ displaystyle O (n)}$ prostoru serveru a vznikne režijní doba běhu ${ displaystyle 2 ^ {O ({ sqrt { log n log log n}})}}$ při vytváření programu, který používá ${ displaystyle n}$ paměťové buňky zapomínají. Tato práce zahájila sérii prací na konstrukci zapomínajících RAM, které pokračují až do dnešního dne. Při porovnávání různých konstrukcí ORAM je třeba vzít v úvahu několik atributů. Nejdůležitějšími parametry konstrukce ORAM jsou množství úložiště klienta, velikost úložiště serveru a časová náročnost při přístupu k jedné paměti. Na základě těchto atributů byla konstrukce Kushilevitze et al.^[6] je nejznámější konstrukce ORAM. Dosahuje to ${ displaystyle O (1)}$ úložiště klienta, ${ displaystyle O (n)}$ úložiště serveru a ${ displaystyle o ( log ^ {2} n)}$ přístup nad hlavou.

Dalším důležitým atributem konstrukce ORAM je, zda je režie přístupu amortizovaný nebo nejhorší případ. Několik dřívějších konstrukcí ORAM má dobré amortizované režijní záruky přístupu, ale mají ${ displaystyle Omega (N)}$ nejhorší přístupové režie. Některé z konstrukcí ORAM s polylogaritmický nejhorší výpočetní režie jsou.^[6]^[7]^[8]^[9]^[10] Stavby^[1]^[4]^[5] byly pro model náhodného věštce, kde klient předpokládá přístup k věštci, který se chová jako náhodná funkce a vrací konzistentní odpovědi pro opakované dotazy. Také si všimli, že toto věštce lze nahradit pseudonáhodnou funkcí, jejíž semenem je tajný klíč uložený klientem, pokud předpokládáme existenci jednosměrných funkcí. Papíry^[11]^[12] byly zaměřeny na úplné odstranění tohoto předpokladu. Autoři^[12] také dosáhnout režie přístupu ${ displaystyle O ( log ^ {3} n)}$ , což je jen log-faktor od nejznámějšího přístupu ORAM.

Zatímco většina dřívějších prací se zaměřuje na prokázání zabezpečení výpočetně, existuje i novějších prací^[3]^[8]^[11]^[12] které používají silnější statistickou představu o bezpečnosti.

Jeden z mála známých spodních limitů režie přístupu ORAM je způsoben Goldreichem et al.^[5] Ukazují a ${ displaystyle Omega ( log {n})}$ dolní mez pro ORAM přístup nad hlavou, kde ${ displaystyle n}$ je velikost dat. K dispozici je také podmíněná dolní mez na režii přístupu ORAM v důsledku Boyle et al.^[13] která toto množství spojuje s velikostí třídicích sítí.

Konstrukce ORAM

Triviální konstrukce

Konstrukce triviálního simulátoru ORAM pro každou operaci čtení nebo zápisu čte a zapisuje na každý jednotlivý prvek v poli, pouze provádí smysluplnou akci pro adresu uvedenou v této jediné operaci. Triviální řešení tedy prohledává celou paměť pro každou operaci. Toto schéma přináší časovou režii ${ displaystyle Omega (n)}$ pro každou paměťovou operaci, kde $n$ je velikost paměti.

Jednoduché schéma ORAM

Jednoduchá verze statisticky zabezpečeného kompilátoru ORAM vytvořeného Chungem a Passem^[3] je popsán v dalším textu spolu s přehledem důkazu o jeho správnosti. Kompilátor na vstupu $n$ a program $Π$ s jeho pamětí $n$ , vypíše ekvivalentní lhostejný program $Π '$ .

Pokud je vstupní program $Π$ používá $r$ registry, výstupní program $Π '$ bude potřeba ${ displaystyle r + n / { alpha} + { text {poly}} log {n}}$ registry, kde ${ displaystyle alpha> 1}$ je parametr konstrukce. $Π '$ používá ${ displaystyle O (n { text {poly}} log n)}$ paměť a její (nejhorší) přístupová režie je ${ displaystyle O ({ text {poly}} log n)}$ .

Překladač ORAM lze velmi snadno popsat. Předpokládejme, že původní program $Π$ má kromě dvou speciálních pokynů také pokyny pro základní matematické a řídicí operace ${ displaystyle { mathsf {číst}} (l)}$ a ${ displaystyle { mathsf {write}} (l, v)}$ , kde ${ displaystyle { mathsf {číst}} (l)}$ přečte hodnotu na místě $l$ a ${ displaystyle { mathsf {write}} (l, v)}$ zapíše hodnotu $proti$ na $l$ . Kompilátor ORAM při konstrukci $Π '$ , jednoduše nahradí každý číst a psát si pokyny s podprogramy Oread a Owrite a udržuje zbytek programu stejný. Je možné poznamenat, že tuto konstrukci lze nastavit tak, aby fungovala i pro požadavky na paměť přicházející v online móda.

Kompilátor ORAM nahradí pokyny pro čtení a zápis v původním programu podprogramy Oread a Owrite.

Organizace paměti zapomenutého programu

Program $Π '$ ukládá kompletní binární strom $T$ hloubky ${ displaystyle d = log (n / alpha)}$ v jeho paměti. Každý uzel v $T$ je reprezentován maximálně binárním řetězcem délky $d$ . Kořen je prázdný řetězec označený $λ$ . Levé a pravé potomky uzlu představovaného řetězcem ${ displaystyle gamma}$ jsou ${ displaystyle gamma _ {0}}$ a ${ displaystyle gamma _ {1}}$ resp. Program $Π '$ myslí na vzpomínku na $Π$ jako jsou rozděleny do bloků, kde každý blok je souvislou posloupností paměťových buněk o velikosti $α$ . Existuje tedy nanejvýš ${ Displaystyle lceil n / alpha rceil}$ celkem. Jinými slovy paměťová buňka $r$ odpovídá bloku ${ displaystyle b = lfloor r / alpha rfloor}$ .

V každém okamžiku existuje asociace mezi bloky a listy dovnitř $T$ Chcete-li sledovat toto sdružení, $Π '$ také ukládá datovou strukturu nazvanou mapa polohy, označená ${ displaystyle Pos}$ , použitím ${ displaystyle O (n / alpha)}$ registry. Tato datová struktura pro každý blok $b$ , ukládá list $T$ spojený s $b$ v ${ displaystyle Pos (b)}$ .

Každý uzel v $T$ obsahuje pole maximálně $K.$ trojnásobek. Každá trojice má formu ${ displaystyle (b, Pos (b), v)}$ , kde $b$ je identifikátor bloku a $proti$ je obsah bloku. Tady, $K.$ je bezpečnostní parametr a je ${ displaystyle O ({ text {poly}} log n)}$ .

Ilustrace paměti zapomnětlivého programu ukazující binární strom a mapu polohy.

Popis lhostejného programu

Program $Π '$ začíná inicializací jeho paměti a registrů na $⊥$ . Popis postupů Owrite a Oread stačí k dokončení popisu $Π '$ . Dílčí rutina Owrite je uveden níže. Vstupy do dílčí rutiny jsou paměťové místo ${ displaystyle l v [n]}$ a hodnota $proti$ být uloženy na místě $l$ . Má tři hlavní fáze, jmenovitě FETCH, PUT_BACK a FLUSH.

    vstup: umístění  $l$ , hodnota  $proti$

    Postup FETCH     // Vyhledejte požadovaný blok.          ${ Displaystyle b leftarrow lfloor l / alpha rfloor}$           //  $b$  je blok obsahující  $l$ .          ${ displaystyle i leftarrow l mod alpha}$           //  $i$  je  $l$ součást v bloku  $b$ .          ${ displaystyle pos leftarrow Pos (b)}$          -li  ${ displaystyle pos = perp}$  pak  ${ displaystyle pos leftarrow _ {R} [n / alpha]}$ .          // Soubor  ${ displaystyle pos}$  na rovnoměrně náhodný list dovnitř  $T$ .         vlajka  ${ displaystyle leftarrow 0}$ .         pro každý uzel  $N$  na cestě od kořene k  ${ displaystyle pos}$  dělat              -li  $N$  má trojnásobek formy  ${ displaystyle (b, pos, x)}$  pak                   Odstranit  ${ displaystyle (b, pos, x)}$  z  $N$ , obchod  $X$  do rejstříku a aktualizovaný odepište  $N$  na  $T$ . vlajka  ${ displaystyle leftarrow 1}$ .              jiný                   Odepsat  $N$  na  $T$ .    Postup PUT_BACK     // Přidejte zpět aktualizovaný blok v kořenovém adresáři.          ${ displaystyle pos ' leftarrow _ {R} [n / alpha]}$ .     // Soubor  ${ displaystyle pos '}$  na rovnoměrně náhodný list dovnitř  $T$ .         -li vlajka ${ displaystyle = 1}$  pak              Soubor  ${ displaystyle x '}$  být stejný jako  $X$  až na  $proti$  na  $i$ -tá pozice. jiný              Soubor  ${ displaystyle x '}$  být blok s  $proti$  na  $i$ -tá pozice a  $⊥$ je všude jinde. -li v kořenovém adresáři zbývá místo pak              Přidejte trojnásobek  ${ displaystyle (b, pos ', x')}$  do kořene  $T$ .         jiný              Přerušit výstup přetékat.    Postup FLUSH     // Zatlačte bloky přítomné v náhodném směru tak daleko, jak je to možné.          ${ displaystyle pos ^ {*} leftarrow _ {R} [n / alpha]}$ .     // Soubor  ${ displaystyle pos ^ {*}}$  na jednotně náhodný list dovnitř  $T$ .         pro každý trojitý  ${ displaystyle (b '', pos '', v '')}$  v uzlech prošla cesta z kořene do  ${ displaystyle pos ^ {*}}$               Zatlačte tuto trojku dolů do uzlu  $N$  který odpovídá nejdelší běžné předponě  ${ displaystyle pos ''}$  a  ${ displaystyle pos ^ {*}}$ .              -li kdykoli se nějaký kbelík přetéká pak                   Přerušit výstup přetékat.

Úkolem FETCH fáze je hledat místo $l$ ve stromě $T$ . Předpokládat ${ displaystyle pos}$ je list spojený s blokem obsahujícím umístění $l$ . Pro každý uzel $N$ v $T$ na cestě od kořene k ${ displaystyle pos}$ , tento postup prochází všemi trojnásobky $N$ a hledá trojnásobek odpovídající bloku obsahujícímu $l$ . Pokud zjistí, že trojnásobek $N$ , odstraní trojitý z $N$ a zapíše zpět aktualizovaný stav $N$ . Jinak jednoduše odepíše celý uzel $N$ .

V další fázi aktualizuje blok obsahující $l$ s novou hodnotou $proti$ , přidruží tento blok s čerstvě vzorkovaným jednotně náhodným listem stromu, zapíše aktualizovanou trojku do kořene $T$ .

Poslední fáze, která se nazývá FLUSH, je další operací k uvolnění paměťových buněk v kořenovém adresáři a dalších vyšších vnitřních uzlech. Algoritmus konkrétně vybere jednotně náhodný list ${ displaystyle pos ^ {*}}$ a poté se pokusí co nejvíce potlačit každý uzel na cestě od kořene k ${ displaystyle pos ^ {*}}$ . Přeruší výstup přetečení, pokud v určitém okamžiku některý kbelík přeteče svou kapacitu.

Dílčí rutina Oread je podobný Owrite. Pro Oread sub-rutina, vstup je pouze místo v paměti ${ displaystyle l v [n]}$ a je téměř stejný jako Owrite. Ve fázi FETCH, pokud nenajde trojitý odpovídající umístění $l$ , vrátí se $⊥$ jako hodnota v místě $l$ . Ve fázi PUT_BACK zapíše zpět stejný blok, který načetl do kořenového adresáře, po jeho přidružení k čerstvě vzorkovanému jednotně náhodnému listu.

Správnost jednoduchého schématu ORAM

Nechat $C$ znamená kompilátor ORAM, který byl popsán výše. Vzhledem k programu $Π$ , nechť $Π '$ označit ${ displaystyle C ( Pi)}$ . Nechat ${ displaystyle Pi (n, x)}$ označují provedení programu $Π$ na vstupu $X$ použitím $n$ paměťové buňky. Také nechte ${ displaystyle { tilde { Pi}} (n, x)}$ označuje vzor přístupu do paměti ${ displaystyle Pi (n, x)}$ . Nechat $μ$ označit funkci takovou, že pro libovolné ${ displaystyle n in mathbb {N}}$ , pro libovolný program $Π$ a pro jakýkoli vstup ${ displaystyle x in {0,1 } ^ {*}}$ , pravděpodobnost, že ${ displaystyle Pi '(n, x)}$ výstup přetečení je maximálně ${ displaystyle mu (n)}$ . Následující lemma je snadno vidět z popisu $C$ .

Rovnocennost Lemma: Nechat ${ displaystyle n in mathbb {N}}$ a ${ displaystyle x in {0,1 } ^ {*}}$ . Vzhledem k programu $Π$ alespoň s pravděpodobností ${ displaystyle 1- mu (n)}$ , výstup ${ displaystyle Pi '(n, x)}$ je shodný s výstupem ${ displaystyle Pi (n, x)}$ .

Je snadné to vidět Owrite a Oread operace prochází kořenem k listovým cestám ve Windows $T$ vybráno jednotně a náhodně nezávisle. Tato skutečnost naznačuje, že distribuce vzorů přístupu do paměti u libovolných dvou programů, které vytvářejí stejný počet přístupů do paměti, jsou k nerozeznání, pokud oba nepřetékají.

Zapomnětlivost Lemma: Vzhledem ke dvěma programům ${ displaystyle Pi _ {1}}$ a ${ displaystyle Pi _ {2}}$ a dva vstupy ${ displaystyle x_ {1}, x_ {2} in {0,1 } ^ {*}}$ takhle ${ displaystyle | { tilde { Pi _ {1}}} (x_ {1}, n) | = | { tilde { Pi _ {2}}} (x_ {2}, n) |}$ alespoň s pravděpodobností ${ displaystyle 1-2 mu (n)}$ , přístupové vzory ${ displaystyle { tilde { Pi _ {1} '}} (x_ {1}, n)}$ a ${ displaystyle { tilde { Pi _ {2} '}} (x_ {2}, n)}$ jsou identické.

Následující lemma doplňuje důkaz správnosti schématu ORAM.

Přetečení Lemma: Existuje zanedbatelná funkce $μ$ takové, že pro velmi program $Π$ , každý $n$ a vstup $X$ , Program ${ displaystyle Pi '(n, x)}$ přetečení výstupů s největší pravděpodobností ${ displaystyle mu (n)}$ .

Výpočetní a paměťové režie

Během každého Oread a Owrite operace, dvě náhodné cesty root-to-leaf $T$ jsou plně prozkoumány $Π '$ . To trvá ${ displaystyle O (K cdot log (n / alpha))}$ čas. To je stejné jako výpočetní režie a je ${ displaystyle O ({ text {poly}} log n)}$ od té doby $K.$ je ${ displaystyle O ({ text {poly}} log n)}$ .

Celková paměť vyčerpaná uživatelem $Π '$ se rovná velikosti $T$ . Každá trojice uložená ve stromu má ${ displaystyle alpha +2}$ slova v něm, a tak tam jsou ${ displaystyle K ( alpha +2)}$ slova na uzel stromu. Protože celkový počet uzlů ve stromu je ${ displaystyle O (n / alpha)}$ , celková velikost paměti je ${ displaystyle O (nK)}$ slova, což je ${ displaystyle O (n { text {poly}} log n)}$ . Proto je paměťová režie stavby ${ displaystyle O ({ text {poly}} log n)}$ .

Reference

^ ^A ^b ^C Goldreich, Oded (1987), "Směrem k teorii ochrany a simulace softwaru pomocí zapomínajících RAM", in Aho, Alfred V. (vyd.), Sborník 19. výročního sympózia ACM o teorii výpočtů (STOC '87), Sdružení pro výpočetní techniku, s. 182–194, doi:10.1145/28395.28416
^ Pippenger, Nicholas; Fischer, Michael J. (1979), „Vztahy mezi opatřeními složitosti“, Deník ACM, 26 (2): 361–381, doi:10.1145/322123.322138, PAN 0528038
^ ^A ^b ^C Chung, Kai-Min; Pass, Rafael (2013), „Jednoduchý ORAM“, Archiv ePrint kryptologie IACR
^ ^A ^b Ostrovský, Rafail (1990), „Efektivní výpočet na lhostejných RAM“, Sborník z 22. výročního sympózia ACM o teorii práce s počítači (STOC '90), Sdružení pro výpočetní techniku, str. 514–523, doi:10.1145/100216.100289
^ ^A ^b ^C ^d Goldreich, Oded; Ostrovský, Rafail (1996), „Softwarová ochrana a simulace na lhostejných RAM“, Deník ACM, 43 (3): 431–473, doi:10.1145/233551.233553, hdl:1721.1/103684, PAN 1408562
^ ^A ^b Kushilevitz, Eyal; Lu, Steve; Ostrovský, Rafail (2012), „On (in) security of hash-based livious RAM and a new balancing scheme“, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Sdružení pro výpočetní techniku, s. 143–156, doi:10.1137/1.9781611973099.13, PAN 3205204
^ Ostrovský, Rafail; Shoup, Victor (1997), "Soukromé úložiště informací (rozšířený abstrakt)", v Leighton, F. Thomson; Shor, Peter W. (eds.), Sborník z dvacátého devátého výročního symposia ACM o teorii práce na počítači (STOC '97), Sdružení pro výpočetní techniku, str. 294–303, doi:10.1145/258533.258606
^ ^A ^b Shi, Elaine; Chan, T.-H. Hubert; Stefanov, Emil; Li, Mingfei (2011), „Oblivious RAM with ${ displaystyle O (( log N) ^ {3})}$ náklady v nejhorším případě “, Lee, Dong Hoon; Wang, Xiaoyun (eds.), Pokroky v kryptologii - ASIACRYPT 2011 - 17. mezinárodní konference o teorii a aplikaci kryptologie a informační bezpečnosti, Soul, Jižní Korea, 4. – 8. Prosince 2011, sborník, Přednášky v informatice, 7073, Springer, str. 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 most-case access overhead“, in Cachin, Christian; Ristenpart, Thomas (eds.), Sborník příspěvků ze 3. workshopu ACM Cloud Computing Security, CCSW 2011, Chicago, IL, USA, 21. října 2011, Sdružení pro výpočetní techniku, str. 95–100, doi:10.1145/2046660.2046680
^ Chung, Kai-Min; Liu, Zhenming; Pass, Rafael (2014), „Statisticky zabezpečený ORAM s ${ displaystyle { tilde {O}} ( log ^ {2} n)}$ režie ", 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., 7-11. Prosince 2014, Proceedings, Part II, Přednášky v informatice, 8874, Springer, str. 62–81, doi:10.1007/978-3-662-45608-8_4
^ ^A ^b Ajtai, Miklósi (2010), „Oblivious RAMs without cryptographic predpoklads [extended abstract]“, Sborník 42. sympozia ACM o teorii výpočtů (STOC 2010), Sdružení pro výpočetní techniku, s. 181–190, doi:10.1145/1806689.1806716, PAN 2743267
^ ^A ^b ^C Damgård, Ivan; Meldgaard, Sigurd; Nielsen, Jesper Buus (2011), „Perfektně zabezpečit zapomenutou RAM bez náhodných věštců“, Ishai, Yuval (ed.), Teorie kryptografie - 8. konference o teorii kryptografie, TCC 2011, Providence, RI, USA, 28. – 30. Března 2011, sborník, Přednášky v informatice, 6597, Springer, str. 144–163, doi:10.1007/978-3-642-19571-6_10
^ Boyle, Elette; Naor, Moni (2016), „Existuje zapomenutá dolní mez RAM?“, Sborník konference ACM 2016 o inovacích v teoretické informatice (ITCS '16), Sdružení pro výpočetní techniku, str. 357–368, doi:10.1145/2840728.2840761, PAN 3629839

Viz také

[G87-1] A ^b ^C Goldreich, Oded (1987), "Směrem k teorii ochrany a simulace softwaru pomocí zapomínajících RAM", in Aho, Alfred V. (vyd.), Sborník 19. výročního sympózia ACM o teorii výpočtů (STOC '87), Sdružení pro výpočetní techniku, s. 182–194, doi:10.1145/28395.28416

[2] Pippenger, Nicholas; Fischer, Michael J. (1979), „Vztahy mezi opatřeními složitosti“, Deník ACM, 26 (2): 361–381, doi:10.1145/322123.322138, PAN 0528038

[CP13-3] A ^b ^C Chung, Kai-Min; Pass, Rafael (2013), „Jednoduchý ORAM“, Archiv ePrint kryptologie IACR

[O90-4] A ^b Ostrovský, Rafail (1990), „Efektivní výpočet na lhostejných RAM“, Sborník z 22. výročního sympózia ACM o teorii práce s počítači (STOC '90), Sdružení pro výpočetní techniku, str. 514–523, doi:10.1145/100216.100289

[GO96-5] A ^b ^C ^d Goldreich, Oded; Ostrovský, Rafail (1996), „Softwarová ochrana a simulace na lhostejných RAM“, Deník ACM, 43 (3): 431–473, doi:10.1145/233551.233553, hdl:1721.1/103684, PAN 1408562

[KLO12-6] A ^b Kushilevitz, Eyal; Lu, Steve; Ostrovský, Rafail (2012), „On (in) security of hash-based livious RAM and a new balancing scheme“, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Sdružení pro výpočetní techniku, s. 143–156, doi:10.1137/1.9781611973099.13, PAN 3205204

[OS97-7] Ostrovský, Rafail; Shoup, Victor (1997), "Soukromé úložiště informací (rozšířený abstrakt)", v Leighton, F. Thomson; Shor, Peter W. (eds.), Sborník z dvacátého devátého výročního symposia ACM o teorii práce na počítači (STOC '97), Sdružení pro výpočetní techniku, str. 294–303, doi:10.1145/258533.258606

[SCSL11-8] A ^b Shi, Elaine; Chan, T.-H. Hubert; Stefanov, Emil; Li, Mingfei (2011), „Oblivious RAM with ${ displaystyle O (( log N) ^ {3})}$ náklady v nejhorším případě “, Lee, Dong Hoon; Wang, Xiaoyun (eds.), Pokroky v kryptologii - ASIACRYPT 2011 - 17. mezinárodní konference o teorii a aplikaci kryptologie a informační bezpečnosti, Soul, Jižní Korea, 4. – 8. Prosince 2011, sborník, Přednášky v informatice, 7073, Springer, str. 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 most-case access overhead“, in Cachin, Christian; Ristenpart, Thomas (eds.), Sborník příspěvků ze 3. workshopu ACM Cloud Computing Security, CCSW 2011, Chicago, IL, USA, 21. října 2011, Sdružení pro výpočetní techniku, str. 95–100, doi:10.1145/2046660.2046680

[CLP14-10] Chung, Kai-Min; Liu, Zhenming; Pass, Rafael (2014), „Statisticky zabezpečený ORAM s ${ displaystyle { tilde {O}} ( log ^ {2} n)}$ režie ", 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., 7-11. Prosince 2014, Proceedings, Part II, Přednášky v informatice, 8874, Springer, str. 62–81, doi:10.1007/978-3-662-45608-8_4

[A10-11] A ^b Ajtai, Miklósi (2010), „Oblivious RAMs without cryptographic predpoklads [extended abstract]“, Sborník 42. sympozia ACM o teorii výpočtů (STOC 2010), Sdružení pro výpočetní techniku, s. 181–190, doi:10.1145/1806689.1806716, PAN 2743267

[DMN11-12] A ^b ^C Damgård, Ivan; Meldgaard, Sigurd; Nielsen, Jesper Buus (2011), „Perfektně zabezpečit zapomenutou RAM bez náhodných věštců“, Ishai, Yuval (ed.), Teorie kryptografie - 8. konference o teorii kryptografie, TCC 2011, Providence, RI, USA, 28. – 30. Března 2011, sborník, Přednášky v informatice, 6597, Springer, str. 144–163, doi:10.1007/978-3-642-19571-6_10

[BN16-13] Boyle, Elette; Naor, Moni (2016), „Existuje zapomenutá dolní mez RAM?“, Sborník konference ACM 2016 o inovacích v teoretické informatice (ITCS '16), Sdružení pro výpočetní techniku, str. 357–368, doi:10.1145/2840728.2840761, PAN 3629839

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]