My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. (This question has been asked also in the CS Theory StackExchange, but with no answers yet. I am posting it here to reach out to a broader group of computational number theorists.)

Assuming the problem of

FACTORING:[Given $N = PQ$ for random primes $P, Q < 2^n$, find $P$, $Q$.]

cannot be solved in polynomial time with nonnegligible probability, the function

PRIME-MULT: [Given bit string $x$ as input, use $x$ as a seed to generate two random primes $P$ and $Q$ (where the lengths of $P$, $Q$ are only polynomially smaller than the length of $x$); then output $PQ$.]

can be shown to be one-way.

Another candidate one-way function is

INTEGER-MULT: [Given random integers $A, B < 2^n$ as input, output $A B$.]

INTEGER-MULT has the advantage that it is easier to define compared to PRIME-MULT. (Notice in particular that in PRIME-MULT, there is a chance (though fortunately negligible) that the seed $x$ fails to generate $P, Q$ that are prime.)

At least in two different places (Arora-Barak, Computational Complexity, page 177, footnote 2) and (Vadhan's Introduction to Cryptography lecture notes) it is mentioned that INTEGER-MULT is one-way assuming average hardness of factoring. However, neither of these two gives the reason or a reference for this fact.

So the question is:

How can we reduce in polynomial time factoring of $N = PQ$ with nonnegligible probability to inverting INTEGER-MULT with nonnegligible probability?

Here is a possible approach (that as we will see does NOT work!): Given $N = PQ$, multiply $N$ by a much (though polynomially) longer random integer $A'$ to get $A = NA'$. The idea is that $A'$ is so large that it has lots of prime factors of size roughly equal to $P, Q$, so that $P, Q$ do not "stand out" among the prime factors of $A$. Then $A$ has approximately the distribution of a uniformly random integer at a given range (say $[0,2^n-1]$). Next choose integer $B$ randomly from the same range $[0,2^n-1]$.

Now if an inverter for INTEGER-MULT can, given $AB$, with some probability find $A', B' < 2^n$ such that $A'B' = AB$, the hope is that one of $A'$ or $B'$ contains $P$ as a factor and the other contains $Q$. If that was the case, we can find $P$ or $Q$ by taking gcd of $A'$ with $N = PQ$.

The problem is that the inverter may choose to separate the prime factors, for example, putting the small factors of $AB$ in $A'$ and the large ones in $B'$, so that $P$ and $Q$ end up both in $A'$ or both in $B'$.

Is there another approach that works?

  • $\begingroup$ You are being sloppy here. N = PQ can always be factorised -- it just can't be factorised (as far as we know) in polynomial time (with non-negligible probability). $\endgroup$ – TonyK Jul 29 '11 at 19:29
  • $\begingroup$ You are right. I will edit my question by adding "in polynomial time" in the necessary places. $\endgroup$ – Omid Etesami Jul 29 '11 at 21:41
  • 2
    $\begingroup$ cstheory.stackexchange.com/questions/7550/… $\endgroup$ – Tsuyoshi Ito Jul 29 '11 at 23:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.