What are some examples of an iterative hash function, where permutations along
A ---> B ---> C ---> D
can be compared, for example D/B, to see if D is a trail from B, and possibly the distance in steps from C to D
1
-
2$\begingroup$ I guess you can use any hash function, you just try to hash B Until you get D and count the number. $\endgroup$– eckesNov 13, 2017 at 7:16
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
SHA-256 or any at least as wide unbroken cryptographic hash will do, if the elements can be that wide (except the first A which is unconstrained). With a $w$-bit ideal hash, probability of entering a cycle in $n\ge1$ steps are $p<n^2/2^{w+1}$, by the Birthday problem. E.g. $w=256$, $n\le2^{100}$ gives residual odds of entering a cycle $p<2^{-57}$, and that's good enough in practice.
Things are not quite as easy when $w$ must be smaller; e.g. for $w=160$. In this case, we want a hash function less likely to iterate than random; that's not a common beast (to be continued after thinking about it).
