Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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

share|improve this answer
"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
but mult have two input, and you onle write N ... I don't understand, is the enunciated "Show The function mult(a,b) is weak one way if the Integer Factorization Assumption is true" wrong? –  juaninf May 8 '13 at 2:07
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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