Re-visiting Simon's separation between one-way permutations and collision-resistant Hash functions

One-way permutations are a fundamental cryptographic primitive which are believed not to imply other stronger primitives, such as collision-resistant hash functions, via a large class of techniques known as black-box separations. In his seminal work, Simon provides evidence for this belief by constructing an oracle world with a permutation oracle pi and collision finder oracle CF in which one-way permutations exist relative to pi, CF, but collision-resistant hash functions do not. Bitansky and Degwekar give a simplified proof of a weakened version of Simon's separation where the hash circuits passed to the CF-oracle can query pi, but not CF. Their argument relies on a smoothening step, and can even handle adversaries with query complexity at most O(2^(lambda / 6)) and success probability 2^(-lambda / 6). Our first contribution is a simplified proof of the same weakened _non-recursive_ separation, where we bypass the smoothening argument and use a compression argument in the style of Gennaro and Trevisan to achieve a bound for adversaries with o(2^(lambda / 2)) query/success ratio. We make progress towards obtaining a full proof of Simon's _recursive_ separation with respect to PPT adversaries, where hash circuits may also query CF. In this setting, the compression argument breaks down if there are _pseudo-collisions_, a concept we introduce in this thesis. We show that, for an appropriately shrunken compression set, individual pseudo-collisions occur only with negligible probability. Building on this, we propose a modified compression procedure that remains smoothening-free, and conjecture that it eliminates all pseudo-collisions, except with negligible probability.