Paper 2019/115

Distributional Collision Resistance Beyond One-Way Functions

Nir Bitansky, Iftach Haitner, Ilan Komargodski, and Eylon Yogev


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 is uniformly random conditioned on colliding with x. The notion lies between one-wayness and collision resistance, but its exact power is still not well-understood. On one hand, distributional collision resistant hash functions cannot be built from one-way functions in a black-box way, which may suggest that they are stronger. On the other hand, so far, they have not yielded any applications beyond one-way functions. Assuming distributional collision resistant hash functions, we construct constant-round statistically hiding commitment scheme. Such commitments are not known based on one-way functions and are impossible to obtain from one-way functions in a black-box way. Our construction relies on the reduction from inaccessible entropy generators to statistically hiding commitments by Haitner et al. (STOC '09). In the converse direction, we show that two-message statistically hiding commitments imply distributional collision resistance, thereby establishing a loose equivalence between the two notions. A corollary of the first result is that constant-round statistically hiding commitments are implied by average-case hardness in the class SZK (which is known to imply distributional collision resistance). This implication seems to be folklore, but to the best of our knowledge has not been proven explicitly. We provide yet another proof of this implication, which is arguably more direct than the one going through distributional collision resistance.

Available format(s)
Publication info
Preprint. Minor revision.
statistically hiding commitmentsdistributional collision resistance
Contact author(s)
eylony @ gmail com
2019-02-08: revised
2019-02-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nir Bitansky and Iftach Haitner and Ilan Komargodski and Eylon Yogev},
      title = {Distributional Collision Resistance Beyond One-Way Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2019/115},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.