Big-O Notation for Menezes-Vanstone Elliptic Curve Cryptography?

Question

I need someone help me about . how can compute time complexity for this algorithm (Menezes-Vanstone Elliptic Curve Cryptography). I have spent much time reading journals and papers but as yet have been unable to find any record of that performance complexity. It is known that the algorithm is encryption function is :

$C1 = k1 * m1$ mod p

$C2 = k2 * m2$ mod p

The decryption function is:

$m1 = C1 * k1^ {-1}$ mod p.

$m2 = C2 * k2^{ -1}$ mod p.

I think the encryption function it take $O(N)^{2}$

where $T(C1) = O(\log n)^2$ bit operations.

$T(C2) = O(\log n)^2$ bit operations.

and the decryption function it take $O(N)^{3}$. where

$T(m1) = O(\log n)^2 + T(k1^{-1})$.

$T(k1^{-1}) = O(\log n)^3$, by extend Euclid’s method.

$T(m1) = O(\log n)^2 + O(\log n)^3$ bit operations.

$T(m2) = O(\log n)^2 + O(\log n)^3$ bit operations.

Is that true?.

Answer 1

Your bounds seem to be correct, assuming $n$ is the length of $p$, though writing $T(C1) = O(\log n)^2$ is wrong on two counts. First, it should be $O(\log^2 n)$ or $O((\log n)^2$) on the right. While $O(\log n)^2$ has the same meaning, it's not a "closed form", rather like writing $O(\sum_{k=1}^n k)$ instead of $O(n^2)$. Second, $T(C1)$ looks like $C1$ is some parameter like the input length or the number of vertices, whereas you intended $T(C1)$ to be the time needed to compute $C1$. Better notation would be $T_{C1}$, say, and you could include the input length $n$ as a parameter.

Moreover, note that there are faster integer multiplication algorithms, and some of them are used in practice in cryptographic contexts (not necessarily the ones which are asymptotically best). So you can get even better bounds on the running time depending on the implementation.

The reason you couldn't find the time complexity is that the algorithms use a constant number of two very common operations, namely multiplication and inverse modulo $p$, so the running times can be read immediately by experienced practitioners. This is even the case with more complicated operations such as modular exponentiation.