# Is a mapping of a k bit string to another k bit string containing 1's a one way function?

I'm new to cryptanalysis and I saw in another answer to a question that $$f: \lbrace0, 1\rbrace^{\kappa}\to \lbrace0, 1\rbrace^{\kappa}, f(x) = 1^{\kappa}$$ is a one way function. Why is this the case? Any help would be appreciated

• The output is always the same for a particular value of k - so how would you figure out which input it came from. So it's irreversible. So it's a one-way function Commented Mar 17, 2022 at 5:41
• @user93353: on the other hand, given $y$ such that $\exists x_0$ with $y=f(x_0)$, it's trivial to exhibit an $x_1$ with $y=f(x_1)$. So it's not collision-resistant. So… Could it be that merely stating the definition of a OWF would allow to settle the question?
– fgrieu
Commented Mar 17, 2022 at 7:10
• @fgrieu - it fulfills the definition "A function f : {0,1}* → {0,1}* is one-way if f can be computed by a polynomial time algorithm, but any polynomial time randomized algorithm F that attempts to compute a pseudo-inverse for f succeeds with negligible probability." The definition doesn't include collision resistance. Down below, they define "A collision-free hash function f is a one-way function that is also collision-resistant" Commented Mar 17, 2022 at 7:28
• @user93353 you are misunderstanding the definition of a OWF. To be a OWF it is required that finding any preimage is hard. This is not the case here. Outputting literally any $\kappa$ bit string is sufficient to break one-wayness of a constant function. This is unsurprising given that we do not even know if one-way functions exist and their existence would imply major breakthroughs in complexity theory. Commented Mar 17, 2022 at 8:16
• @Maeher got it now. All inputs are preimages of the constant output Commented Mar 17, 2022 at 8:30

The claim (which I can't find anywhere in the answers to the linked question) is incorrect. A constant function can't be one-way. To see why, let's recall the definition of a one-way function.

A function $$f : \{0,1\}^* \to \{0,1\}^*$$ is one-way, if

1. There exists a polynomial time algorithm $$M_f$$ such that $$M_f(x) = f(x)$$ for all $$x\in\{0,1\}^*$$.
2. For every PPT algorithm $$\mathcal{A}$$ there exists a negligible function $$\mathsf{negl}$$ such that for all $$\kappa\in\mathbb{N}$$ it holds that $$\Pr[x\gets\{0,1\}^\kappa, y:=f(x)\;:\;f(\mathcal{A}(1^\kappa,y))=y ] \leq \mathsf{negl}(\kappa)$$

However, for any constant function is is easy to specify a PPT algorithm $$\mathcal{A}$$ for which $$\Pr_{x\gets\{0,1\}^\kappa}\bigl[f\bigl(\mathcal{A}(1^\kappa,f(x))\bigr)=f(x)\bigr] = 1$$ for all $$\kappa\in\mathbb{N}$$. E.g., we can define $$\mathcal{A}$$ as the algorithm that always outputs $$1^\kappa$$. I.e., for all $$x\in\{0,1\}^\kappa$$ we have $$f\bigl(\mathcal{A}(1^\kappa,f(x))\bigr) = f(1^\kappa)$$ and since the function $$f$$ is constant, it holds for all $$x\in\{0,1\}^\kappa$$ that $$f(1^\kappa) = f(x)$$. Thus $$\mathcal{A}$$ breaks the one-wayness of $$f$$ with probability $$1$$ and $$f$$ is not one-way.

• Is there an explicit reason not to say $f$ is polynomial time? Commented Mar 17, 2022 at 17:08
• $f$ is not an algorithm, so it doesn't have a well defined runtime that could be polynomial. Commented Mar 17, 2022 at 17:39
• Thank you. This is what I thought. In the linked question, there was a comment to the correct answer saying that "if you really must have two distinct one-way functions, you could always, say, use $1^{𝑛/2}$ instead of $0^{𝑛/2}$ for one of them. Commented Mar 21, 2022 at 5:04
• What that comment was suggesting is using the two functions $f_1(x_1\Vert x_2) = 0^{n/2}\Vert h(x_1)$ and $f_2(x_1\Vert x_2) = 1^{n/2}\Vert h(x_1)$, just to get two different functions, if that were somehow required. (There are simpler solutions in that case.) Commented Mar 21, 2022 at 13:12