Oracle aleatori

En criptografia, un oracle aleatori és un oracle (una caixa negra teòrica) que respon a cada petició diferent amb una resposta (veritablement) aleatòria escollida uniformement d'entre el seu domini de sortida. Expressat d'altra manera, un oracle aleatori és una funció matemàtica que assigna una sortida aleatòria del seu domini a cada entrada possible.

Els oracles aleatoris són una abstracció matemàtica utilitzada en demostracions criptogràfiques; s'acostumen a utilitzar quan no es coneix cap funció implementable que satisfaci les propietats requerides per a la demostració. Un sistema que sigui demostrat segur utilitzant una demostració d'aquest tipus es descriu com a segur en el model d'oracle aleatori (en contraposició amb la descripció de segur en el model estàndard). A la pràctica, els oracles aleatoris s'acostumen a utilitzar per a modelar funcions resum criptogràfiques en esquemes que requereixin assumpcions fortes de l'aleatorietat de la seva sortida. En aquest tipus de demostracions sovint es demostra que un sistema o protocol és segur mostrant que, per tal de trencar-lo, l'atacant necessita un comportament impossible per part de l'oracle, o que li cal solucionar algun problema matemàtic que es creu que és difícil. No totes les funcions de resum criptogràfiques requereixen oracles aleatoris: per a esquemes que només demanen propietats per a les quals es disposa de definicions al model estàndard (com per exemple resistència a les col·lisions) sovint l'oracle no és necessari.

Aplicacions

Els oracles aleatoris s'utilitzen normalment com a reemplaçament idealitzat de les funcions hash criptogràfiques en esquemes on es necessiten suposicions d'aleatorietat fortes de la sortida de la funció hash. Aquesta prova sovint mostra que un sistema o un protocol és segur mostrant que un atacant ha d'exigir un comportament impossible de l'oracle, o resoldre algun problema matemàtic que es creu dur per trencar-lo. Tanmateix, només demostra aquestes propietats en el model d'oracle aleatori, assegurant-se que no hi ha defectes importants de disseny. En general, no és cert que aquesta prova impliqui les mateixes propietats en el model estàndard. Tot i així, una prova en el model d'oracle aleatori es considera millor que cap prova de seguretat formal.

No tots els usos de les funcions hash criptogràfiques requereixen oracles aleatoris: els esquemes que només requereixen una o més propietats que tinguin una definició en el model estàndard (com la resistència a la col·lisió, la resistència a la preimatge, la resistència a la segona preimatge, etc.) sovint es poden demostrar segurs a l'estàndard. model (per exemple, el sistema criptogràfic Cramer–Shoup).

Els oracles aleatoris s'han considerat durant molt de temps en la teoria de la complexitat computacional, i molts esquemes s'han demostrat segurs en el model d'oracles aleatoris, per exemple Optimal Asymmetric Encryption Padding, RSA-FDH i Probabilistic Signature Scheme. El 1986, Amos Fiat i Adi Shamir van mostrar una aplicació important d'oracles aleatoris: l'eliminació de la interacció dels protocols per a la creació de signatures. El 1989, Russell Impagliazzo i Steven Rudich van mostrar la limitació dels oracles aleatoris, és a dir, que la seva existència per si sola no és suficient per a l'intercanvi de claus secretes.

El 1993, Mihir Bellare i Phillip Rogaway van ser els primers a defensar el seu ús en construccions criptogràfiques. En la seva definició, l'oracle aleatori produeix una cadena de bits de longitud infinita que es pot truncar a la longitud desitjada. Quan s'utilitza un oracle aleatori dins d'una prova de seguretat, es posa a disposició de tots els jugadors, inclosos l'adversari o els adversaris.

Vegeu també

• Família de funcions pseudoaleatòries

Enllaços externs

• Pseudorandom functions Arxivat 2015-03-21 a Wayback Machine.