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

-

## 1 Answer

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. $\;\;$ –  Ricky Demer May 7 '13 at 22:36
I don't understand, @poncho You claim then that mult is not weak one way function?. This contradicts the theory of my lecture. See the Theorem 3 in cs.cornell.edu/courses/cs6830/2011fa/scribes/lecture5.pdf –  juaninf May 8 '13 at 0:34
Theorem 3 only works if they assume the adversary does not output [1,N] or [N,1] on the input N. –  Ricky Demer May 8 '13 at 1:53
The restriction "if they assume the adversary does not output [1,N] or [N,1] on the input N" is explicit here cs.cornell.edu/courses/cs6830/2011fa/scribes/lecture5.pdf ?. My question above is in the Theorem 3.10 in my book aleph0.info/cursos/ic/notas/cripto.pdf, the book is wrong?. Thanks by your patience –  juaninf May 8 '13 at 2:47
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. $\:$ –  Ricky Demer May 8 '13 at 16:35