I kryptografi är ett slumpmässigt orakel en idealiserad hashfunktion som, för varje ny begäran, producerar ett slumpmässigt svar, jämnt fördelat över värdeintervallet, med villkoret: om samma begäran kommer två gånger måste svaret vara detsamma. Med andra ord är ett slumpmässigt orakel en matematisk funktion , vald slumpmässigt, som mappar varje möjlig fråga till ett fast slumpmässigt svar från ett förberett svarsområde.
Slumpmässiga orakel som en matematisk abstraktion användes först i rigorösa kryptografiska bevis i en publikation från 1993 av Mihir Bellare och Philip Rogaway . De används ofta i fall där bevisningen inte kan göras med svagare antaganden om den kryptografiska hashfunktionen . Ett system som har visat sig säkert när varje hashfunktion ersätts av ett slumpmässigt orakel beskrivs som säkert i den slumpmässiga orakelmodellen, till skillnad från att vara säkert i standardkryptografimodellen .
Ett slumpmässigt orakel är mycket kraftfullt eftersom det har tre egenskaper: determinism , effektivitet och att säkerställa en enhetlig fördelning av de resulterande värdena [1] .
Slumpmässiga orakel används vanligtvis som en idealiserad ersättning för kryptografiska hashfunktioner i system där starka antaganden om hashutgångens slumpmässighet behövs [1] . Ett sådant bevis visar vanligtvis att systemet eller protokollet är säkert, vilket visar att angriparen måste kräva ett omöjligt beteende från oraklet, eller måste lösa något matematiskt problem som anses svårt att lösa. Inte all användning av kryptografiska hashfunktioner kräver slumpmässiga orakel [2] : scheman som kräver endast en eller ett fåtal egenskaper definierade i standardmodellen (såsom kollisionsmotstånd , förbildsmotstånd, andra förbildsmotstånd , etc.), kan ofta bevisas att vara säker i standardmodellen (t.ex. Cramer–Shope-kryptosystemet ).
Slumpmässiga orakel har länge ansetts i beräkningskomplexitetsteorin , och många system har bevisats säkra i den slumpmässiga orakelmodellen, såsom optimal asymmetrisk kryptering , RSA-FDH [3] och det probabilistiska signaturschemat . 1986 visade Amos Fiat och Adi Shamir [4] den huvudsakliga tillämpningen av slumpmässiga orakel - borttagandet av interaktion från protokoll för att skapa signaturer.
1989 visade Russell Impalazzo och Steven Rudich [5] en begränsning av slumpmässiga orakel, nämligen att deras existens ensam inte räcker för att utbyta en hemlig nyckel .
1993 var Mihir Bellare och Philippe Rogaway [6] de första som förespråkade deras användning i kryptografiska konstruktioner. Enligt deras definition skapar ett slumpmässigt orakel en bitsträng med oändlig längd som kan trunkeras till önskad längd.
När ett slumpmässigt orakel används som bevis på säkerhet blir det tillgängligt för alla spelare, inklusive motståndaren eller motståndarna. Ett orakel kan ses som flera orakel, före en fast bitsträng i början av varje begäran (till exempel kan förfrågningar formaterade som "1| x " eller "0| x " ses som anrop till två separata slumptal ). Orakel, liknande "00 | x ", "01 | x ", "10 | x " och "11 | x " kan användas för att representera anrop till fyra separata slumpmässiga orakel).
Ett slumpmässigt orakel är en kraftfull hypotetisk deterministisk funktion som effektivt beräknar enhetligt fördelade slumpvariabler . Modellen av ett slumpmässigt orakel antar att det inte bara finns ett slumpmässigt orakel, utan också en speciell agent - en imitator . Imitatören är tänkt att kunna imitera vilket slumpmässigt orakel som helst (även en angripare). Således, om någon vill applicera ett slumpmässigt orakel G på ett nummer a , då kommer han automatiskt att skicka en begäran till simulatorn till ett slumpmässigt orakel och få resultatet G(a) från honom . Simulatorn utför alltid ärligt varje begäran och returnerar alltid sitt resultat.
Tack vare denna regel kan simulatorn exakt efterlikna beteendet hos ett slumpmässigt orakel. Låt simulatorn upprätthålla en G-lista för oraklet G som innehåller par (a, G(a)) där de tidigare frågorna a lagras . Simuleringen är enkel: efter att ha tagit emot frågan a , kontrollerar simulatorn om den är lagrad i listan och i så fall returnerar värdet G(a) (det deterministiska resultatet av frågan), annars extraherar simulatorn ett nytt värde G( a) från den allmänna populationen av enhetligt fördelade tal , skickar ett svar och fyller i det givna paret (a, G(a)) i en sorterad lista som tar log N tidsenheter att söka (på grund av denna funktion, det slumpmässiga oraklet är effektivt).
Således imiteras det slumpmässiga oraklet exakt av den polynomiellt bundna algoritmen [7] .
Det finns några kända artificiella signatur- och krypteringsscheman som har visat sig vara säkra i den slumpmässiga orakelmodellen, men de är trivialt osäkra när någon verklig funktion ersätter det slumpmässiga oraklet. [8] Men för alla mer naturliga protokoll ger säkerhetsbeviset i den slumpmässiga orakelmodellen mycket starka bevis för protokollets praktiska säkerhet. [9]
I allmänhet, om ett protokoll bevisas vara säkert, måste attacker på det protokollet antingen gå utöver vad som har bevisats eller bryta mot ett av antagandena i beviset; till exempel, om beviset förlitar sig på komplexiteten i heltalsfaktorisering , för att bryta detta antagande måste man hitta en snabb heltalsfaktoriseringsalgoritm . Istället, för att bryta det slumpmässiga orakelantagandet, måste någon okänd och oönskad egenskap hos den faktiska hashfunktionen upptäckas ; för bra hashfunktioner , där sådana egenskaper anses osannolika, kan protokollet i fråga anses vara säkert. [tio]
Även om Baker-Gill-Solovey-satsen [11] [12] visade att det finns ett orakel A så att P A = NP A , visade efterföljande arbete av Bennett och Gill [13] att för ett slumpmässigt orakel B (en funktion från { 0,1 } n n till {0,1} så att varje ingångselement mappas till var och en av 0 eller 1 med sannolikhet 1/2, oavsett avbildning av alla andra indata), P B ⊊ NP B med sannolikhet 1. Liknande uppdelningar, och även det faktum att slumpmässiga orakel separerar klasser med en sannolikhet på 0 eller 1 (som en konsekvens av Kolmogorovs noll-ett-lag ), vilket ledde till skapandet av den slumpmässiga orakelhypotesen att två "acceptabla" komplexitetsklasser C 1 och C 2 är lika om och endast om de är lika (med sannolikhet 1) under ett slumpmässigt orakel (acceptabiliteten av komplexitetsklassen definieras i BG81 [13] Denna gissning visade sig senare vara falsk, eftersom de två acceptabla komplexitetsklasserna IP och PSPACE visades vara lika trots det faktum att IP A ⊊ PSPACE A för ett slumpmässigt orakel A med sannolikhet 1.
Ett idealiskt chiffer är ett slumpmässigt permutationsorakel som används för att modellera ett idealiserat blockchiffer [14] .
En godtycklig permutation dekrypterar varje chiffertextblock till ett och endast ett klartextblock och vice versa, så det finns en en-till-en-korrespondens. Vissa kryptografiska bevis gör inte bara en "framåt" permutation tillgänglig för alla spelare, utan också en "omvänd" permutation.
Nyligen arbete har visat att ett idealiskt chiffer kan konstrueras från ett slumpmässigt orakel med 10-runda [15] eller till och med 8-runda [16] Feistel-nätverk .
Canetti, Goldreich och Halevi uttryckte en negativ inställning till bevis baserade på den slumpmässiga orakelmodellen [17] . De visade att det finns digitala signaturer och krypteringssystem som bevisligen är säkra inom ramen för den slumpmässiga orakelmodellen, men sårbara för implementering i verkliga applikationer. Deras huvudidé var att uppfinna dåliga digitala signaturer eller krypteringsscheman . Under normala förhållanden fungerar dessa system bra, men under vissa förhållanden (mest ett brott mot slumpmässighet) blir de dåliga. De tre författarna kom dock till olika slutsatser angående användbarheten av den slumpmässiga orakelmodellen.
Canetti menar att den slumpmässiga orakelmodellen representerar en olycklig abstraktion och minskar värdet av metoden "motsägelseminskning". Han föreslog att vetenskaplig forskning borde inriktas på sökandet efter specifika användbara egenskaper hos den slumpmässiga orakelmodellen [18] .
Goldreich menar att problemet ligger i modellens ofullständighet och rekommenderar att bevis som använder denna metod inte tas med. Han menar dock att den slumpmässiga orakelmodellen har ett visst värde för att testa kryptosystem för säkerhet [18] .
Halevi anser att de nuvarande framgångarna med metoden att reducera till en motsägelse är tillfälliga: "Det finns ingen anledning att hävda att alla befintliga system, vars stabilitet har bevisats med hjälp av den slumpmässiga orakelmodellen, faktiskt är stabila" [18] .