Let $f\colon \{0,1\}^n \to \{0,1\}^n$ be a length-preserving (i.e., $|f(x)| = |x|$) one-way function. Then, for $k \in \mathbb{N}$ and $m = n^k$, the function $g\colon \{ 0,1\}^m \to \{0,1\}^n$ with $$g(x_1, \ldots, x_m) = f(x_1)$$ is also one-way. Otherwise, being given $f(x)$ and $1^n$ as well as the description of a PPT $A$ which inverts $g$, one could run $A(f(x), 1^m)$ to obtain a preimage $x'$ for $f(x)$. This procedure can be realized in polynomial time since $m = n^k$ is polynomial in $n$.

The above gives a one-way function $g$ for which $|g(x)| = |x|^{\frac{1}{k}}$ for constant $k$. My question is: Does there exist one-way functions whose value is even shorter than this? For example, is there a one-way $g$ for which $|g(x)| = \log |x|$?

Clearly, $|g(x)| \in O(1)$ is not possible since producing preimages for $g$ would then be possible with only constant information; hence my question about this apparent "gap" between $O(1)$ and $O(n^{\frac{1}{k}})$.

  • 1
    $\begingroup$ Remember why we give $1^n$ to the adversary in the first place. $\endgroup$
    – fkraiem
    May 10, 2019 at 12:55
  • $\begingroup$ @fkraiem So the complexity of inverting $f$ is related not only to $|f(x)|$, but also to the length $|x|$ of (some) preimage $x$. But why would this rule out $|f(x)| = \log |x|$? $\endgroup$
    – dkaeae
    May 10, 2019 at 13:02
  • $\begingroup$ What if $f$ is not length preserving? $\endgroup$
    – kelalaka
    May 10, 2019 at 14:06
  • $\begingroup$ @kelalaka Well, the construction of $g$ just presupposes there is such an $f$. The existence of a length-preserving OWF is directly implied by the existence of OWFs (by using padding; in a way it is similar to the construction here, but in "reverse"). $\endgroup$
    – dkaeae
    May 10, 2019 at 14:25


Your Answer

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

Browse other questions tagged or ask your own question.