Re: Added hashes.

John A. Malley wrote:
>There are two worlds, world 0 consists of two random oracles returning
>strings from {0,1}^n, and world 1 consists of two nonkeyed hash functions
>G, H that both map {0,1}^* -> {0,1}^n. The Adversary is given oracle
>access to the outputs of the random oracles, and the outputs of the two
>nonkeyed hash functions. Each time the Adversary "invokes" the oracle
>access, he gets a pair of outputs.
>
>Now, in world 1, each time the oracle access is invoked, a random input
>for the nonkeyed hash functions is selected at random from a set of
>inputs, and that value is fed into both hash functions.
>
>The game is played by flipping a coin, heads the Adversary gets world 0,
>tails the Adversary gets world 1.
>
>The Adversary asks for as many output pairs via oracle access as he
>can given his computational resources, and tries to determine with
>non-negligible probability which world he's in.

Unfortunately, I suspect this is probably too weak. It only provides
any kind of security if the adversary never gets to see any hash input;
otherwise, all bets are off. But protocols in the real world often let
the adversary see the input to the hash, so even if the hashes meet this
condition, that tells us nothing about what will happen when we use the
hashes with a protocol that lets the adversary ever see any part of any
hash input (or even worse, choose a part of it).

Here's another way to put it. Suppose n = 160, and the world chooses
a random 320-bit input to send to each hash. Define G,H by
  G(x) = first160bits(x) H(x) = last160bits(x).
Then G,H form a pair of hashes that would be considered "secure" under
your definition, but that are clearly cryptographically useless.
Received on Fri Dec 23 20:10:21 2005