Factoring assumption

The factoring assumption states that there is no efficient algorithm that factors the product $N=pq$ of two large, random, equal-length primes $p$ and $q$. This is one of the oldest and most studied hardness assumptions in computational number theory and is the basis of RSA-based cryptography.

Assumption

For security parameter $\lambda$, let $p,q$ be independently uniform random $\lambda$-bit primes and $N=pq$. The factoring advantage of an adversary $\mathcal{A}$ is

$${\mathbf{Adv}}_{\mathcal{A}}^{\mathrm{fac}}(\lambda ):=\mathrm{Pr}\left[\mathcal{A}(1^{\lambda },N)\in \{p,q\}\right].$$

Factoring is hard if for all efficient $\mathcal{A}$, ${\mathbf{Adv}}_{\mathcal{A}}^{\mathrm{fac}}(\lambda )$ is negligible.

Known Results

• RSA hardness implies factoring hardness, since the factors of $N$ give $\phi (N)$ and hence the decryption exponent — RSA78; the converse is open in the standard model, and RSA ⇔ FAC holds in the generic ring model — AM09, DLO24
• QR ⇒ FAC (for Blum moduli); the converse is open.
• DCR ⇒ FAC; the converse is open.
• Quantum computers can factor in polynomial time via Shor’s algorithm — Shor97

Variations

Strong RSA assumption

The strong RSA assumption requires that it is hard to compute any $e$-th root of a random group element for an adversarially chosen $e>1$, not just a fixed $e$. This is a stronger assumption than standard RSA.

Factoring with known factor structure

For security parameter $\lambda$, let $p,q$ be independent uniform $\lambda$-bit primes with $p\equiv q\equiv 3(\mathrm{mod}4)$, and $N:=pq$, a Blum integer. Factoring Blum integers is hard if for all efficient $\mathcal{A}$,

$$\mathrm{Pr}\left[\mathcal{A}(1^{\lambda },N)\in \{p,q\}\right]$$

is negligible. Squaring modulo a Blum integer permutes ${\mathrm{QR}}_N$ — BBS86 — which makes Rabin’s function, whose inversion is as hard as factoring — Rab79 — a trapdoor permutation; Blum integers also underlie the Blum–Blum–Shub generator — BBS86. Other protocols assume factoring is hard for other structured moduli, such as $N=p^{r}q$ — standard.

Attacks

• Trial division: $O(\sqrt{N})$ — practical only for very small factors
• Pollard’s $\rho$ algorithm: $O(N^{1/4})$ expected time
• Elliptic curve method (ECM): efficient when $p$ is small; runs in $L_p[1/2,\sqrt{2}]$
• Quadratic sieve: $L_N[1/2,1]$ — best algorithm for $N<10^{100}$
• General Number Field Sieve (GNFS): sub-exponential $L_N[1/3,(64/9{)}^{1/3}]\approx L_N[1/3,1.923]$ — best known classical algorithm for large $N$
• Quantum: Shor’s algorithm — polynomial time $O((\log N{)}^3)$ — Shor97

Participates in

Builds on Factoring assumption

• FAC ∈ BQP (Shor)
• FAC ∈ coNP
• FAC ⇒ DS
• FAC ⇒ Factoring Blum integers
• FAC ∈ NP
• FAC ∈ PPA (under randomized reductions)
• FAC ∈ PWPP (under randomized reductions)
• FAC ⊆ TFNP
• Factoring + UOWHF ⇒ CCA-secure PKE (Hofheinz–Kiltz) (via Factoring with known factor structure)
• Factoring Blum integers ∈ BQP (Shor) (via Factoring with known factor structure)
• Factoring ⇒ Claw-free permutations (GMR) (via Factoring with known factor structure)
• Factoring ⇒ TDP (Rabin) (via Factoring with known factor structure)
• Factoring with known factor structure ⇒ PRG (via Factoring with known factor structure)

Produces Factoring assumption

• DCR ⇒ FAC
• FAC ⇒ Factoring Blum integers (via Factoring with known factor structure)
• QR ⇒ FAC (via Factoring with known factor structure)
• RSA ⇔ FAC
• RSA ⇒ FAC

Barriers

• No straight-line reduction from FAC to low-exponent RSA