1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ @dkaeae: Yes I realized that also. $\endgroup$ – orgesleka Jun 17 at 7:10
  • 1
    $\begingroup$ 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. $\endgroup$ – dkaeae Jun 17 at 8:27
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But is $g$ a function which maps $\mathbb{N_0} $ to $\mathbb{N_0}$? $\endgroup$ – orgesleka Jun 17 at 7:14
  • $\begingroup$ 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$). $\endgroup$ – dkaeae Jun 17 at 7:15
  • $\begingroup$ The question asked specifically about bijective functions, also wikipedia page about OWF talks specifically about functions returning strings of zeroes $\endgroup$ – Bulat Jun 17 at 7:27
2
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ Thanks @Bulat for your insight to this question! (+1) $\endgroup$ – orgesleka Jun 17 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.