Quantum computers have the potential to perform calculations faster than ever possible before, inviting a significant rethink in how we approach cyber security.
Given the amount of research being ploughed into this area, we are likely to see a commercially viable machine in the near future, so cryptographers and the cyber security industry in general should work to have a clear view on the implications way ahead of that achievement.
Sure, but what is quantum computing?
Every current computer - smartphones, laptops, smart TVs - manipulates binary digits (‘bits’), and these bits can only have two values: '0' or '1'. (Note: bits are also used to quantify the strength of an encryption method e.g. 128-bit, 256-bit encryption... the more the better!) Quantum computers, however, use quantum bits (also known as ‘qubits’), where the value can be 0, 1 or both.
The main differentiator between quantum and classical computing is that a group of bits can only have one state at a point time whereas a group of qubits can be in several states simultaneously.
What can it be used for?
This particularity makes groups of qubits very efficient at solving specific (but not all) types of problems, such as factorisation of an integer i.e being given a number then finding out which two prime numbers can be multiplied together to get that number as a result, such as: 15 = 3 x 5. Classic computers are usually very slow at solving this type of problem, especially when the number has several hundreds of digits. Quantum computing can find this result much faster.
Why is this an issue for security?
These days, some form of data encryption comes as standard in any company worth dealing with. Anyone wishing to unlock encrypted data would need an encryption key. Quantum computing could increase the success rate of anyone attempting to brute-force cryptographic keys, depending on what type of encryption you are dealing with: asymmetric or symmetric. So how does quantum computing impact asymmetric and symmetric encryption?
Asymmetric encryption also known as Public Key Infrastructure (PKI) or public/private key pair - helps to identify that User A is always User A. It also allows anyone who wants to send data to User A to be sure that only User A can read that data. It is also used for digital signatures. For example, it allows me to be sure that the information from the chip of my passport has been created and written by the French government. It is widely used for securing sensitive data, particularly when sent over Internet, and its most common implementation is in a cryptosystem called RSA.
PKI relies on a pair of keys: public and private. The public key (which can be used for encrypting data) can be distributed to anyone and the private one (which can be used for decrypting data) should never be shared. These two ‘keys’ are actually two very big prime numbers - several hundreds of digits - and they are linked together by a formula. For the sake of simplicity, let’s say it is a multiplication. The security relies on the fact that factoring in the two initial primes for a very big number takes a lot of time for regular computers - too much time to even consider trying. With the fastest classical factoring algorithm, factoring the 600-digit-largest-ever encryption number would take longer than the age of the universe. Theoretically, quantum computers could do the task in an hour. Starting from the public key, a quantum computer could find out the private key and therefore impersonate a user to decrypt data.
Symmetric encryption allows a number of interested parties to communicate privately by sharing the same key needed to encrypt and decrypt the data. There is no way of identifying who sends the data (when there is more than one person) and no way to validate the origin of the data either. The key should only be shared within the interested parties. One of the most popular implementations of this type of encryption is called AES. For example, if you send an order via your favourite online shopping platform, it is likely that your order details are encrypted with symmetric encryption. Your mobile phone encrypts the data with a key agreed between you and the platform; therefore only the platform can decrypt your order data.
The bad news is that due to quantum algorithms like Grover’s algorithm, quantum computing will likely make symmetric encryption roughly twice as weak. A 128-bit symmetric key will be as weak as a 64-bit key. However, for many people data is considered secure with a symmetric encryption key of 80 bits, so using 256-bit keys would, in theory, still be secure enough against quantum computers.
What can we do to preserve our security?
New quantum resistant algorithms are being developed, but there are no globally recommend solutions as yet. Until there are clear recommendations as to which implementation of encryption (symmetric or asymmetric) is resistant to quantum computers, using hybrid encryption (a combination of several types of encryption) as well as rolling keys as regularly as possible should provide strong security against current known attacks and soon to come ‘quantum attacks’.
For now, we still have a little time to develop the right defences as the complexity of problems that a quantum computer can solve is severely limited.
Cyrille Quemin, Head of Mobile, Yoti
Image source: Shutterstock/welcomia