Re: from random oracle model to pseudorandom oracle model

newstome_at_comcast.net
Date: 01/23/05 

Date: Sun, 23 Jan 2005 11:35:34 -0600

jwu1@lakeheadu.ca wrote:
> David Wagner wrote:
>> Jiang Wu wrote:
>> >Maybe we can revise the Random Oracle Methology to a "Pseudorandom
>> >Oracle Methology":
>> >1. design an ideal system in which all parties (including the
>> >adversary) have oracle access to a pseudorandom function, and proves
>> >the security of this ideal system.
>> >2. replaces the pseudorandom oracle by a good cryptographic hashing
>> >function such as SHA-1.
>>
>> I don't see how. A pseudorandom function is a keyed function
>> F(k,x). Are you going to give all parties oracle access to the
>> function F(k,.) in step 1.?
> Yes, it's the same as in the Random Oracle Methology. The only
> difference is, in Random Oracle Methology, the instance function is
> taken from all possible functions from X to Y (X is the message set and
> Y is the hash value set), while in "Pseudorandom Oracle Methology", the
> instance function is taken from a subset of all possible functions from
> X to Y.
>> If so, how are you going to implement
>> this in step 2.? You can't just pick a key k and publish it, since
>> the security of a pseudorandom function rests on the secrecy of the
>> key.
> In step 2, use a hash function to replace the oracle, it's the same as
> in Random Oracle Methology.

Which isn't secure (or at least, it's not foolproof). In fact, just
using a hash function in a simplistic way isn't secure at all because
of some extensibility properties of hash functions based on repeatedly
applying a compression function (like MD5 and SHA1) -- this was noted
in the original Random Oracle paper.

> I'm not sure whether it's equivalent to
> picking a key k and publishing it. If yes, then the Random Oracle
> Methology is at the same risk (which doesn't seem true); if no, your
> conclusion below is not sufficiently supported.

Yep -- which is really the key point of the "Random Oracle Model
Revisited" paper. They show that, in a certain sense, you *can't*
instantiate the random oracle in the "real world" in a way that
accurately reflects the important properties of a true random oracle.
Doesn't matter if you use an unkeyed hash function, or HMAC, or a
pseudorandom generator... 

-- 
That's News To Me!
newstome@comcast.net

Relevant Pages

  • Re: SHA1 and entropy
    ... we don't need to get into all that random oracle ... then let's just talk about SHA1. ... As for design principles for building the inner core of a hash function, ...
    (sci.crypt)
  • Re: Random oracles
    ... interesting part of the random oracle debate. ... is it possible that someone finds an attack ... and that does not translate into an attack on the hash function? ...
    (sci.crypt)
  • Re: Whos familiar with random oracle model?
    ... I am not an expert on the random oracle model. ... A practical random oracle is a hash function, ... lines of "the attacker needs X oracle invocations where the average ...
    (sci.crypt)
  • Re: from random oracle model to pseudorandom oracle model
    ... When random oracle is used in proof, ... that the attacker won't use any property of the hash function ... But in practice, the adversary could somehow ... the hash function in the proof while still assuming the attacker ...
    (sci.crypt)