How to prove a lemma that is based on phi-hiding assumption?

Question

Assume that the $\phi$-hiding assumption is true, i.e. that for a composite number $m$, a PPT adversary A cannot distinguish between a prime $p_0$ that divides $\phi(m)$ and another prime $p_1$ that doesn't divide $\phi(m)$.

How to prove that a PPT adversary B cannot distinguish $q_0 = (r \cdot p_0) \bmod \phi(m)$ and $q_1 = (r \cdot p_1) \bmod \phi(m)$, where $r$ is a random integer between 1 and $\phi(m)$ inclusive?

I know the basic idea is to let A construct $q_0$ and $q_1$ and give them to B. But the issue is that A doesn't know $\phi(m)$.

Answer 1

There exists a distinguisher that works with nontrivial advantage, $O(1/\log \phi(m))$.

This is because $q_0$ must be a multiple of $p_0$; however $q_1$ is a random value between $0$ and $\phi(m)-1$.

Hence, the distinguisher is "test both for primality, if one is prime, say that one is $r \cdot p_1 \bmod \phi(m)$"

$q_1$ is a random value, and hence it will be prime with probability $O(1 / \log \phi(m))$.

$q_0$ is a value $k p_0$, for a random $k \in (0, \phi(m)/p_0)$; hence it will be prime only if $k=1$, which happens with tiny probability $p_0 / \phi(m)$

$1 / \log(\phi(m)) \ggg p_0 / \phi(m)$, and hence this is an effective distinguisher.

If the adversary is given several rounds, say, multiple values $q_0, q'_0$ and $q_1, q'_1$, much better distinguishers can be constructed.