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)$.


1 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.

  • $\begingroup$ @JanLeo: I think you mean selecting $r$ such that $r \cdot q_1 \bmod \phi(m)$ is never prime; still, that's problematic; you still have to worry about the case that $q_1 = 2^\lambda \cdot \textit{prime}$; in addition, if the attacker knows that $p_0$ is large, then you have to worry about $q_1$ being a smooth number times a large prime. Trying to find a strategy to select $r$ to avoid all these pitfalls looks tricky (and the more complex you make it, the harder it'll likely be to prove it to be secure). $\endgroup$
    – poncho
    Commented Jun 13, 2016 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.