Random oracle: Difference between revisions

Revision as of 20:16, 29 September 2006

Revision as of 12:27, 8 February 2007

Line 5:

In the more precise definition formalized by Bellare/Rogaway (1993), the random oracle produces a bit-string of infinite length which can be truncated to the length desired. When a random oracle is used within a security proof, it is made available to all players, including the adversary or adversaries. A single oracle may be treated as multiple oracles by pre-pending a fixed bit-string to the beginning of each query (e.g., queries formatted as "1|x" or "0|x" can be considered as calls to two separate random oracles).

No real function can implement 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.{{citationneededFact|date=February 2007}} Nonetheless, for any more natural protocol a proof of security in the random oracle model gives very strong evidence that an attack which does not break the other assumptions of the proof, if any (such as the hardness of [[integer factorization]]) must discover some unknown and undesirable property of the hash function used in the protocol to work. Many schemes have been proven secure in the random oracle model, for example [[Optimal Asymmetric Encryption Padding|OAEP]] and [[Probabilistic Signature Scheme|PSS]].

==See also==