Is phi-hiding assumption as hard as integer factorization?

Question

Phi-hiding assumption can be simply stated as (wrt hardness)

It is difficult to find small factors of $\varphi(m)$ where $m$ is a number whose factorization is unknown and $\varphi$ is Euler's totient function.

Is the hardness due to this assumption comparatively higher than than the hardness of integer factorization?

My intuition says that finding prime factors of $\varphi(m)$ is simpler than finding the prime factors of $m$. So I believe that the hardness of the phi-hiding assumption is at most equal to the hardness of integer factorization.

Answer 1

Firstly, the phi-hiding assumption [CMS,KK] states that it is computationally-hard to distinguish the cases $(e,\phi(N))=1$ (where $(\cdot,\cdot)$ denotes the GCD) and $e|\phi(N)$ for a given RSA modulus $N$ and "small" prime $e>2$ ($e\ll N^{1/4}$, to be precise). In the former case, the exponentiation map $x\mapsto x^e\bmod{N}$ is injective (i.e., the RSA permutation), whereas in the latter case the map is lossy. Therefore, one could rephrase the assumption as assuming that the lossy and injective modes of the exponentiation map are computationally-indistinguishable [KK]. Note that this is stronger than simply assuming it to be hard to find small factors of $\phi(N)$ (the same way DDH is a stronger assumption than CDH is).$^*$

The assumption is clearly at least as strong as the factoring assumption as given an efficient algorithm that factors $N$, it is easy to compute $\varphi(N)$ and therefore decide whether a given prime $e$ divides $\varphi(N)$. Moreover, it is claimed in [KK] to be at least as strong as the RSA assumption. I couldn't find a proof of this anywhere, but the following reduction seems to work: given $(N,e)$ where either $(e,\phi(N))=1$ or $(e,\phi(N))=1$ and access to an oracle $A$ that computes $e$-th roots:

1. Sample $x_1,\cdots,x_n$ uniformly at random from $\mathbb{Z}_N^*$
2. Send $x_1^e\bmod{N},\cdots,x_n^e\bmod{N}$ to the oracle $A$ to obtain $x_1',\cdots,x_n'$
3. Return "$(e,\varphi(N)=1)$" if $x_i=x_i'$ for all $i\in[1,n]$

Showing the converse statement -- i.e., that the factoring assumption is at least as strong as the phi-hiding assumption -- is, as far as I know, an open problem.$^{**}$ This would require factoring $N$ (or find $e$-th root for that matter) given access to an oracle that on input $(N,e)$ decides whether $(e,\phi(N))=1$. Settling this problem would require first settling the equivalence between RSA problem and factoring (which is an easier question).

Finally, it is worth pointing out that for "large" value of $e$s ($e\geq N^{1/4}$, to be precise), the phi-hiding assumption does not hold as given such an $e|\phi(N)$ it is possible to factor $N$ using Coppersmith's attacks. You can read more about this in [CMS,KK]. Some moduli where the assumption does not hold are. discussed in [SF]

$^*$The definition in this Wikipedia article is also wrong: computing $\varphi(N)$ given $N$ is known to be equivalent to factoring $N$.

$^{**}$ Although it is believed that the equivalence holds: see discussion in [KK,§1.1].

[CMS]: Cachin, Micali and Stadler, Computationally Private Information Retrieval with Polylogarithmic Communication, Eurocrypt'99

[KK]: Kakvi and Kiltz, Optimal Security Proofs for Full Domain Hash, Revisited, JoC'18

[SF]: Schridde and Freisleben, On the Validity of the Phi-Hiding Assumption in Cryptographic Protocols, Asiacrypt'08