1
$\begingroup$

Supposing a secure hash function $f(\cdot): \{0,1\}^* \rightarrow \{0,1\}^n$ satisfies pre-image resistance.

That is, given a hash value $y$ it should be difficult to find any message $x$ such that $y = f(x)$ within $O(2^{n})$ efforts.

The question is:

Given $y \in \{0,1\}^n$, if we find $x_1,x_2$ such that $f(x_1) + Rf(x_2) = y$, can we say that we break the pre-image resistance?, where $R$ is a positive integer.

Improve this question
$\endgroup$
4
  • $\begingroup$ An interesting result of this $f(x_1) + Rf(x_2) = y$ is one gets pre-image of $f(x_1) = y + Rf(x_2)$ or $Rf(x_2) = y+ f(x_1) $ but that doesn't help to find arbitrary since we don't have the control, $\endgroup$
    – kelalaka
    Commented Dec 21, 2020 at 11:28
  • $\begingroup$ @kelalaka Yes, I hope this result can solve the problem. $\endgroup$
    – Zi-Yuan Liu
    Commented Dec 21, 2020 at 12:03
  • 1
    $\begingroup$ Hint: assume $f$ is an ideal hash function (thus collision-resistant by your definition). For any fixed $R$, find an algorithm of cost less than $O(2^n)$ that, given $y \in \{0,1\}^n$, finds $x_1,x_2$ such that $f(x_1) + Rf(x_2) = y$. Then conclude. $\endgroup$
    – fgrieu ♦
    Commented Dec 21, 2020 at 12:07
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – fgrieu ♦
    Commented Dec 22, 2020 at 3:26

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.