În criptografie , un oracol aleatoriu este o funcție hash idealizată care, pentru fiecare nouă cerere, produce un răspuns aleator, distribuit uniform pe intervalul de valori, cu condiția: dacă aceeași cerere ajunge de două ori, atunci răspunsul trebuie să fie același. Cu alte cuvinte, un oracol aleatoriu este o funcție matematică , aleasă la întâmplare, care mapează fiecare interogare posibilă într-un răspuns aleator fix dintr-o zonă de răspuns pre-preparată.
Oracolele aleatorii ca abstractizare matematică au fost folosite pentru prima dată în dovezi criptografice riguroase într-o publicație din 1993 a lui Mihir Bellare și Philip Rogaway . Ele sunt utilizate în mod obișnuit în cazurile în care demonstrarea nu poate fi făcută folosind ipoteze mai slabe despre funcția hash criptografică . Un sistem care sa dovedit sigur atunci când fiecare funcție hash este înlocuită cu un oracol aleatoriu este descris ca sigur în modelul de oracol aleatoriu, spre deosebire de a fi sigur în modelul standard de criptare .
Un oracol aleatoriu este foarte puternic deoarece are trei proprietăți: determinism , eficiență și asigurarea unei distribuții uniforme a valorilor rezultate [1] .
Oracolele aleatoare sunt utilizate în mod obișnuit ca înlocuitor idealizat pentru funcțiile hash criptografice în schemele în care sunt necesare ipoteze puternice despre aleatoritatea rezultatului hash [1] . O astfel de dovadă arată de obicei că sistemul sau protocolul este sigur, arătând că atacatorul trebuie să solicite un comportament imposibil de la oracol sau trebuie să rezolve o problemă matematică care este considerată dificil de rezolvat. Nu toate utilizările funcțiilor hash criptografice necesită oracole aleatorii [2] : schemele care necesită doar una sau câteva proprietăți definite în modelul standard (cum ar fi rezistența la coliziune , rezistența preimagine, rezistența a doua preimagine etc.), adesea pot fi dovedite că fi sigur în modelul standard ( de exemplu, criptosistemul Cramer–Shope ).
Oracolele aleatoare au fost mult timp luate în considerare în teoria complexității computaționale și multe scheme s-au dovedit sigure în modelul de oracol aleatoriu, cum ar fi criptarea asimetrică optimă , RSA-FDH [3] și schema de semnătură probabilistică . În 1986, Amos Fiat și Adi Shamir [4] au arătat aplicația principală a oracolelor aleatorii - eliminarea interacțiunii din protocoalele de creare a semnăturilor.
În 1989, Russell Impalazzo și Steven Rudich [5] au demonstrat o limitare a oracolelor aleatorii, și anume că existența lor singură nu este suficientă pentru a schimba o cheie secretă .
În 1993, Mihir Bellare și Philippe Rogaway [6] au fost primii care au susținut folosirea lor în construcții criptografice. Prin definiția lor, un oracol aleatoriu creează un șir de biți de lungime infinită care poate fi trunchiat la lungimea dorită.
Când un oracol aleatoriu este folosit ca dovadă de securitate, acesta devine disponibil pentru toți jucătorii, inclusiv pentru adversar sau adversari. Un oracol poate fi considerat ca mai multe oracole, adăugând un șir de biți fix la începutul fiecărei solicitări (de exemplu, cererile formatate ca „1| x ” sau „0| x ” pot fi considerate ca apeluri către două numere aleatoare separate. ). Oracole, similare cu „00 | x ", "01 | x ", "10 | x " și "11 | x " poate fi folosit pentru a reprezenta apeluri la patru oracole aleatorii separate).
Oracolul aleatoriu este o funcție deterministă ipotetică puternică care calculează eficient variabile aleatoare distribuite uniform . Modelul unui oracol aleatoriu presupune existența nu numai a unui oracol aleatoriu, ci și a unui agent special - un imitator . Imitatorul ar trebui să fie capabil să imite orice oracol aleatoriu (chiar și un atacator). Astfel, dacă cineva dorește să aplice un oracol aleatoriu G unui număr a , atunci va trimite automat o solicitare la simulator către un oracol aleatoriu și va obține rezultatul G(a) din acesta . Simulatorul execută întotdeauna cu sinceritate orice cerere și returnează întotdeauna rezultatul.
Datorită acestei reguli, simulatorul poate imita cu exactitate comportamentul unui oracol aleatoriu. Lăsați simulatorul să mențină o listă G pentru oracolul G care conține perechi (a, G(a)) în care sunt stocate interogările anterioare a . Simularea este simplă: după primirea interogării a , simulatorul verifică dacă aceasta este stocată în listă și, dacă da, returnează valoarea G(a) (rezultatul determinist al interogării), în caz contrar simulatorul extrage o nouă valoare G( a) din populația generală de numere distribuite uniform , trimite un răspuns și populează perechea dată (a, G(a)) într-o listă sortată care necesită log N unități de timp pentru a căuta (din cauza acestei caracteristici, oracolul aleatoriu este eficient).
Astfel, oracolul aleatoriu este imitat exact de algoritmul mărginit polinomial [7] .
Sunt cunoscute unele scheme artificiale de semnătură și criptare care s-au dovedit sigure în modelul de oracol aleatoriu, dar sunt trivial nesigure atunci când orice funcție reală înlocuiește oracolul aleatoriu. [8] Cu toate acestea, pentru orice protocol mai natural, dovada securității în modelul de oracol aleatoriu oferă dovezi foarte puternice pentru securitatea practică a protocolului. [9]
În general, dacă se dovedește că un protocol este sigur, atacurile asupra protocolului respectiv trebuie fie să depășească ceea ce a fost dovedit, fie să încalce una dintre ipotezele din dovadă; de exemplu, dacă demonstrația se bazează pe complexitatea factorizării întregi , pentru a rupe această ipoteză trebuie să găsiți un algoritm rapid de factorizare a întregului . În schimb, pentru a încălca ipoteza oracolului aleatoriu, trebuie descoperită o proprietate necunoscută și nedorită a funcției hash ; pentru funcții hash bune , unde astfel de proprietăți sunt considerate puțin probabile, protocolul în cauză poate fi considerat sigur. [zece]
Deși teorema Baker-Gill-Solovey [11] [12] a arătat că există un oracol A astfel încât P A = NP A , lucrările ulterioare ale lui Bennett și Gill [13] au arătat că pentru un oracol aleatoriu B (o funcție din { 0,1 } n n la {0,1} astfel încât fiecare element de intrare să se mapeze la fiecare dintre 0 sau 1 cu probabilitatea 1/2, indiferent de maparea tuturor celorlalte intrări), P B ⊊ NP B cu probabilitatea 1. Împărțiri similare, și, de asemenea, faptul că oracolele aleatoare separă clase cu o probabilitate de 0 sau 1 (ca o consecință a legii zero-unu a lui Kolmogorov ), ceea ce a condus la crearea ipotezei oracolului aleatoriu că două clase de complexitate „acceptabile” C 1 și C 2 sunt egale dacă și numai dacă sunt egale (cu probabilitatea 1) sub un oracol aleatoriu (acceptabilitatea clasei de complexitate este definită în BG81 [13] Această presupunere s-a dovedit ulterior a fi falsă, deoarece cele două clase de complexitate acceptabile IP și PSPACE s-au dovedit a fi egale în ciuda faptului că IP A ⊊ PSPACE A pentru un oracol aleatoriu A cu probabilitate 1.
Un cifr ideal este un oracol de permutare aleatoare care este folosit pentru a modela un cifru bloc idealizat [14] .
O permutare arbitrară decriptează fiecare bloc de text cifrat într-un singur bloc de text simplu și invers, astfel încât există o corespondență unu-la-unu. Unele dovezi criptografice fac nu numai o permutare „înainte” disponibilă tuturor jucătorilor, ci și o permutare „inversă”.
Lucrări recente au arătat că un cifr ideal poate fi construit dintr-un oracol aleatoriu folosind rețele Feistel cu 10 runde [15] sau chiar 8 runde [16] .
Canetti, Goldreich și Halevi și-au exprimat o atitudine negativă față de dovezile bazate pe modelul oracolului aleatoriu [17] . Ei au demonstrat că există scheme de semnătură digitală și de criptare care se dovedesc sigure în cadrul modelului de oracol aleatoriu, dar vulnerabile la implementarea în aplicații reale. Ideea lor principală a fost să inventeze semnături digitale sau scheme de criptare proaste . În condiții normale, aceste scheme funcționează bine, dar în anumite condiții (mai ales o încălcare a aleatoriei) devin proaste. Cu toate acestea, cei trei autori au ajuns la concluzii diferite cu privire la utilitatea modelului de oracol aleatoriu.
Canetti consideră că modelul oracolului aleatoriu reprezintă o abstractizare nefericită și reduce valoarea metodei „reducerii contradicției”. El a sugerat că cercetarea științifică ar trebui îndreptată către căutarea unor proprietăți utile specifice ale modelului oracolului aleatoriu [18] .
Goldreich consideră că problema constă în caracterul incomplet al modelului și recomandă să nu fie incluse dovezile care folosesc această metodă. Cu toate acestea, el crede că modelul de oracol aleatoriu are o anumită valoare în testarea criptosistemelor pentru securitate [18] .
Halevi consideră că succesele actuale ale metodei de reducere la o contradicție sunt întâmplătoare: „Nu există niciun motiv să se afirme că toate schemele existente, a căror stabilitate a fost dovedită folosind modelul oracol aleatoriu, sunt de fapt stabile” [18] .