As part of an exercise in a cryptography course, I want to come up with a one way function for which it is "easy" to find a collision from a given OWF. To achieve this, I tried the following: given a OWF $f$ (it can be assumed to exist), construct $f'$ as follows: $$f'(x)=\begin{cases}f(y), &x=x^*\\ f(x),& \text{else} \end{cases}$$ for some $x^*,y\in \{0,1\}^*$. now an adversary might output those two when asked to find a collision in $f'$. My intuition is that $f'$ is still a OWF because this fixed point has negligible change on $f$ with respect to the hardness of computing a pseudo-inverse.

Does it make sense?

note: The definition of a OWF I'm working with is the one from wikipedia

  • 2
    $\begingroup$ Looks correct! Athough it is not a fixed point (but you can easily make one). $\endgroup$
    – Fractalice
    Jan 1, 2022 at 20:44
  • 1
    $\begingroup$ It should be like $f'(x)=\begin{cases}x, &x=x^* \bmod n \\ f(x),& \text{else} \end{cases}$ so that it has fixed point and collision... $\endgroup$
    – kelalaka
    Jan 1, 2022 at 23:33


Your Answer

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