2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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 $\endgroup$
    – user93353
    Mar 17, 2022 at 5:41
  • 1
    $\begingroup$ @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? $\endgroup$
    – fgrieu
    Mar 17, 2022 at 7:10
  • $\begingroup$ @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" $\endgroup$
    – user93353
    Mar 17, 2022 at 7:28
  • 4
    $\begingroup$ @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. $\endgroup$
    – Maeher
    Mar 17, 2022 at 8:16
  • 1
    $\begingroup$ @Maeher got it now. All inputs are preimages of the constant output $\endgroup$
    – user93353
    Mar 17, 2022 at 8:30

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Is there an explicit reason not to say $f$ is polynomial time? $\endgroup$
    – kelalaka
    Mar 17, 2022 at 17:08
  • $\begingroup$ $f$ is not an algorithm, so it doesn't have a well defined runtime that could be polynomial. $\endgroup$
    – Maeher
    Mar 17, 2022 at 17:39
  • $\begingroup$ 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. $\endgroup$
    – amlearn369
    Mar 21, 2022 at 5:04
  • $\begingroup$ 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.) $\endgroup$
    – Maeher
    Mar 21, 2022 at 13:12

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.