Reducing factoring prime products to factoring integer products (in average-case)

Question

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 < 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?

Answer 1

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