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$
$\endgroup$
4
-
$\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 ♦Commented Dec 7, 2014 at 14:25
-
$\begingroup$ @fgrieu I don't get how you conclude $O(n^3)$ from $O(n^2)$. $\endgroup$– user13676Commented Dec 7, 2014 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$– yyyyyyyCommented Dec 7, 2014 at 14:40
-
$\begingroup$ Many thanks. I found a detailed explanation: crypto.stackexchange.com/questions/6164/… $\endgroup$– user13676Commented Dec 7, 2014 at 15:10
Add a comment
|