Pregunta

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!

No hay solución correcta

Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange
scroll top