I need to know the computational complexity of the public key encryption (e.g. Paillier), please.

(i.e.Paillier in his paper mentions that the computational complexity of most of public key encryptions is $O(n^3)$, but is not clear to me why)

  • $\begingroup$ Hint: start by establishing that (for arguments of $n$ bits) the cost of the classic multiplication algorithm is $O(n^2)$ for arguments of $n$ bits; extend to $O(n^2)$ for $a\cdot b\bmod N$; then $O(n^3)$ for $x^d\bmod N$. There are faster algorithms, but they are not extremely useful in cryptography because $n$ is at most in the thousands (for RSA) or hundreds (for ECC). $\endgroup$
    – fgrieu
    Dec 7 '14 at 14:25
  • $\begingroup$ @fgrieu I don't get how you conclude $O(n^3)$ from $O(n^2)$. $\endgroup$
    – user13676
    Dec 7 '14 at 14:35
  • 2
    $\begingroup$ Using exponentiation by squaring, one needs $\mathcal O(n)$ underlying operations for a $n$-bit exponent. Hence, if the operation is computable in $\mathcal O(n^2)$ steps (which is mostly the case for practical systems, as mentioned above), the total cost is in $\mathcal O(n^3)$. $\endgroup$
    – yyyyyyy
    Dec 7 '14 at 14:40
  • $\begingroup$ Many thanks. I found a detailed explanation: crypto.stackexchange.com/questions/6164/… $\endgroup$
    – user13676
    Dec 7 '14 at 15:10