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

  • $\begingroup$ "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. $\;\;$ $\endgroup$ – user991 May 7 '13 at 22:36
  • $\begingroup$ 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 $\endgroup$ – juaninf May 8 '13 at 0:34
  • $\begingroup$ Theorem 3 only works if they assume the adversary does not output [1,N] or [N,1] on the input N. $\endgroup$ – user991 May 8 '13 at 1:53
  • 1
    $\begingroup$ 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 $\endgroup$ – juaninf May 8 '13 at 2:47
  • 1
    $\begingroup$ 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. $\:$ $\endgroup$ – user991 May 8 '13 at 16:35

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.