A kriptográfiában a véletlen orákulum egy idealizált hash függvény , amely minden új kérésre véletlenszerű választ ad, egyenletesen elosztva az értéktartományban, azzal a feltétellel, hogy ha ugyanaz a kérés kétszer érkezik, akkor a válasznak meg kell egyeznie. Más szavakkal, a véletlenszerű orákulum egy véletlenszerűen kiválasztott matematikai függvény , amely minden lehetséges lekérdezést leképez egy rögzített véletlenszerű válaszra egy előre elkészített választerületről.
A véletlenszerű orákulumokat mint matematikai absztrakciót Mihir Bellare és Philip Rogaway 1993-as publikációjában használták először szigorú kriptográfiai bizonyításokban . Általában olyan esetekben használatosak, amikor a bizonyítás nem végezhető el a kriptográfiai hash függvény gyengébb feltevéseivel . Egy olyan rendszert, amely biztonságosnak bizonyult, amikor minden hash függvényt véletlenszerű orákulum helyettesít, a véletlenszerű orákulum modellben biztonságosnak írják le, szemben a szabványos kriptográfiai modellben .
A véletlenszerű orákulum nagyon erős , mert három tulajdonsága van: determinizmus , hatékonyság és a kapott értékek egyenletes eloszlásának biztosítása [1] .
A véletlenszerű orákulumokat általában a kriptográfiai hash függvények idealizált helyettesítésére használják olyan sémákban, ahol erős feltételezésekre van szükség a hash kimenet véletlenszerűségére vonatkozóan [1] . Az ilyen bizonyítékok általában azt mutatják, hogy a rendszer vagy a protokoll biztonságos, ami azt mutatja, hogy a támadónak lehetetlen viselkedést kell követelnie az orákulumtól, vagy meg kell oldania valamilyen nehezen megoldhatónak ítélt matematikai problémát. A kriptográfiai hash függvények nem minden használatához szükségesek véletlenszerű orákulumok [2] : gyakran bizonyítható, hogy azok a sémák, amelyek csak egy vagy néhány, a szabványos modellben meghatározott tulajdonságot igényelnek (például ütközésállóság , előkép-ellenállás, második előkép-ellenállás stb.) legyen biztonságos a szabványos modellben (például a Cramer–Shope kriptorendszerben ).
A véletlenszerű orákulumokat régóta figyelembe veszik a számítási komplexitáselméletben , és számos séma biztonságosnak bizonyult a véletlenszerű orákulummodellben, mint például az optimális aszimmetrikus titkosítás , az RSA-FDH [3] és a valószínűségi aláírási séma . 1986-ban Amos Fiat és Adi Shamir [4] bemutatta a véletlenszerű orákulumok fő alkalmazását - az interakciók eltávolítását az aláírások létrehozására szolgáló protokollokból.
1989-ben Russell Impalazzo és Steven Rudich [5] kimutatta a véletlenszerű orákulumok korlátait, nevezetesen, hogy létezésük önmagában nem elegendő egy titkos kulcs kicseréléséhez .
1993-ban Mihir Bellare és Philippe Rogaway [6] voltak az elsők, akik támogatták a kriptográfiai konstrukciókban való alkalmazásukat. Definíciójuk szerint egy véletlenszerű orákulum végtelen hosszúságú bitsort hoz létre, amely a kívánt hosszúságúra csonkolható.
Amikor egy véletlenszerű jóslatot használnak a biztonság bizonyítékaként, az minden játékos számára elérhetővé válik, beleértve az ellenfelet vagy az ellenfeleket is. Egy orákulum több orákulumként is felfogható, minden kérés elején rögzített bitsort fűzve (például az "1| x " vagy "0| x " formátumú kéréseket két külön véletlen szám hívásának tekinthetjük ). Oracle, hasonló a "00 | x ", "01 | x ", "10 | x " és "11 | x " használható négy különálló véletlenszerű orákulum hívásainak ábrázolására).
A véletlen orákulum egy erős hipotetikus determinisztikus függvény, amely hatékonyan számítja ki az egyenletes eloszlású valószínűségi változókat . A véletlenszerű orákulum modellje nemcsak egy véletlen jóslat, hanem egy speciális ügynök – egy imitátor – létezését is feltételezi . Az imitátor állítólag képes bármilyen véletlenszerű jóslatot utánozni (még egy támadót is). Így ha valaki egy G véletlenszerű orákuumot akar alkalmazni egy a számra , akkor automatikusan kérést küld a szimulátornak egy véletlenszerű jósnak , és megkapja tőle a G(a) eredményt . A szimulátor mindig őszintén végrehajt minden kérést, és mindig visszaadja az eredményt.
Ennek a szabálynak köszönhetően a szimulátor pontosan képes utánozni egy véletlenszerű orákulum viselkedését. Hagyja, hogy a szimulátor G-listát tartson fenn az (a, G(a)) párokat tartalmazó oracle G számára, ahol az előző a lekérdezések vannak tárolva . A szimuláció egyszerű: az a lekérdezés vétele után a szimulátor ellenőrzi, hogy az el van-e tárolva a listában, és ha igen, akkor visszaadja a G(a) értéket (a lekérdezés determinisztikus eredménye), ellenkező esetben a szimulátor új G( a) az egyenletes eloszlású számok általános sokaságából választ küld, és az adott párt (a, G(a)) egy rendezett listába tölti fel, amely log N időegységet vesz igénybe a kereséshez (e miatt a véletlenszerű orákulum hatékony).
Így a véletlenszerű orákulumot pontosan utánozza a polinomiálisan korlátos algoritmus [7] .
Ismert néhány mesterséges aláírási és titkosítási sémát , amelyek biztonságosnak bizonyultak a véletlenszerű orákulum modellben, de triviálisan bizonytalanok, ha bármilyen valós funkció helyettesíti a véletlenszerű jóslatot. [8] Azonban minden természetesebb protokoll esetében a véletlenszerű orákulummodellben a biztonság bizonyítása nagyon erős bizonyítékot szolgáltat a protokoll gyakorlati biztonságára. [9]
Általánosságban elmondható, hogy ha egy protokoll biztonságosnak bizonyul, a protokoll elleni támadásoknak vagy túl kell haladniuk a bizonyítotton, vagy meg kell sérteni a bizonyítás valamely feltételezését; Például, ha a bizonyítás az egész számok faktorizálásának összetettségére támaszkodik , ennek a feltevésnek a megdöntéséhez meg kell találni egy gyors egész faktorizációs algoritmust . Ehelyett a véletlenszerű orákulum-feltevés megtöréséhez fel kell fedezni a tényleges hash függvény néhány ismeretlen és nemkívánatos tulajdonságát ; a jó hash függvények esetében, ahol az ilyen tulajdonságok valószínűtlennek tekinthetők, a kérdéses protokoll biztonságosnak tekinthető. [tíz]
Bár a Baker-Gill-Solovey-tétel [11] [12] kimutatta, hogy létezik olyan A orákulum, amelyre P A = NP A , Bennett és Gill [13] későbbi munkája kimutatta, hogy egy véletlenszerű B orákulumra (függvény a { 0,1 } n n - {0,1} úgy, hogy minden bemeneti elem 0-ra vagy 1-re 1/2 valószínűséggel leképeződik, függetlenül az összes többi bemenet leképezésétől), P B ⊊ NP B 1 valószínűséggel. Hasonló felosztások, valamint az a tény is, hogy a véletlen orákulumok 0 vagy 1 valószínűséggel választanak el osztályokat ( a Kolmogorov-féle nulla-egyes törvény következményeként ), ami annak a véletlenszerű orákulum-hipotézisnek a megalkotásához vezetett, hogy két „elfogadható” komplexitási osztály C 1 és C 2 akkor és csak akkor egyenlőek (1 valószínűséggel) egy véletlenszerű orákulum alatt (a komplexitási osztály elfogadhatóságát a BG81 határozza meg [13] Ez a sejtés később hamisnak bizonyult, mivel a két elfogadható komplexitási osztály IP és PSPACE egyenlőnek bizonyultak annak ellenére, hogy IP A ⊊ PSPACE A egy véletlenszerű A orákulumra 1 valószínűséggel.
Az ideális rejtjel egy véletlen permutációjú orákulum , amelyet egy idealizált blokkrejtjel modellezésére használnak [14] .
Egy tetszőleges permutáció minden titkosított szöveg blokkot egy és csak egy egyszerű szöveg blokkra dekódol , és fordítva, így van egy-egy megfelelés. Egyes kriptográfiai bizonyítások nemcsak "előre" permutációt tesznek elérhetővé minden játékos számára, hanem "fordított" permutációt is.
A közelmúltban végzett munkák kimutatták, hogy egy véletlenszerű orákulumból 10-körű [15] vagy akár 8 körös [16] Feistel-hálózatok segítségével ideális rejtjel szerkeszthető .
Canetti, Goldreich és Halevi negatív attitűdöt fejeztek ki a véletlenszerű orákulummodell alapján történő bizonyítással kapcsolatban [17] . Bebizonyították, hogy léteznek olyan digitális aláírási és titkosítási sémák, amelyek bizonyíthatóan biztonságosak a véletlenszerű orákulum-modell keretein belül, de sérülékenyek a valós alkalmazásokban való megvalósítással szemben. A fő ötletük az volt, hogy rossz digitális aláírási vagy titkosítási sémákat találjanak ki . Normál körülmények között ezek a sémák jól működnek, de bizonyos körülmények között (leginkább a véletlenszerűség megsértése esetén) rosszvá válnak. A három szerző azonban eltérő következtetésekre jutott a véletlenszerű orákulummodell hasznosságát illetően.
Canetti úgy véli, hogy a véletlenszerű orákulummodell egy szerencsétlen absztrakciót képvisel, és csökkenti az "ellentmondáscsökkentés" módszerének értékét. Azt javasolta, hogy a tudományos kutatást a véletlenszerű orákulummodell konkrét hasznos tulajdonságainak felkutatására kell irányítani [18] .
Goldreich úgy véli, hogy a probléma a modell hiányosságában rejlik, és azt javasolja, hogy az ezzel a módszerrel végzett bizonyításokat ne vegyék bele. Úgy véli azonban, hogy a véletlenszerű orákulummodellnek van némi értéke a kriptorendszerek biztonságának tesztelésében [18] .
Halevi úgy véli, hogy az ellentmondásba redukálás módszerének jelenlegi sikerei véletlenek: „Nincs ok azt állítani, hogy minden létező séma, amelynek stabilitása a véletlenszerű orákulummodell segítségével bizonyított, valójában stabil” [18]. .