3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Did you ever find out the answer? $\endgroup$
    – StephCurry
    Commented Dec 19, 2020 at 17:19
  • $\begingroup$ Sadly, I did not. Any insights or feedback that you would like to share? $\endgroup$
    – Leo
    Commented Dec 21, 2020 at 5:02

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Leo
    Commented Jul 18, 2019 at 9:50

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.