3 ms·
> `f : {0,1}^n → {0,1}^n` is a perfect PRF if and only if given a distribution `d : {0,1}^n → [0,1]`, `f` maps inputs following the distribution `d` to the unif
by thomasahle 10y ago
> `f : {0,1}^n → {0,1}^n` is a perfect PRF if and only if given a distribution `d : {0,1}^n → [0,1]`, `f` maps inputs following the distribution `d` to the uniform distribution.
Is this even possible? If the distribution `d` always returns 0, how can a function make it uniform?
It would be nice, if the article would go into more details on how SeaHash obtains this property, and how it related to collision avoidance.
- petters 10y agoIt's not clear what the author means here. This is not a very mathematical article. (Nit: d is a distribution so it can not always return 0 -- it has to sum to 1. But your point stands.)
- pdpi 10y agoI believe the point is that you get a uniform distirbution of 1s and 0s after going through the PRF irrespectively of the distribution of 1s and 0s in the input. This is certainly a desirable property for a hash function.
- deleted 10y ago[deleted]
- jamessb 10y agoA (translated) Dirac delta function might be a better example [1]. [1]: https://en.wikipedia.org/wiki/Dirac_delta_function https://en.wikipedia.org/wiki/Dirac_delta_function