8
$\begingroup$

Let's assume a simple algorithm like the Skein hash function.

Is it possible, given the algorithm, to construct a proof that it does not have a particular distinguisher, something like:

$P(xyz)$ is the probability that $xyz$ is truly random over some alphabet,

Given $\vert y \vert = l$, for some fixed length l, $z = f(x)$ (i.e., $z$ is dependent on $x$).

Not in general, of course, but for a particular such distinguisher.

$\endgroup$
5
  • $\begingroup$ Welcome to crypto.se; your Q has been moved here on account of being more on topic here than on SO - do feel free to register an account to pick up your rep and more importantly responses here :) $\endgroup$
    – user46
    Commented Apr 23, 2012 at 9:12
  • $\begingroup$ Whats the policy on here on helping people answer what are pretty homework questions/ facilitating cheating? $\endgroup$ Commented Apr 24, 2012 at 1:59
  • 4
    $\begingroup$ 1 - This isn't a homework question. I asked because I was wondering if such proofs are constructed for hash functions. 2 - If it was a homework, the homework would have been turned in long ago - the question was first asked over a year ago! $\endgroup$
    – Vanwaril
    Commented Apr 24, 2012 at 2:13
  • $\begingroup$ There is at least some PRNGs for which proofs exist that show that they're indistinguishable provided a certain other problem is hard. en.wikipedia.org/wiki/Blum_Blum_Shub $\endgroup$ Commented Apr 25, 2012 at 12:18
  • $\begingroup$ The hash function Skein is not exactly what I would call "simple" from the point of view of understanding the way it maps its inputs to outputs. Otherwise, one would "simply" find pre-images and collisions for it! $\endgroup$
    – bob
    Commented Oct 29, 2012 at 12:46

1 Answer 1

4
$\begingroup$

There are a number of distinguishers that it it would be easy to prove are not present in a hash function.

For example, I can easily prove that Skein does not have the distinguisher "the 2nd bit in the output is equal to the first bit of the output with probability 1". The proof would be a simple example of a message whose digest does not have this property (which should be fairly easy to find).

For more interesting distinguishers, the problem becomes much harder (on a side note, is the distinguisher really interesting if I can prove it doesn't hold for a particular hash function?).

My gut feeling is that yes, one could come up with an "interesting" distinguisher and then show that it doesn't hold for the hash function, but I can not offer more than a gut feeling.

$\endgroup$
1
  • $\begingroup$ Yeah, I was wondering if there were 'real' arguments for 'real' hashing functions that showed one did not contain a distinguisher that another is susceptible to. $\endgroup$
    – Vanwaril
    Commented Apr 25, 2012 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.