0
$\begingroup$

In page 408 of Hoffstein, Piper, and Silverman's Introduction to Mathematical Cryptography, it says

"Roughly speaking, in order to achieve $k$ bits of security, encryption and decryption for Elgamal, RSA, and ECC, requires $\mathcal{O}(k^3)$ operations, while encryption and decryption for lattice-based systems requires only $\mathcal{O}(k^2)$ operations".

Why does Elgamal encryption and decryption require $\mathcal{O}(k^3)$ operations?

$\endgroup$
1
$\begingroup$

Roughly speaking, in order to achieve $k$ bits of security, encryption and decryption for Elgamal, RSA, and ECC, require $\mathcal{O}(k^3)$ operations, while encryption and decryption for lattice-based systems require only $\mathcal{O}(k^2)$ operations.

That quote uses "$k$ bits of security" where there should be "a security parameters of $k$ bits" or "key size of $k$ bits". In particular, having RSA and ECC together can only mean that a confusion is made between security in bits (that I now note $b$) and key size $k$. As an aside, the quote uses $\mathcal{O}$ where formally there should be $\Theta$ or $\Omega$, see this for the difference. That's a common, I do it often!

Let's independently derive the cost counted as instructions on standard computers with fixed-width word (as customary), for $b$-bit security meaning $\Theta(2^b)$ work for an attacker to break the system,

Consider RSA with $k$-bit public modulus, and ElGamal as originally formulated, that is the group $\Bbb Z_p^*$ with $p$ a $k$-bit public prime and a generator for all or most of the group. The cost of the private-key operation is dominated by $\Theta(k)$ modular multiplications. Each of these has costs $\Theta(k^2)$ work using common algorithms, $\Theta(k^{\approx1.6})$ for large parameters with Karatsuba, $\Theta(k^{\approx1.5})$ for huge parameters with Toom-Cook, $\Theta(k\log k)$ in theory only. Ignoring anything better than Toom-Cook, we get $\Theta(k^3)$ to $\Theta(k^{2.5})$ work. For RSA, subtract $1$ from the exponent for public-key use (encryption, signature verification) and fixed public exponent.

The two algorithms considered are vulnerable to GNFS, with heuristic cost $L_{(2^k)}\left[1/3,\sqrt[3]{64/9}\,\right]$ in L-notation. Assuming this remains the best attack, and keeping only the first parameter in the interest of simplicity and a little safety margin (from the standpoint of the legitimate user), we have like $\Theta(k^{1/3})$-bit security.

At $b$-bit security, the work for ElGamal as originally formulated, and RSA signature/decryption, thus comes out roughly as $\Theta(b^9)$ to $\Theta(b^{7.5})$.

| improve this answer | |
$\endgroup$

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.