2
$\begingroup$

Why does pre-image resistance not guarantee strong collision resistance?

Logically I can make sense of this, but I am wondering if there's any general theorem that proves this?

$\endgroup$
2
$\begingroup$

With the definitions that a function $F$ is

  • (strongly) collision-resistant when a [computationally bounded] adversary can't [with sizable odds] exhibit any $(a,b)$ with $a\ne b$ and $F(a)=F(b)$;
  • first-preimage-resistant when, given $f$ determined as $F(a)$ for an unknown random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with $F(b)=f$;
  • second-preimage-resistant when, given a random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with $a\ne b$ and $F(a)=F(b)$;

neither form of pre-image resistance guarantees (strong) collision resistance. As to why: there's no argument that such guarantee should hold; and we have counterexamples, both practical (e.g. MD5), and theoretical.

Consider an hypothetical random function $H$ from bitstrings to $k$-bit bitstrings; or a good practical cryptographic hash with $k$-bit output (assuming that exists). This $H$ has all three properties, for large enough $k$. Define another function $F$, as $$F(x)=\begin{cases}H(\mathtt{“b”})&\text{if }x\text{ is the string }\mathtt{“a”}\\H(x)&\text{otherwise}\\\end{cases}$$ $F$ is not collision-resistant since the strings $\mathtt{“a”}$ and $\mathtt{“b”}$ collide; but is preimage-resistant (in both senses) for large enough $k$.

The above counterexample still works if we use quantitative definitions of the three properties, requiring effort $O(2^{k/2})$ to break collision-resistance, and effort $O(2^k)$ to break preimage-resistance.

$\endgroup$
  • $\begingroup$ Thanks for the response fgrieu. What about the other way? Do you know of any theorems that prove Strong collision resistance does not imply pre-image resistance? $\endgroup$ – Syed Rahman Nov 28 '16 at 21:21
  • $\begingroup$ @Syed Rahman: try this question. $\endgroup$ – fgrieu Nov 28 '16 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.