Two Sides of the Quantum Coin

Two Sides of the Quantum Coin

Will AES Be Broken by Quantum Computers, and Can I Implement AES on a Quantum Computer?

Like it or not, quantum computers are on our horizon. They will bring benefits to many areas of computation. If you are interested, here is our latest paper on detecting botnet domain generation using quantum computers [here]:

In a quantum computer, a qubit is a quantum mechanical phenomenon of superposition that can be — in all probability — in two states — and which can be represented as a 0 and a 1. This property allows us to speed up certain computing problems. These quits can then be created from trapped ions or photons — and which often requires usto cool down the QC to a temperature of near zero.

The great advantage of a quantum computer, though, is the scale-up in coping with bits, and 1,000 quits would represent 2¹⁰⁰⁰ binary digits of our conventional computers. With RSA, for example, it would take millions — if not billions — of years to find the two prime numbers that make up a 2,048-bit number. But a quantum computer would solve it in minutes.

Breaking symmetric key?

As you may know our public key methods will be broken by QCs. For this, Shor’s algorithm defined that we solve with O((log N)³), and where N is the value to be factorized. But what about symmetric key encryption, such as AES? Well, Grover’s algorithm speeds up the attack on AES and could break 128-bit AES. But, we can protect by moving to 256-bit AES, and a QC will not be able to break effectively. With hashing methods, we need to move to 256-bit hashes, such as SHA-256, SHA-3 or Blake2. Anyone using MD5 (128-bit hash) or SHA-1 (160-bit hash) should have migrated their applications a while ago, but the advent of QC will increase the drive to move to 256-bit hashes.

Symmetric keys with QCs

A symmetric key encryption method uses the same key to encrypt, as to decrypt. And, so, Bob and Alice share the same encryption key, but keep it secret. The most common symmetric key method is AES (Advanced Encryption Standard). Grassl et al. [3] were among the first researchers to implement AES within a quantum circuit and used a “zig-zag” method to reduce the number of qubits. Kim et al. [4] then showed a method of implementing the SubBytes operations. The latest work now focuses on minimising the number of qubits in AES [1] and SM4 [2]:

If you want to understand how AES works, try here:

This can be represented as [1]:

AES in 48 qubits

The implementation of 128-bit AES with a quantum computer requires for the methodology to be converted into qubits, and with S-AES (Sample AES) implemented in just 48 qubits [1]. The quantum circuits for the key expansion element is defined as:

For this, we see that parts of the key are used in each round, as we do in AES implementations.

Crib sheet for QC’s cracking encryption

So here’s a crib sheet on QC’s cracking encryption:

• Algorithms: Not every algorithm will run more efficiently on a quantum computer than on a traditional one. But they are well-matched to factorization problems and which breaks public key encryption.
• Public key encryption: Shor’s algorithm shows that we will be able to break ALL existing public key methods, such as RSA, ECC and discrete logs. In the case of RSA, we can determine the two prime numbers (p and q) that make up the public modulus (N). If you use digital signatures (eg RSA, DSA, ECDSA and EdDSA), public key encryption (RSA and ElGamal), and key handshaking (eg TLS and IPSec), you will need to migrate your existing methods to a PQC (Post Quantum Cryptography) method, such as CRYSTALS-Kyber for key exchange/public key and CRYSTALS-Dilithium or SPHINCS+ for digital signatures.
• Symmetric key: Grover’s algorithm showed a speed-up in the attack on AES, and could break 128-bit AES. We thus only need to move to 256-bit AES to overcome this. If you are on 256-bit AES, you are fine in the face of the onset of quantum computers but will need to upgrade to 256-bit AES, if not.
• Hashing: To be safe, we need to move to 256-bit hashing methods, such as SHA-256, Blake 2/3 and SHA-3. Anyway, you shouldn’t be using MD5 or SHA-1 in your applications. If you are, please stop, and upgrade to a 256-bit hashing method!

Conclusions

QCs will happen at a production level, so organisations need to start planning for a world which can use them to enhance computation, and also in the damage they may create on the Internet. An Internet without public key encryption is one that has virtually no trust, at all.

References

[1] Wang, Z. G., Wei, S. J., & Long, G. L. (2022). A quantum circuit design of AES requiring fewer quantum qubits and gate operations. Frontiers of Physics, 17(4), 41501.

[2] Luo, Q., Li, Q., Li, X., Yang, G., Shen, J., & Zheng, M. (2023). Quantum implementaion of SM4 block cipher with less qubits.

[3] Grassl, M., Langenberg, B., Roetteler, M., & Steinwandt, R. (2016, February). Applying Grover’s algorithm to AES: quantum resource estimates. In International Workshop on Post-Quantum Cryptography (pp. 29–43). Cham: Springer International Publishing.

[4] Kim, P., Han, D., & Jeong, K. C. (2018). Time–space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2. Quantum Information Processing, 17, 1–39.