Re: Added hashes.

Mike Amling wrote:
[...]
> E.g. F's oracle keeps track of all previous queries, and responds with
> a fresh random bitstring for novel queries. G calls F for each query and
> may or may not be responding with an AES encryption of F's value using a
> secret key. (I guess this isn't a perfect example, since if all
> collisions in F were also collisions in G, you'd know they were not
> independent.)
>
> --Mike Amling

I think that is a step in the right direction for defining independent hash
functions. Two hash functions are independent (with respect a level of resources
defined for an adversary) if the pair cannot be distinguished from a pair of
random oracles, both oracles keeping track of all previous queries in order to
respond a fresh random string for novel queries.

Ideally, (I think) two hashes F: (0,1)^* -> {0,1}^n, and G: {0,1}^* -> {0,1}^n,
chosen uniformly at random from the set of all possible mappings, can be called
"independent" if

P(F(x) = y AND G(x) = y ) is the birthday paradox collision probability (on the
order of 2^-(n-1),

and

P(F(x) = F(y) AND G(x) = G(y) ) is the probability of a collision in G and H
with the same input pair <x,y>, the birthday paradox collision probability
squared, on the order of 2^-n.

Hm, sitting here typing, and it occurs to me that

P(F(x) = F(y) AND G(j) = G(k) ), where j is a function of x and k is a function
of y, for an input pair <x,y>, might be a stronger statement about independence.

P(F(x) = F(y) AND G(f(x)) = G(h(y)) ) is the probability of a collision in G and
H with the same input pair <x,y> and functions f(), g() relating j and k to x
and y, the birthday paradox collision probability squared, on the order of 2^-n.

(We would need to say something about the nature of f() and g() in that
definition, though, it's not complete and I bet someone will immediately think
of a degenerate or corner condition input that won't make it work. :-) )

Does this make sense? Or did I miss something (and I know I could, I am so sleep
deprived this quarter...)

John A. Malley
102667.2235@compuserve.com

-- 
"Support Our 'OOPS!"
- George, Condi, Rummy and Dick