1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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