Score:2

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

mx flag

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

et flag
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
fgrieu avatar
ng flag
@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](https://en.wikipedia.org/wiki/One-way_function#Theoretical_definition) would allow to settle the question?
et flag
@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"
cn flag
@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.
cn flag
Has the answer this question refers to been deleted? The (incorrect) claim that a constant function is one-way does not appear in any of the answers I can see.
et flag
@Maeher got it now. All inputs are preimages of the constant output
fgrieu avatar
ng flag
@Maeher: the one deleted answer to the [linked question](https://crypto.stackexchange.com/q/24348/555) does not contain anything remotely like the incorrect claim in the present question.
Score:6
cn flag

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.

kelalaka avatar
in flag
Is there an explicit reason not to say $f$ is polynomial time?
cn flag
$f$ is not an algorithm, so it doesn't have a well defined runtime that could be polynomial.
amlearn369 avatar
mx flag
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.
cn flag
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.)
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.