Salaustekniikassa satunnainen oraakkeli on idealisoitu hash - funktio , joka jokaiselle uudelle pyynnölle tuottaa satunnaisen vastauksen, joka jakautuu tasaisesti arvoalueelle, ja jossa on ehto: jos sama pyyntö saapuu kahdesti, vastauksen on oltava sama. Toisin sanoen satunnainen oraakkeli on satunnaisesti valittu matemaattinen funktio , joka kartoittaa jokaisen mahdollisen kyselyn kiinteäksi satunnaiseksi vastaukseksi valmiilta vastausalueelta.
Satunnaisia oraakkeleita matemaattisena abstraktiona käytettiin ensimmäisen kerran tiukoissa kryptografisissa todisteissa Mihir Bellaren ja Philip Rogawayn julkaisussa vuonna 1993 . Niitä käytetään yleisesti tapauksissa, joissa todistetta ei voida tehdä käyttämällä heikompia oletuksia kryptografisesta hajautusfunktiosta . Järjestelmä, joka on osoittautunut turvalliseksi, kun jokainen hash-funktio korvataan satunnaisella oraakkelilla, kuvataan satunnaisessa oraakkelimallissa turvalliseksi, toisin kuin tavallisessa salausmallissa .
Satunnainen oraakkeli on erittäin voimakas , koska sillä on kolme ominaisuutta: determinismi , tehokkuus ja tuloksena olevien arvojen tasaisen jakautumisen varmistaminen [1] .
Satunnaisia oraakkeleita käytetään yleisesti idealisoituna korvaajana kryptografisille hash-funktioille järjestelmissä, joissa tarvitaan vahvoja oletuksia hash-tulosteen satunnaisuudesta [1] . Tällainen todiste yleensä osoittaa, että järjestelmä tai protokolla on turvallinen, mikä osoittaa, että hyökkääjän on vaadittava oraakkelilta mahdotonta käyttäytymistä tai ratkaistava jokin vaikeasti ratkaistava matemaattinen ongelma. Kaikki kryptografisten hajautusfunktioiden käyttötavat eivät vaadi satunnaisia oraakkeleita [2] : skeemat, jotka vaativat vain yhden tai muutaman vakiomallissa määritellyn ominaisuuden (kuten törmäyskestävyys , esikuvan vastus, toisen esikuvan vastustuskyky jne.), voidaan usein todistaa olla turvallinen vakiomallissa (esim . Cramer-Shope-salausjärjestelmä ).
Satunnaisia oraakkeleita on jo pitkään otettu huomioon laskennallisessa monimutkaisuusteoriassa , ja monet skeemat on todistettu turvallisiksi satunnaisessa oraakkelimallissa, kuten optimaalinen epäsymmetrinen salaus , RSA-FDH [3] ja todennäköisyyspohjainen allekirjoitusmalli . Vuonna 1986 Amos Fiat ja Adi Shamir [4] osoittivat satunnaisten oraakkelien pääsovelluksen - vuorovaikutuksen poistamisen protokollien allekirjoitusten luomiseksi.
Vuonna 1989 Russell Impalazzo ja Steven Rudich [5] osoittivat satunnaisten oraakkelien rajoituksen, nimittäin sen, että niiden olemassaolo ei yksin riitä salaisen avaimen vaihtamiseen .
Vuonna 1993 Mihir Bellare ja Philippe Rogaway [6] olivat ensimmäiset, jotka puolsivat niiden käyttöä kryptografisissa rakenteissa. Määritelmänsä mukaan satunnainen oraakkeli luo äärettömän pituisen bittijonon , joka voidaan lyhentää haluttuun pituuteen.
Kun satunnaista oraakkelia käytetään todisteena turvallisuudesta, se tulee kaikkien pelaajien saataville, myös vastustaja tai vastustajat. Yhtä oraakkelia voidaan pitää useana oraakkelina, joka lisää kiinteän bittijonon jokaisen pyynnön alussa (esimerkiksi "1| x " tai "0| x " muotoilla muotoiltuja pyyntöjä voidaan pitää kutsuina kahdelle erilliselle satunnaisnumerolle ). Oraakkelit, samankaltaiset kuin "00 | x ", "01 | x ", "10 | x " ja "11 | x " voidaan käyttää edustamaan kutsuja neljälle erilliselle satunnaiselle oraakkelille).
Satunnaisoraakkeli on voimakas hypoteettinen deterministinen funktio, joka laskee tehokkaasti tasaisesti jakautuneita satunnaismuuttujia . Satunnaisen oraakkelin malli olettaa, että on olemassa paitsi satunnainen oraakkeli myös erikoisagentti - jäljittelijä . Jäljittelijän oletetaan pystyvän jäljittelemään mitä tahansa satunnaista oraakkelia (jopa hyökkääjää). Siten, jos joku haluaa soveltaa satunnaista oraakkelia G numeroon a , hän lähettää automaattisesti pyynnön simulaattoriin satunnaiselle oraakkelille ja saa tuloksen G(a) häneltä . Simulaattori suorittaa aina rehellisesti minkä tahansa pyynnön ja palauttaa aina tuloksensa.
Tämän säännön ansiosta simulaattori voi jäljitellä tarkasti satunnaisen oraakkelin käyttäytymistä. Anna simulaattorin ylläpitää G-listaa oraakkelille G, joka sisältää parit (a, G(a)) , joihin aiemmat kyselyt a on tallennettu . Simulaatio on yksinkertainen: saatuaan kyselyn a simulaattori tarkistaa, onko se tallennettu listaan ja jos on, palauttaa arvon G(a) (kyselyn deterministinen tulos), muuten simulaattori poimii uuden arvon G( a) tasaisesti jakautuneiden lukujen yleisestä populaatiosta lähettää vastauksen ja täyttää annetun parin (a, G(a)) lajiteltuun luetteloon, jonka etsimiseen kuluu log N aikayksikköä (tämän ominaisuuden vuoksi satunnainen oraakkeli on tehokas).
Näin ollen satunnaista oraakkelia jäljittelee tarkasti polynomirajoitettu algoritmi [7] .
Tunnetaan joitain keinotekoisia allekirjoitus- ja salausjärjestelmiä , jotka ovat osoittautuneet turvallisiksi satunnaisessa oraakkelimallissa, mutta ne ovat triviaalisti turvattomia, kun mikä tahansa todellinen toiminto korvaa satunnaisen oraakkelin. [8] Kuitenkin kaikille luonnollisemmille protokollille satunnaisen oraakkelimallin turvallisuuden todiste tarjoaa erittäin vahvan todisteen protokollan käytännön turvallisuudesta. [9]
Yleensä, jos protokolla todistetaan turvalliseksi, siihen protokollaan kohdistuvien hyökkäysten on joko ylitettävä se, mikä on todistettu, tai rikottava jotakin todisteessa olevista oletuksista; Jos todistus esimerkiksi perustuu kokonaislukujen tekijöiden jakamisen monimutkaisuuteen, tämän oletuksen murtamiseksi on löydettävä nopea kokonaislukujen tekijöiden jakamisen algoritmi . Sen sijaan satunnaisen oraakkeli-oletuksen murtamiseksi on löydettävä jokin todellisen hash-funktion tuntematon ja ei-toivottu ominaisuus ; Hyvien hash-funktioiden osalta, jos tällaisia ominaisuuksia pidetään epätodennäköisinä, kyseistä protokollaa voidaan pitää turvallisena. [kymmenen]
Vaikka Baker-Gill-Soloveyn lause [11] [12] osoitti, että on olemassa oraakkeli A, jolla P A = NP A , myöhempi Bennettin ja Gillin [13] työ osoitti, että satunnaiselle oraakkelille B (funktio lähteestä { 0,1 } n n - {0,1} niin, että jokainen syöteelementti vastaa arvoon 0 tai 1 todennäköisyydellä 1/2, riippumatta kaikkien muiden syötteiden kartoittamisesta), P B ⊊ NP B todennäköisyydellä 1. Samanlaiset splitsit, ja myös se tosiasia, että satunnaiset oraakkelit erottavat luokkia todennäköisyydellä 0 tai 1 ( Kolmogorovin nolla-yksilain seurauksena ), mikä johti satunnaisen oraakkelihypoteesin luomiseen, että kaksi "hyväksyttävää" kompleksisuusluokkaa C 1 ja C 2 ovat yhtä suuret silloin ja vain, jos ne ovat yhtä suuret (todennäköisyydellä 1) satunnaisessa oraakkelissa (monimutkaisuusluokan hyväksyttävyys on määritelty BG81:ssä [13] Tämä olettamus osoittautui myöhemmin vääräksi, koska kaksi hyväksyttävää kompleksisuusluokkaa IP ja PSPACE osoitettiin yhtäläisiksi huolimatta siitä, että IP A ⊊ PSPACE A satunnaiselle oraakkelille A todennäköisyydellä 1.
Ihanteellinen salaus on satunnainen permutaatiooraakkeli , jota käytetään idealisoidun lohkosalauksen mallintamiseen [14] .
Satunnainen permutaatio purkaa jokaisen salatekstilohkon yhdeksi ja vain yhdeksi selvätekstilohkoksi ja päinvastoin, joten on olemassa yksi-yhteen vastaavuus. Jotkut kryptografiset todisteet tarjoavat paitsi "eteenpäin"-permutaation kaikille pelaajille, vaan myös "käänteisen" permutaation.
Viimeaikainen tutkimus on osoittanut, että ihanteellinen salaus voidaan rakentaa satunnaisesta oraakkelista käyttämällä 10-kierroksen [15] tai jopa 8-kierroksen [16] Feistel-verkkoja .
Canetti, Goldreich ja Halevi ilmaisivat kielteisen asenteen satunnaiseen oraakkelimalliin perustuviin todisteisiin [17] . He osoittivat, että on olemassa digitaalisia allekirjoitus- ja salausjärjestelmiä , jotka ovat todistetusti turvallisia satunnaisen oraakkelimallin puitteissa, mutta alttiin toteuttaa todellisissa sovelluksissa. Heidän pääideansa oli keksiä huonoja digitaalisia allekirjoituksia tai salausjärjestelmiä . Normaaleissa olosuhteissa nämä suunnitelmat toimivat hyvin, mutta tietyissä olosuhteissa (useimmiten sattumanvaraisuuden rikkominen) niistä tulee huonoja. Kolme kirjoittajaa tulivat kuitenkin erilaisiin johtopäätöksiin satunnaisen oraakkelimallin hyödyllisyydestä.
Canetti uskoo, että satunnainen oraakkelimalli edustaa valitettavaa abstraktiota ja vähentää "ristiriitojen vähentämisen" menetelmän arvoa. Hän ehdotti, että tieteellinen tutkimus olisi suunnattava satunnaisoraakkelimallin tiettyjen hyödyllisten ominaisuuksien etsimiseen [18] .
Goldreich uskoo, että ongelma on mallin epätäydellisyydessä ja suosittelee, että tätä menetelmää käyttäviä todisteita ei oteta mukaan. Hän kuitenkin uskoo, että satunnaisella oraakkelimallilla on jonkin verran arvoa kryptojärjestelmien turvallisuuden testaamisessa [18] .
Halevi uskoo, että ristiriitaiseksi pelkistysmenetelmän nykyiset onnistumiset ovat sattumanvaraisia: "Ei ole mitään syytä väittää, että kaikki olemassa olevat skeemat, joiden stabiilius on todistettu satunnaisoraakkelimallilla, ovat itse asiassa stabiileja" [18] .