Is the sum $f+g$ of two one-way-functions a one-way-function?

Question

Since there exists a bijection of sets from $\{0,1\}^*$ to $\mathbb{N_0}$, we might view one-way-functions as functions $f :\mathbb{N_0} \rightarrow \mathbb{N_0}$. My question is, suppose $f,g$ are one-way-functions, is then $(f+g)(n):=f(n)+g(n)$ a one-way-function or can one construct a counterexample? (The length of $n$ is $\text{ floor}(\frac{\log(n)}{\log(2)})=$ the number of bits to represent $n$)

Comment on answer of @Bulat: Suppose $f$ is an owf. If (?) there exists a $k \in \mathbb{N}$ such that for all $x \in \mathbb{N_0}$ we have $f(x) \le x^k$. Then as @Bulat mentioned, construct $g(x) = x^k-f(x) \ge 0$. Then $g(x)$ is an owf as $f$ is, but $h(x) = g(x)+f(x) = x^k$ is not an owf. So the question is, if there exists such an $k$. The argument would also work considering $k^x$ instead of $x^k$. But the same question remains? Why would such an $k$ exist?

Thanks for your help!

Answer 1

The answer is no.

Given $f$ one-way, consider $g(x) = -f(x)$. $g$ is then also one-way, because inverting $g$ would imply inverting $f$. In particular, supposing $g$ is not one-way, one can invert $f(x)$ simply by negating it and applying the inverter for $g$ (and the success probability is even equal).

In this setting, $h(x) = f(x) - f(x) = 0$ is not one-way as it can be.

Answer 2

I think your error is that you expect that for OWF each and any f(x) computation should be hard to reverse. But it seems incorrect, f.e. modular squaring is easily reversible for x=0. EDIT: Wikipedia specifically says "Note that, by this definition, the function must be "hard to invert" in the average-case, rather than worst-case sense."

By using g(x) = x - f(x) you will have a pair of functions that are hard to revert, but their sum is identity function.

Answer 3

Let's consider arbitrary one-way function f(x). We want to construct easily reversible h(x) with the property h(x) >= f(x) for any x.

Let's encode in h result value x and then add enough to make sure that h(x) >= f(x). We can do it f.e. in this way - use lower bits of result to RLE-encode N = bit length of x value, f.e. if it contains 3 bits then encoding will be 0111, then encode N bits of x value itself, and finally, use higher bits to encode f(x) value shifted by 2*N+1 bits. Well, we can put in these bits arbitrary data as far as overall value is larger than the f(x).