2
$\begingroup$

$\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?
$\endgroup$
  • 1
    $\begingroup$ 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}]$. $\endgroup$ – SEJPM Dec 19 '18 at 20:46
  • 1
    $\begingroup$ @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)$. $\endgroup$ – satya Dec 19 '18 at 23:19
  • $\begingroup$ 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. $\endgroup$ – Geoffroy Couteau Dec 20 '18 at 1:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.