Post Quantum Encryption

Why AES encryption makes data safe from quantum eavesdroppers

Post Quantum Encryption

After my 2 articles on post-quantum VPN (link) and post-quantum session key management (link) which focused on the "how", I was recently asked about the "why".

Why would using AES encryption make the data safe from quantum eavesdroppers?

To appreciate the answer from a cybersecurity point of view, we must understand the threat that quantum computers pose. And this threat stems from the vulnerability that can be exploited by an attacker with a quantum computer.

Vulnerabilities exploitable by quantum computers

So where are the vulnerabilities that a  quantum-equipped attacker can exploit? These are broadly broken into 2 main categories:

  • Classical Public-Key Cryptography (RSA, ECC, DH). Public-Key Cryptography works on the concept of a key-pair. Each user has a private key (which has to be kept secret) and a corresponding public key (which is made publicly available to the communicating party). Communicating parties use protocols such as digital signing and session key negotiation to achieve the necessary confidentiality, integrity and authentication (CIA) of the data. If the user's private key is compromised (e.g. stolen, exposed), then the communication is no longer secure. Current computing technology will require millions of years for an attacker to calculate the private key when given the public key. However, on a quantum computer, an attacker can use Shor's algorithm to perform this calculation at an exponentially faster speed, resulting in the compromise of the private key in a matter of hours or days.
  • Symmetric Key and Hash-based Cryptography (AES, SHA). Symmetric and Hash-based Cryptography works on the concept of transforming data, through a complex series of  non-mathematical permutation and substitution, to a enciphered form. In Symmetric Key Cryptography, a random secret key is used by communicating parties to uniquely change how the data is permuted and substituted so that only parties that know the secret key will be able to reverse the permutation/substitution process and recover the original data. Current computing technology will similarly require millions of years for an attacker to discover the random secret key when given the enciphered data. On a quantum computer, an attacker can use Gover's algorithm to perform this discovery at a quadratically faster speed. This only weakens the encipherment, making the secret key discovery process take thousands of years, but does not result in a compromise of the data.

The threat model therefore from quantum computers is that data and communications protected using classical public key cryptography and/or weak symmetric key cryptography is no longer secure when quantum computers are available for attacks.  There are different ways to mitigate the threat, and herein lies the use of AES in my earlier articles. 

Mitigate the quantum computing threat

There are application use-cases (e.g. VPN) which rely on classical public key cryptography to perform session key exchange and AES for session data encryption.  In most protocols, the communicating parties first generate a random value which is exchanged amongst the each other using RSA or ECDH, and then use this random value as the AES secret key to encrypt the ensuing data exchange that happens. 

The threat in this scenario comes from an attacker who is able to use the quantum computer to compromise the private keys of the communicating parties and obtain this random value. With knowledge of the random value, the attacker can then use AES to decrypt the ensuing data exchange and get access to the information that is communicated. Note that AES is not compromised in the attack.

We can mitigate this threat by not using classical public key cryptography (e.g. RSA or ECDH) to perform the key exchange, but by relying on alternative means such as manually exchanging keys, using RFC 8784, or using post-quantum cryptography. This essentially takes away the vulnerability that the attacker can exploit, thereby mitigating the quantum threat. Do pay attention to the design of the alternative key exchange so that it does not open new threats to the application.

In my articles, I mentioned using physical means to exchange keys but this is definitely not the only solution.

A word on Post-Quantum Cryptography

The industry is moving to replacing the use of classical public key cryptography with post-quantum cryptography. This is a branch of study that retains the use of private-public key pairs, but in a way that cannot be compromised using a quantum computer. 

You should check out more information on the NIST website (link)

Author

Tan Teik Guan

Teik Guan is CEO of pQCee.com. He works in the niche area of cryptographic security design and integration, having implemented numerous successful projects for banks, government agencies and enterprises. He holds a BSc and MSc from NUS and a PhD from SUTD.