May 11, 2021

SpywareNews.com

Dedicated Forum to help removing adware, malware, spyware, ransomware, trojans, viruses and more!

Distributional Collision Resistance Beyond One-Way Functions. (arXiv:2105.00710v1 [cs.CR])

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
emph{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.