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?
