Can a proof be constructed to show there is no distinguisher?

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.

-

migrated from stackoverflow.comApr 23 '12 at 9:05

This question came from our site for professional and enthusiast programmers.

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 :) –  Ninefingers Apr 23 '12 at 9:12
Whats the policy on here on helping people answer what are pretty homework questions/ facilitating cheating? –  imichaelmiers Apr 24 '12 at 1:59
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! –  Vanwaril Apr 24 '12 at 2:13
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 –  CodesInChaos Apr 25 '12 at 12:18
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! –  bob Oct 29 '12 at 12:46

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.

-
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. –  Vanwaril Apr 25 '12 at 1:16