Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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 – 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 ?. My question above is in the Theorem 3.10 in my book, 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

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.