1
$\begingroup$

I need some insight for the following problem in ElGamal encryption procedure. It is stated that ElGamal problem in a group $\mathbb{Z}_p^*$ becomes easier in subgroups. Assume I have a subgroup of index 2. Can you explain how is easier the discrete logarithm problem in this case?

$\endgroup$

1 Answer 1

1
$\begingroup$

As an example, algorithms, such as baby step giant step with time and memory complexity $$T=M=O(\sqrt{N})$$ or Pollard's rho with time and memory complexity $$T=O(\sqrt{N}),\quad M=O(1)$$have complexities that depend on the size $N$ of the group over which the DL is defined.

So $N=\mathbb{Z}_p^{\ast}=p-1,$ while a subgroup of index 2 has size $N'=(p-1)/2$ and the complexity improves accordingly.

$\endgroup$
2
  • $\begingroup$ Complexity is only improving by a constant, is that so bad? $\endgroup$ Oct 31, 2016 at 8:42
  • $\begingroup$ The subgroup used in El Gamal can have a much higher index, i.e., be much smaller. $\endgroup$
    – kodlu
    Oct 31, 2016 at 9:29

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.