# Lower bound for the length of a one-way function's value?

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}})$$.

• Remember why we give $1^n$ to the adversary in the first place. May 10, 2019 at 12:55
• @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|$? May 10, 2019 at 13:02
• What if $f$ is not length preserving? May 10, 2019 at 14:06
• @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"). May 10, 2019 at 14:25