I kryptografi er et tilfældigt orakel en idealiseret hash-funktion , der for hver ny anmodning producerer et tilfældigt svar, jævnt fordelt over værdiintervallet, med betingelsen: hvis den samme anmodning kommer to gange, så skal svaret være det samme. Med andre ord er et tilfældigt orakel en matematisk funktion , der er valgt tilfældigt, der kortlægger hver mulig forespørgsel til et fast tilfældigt svar fra et forudforberedt svarområde.
Tilfældige orakler som en matematisk abstraktion blev først brugt i strenge kryptografiske beviser i en publikation fra 1993 af Mihir Bellare og Philip Rogaway . De bruges almindeligvis i tilfælde, hvor beviset ikke kan udføres ved hjælp af svagere antagelser om den kryptografiske hash-funktion . Et system, der har vist sig at være sikkert, når hver hash-funktion erstattes af et tilfældigt orakel, beskrives som sikkert i den tilfældige orakelmodel, i modsætning til at være sikkert i standardkryptografimodellen .
Et tilfældigt orakel er meget kraftfuldt , fordi det har tre egenskaber: determinisme , effektivitet og sikring af en ensartet fordeling af de resulterende værdier [1] .
Tilfældige orakler bruges almindeligvis som en idealiseret erstatning for kryptografiske hash-funktioner i skemaer, hvor stærke antagelser om tilfældigheden af hash-output er nødvendige [1] . Et sådant bevis viser normalt, at systemet eller protokollen er sikker, hvilket viser, at angriberen skal kræve umulig adfærd fra oraklet, eller skal løse et matematisk problem, som anses for vanskeligt at løse. Ikke alle anvendelser af kryptografiske hash-funktioner kræver tilfældige orakler [2] : skemaer, der kun kræver en eller nogle få egenskaber defineret i standardmodellen (såsom kollisionsmodstand , præbilledemodstand, anden præbilledemodstand osv.), kan ofte bevises at være sikker i standardmodellen (f.eks . Cramer-Shope-kryptosystemet ).
Tilfældige orakler har længe været overvejet i beregningsmæssig kompleksitetsteori , og mange skemaer har vist sig at være sikre i den tilfældige orakelmodel, såsom optimal asymmetrisk kryptering , RSA-FDH [3] og det probabilistiske signaturskema . I 1986 viste Amos Fiat og Adi Shamir [4] hovedanvendelsen af tilfældige orakler - fjernelse af interaktion fra protokoller til at skabe signaturer.
I 1989 demonstrerede Russell Impalazzo og Steven Rudich [5] en begrænsning af tilfældige orakler, nemlig at deres eksistens alene ikke er nok til at udveksle en hemmelig nøgle .
I 1993 var Mihir Bellare og Philippe Rogaway [6] de første til at anbefale deres brug i kryptografiske konstruktioner. Efter deres definition skaber et tilfældigt orakel en bitstreng med uendelig længde , der kan afkortes til den ønskede længde.
Når et tilfældigt orakel bruges som bevis på sikkerhed, bliver det tilgængeligt for alle spillere, inklusive modstanderen eller modstanderne. Et orakel kan opfattes som flere orakler, foran en fast bitstreng i starten af hver anmodning (for eksempel kan anmodninger formateret som "1| x " eller "0| x " opfattes som kald til to separate tilfældige tal ). Orakler, der ligner "00 | x ", "01 | x ", "10 | x " og "11 | x " kan bruges til at repræsentere opkald til fire separate tilfældige orakler).
Det tilfældige orakel er en kraftfuld hypotetisk deterministisk funktion, der effektivt beregner ensartet fordelte tilfældige variabler . Modellen af et tilfældigt orakel antager eksistensen af ikke kun et tilfældigt orakel, men også en speciel agent - en imitator . Imitatoren formodes at være i stand til at efterligne ethvert tilfældigt orakel (selv en angriber). Således, hvis nogen ønsker at anvende et tilfældigt orakel G til et tal a , så sender han automatisk en anmodning til simulatoren til et tilfældigt orakel og får resultatet G(a) fra ham . Simulatoren udfører altid ærligt enhver anmodning og returnerer altid sit resultat.
Takket være denne regel kan simulatoren nøjagtigt efterligne opførselen af et tilfældigt orakel. Lad simulatoren opretholde en G-liste for oraklet G, der indeholder par (a, G(a)), hvor de tidligere forespørgsler a er gemt . Simuleringen er enkel: efter at have modtaget forespørgslen a , kontrollerer simulatoren, om den er gemt på listen, og returnerer i så fald værdien G(a) (det deterministiske resultat af forespørgslen), ellers udtrækker simulatoren en ny værdi G( a) fra den generelle population af ensartet fordelte tal , sender et svar og udfylder det givne par (a, G(a)) i en sorteret liste, der tager log N tidsenheder at søge (på grund af denne funktion, det tilfældige orakel er effektiv).
Således er det tilfældige orakel nøjagtigt efterlignet af den polynomielt afgrænsede algoritme [7] .
Der er kendt nogle kunstige signatur- og krypteringssystemer , som har vist sig at være sikre i den tilfældige orakel-model, men de er trivielt usikre, når en reel funktion erstatter det tilfældige orakel. [8] Men for enhver mere naturlig protokol giver beviset for sikkerhed i den tilfældige orakelmodel meget stærke beviser for protokollens praktiske sikkerhed. [9]
Generelt, hvis en protokol viser sig at være sikker, skal angreb på denne protokol enten gå ud over det, der er blevet bevist, eller overtræde en af antagelserne i beviset; for eksempel, hvis beviset er afhængigt af kompleksiteten af heltalsfaktorisering , for at bryde denne antagelse skal man finde en hurtig heltalsfaktoriseringsalgoritme . I stedet, for at bryde den tilfældige orakel-antagelse, skal en ukendt og uønsket egenskab ved den faktiske hash-funktion opdages ; for gode hash-funktioner , hvor sådanne egenskaber anses for usandsynlige, kan den pågældende protokol betragtes som sikker. [ti]
Selvom Baker-Gill-Solovey-sætningen [11] [12] viste, at der eksisterer et orakel A, således at P A = NP A , viste efterfølgende arbejde af Bennett og Gill [13] , at for et tilfældigt orakel B (en funktion fra { 0,1 } n n til {0,1}, så hvert input-element afbildes til hver af 0 eller 1 med sandsynlighed 1/2, uanset afbildning af alle andre input), P B ⊊ NP B med sandsynlighed 1. Lignende opdelinger, og også det faktum, at tilfældige orakler adskiller klasser med en sandsynlighed på 0 eller 1 (som en konsekvens af Kolmogorovs nul-en-lov ), hvilket førte til skabelsen af den tilfældige orakelhypotese, at to "acceptable" kompleksitetsklasser C 1 og C 2 er lige, hvis og kun hvis de er ens (med sandsynlighed 1) under et tilfældigt orakel (acceptabiliteten af kompleksitetsklassen er defineret i BG81 [13] Denne formodning har senere vist sig at være falsk, da de to acceptable kompleksitetsklasser IP og PSPACE viste sig at være ens på trods af, at IP A ⊊ PSPACE A for et tilfældigt orakel A med sandsynlighed 1.
En ideel chiffer er et tilfældigt permutationsorakel , der bruges til at modellere en idealiseret blokchiffer [14] .
En vilkårlig permutation dekrypterer hver chiffertekstblok til én og kun én almindelig tekstblok og omvendt, så der er en en-til-en korrespondance. Nogle kryptografiske beviser gør ikke kun en "fremad" permutation tilgængelig for alle spillere, men også en "omvendt" permutation.
Nyere arbejde har vist, at en ideel chiffer kan konstrueres ud fra et tilfældigt orakel ved hjælp af 10-runde [15] eller endda 8-runde [16] Feistel-netværk .
Canetti, Goldreich og Halevi udtrykte en negativ holdning til beviser baseret på den tilfældige orakelmodel [17] . De demonstrerede, at der findes digitale signatur- og krypteringssystemer , der beviseligt er sikre inden for rammerne af den tilfældige orakelmodel, men sårbare over for implementering i rigtige applikationer. Deres hovedidé var at opfinde dårlige digitale signaturer eller krypteringssystemer . Under normale forhold fungerer disse ordninger godt, men under visse forhold (for det meste en krænkelse af tilfældighed) bliver de dårlige. De tre forfattere kom dog til forskellige konklusioner med hensyn til anvendeligheden af den tilfældige orakelmodel.
Canetti mener, at den tilfældige orakelmodel repræsenterer en uheldig abstraktion og reducerer værdien af "modsigelsesreduktion"-metoden. Han foreslog, at videnskabelig forskning skulle rettes mod at søge efter specifikke nyttige egenskaber ved den tilfældige orakelmodel [18] .
Goldreich mener, at problemet ligger i modellens ufuldstændighed og anbefaler, at beviser, der anvender denne metode, ikke medtages. Han mener dog, at den tilfældige orakelmodel har en vis værdi i at teste kryptosystemer for sikkerhed [18] .
Halevi mener, at de nuværende succeser med metoden til at reducere til en selvmodsigelse er tilfældige: "Der er ingen grund til at hævde, at alle eksisterende ordninger, hvis stabilitet er blevet bevist ved hjælp af den tilfældige orakelmodel, faktisk er stabile" [18] .