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

• 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 :)
– user46
Commented Apr 23, 2012 at 9:12
• Whats the policy on here on helping people answer what are pretty homework questions/ facilitating cheating? Commented Apr 24, 2012 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! Commented Apr 24, 2012 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 Commented Apr 25, 2012 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
Commented Oct 29, 2012 at 12:46