Why is public-key encryption so much less efficient than secret-key encryption? I'm currently reading Cryptography Engineering. After giving a high level explanation of the difference between secret-key encryption and public-key encryption, the book says:


  So why do we bother with secret-key encryption if public-key encryption is so much easier? Because public-key encryption is much less efficient, by several orders of magnitude.


That statement really surprised me, and its not explained which leads me to believe I didn't understand the high level explanation as well as I thought.

Why is public-key encryption so much less efficient then secret-key encryption?
There are three efficiency issues to discuss here: CPU, network bandwidth, and functionalities.

The "moral" reason of public key encryption being slower than private key encryption is that it must realize a qualitatively harder feature: to be able to publish the encryption key without revealing the decryption key. This requires heavier mathematics, compared to symmetric encryption which is "just" making a big tangle of bits. Most known asymmetric encryption systems seem to achieve the needed security, but at some relatively heavy computational cost. Note that the McEliece cryptosystem and NTRUEncrypt achieve asymmetric encryption and decryption at high speed (much higher than, say, RSA or El Gamal over elliptic curves). There is no proof that asymmetric encryption must really be harder, computationally-wise, than symmetric encryption, but the contrary would still be mildly surprising.

Another efficiency issue with asymmetric encryption is network bandwidth. This one is an absolute limitation. Public key encryption is public: anybody, including the attacker, can use the public key to encrypt arbitrary messages. This means that if the encryption is deterministic, then the attacker can run an exhaustive search on the encrypted data (i.e. encrypting potential messages until one matches). The data which is encrypted is still "useful data": it has structure, it is subject to such a search. Therefore, an asymmetric encryption scheme must include extra randomness. This, in turn, necessarily implies a data size increase. For instance, with RSA as described by PKCS#1, with a 1024-bit key, you can encrypt a data element only up to 117 bytes, yielding a 128-byte value. Therefore, if you were to encrypt a big file with "only RSA", you would end up with an encrypted message about 9% bigger than the plaintext: that's 900 extra megabytes for a 10 GB message. On the other hand, symmetric encryption only incurs a constant size overhead (say, at most +32 bytes for AES-CBC, including room for the initial value). There are many contexts where network bandwidth is a scarcer resource than CPU.

Finally, there are key exchange algorithms, which are like asymmetric encryption except that you do not get to choose the "message" you send: the sender and receiver do end up with a shared secret, but that value is mostly "randomly selected". Diffie-Hellman is the most well-known key exchange algorithm. To do "asymmetric encryption" with a key exchange algorithm involves using the "shared secret" as key in a symmetric encryption algorithm.