2
$\begingroup$

How to calculate time and space complexity of ElGamal encryption and decryption as there are two exponentiation operation during encryption and one during decryption? Here is my code for encryption:

for i=1:d 
    pow=pow*g;
    y=pow%p;
for j=1:r
    pow1=pow1*g;
    C1=pow1*g;
    pow2=pow2*y;
    C2=(M*pow2)%p;

I think the first for loop will execute $O(d)$ times and second for loop will execute $O(r)$ so total time complexity of this is $O(d)+O(r)$ as it is not known which is bigger among $r$ and $d$.

$\endgroup$
1
  • 2
    $\begingroup$ Your time complexity assumptions are correct for this algorithm, and space complexity is $O(1)$ in the number of variables or $O(n)$ if you consider the length of the numbers. However, the algorithm can be achieved faster, because of what poncho wrote in his answer. Basically, it is like calculating $a \cdot b$ as $a+a+a...+a$ with $b$ summands. $\endgroup$
    – tylo
    Jul 21, 2014 at 15:42

1 Answer 1

4
$\begingroup$

Well, there are some major problems with your code. Technically, the time estimate of your code is correct (that is, if you insert modulo operations when you update pow1 and pow2), however no one would actually use that algorithm to do ElGamal.

Lets hit some of the issues:

  • You use an $O(N)$ algorithm to compute $x^N$; in real usage, exponents are huge (perhaps around $2^{256}$), and an algorithm that takes $O(2^{256})$ iterations is utterly infeasible. In practice, we use an algorithm that performs in $O(\log N)$ operations (modular multiplications), such as this one; this reduces the amount of work to something that can be implemented in practice.

  • On the less drastic, but still real issue: your code appears to assume that you have the private key $d$ when doing encryption; in practice, you'll start with the public key (which I believe in your code is $y$.

  • Also, while I'm listing nits, you also need to perform a modular reduction when you compute C1 as well. Furthermore, you don't need to recompute C1 and C2 in the loop; you're interesting only in the final values, and so you can compute those after you have the final values of pow1 and pow2.

I'm sure there are other issues I missed. However, the bottom line is that if you really want to compute the time complexity of ElGamal, you need to use the algorithm that we actually implement in practice.

$\endgroup$

Your Answer

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

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