Score:1

One way function with fixed point

ke flag

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

Fractalice avatar
in flag
Looks correct! Athough it is not a fixed point (but you can easily make one).
kelalaka avatar
in flag
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...
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.