Re: Added hashes.

John A. Malley wrote:
> 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.

   I don't think you're going to be able to establish independence from
looking at the input/output pairs.
>
> 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

   If you know F and G are chosen uniformly at random from that set, you
already know know F or G are both "perfect" and you already know the
probability of their not being independent is negligible.

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

   I don't follow this. I take it that the probability you denote is
just P(F(x)=G(x)), taken over all possible x. That should be 2**-n,
right? Birthday paradox probabilities are closer to 2**(-n/2).

>
> 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.

   What's H?
   P(F(x)=F(y) AND G(x)=G(y)), taken over all <x,y> pairs, should be 2**-2n.
Note: If you're really going to use bitstrings of unlimited length as
the domain, is the criterion to be that for every eps>0 there exists an
N such that abs(P(F(x)=F(y) AND G(x)=G(y))-2**-2n)<eps when x and y vary
over all bitstrings of length less than m, for all m>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.

   It looks like you mean P(F(x)=F(y) AND G(j)=G(k))[taken over all
<x,y>]=2**-2n holds separately for all function J and K, where j=J(x)
and k=K(y)

But that's an impossible criterion. It's going to fail for, e.g., the
constant functions J(x)=1 and K(y)=1.

>
> 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.

   What's h()? What's H?

   I don't think you'll be able to assign a value to that probability
that will hold for all functions f() and g() (aka h()).
   Choosing f() and g() to each be the identity function, we expect the
probability to be 2**-2n.
   Choosing f() such that f(x) is a string that G maps to F(x), and
choosing g(x)=f(x) makes the expected probability 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...)

--Mike Amling
Received on Fri Dec 23 20:10:16 2005