Random oracle: Difference between revisions

Revision as of 11:32, 30 October 2004

Revision as of 23:21, 10 November 2004

Line 1:

A '''random oracle''' is a theoretical model of a perfect [[cryptographic hash function]]. Although notIt is used in practice,proofs itthat isindicate oftenthat used[[cryptography|cryptographic]] tosystems buildor aprotocols 'randomare oraclesecure model'by inshowing theoreticalthat [[cryptography]]an papersattacker asmust parteither ofconsider attemptshow tothe provehash thefunction securityworks, ofor asolve cryptographicsome other problem believed hard, in order to break the systemprotocol.

When a random oracle is given a query ''x'' it does the following,

*If the oracle has been given the query ''x'' before it responds with the same value it gave the last time.

*If the oracle hasn't been given the query ''x'' before it generates a [[random]] response which has uniform probability of being chosen from anywhere in the oracle's output ___domain.

No real hash function can implements a true random oracle. In fact, certain very artificial protocols have been constructed which are proven secure in the random oracle model, but which are trivially insecure when any real hash function is substituted for the random oracle. Nonetheless, for any more natural protocol a proof of security in the random oracle gives very strong evidence that an attack which does not break the other assumptions of the proof (such as the hardness of [[integer factorization]]) must discover some unknown and undesirable property of the hash function used in the protocol to work.

==See also==