22 October 2026
One of the things I have always loved in cryptography is black-box separation results [RTV04]. Two classic examples are the separation of key agreement (and hence Public Key Encryption) from One-way Permutations (OWP) by Impagliazzo and Rudich [IR89], and the separation of Collision Resistant Hash Functions (CRHF) from OWPs by Simon [Sim98]. After Simon’s seminal paper, I started reading Hsiao and Reyzin’s paper on separating public-coin CRHFs from secret-coin CRHFs [HR04], which claims on the first page that
It is easy to see there is no meaningful way to formalize the notion of collision-resistance for a single fixed-output-length hash function.