Distributional Collision Resistance Beyond One-Way Functions

Nir Bitansky, Iftach Haitner, Ilan Komargodski +1

Distributional collision resistance is a relaxation of collision resistance that only requires that it is hard to sample a collision $(x,y)$ where $x$ is uniformly random and $y$ i…