Symmetric vs. Asymmetric Encryption

Encryption aims to provide confidentiality, the first listed objective in the CIA Triad (see Crypt(?)). It transforms meaningful data (the cleartext) into a form that conceals its meaning (the ciphertext). Of course, concealing should hold for all parties except the one(s) that are intended to read the data, i.e., to decrypt. Decryption is thus the reverse operation of encryption; it means to obtain - by proper means (owning and using a decryption key) - the plaintext from the ciphertext.

Decryption allows restoring the data in its original form by legitimate parties. Others (e.g., adversaries) should not be able to reverse the encryption, and if they succeed (in an efficient time), this is the result of successful cryptanalysis. If the adversary manages to revert (even partially) the ciphertext into the plaintext, we say that the adversary broke encryption.

Encryption is handy in all information states (see Crypt(?)). Only to mention some examples: in transmission - to communicate securely over the internet; in storage - to secure sensitive data on a server; in computation - to perform analytics on encrypted data (As a note, homomorphic encryption is still a hot research topic nowadays).

Encryption and decryption follow precise steps defined by a cryptographic algorithm that used (at least) one cryptographic key. The internals of the algorithms are (in general) public, and the security of the encryption system resides in the secrecy of the cryptographic key(s) only (see Principles - Kerckhoff's principle). 

We can define an encryption scheme as a triplet (Enc, Dec, KeyGen) where Enc is the encryption algorithm, Dec is the decryption algorithm, and KeyGen is the key generation algorithm. Enc takes as input a message (plaintext) m and a key and returns a ciphertext c. Dec takes as input a ciphertext c and a key and returns a message (plaintext) m. By convention, the key is the first input parameter for Enc and Dec. (Note: In literature, you will sometimes find the key not as a parameter but as a subscription for Enc and Dec; this is because, in cryptology, the same key is usually used several times, e.g., for all messages exchanged within a session). KeyGen returns a (uniformly random distributed) key in a space K (Note: KeyGen usually takes as input a security parameter, e.g., the key's size; I will come back to this in a later post). As a note, the algorithms can receive as input other parameters; e.g., Enc and Dec get some authenticated data in the case of Authenticated Encryption with Associated Data (AEAD) [1], but we ignore these constructions for now. 

There are two types of encryption schemes: symmetric and asymmetric. A symmetric encryption scheme uses the same cryptographic key k for both encryption and decryption. An asymmetric encryption scheme uses (for each entity) a pair of keys: one for encryption, which is public - pk and another one for decryption, which is private (secret) - sk. Because of the public key, asymmetric cryptography is also called public-key cryptography. Of course, the keys in asymmetric settings must be in a mathematical relationship to satisfy some necessary properties; e.g., the public key must not expose the private key.

 

An encryption scheme has to be correct, meaning that the legitimate parties should obtain the original cleartext after decryption (This might sometimes fail with a negligible probability, but I do not discuss this here). A symmetric encryption scheme is correct if, for any cleartext m and any key k from the key space K the decryption of the encryption of m (both algorithms using the same key k) is m. An asymmetric encryption scheme is correct if, for any cleartext m and any pair of keys (pk,sk) from the key space K, decryption with sk correctly reveals the cleartext m that was previously encrypted using the public key pk. 

If Alice wishes to send a message m to Bob using a symmetric cipher, then Alice encrypts the message using a cryptographic key k and obtains the ciphertext c = Enc(k,m). The ciphertext c is apparently meaningless, so Alice sends it over a public communication channel to Bob. Bob receives c, decrypts it using the same key k, and finds the original message m = Dec(k,c). Similarly, if Bob wants to respond to Alice with a message m', he encrypts the cleartext m' using the cryptographic key k and obtains c' = Enc(k,m'). He then sends c' over the public channel. Alice receives c' and decrypts it to get the plaintext m' = Dec(k,c').

If Alice wishes to send a message m to Bob using an asymmetric cipher, then Alice encrypts the message using Bob's public key and obtains the ciphertext c = Enc(pk_B,m). The ciphertext c is apparently meaningless, so Alice sends it over a public communication channel to Bob. Bob receives c, decrypts it using the decryption key sk_B, and finds the original message m = Dec(sk_B,c). Similarly, if Bob wants to respond to Alice with a message m', he encrypts the cleartext m' using Alice's public key k and obtains c' = Enc(pk_A,m'). He then sends c' over the public channel. Alice receives c' and decrypts it using her private key to get the plaintext m' = Dec(sk_A,c').

There are many constructions for symmetric and asymmetric encryption. I only mention the Advanced Encryption Standard (AES) - FIPS197-upd1 [2] and the RSA encryption [3], which are perhaps the most well-known constructions for symmetric and asymmetric encryption, respectively. A beautiful animation that explains Rijndael (the algorithm behind AES) - is available here.

Both symmetric and asymmetric systems have strong points and weak points. One problem to solve in symmetric settings is the key establishment, or how to make Alice and Bob know both the same key k without revealing (not even some bits of) it to others (and, of course, not meeting in person 😄). Key establishment is a stand-alone problem that comes in many flavors (key distribution, key transport, key agreement, ...), and it can be solved by asymmetric cryptography. Refer to the very well-known paper of Diffie and Hellman [4] for the first key exchange construction (in public key cryptography).

Key establishment is not a real problem in asymmetric cryptography because the private key never leaves its owner. (Note that - under some circumstances - the owner can even generate it locally). Nevertheless, other issues arise, such as, for example, how to prove the ownership of the public key. In real-life, this brings in digital certificates and the complexity of Public Key Infrastructure (PKI). On the other hand, asymmetric cryptography is usually more expensive in time and resources, hence is unsuitable for encrypting large plaintexts. It also requires longer keys than symmetric cryptography to achieve the same security level. A few nice but old ENISA reports on key sizes (among others) are available online [5,6]. A 2021 academic paper on cryptographic key sizes is available here [7].

Besides the key's length, the number of keys to remain private is also of interest. That is because, in general, it is easier to secure less than more (shorter keys, fewer keys, etc.) but also for efficiency reasons (security is at a trade-off with efficiency, usability, etc.). Let's consider a group of N parties (Alice, Bob, Charlie, Daisy, ...) for which any party must securely communicate with any other party.

In symmetric cryptography, each couple must use a different key: Alice uses a key k1 to communicate with Bob, a key k2 to communicate with Charlie, a key k3 to communicate with Daisy, etc. Therefore, each party needs to securely store N-1 keys, one for each other party. So, for N parties: N(N-1). If a single key is used regardless of the direction of communication (from Alice to Bob or from Bob to Alice), then the number of distinct keys becomes N(N-1)/2. 

In asymmetric cryptography, each party has to secure his/her private key only (the public key is publicly available). So, one key for each party and N keys in total for N parties. Of course, one uses the other party's public key to encrypt, so Alice needs to know N-1 public keys (Bob's, Charlie's, Daisy's, ...). As the public key is the same regardless the transmitter (e.g., Alice and Bob use the same key - Charlie's public key - to encrypt messages intended for Charlie), the total number of public keys is N.

Combining the advantages of both methods, hybrid encryption first uses asymmetric encryption to transfer a cryptographic key k, then symmetric encryption and the key k to encrypt the data. Think of Alice that wants to send a message to Bob. She first chooses a key k, then encrypts k using Bob's public key, and finally encrypts her communication to Bob using the key k and a symmetric system. It is a simple method to overcome both the problem of key establishment in symmetric cryptography and the computation overload in asymmetric cryptography.

[1] Rogaway, P. (2002, November). Authenticated-encryption with associated-data. In Proceedings of the 9th ACM Conference on Computer and Communications Security (pp. 98-107). Available at: https://www.cs.ucdavis.edu/~rogaway/papers/ad.pdf

[2] NIST. FIPS197 Update 1. Advanced Encryption Standard (AES). Available at: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197-upd1.pdf 

[3] Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126. Available at: https://dl.acm.org/doi/pdf/10.1145/359340.359342

[4] Diffie, W., & Hellman, M. E. (2022). New directions in cryptography. In Democratizing Cryptography: The Work of Whitfield Diffie and Martin Hellman (pp. 365-390). Available at: https://caislab.kaist.ac.kr/lecture/2010/spring/cs548/basic/B08.pdf

[5] ENISA. Algorithms, key size and parameters report 2013. Available at: https://www.enisa.europa.eu/publications/algorithms-key-sizes-and-parameters-report

[6] ENISA. Algorithms, key size and parameters report 2014. Available at: https://www.enisa.europa.eu/publications/algorithms-key-size-and-parameters-report-2014

[7] Smart, N. P., & Thomé, E. (2021). History of Cryptographic Key Sizes. Cryptology ePrint Archive, Paper 2021/894. Available at: https://eprint.iacr.org/2021/894.pdf