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

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?

• @dkaeae: Yes I realized that also. – user41014 Jun 17 '19 at 7:10
• Regarding your "comment": If the value of $f$ is polynomially bounded (i.e., $f(x) \le x^k$), then $f$ can be inverted by computing it on polynomially many values (e.g., $x^k + 1$ values) and using the pidgeonhole principle. So it seems that you want $k^x$ (actually $k^{|x|}$, I suppose?), in which case you might well have $k = 2$, which is a trivial bound. – dkaeae Jun 17 '19 at 8:27

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.

• But is $g$ a function which maps $\mathbb{N_0}$ to $\mathbb{N_0}$? – user41014 Jun 17 '19 at 7:14
• Well, then consider the negation modulo $N$, which is a large integer picked as a function of $n$ (e.g., $N = 2^n$). Then $h(x)$ will always be a predictable pattern (e.g., $10^\ast$). – dkaeae Jun 17 '19 at 7:15

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.

• but how do you guarantee that $g(x)>=0$? – user41014 Jun 17 '19 at 7:22
• @orgesleka compute it modulo 2^N – Bulat Jun 17 '19 at 7:25
• what is N, the length of x in bits? – user41014 Jun 17 '19 at 7:27
• yes, of course. – Bulat Jun 17 '19 at 7:28
• I do not understand the argument with $2^N$. Maybe you can comment on that in your answer? – user41014 Jun 17 '19 at 7:34

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

• Thanks @Bulat for your insight to this question! (+1) – user41014 Jun 17 '19 at 8:51