# Is $g(x)$, the first $(n -\log(n))$ bit of $f(x)$, a (strong) one-way function?

Given a (strong) n-bit-by-n-bit one-way function $$f$$, is $$g(x)$$, the first $$(n - \log(n))$$ bit of $$f(x)$$, a (strong) one-way function, too?

When reading Prof. Sanjam Garg's Graduate Cryptography lecture notes, I came across this problem. I am trying to construct an adv. cracking $$f$$ based on an adv. cracking $$g$$, but unable to bound the ratio of $$|\{x|g(x) = v$$ and $$f(x) = v||u\}|$$ to $$|\{x|g(x) = v\}|$$ for arbitrary eligible $$v$$ and $$u$$ from the fact that $$f$$ is a one-way function.

Is there another way to prove/disprove this statement? Thanks.

• Did you ever find out the answer? Dec 19 '20 at 17:19
• Sadly, I did not. Any insights or feedback that you would like to share?
– Leo
Dec 21 '20 at 5:02

Without knowing the details, note that any algorithm can utilize the $$n-\log n$$ bits of $$g$$ to invert it, can then brute force the remaining $$\log n$$ bits in time complexity $$O(2^{\log n})=O(n),$$ thus inverting $$f.$$
This will at most multiply the overall complexity by a linear factor, thus cannot achieve more than a polynomial gain between inverting $$f$$ and inverting $$g$$.
• Thanks for the reply. But $g(x)$ is the first $(n - \log(n))$ bits of $f(x)$ rather than a function taking the first $(n - \log(n))$ bits of $x$ as its input. I don't see how the brute-force would work. By the way, if $f$ is one-to-one, a probabilistic variant of your answer works, and that's why I was bounding the ratio.