# 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 :) –  user46 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