V kryptografii je náhodný orákulum idealizovanou hashovací funkcí , která pro každý nový požadavek vytvoří náhodnou odpověď, rovnoměrně rozloženou v rozsahu hodnot, s podmínkou: pokud stejný požadavek dorazí dvakrát, pak odpověď musí být stejná. Jinými slovy, náhodné orákulum je náhodně vybraná matematická funkce , která mapuje každý možný dotaz do pevné náhodné odpovědi z předem připravené oblasti odpovědi.
Náhodné věštby jako matematická abstrakce byly poprvé použity v přísných kryptografických důkazech v publikaci Mihir Bellare a Philip Rogaway z roku 1993 . Běžně se používají v případech, kdy důkaz nelze provést pomocí slabších předpokladů o kryptografické hashovací funkci . Systém, který se ukázal jako bezpečný, když je každá hashovací funkce nahrazena náhodným orákulem, je popsán jako bezpečný v modelu náhodného orákula, na rozdíl od toho, aby byl bezpečný ve standardním kryptografickém modelu .
Náhodné orákulum je velmi silné , protože má tři vlastnosti: determinismus , účinnost a zajištění rovnoměrného rozložení výsledných hodnot [1] .
Náhodná věštkyně se běžně používají jako idealizovaná náhrada za kryptografické hashovací funkce ve schématech, kde jsou zapotřebí silné předpoklady o náhodnosti výstupu hash [1] . Takový důkaz obvykle ukazuje, že systém nebo protokol je bezpečný, což ukazuje, že útočník musí od orákula vyžadovat nemožné chování nebo musí vyřešit nějaký matematický problém, který je považován za obtížně řešitelný. Ne všechna použití kryptografických hašovacích funkcí vyžadují náhodná orákula [2] : schémata, která vyžadují pouze jednu nebo několik vlastností definovaných ve standardním modelu (jako je odolnost proti kolizi , odolnost předobrazu, odolnost proti druhému předobrazu atd.), často lze prokázat, že být bezpečný ve standardním modelu (např . kryptosystém Cramer–Shope ).
Náhodná věštkyně byla dlouho zvažována v teorii výpočetní složitosti a mnoho schémat bylo prokázáno jako bezpečné v modelu náhodného orákula, jako je optimální asymetrické šifrování , RSA-FDH [3] a schéma pravděpodobnostního podpisu . V roce 1986 Amos Fiat a Adi Shamir [4] ukázali hlavní aplikaci náhodných věštců – odstranění interakce z protokolů pro vytváření podpisů.
V roce 1989 Russell Impalazzo a Steven Rudich [5] prokázali omezení náhodných věštců, totiž že jejich existence sama o sobě nestačí k výměně tajného klíče .
V roce 1993 byli Mihir Bellare a Philippe Rogaway [6] první, kdo obhajoval jejich použití v kryptografických konstrukcích. Podle jejich definice náhodné orákulum vytváří nekonečný bitový řetězec, který lze zkrátit na požadovanou délku.
Když je náhodný orákulum použit jako důkaz bezpečnosti, stane se dostupným pro všechny hráče, včetně protivníka nebo protivníků. Jedno orákulum lze považovat za více věštců, které na začátek každého požadavku vkládají pevný bitový řetězec (například požadavky formátované jako „1| x “ nebo „0| x “ lze považovat za volání dvou samostatných náhodných čísel ). Oracles, podobné "00 | x ", "01 | x ", "10 | x " a "11 | x " lze použít k reprezentaci volání čtyř samostatných náhodných věštců).
Náhodné orákulum je mocná hypotetická deterministická funkce, která efektivně počítá rovnoměrně rozložené náhodné proměnné . Model náhodného orákula předpokládá existenci nejen náhodného orákula, ale také speciálního agenta - imitátora . Imitátor má být schopen napodobit jakékoli náhodné orákulum (i útočníka). Pokud tedy někdo chce použít náhodné orákulum G na číslo a , pak automaticky odešle požadavek do simulátoru náhodnému orákulu a získá z něj výsledek G(a) . Simulátor vždy poctivě vyřídí jakýkoliv požadavek a vždy vrátí jeho výsledek.
Díky tomuto pravidlu dokáže simulátor přesně napodobit chování náhodného orákula. Nechte simulátor udržovat G-seznam pro oracle G obsahující páry (a, G(a)) , kde jsou uloženy předchozí dotazy a . Simulace je jednoduchá: po obdržení dotazu a simulátor zkontroluje, zda je uložen v seznamu, a pokud ano, vrátí hodnotu G(a) (deterministický výsledek dotazu), jinak simulátor extrahuje novou hodnotu G( a) z obecné populace rovnoměrně rozložených čísel odešle odpověď a naplní danou dvojici (a, G(a)) do setříděného seznamu, jehož hledání zabere log N jednotek času (kvůli této funkci náhodný orákulum je efektivní).
Náhodné orákulum je tedy přesně napodobeno polynomiálně ohraničeným algoritmem [7] .
Jsou známa některá umělá schémata podpisu a šifrování , která se v modelu náhodného orákula osvědčila jako bezpečná, ale jsou triviálně nejisté, když náhodné orákulum nahradí jakákoli skutečná funkce. [8] Pro jakýkoli přirozenější protokol však důkaz bezpečnosti v modelu náhodného orákula poskytuje velmi silný důkaz pro praktickou bezpečnost protokolu. [9]
Obecně platí, že pokud se prokáže, že protokol je bezpečný, útoky na tento protokol musí jít nad rámec toho, co bylo prokázáno, nebo porušovat jeden z předpokladů v důkazu; například, jestliže důkaz se spoléhá na složitost faktorizace celého čísla , rozbít tento předpoklad jeden musí najít rychlý celočíselný faktorization algoritmus . Místo toho, aby se prolomil náhodný věštecký předpoklad, musí být objevena nějaká neznámá a nežádoucí vlastnost aktuální hashovací funkce ; pro dobré hashovací funkce , kde jsou takové vlastnosti považovány za nepravděpodobné, lze příslušný protokol považovat za bezpečný. [deset]
Ačkoli Baker-Gill-Solovey teorém [11] [12] ukázal, že existuje orákulum A takové, že P A = NP A , následná práce Bennetta a Gilla [13] ukázala, že pro náhodné orákulum B (funkce z { 0,1 } n n až {0,1} tak, že každý vstupní prvek mapuje na každou z 0 nebo 1 s pravděpodobností 1/2, bez ohledu na mapování všech ostatních vstupů), P B ⊊ NP B s pravděpodobností 1. Podobné rozdělení, a také skutečnost, že náhodná orákula oddělují třídy s pravděpodobností 0 nebo 1 (v důsledku Kolmogorovova zákona nula-jedna ), což vedlo k vytvoření hypotézy náhodného orákula, že dvě „přijatelné“ třídy složitosti C 1 a C 2 jsou stejné právě tehdy a jen tehdy, jsou-li stejné (s pravděpodobností 1) pod náhodným orákulem (přijatelnost třídy složitosti je definována v BG81 [13] Tato domněnka se později ukázala jako nepravdivá, protože dvě přijatelné třídy složitosti IP a PSPACE se ukázaly být stejné navzdory skutečnosti, že IP A ⊊ PSPACE A pro náhodné orákulum A s pravděpodobností 1.
Ideální šifra je orákulum náhodné permutace , které se používá k modelování idealizované blokové šifry [14] .
Libovolná permutace dešifruje každý blok šifrovaného textu do jednoho a pouze jednoho bloku otevřeného textu a naopak, takže existuje korespondence jedna ku jedné. Některé kryptografické důkazy zpřístupňují všem hráčům nejen "dopřednou" permutaci, ale také "reverzní" permutaci.
Nedávná práce ukázala, že ideální šifru lze sestavit z náhodného orákula pomocí 10-kolových [15] nebo dokonce 8-kolových [16] sítí Feistel .
Canetti, Goldreich a Halevi vyjádřili negativní postoj k důkazům založeným na modelu náhodného orákula [17] . Prokázali, že existují schémata digitálního podpisu a šifrování , která jsou prokazatelně bezpečná v rámci modelu náhodného orákula, ale zranitelná vůči implementaci v reálných aplikacích. Jejich hlavní myšlenkou bylo vymyslet špatný digitální podpis nebo šifrovací schémata . Za normálních podmínek tato schémata fungují dobře, ale za určitých podmínek (většinou porušení náhodnosti) se stanou špatnými. Nicméně, tři autoři dospěli k odlišným závěrům ohledně užitečnosti modelu náhodného orákula.
Canetti věří, že model náhodného orákula představuje nešťastnou abstrakci a snižuje hodnotu metody „redukce rozporu“. Navrhl, že vědecký výzkum by měl být zaměřen na hledání konkrétních užitečných vlastností modelu náhodného orákula [18] .
Goldreich se domnívá, že problém spočívá v neúplnosti modelu a doporučuje, aby důkazy pomocí této metody nebyly zahrnuty. Domnívá se však, že model náhodného orákula má určitou hodnotu při testování bezpečnosti kryptosystémů [18] .
Halevi se domnívá, že současné úspěchy metody redukce na rozpor jsou náhodné: „Není důvod tvrdit, že všechna existující schémata, jejichž stabilita byla prokázána pomocí modelu náhodného orákula, jsou ve skutečnosti stabilní“ [18] .