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
$\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$
  • $\begingroup$ Complexity is only improving by a constant, is that so bad? $\endgroup$ – Javier Oct 31 '16 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 '16 at 9:29

Your Answer

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

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