No relativizing reduction from OWP to CRHF

Unconditional · against relativizing reductions · Sim98

Statement

Relative to a random permutation $\pi$ together with an oracle that finds collisions in circuits with $\pi$-gates, one-way permutations exist and collision-resistant hash functions do not, “for a suitably strong definition” of collision intractability; hence no relativizing, and in particular no fully-black-box, construction of a collision-resistant hash function from a one-way permutation exists — Sim98.