# What are the known attacks on $\phi$-hiding assumption? How to chose its parameters?

$$\phi$$-hiding assumption states the following.

Sample 2 random primes $$e_0$$ and $$e_1$$ in the range $$[5, 2^{\lambda/4}]$$. Sample $$N = pq$$ of length $$\lambda$$ ($$p$$ and $$q$$ are large primes of length $$0.5\lambda$$) such that only one of $$e_0$$, $$e_1$$ divides $$\phi(N) = (p-1).(q-1)$$. If an poly-time adversary is given $$e_b$$ for a random bit b, he cannot tell whether $$e_b$$ divides $$\phi(N)$$ or not with advantage significantly greater than $$0.5$$.

1. What are the currently known attacks on this assumption?
2. Does it hold for any randomly chosen N?
3. Why should $$e_0$$ and $$e_1$$ be random primes? Are there any attacks if they are composite? Should $$e_0$$, $$e_1$$ be random? Can't they be fixed?
4. Why should $$e_0$$ and $$e_1$$ be chosen in the range $$[5, 2^{\lambda/4}]$$? Are there known attacks if they are less than $$5$$ or greater than $$2^{\lambda/4}$$.
5. In case $$e$$ divides $$\phi(N)$$, we say that "$$N$$ $$\phi$$-hides $$e$$". What does the phrase mean?
6. Is $$\phi$$-hiding equivalent to RSA?
7. For 256 bit security, I need to choose RSA modulus N to be 3072 bits long. If I am using $$\phi$$-hiding assumption instead of RSA, how long should modulus N be?
• Note that $\phi(N)$ for $N=pq$ is always divisible by 2 and 4 so it probably was more convenient to also exclude 3 than to write $\{3\}\cup [5,2^{\lambda/4}]$. – SEJPM Dec 19 '18 at 20:46
• @SEJPM We can detect whether $3 | \phi(N)$ as well. We know that, either N = 2 mod 3 or N = 1 mod 3 with equal probability. If N = 2 mod 3, then p = 1 mod 3 and q = 2 mod 3 or vice-versa. Therefore, $3 | \phi(N)$. – satya Dec 19 '18 at 23:19
• 1. for proper choice of parameters, no better attack than factorization is known. 5. It means that $N$ has $e$ "encoded inside it", but hidden in $\phi(N)$. 6. No. – Geoffroy Couteau Dec 20 '18 at 1:09