Let a function $f$ be one-way, if there exists a probabilistic polynomial time algorithm to find the preimage of $y = f(x)$ for uniformly chosen $x$ with non-negligible probability.

Define the function as $f(x,y) = x\times y$, where the values of $x$ and $y$ range across the integers in $[2^{n-1}, 2^n-1]$ (basically, they are $n$-bit numbers with the left-most bit set). Is $f$ one-way??

(Although with probability 0.75 the received $y$ is even, $2$ and $y/2$ cannot be output as the factors, since I want the preimages to lie in that specific range)

  • $\begingroup$ Welcome to Cryptography. Question a bit vague. Could you check it? $\endgroup$
    – kelalaka
    Aug 18 '19 at 8:50
  • 1
    $\begingroup$ Inverting this f is equivalent to the factoring problem (because you can break Rabin with such an inverter which is provably equivalent). $\endgroup$
    – SEJPM
    Aug 18 '19 at 8:53
  • $\begingroup$ @SEJPM could you please explain how it can be done? The inverter need not work for numbers that are product of primes right? It can output factors for other products, and it would still have non-negligible probability. $\endgroup$
    – Deepak K
    Aug 18 '19 at 9:14
  • $\begingroup$ Yeah, I think you are right, my intuition when it comes to OWFs isn't all too great yet... $\endgroup$
    – SEJPM
    Aug 18 '19 at 11:30

What you are wondering about is the difference between weak one-way function, and strong one-way function. Google should give you the definitions (e.g. here is the first link I found). The factoring function for general inputs is not a strong one-way function, since there are outputs for which it is easy to invert. But it is a weak OWF, because no polytime adversary can have more than a probability $1-1/\mathsf{poly}$ of inverting it (as far as we know).

Furthermore, even though a weak OWF is not a strong OWF in general, we know a generic way of building strong OWFs from weak OWFs - in other words, both assumptions are formally equivalent. See e.g. this online course, that deals specifically with the product function which you care about.


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.