Reducing factoring prime products to factoring integer products (in average-case) 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. 

Assuming the problem of


  FACTORING:[Given $N = PQ$ for random primes $P, Q &lt; 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 &lt; 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&#39;$ to get $A = NA&#39;$. The idea is that $A&#39;$ 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&#39;, B&#39; &lt; 2^n$ such that $A&#39;B&#39; = AB$, the hope is that one of $A&#39;$ or $B&#39;$ 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&#39;$ 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&#39;$ and the large ones in $B&#39;$, so that $P$ and $Q$ end up both in $A&#39;$ or both in $B&#39;$.

Is there another approach that works?
This is not really an answer, yet it sheds some light on the difficulty of demonstrating such reductions.



The problem can be summarized as follows:
Let $\mathcal{A}$ be an algorithm which solves the INTEGER-MULT problem with non-negligible probability. Let this probability be at least $n^{-c}$, for some constant $c \in \mathbb{N}$ (when the size of input is $n$). Prove that there exists a PPT (probabilistic polynomial-time) algorithm $\mathcal{A}&#39;$ which, uses $\mathcal{A}$ as subroutine, and solves an instance of the FACTORING problem of size $n$ with probability at least $n^{-d}$, for some constant $d \in \mathbb{N}$.

Consider an algorithm $\mathcal{A}^*$ which solves the INTEGER-MULT problem if and only if the input $N$ has the special from $N = PQR$, where $P$ and $Q$ are primes of size $n/4$ and $R$ is a prime of size $n/2$, and otherwise fails. Moreover, on input an integer $N$ of the above form, it outputs $PQ$ and $R$. We first show that $\mathcal{A}^*$ has a non-negligible probability of solving the INTEGER-MULT problem. To this end, it suffices to find the fraction of $n$-bit integers of the special form, as this fraction bounds the success probability of $\mathcal{A}^*$ from below.

By prime number theorem, the number of primes whose size is $k$-bits is:

$2^k / \ln(2^k) - 2^{k-1} / \ln(2^{k-1}) = \Theta(2^k / k)$

Therefore, the fraction of $n$-bit integers of the special form is:

$\frac{\Theta(2^{n/4} / (n/4))^2 \cdot \Theta(2^{n/2} / (n/2))}{2^{n-1}} = \Theta(n^{-3})$

which is non-negligible in $n$.

Therefore, one should be able to prove the existence of a PPT algorithm $\mathcal{A}&#39;$ which, uses $\mathcal{A}^*$ as subroutine, and solves an instance of the FACTORING problem of size $n$ with probability at least $n^{-d}$, for some constant $d \in \mathbb{N}$.

IMHO, this seems a very difficult task, since $\mathcal{A}^*$ only (partially) decomposes integers of the special form, and there does not seem to be a way to use it to decompose integers of the form $PQ$.