# Weak One Way Function

Show The function $mult(a,b)$ is weak one way if the Integer Factorization Assumption is true.

I am read the proof of this enunciated but I want know if I understand this in my way. The proof use the lemma:

For $k$ big, the probability for one number with $k$ bits, choosen in random form, is prime is greater than $1/k$.

If I choose two numbers the probability that they are prime is $1/k^2$. Using this fact, I will be able to say given the fact that for the probability $1 / k ^ 2$ a mult function is difficult to invert, then to $1/k^2$ cases the mult function will fail, then as $1 / k ^ 2$ is not negligence. The proof is completed.

Well, if "weak one way" means that you shouldn't be able to consistently find preimages, that is, inputs that generate a specific output, and $mult(a, b)$ is defined as the integer multiplication $a \times b$, then $mult$ would not meet that definition.
For an arbitrary output $C$, we can set $a = C$ and $b = 1$; hence $mult(a, b) = C$.
• "weak one way" is a stronger condition than what you gave. $\:$ If one could always find preimages $\hspace{.75 in}$ for odd security parameters but it was infeasible to do so for even security parameters, $\hspace{1.2 in}$ then the function would nonetheless not be weak one way. $\;\;$ – user991 May 7 '13 at 22:36
• Yes, because when N is a product of two primes, the only other way mult $\hspace{1.85 in}$ can output N is using those two primes. $\:$ – user991 May 8 '13 at 16:35