Table of Contents
Encryption of data is the core of online communication. Without it, it would not be possible to be able to communicate securely with peers across the Internet. Furthermore online banking and intergovernmental communication would be at a large risk to ensuring the privacy of such data.
Encryption is the conversion of data from plain text to ciphertext. This implies that when data is encrypted, if an eavesdropper (Eve) would be to intercept the message it would look like complete gibberish to them. Only with the correct key are they able to decrypt the message back into the original plaintext to be able to read the same message.
Moreover encryption can be split into two different main categories. Primarily Symmetric encryption is when one key is used to both encrypt and decrypt data. An issue that arises with this is that identical keys have to be used by both the receiver (Bob) and sender (Alice), as a result of this the key has to be transmitted across the internet for the other user to receive the key. This means that if Eve gets a hold of this key the encryption is meaningless as Eve can copy the ciphertext of the message and use the key to decrypt the messages. Due to this issue of key distribution there is Asymmetric encryption which uses two keys to be able to form one shared/compound key.
127 our experts are availableright now
The process of this type of encryption involves the sender using the receivers public key that is known to everyone to securely encrypt this message. The whole internet has access to this key, however, this key cannot be used to decrypt the message. This can be simplified to a one-way key. The receiver then uses their unique private key to decrypt the message. It is important to note that in Asymmetric encryption a message can only be decrypted with the receiver’s private key. This concept can be generalized with the idea that anyone can send a message to anyone an encrypted but only the receiver has the correct key to unlock it.
Developments in Quantum Computing
The theory behind quantum computing has been present since the 1980’s as they rely on the many different properties of quantum mechanics most predominantly superposition which have been explored since this time. However there have only been small steps in the development of these computers as the technological requirements needed for these computers has to be very precise. There have been two major and recent developments of quantum computers. One computer called the D Wave 2X that contains up to 2000 qubits, has the largest qubit volume (D Wave Systems,2018.) However this type of quantum computing focuses on quantum annealing which is when the qubits are not manipulated, and rather they are used to monitor the energy released from qubits during their natural evolution for optimization problems (A.B. Finnila, et al, 1994).
This essay will focus on gate based quantum computers as these are the computers that currently are able to work with problems involving encryption. These quantum computers rely on the manipulation of the qubits meaning that they can be monitored and controlled. The most advanced gate based quantum computer was produced by Google on October 23rd 2019, called by the name of its processor, “Sycamore”(Google, 2019). This processor only has 54 qubits, due to the extreme difficulty and accuracy to do with the manipulation of qubits. Google have claimed that they have reached quantum supremacy during the tests with the Sycamore processor (Frank Arute, et al, 2019).
This is the point at which a quantum computer has outperformed the strongest to date modern computer, possible bias in this statement is highlighted later in the essay. For this project this essay will be making the comparison between quantum computers (Sycamore processor) and the most powerful super computer (IBM Summit) through the encryption method AES. Additionally this essay will look at how RSA, which is an Asymmetric algorithm is effected by Quantum Computers. However this is done through the comparison of RSA key sizes into AES.
This essay will focus on the comparison with AES 128 and 256 bit encryption as it is the most reliable way to compare these two computers. Furthermore the data originates from a simple brute force attack with both, Quantum and Modern Super computers. Comparing the time to crack for each. It is important to note that a brute force attack against any encryption method is the most inefficient method of password cracking as it is the trial and error of every single passcode.
There are many different methods that can reduce the time to crack encryption algorithms more efficiently, however these different methods cannot be directly linked to quantum computing at the current time due to the lack of practical testing in this particular field. As a result of this, the only valid comparison is a brute force attack as the main basis of this attack is how many operations per second a computer can do and heavily relies on processing power.
The numbers 128 and 256 (N) in AES is the bit length of the key and signifies the number of possibilities that could be the key. A bit can either take the value of a 1 or a 0 and so the total number of possibilities of each key is 2^128 and 2^256. This is because the key in AES can be any value from 0 to 2^N. Each key is equally as hard to crack. as you will see later in the essay that the key is compared to the 8 bits in a byte and put into an XOR logic gate to substitute new values.
Case Study
Through the testing of Google’s quantum computer they have claimed that the Sycamore processor had completed an operation in 2 minutes and that it would take IBM’s Summit 10,000 years to complete (Edwin Pedault,et al, 2019). From this difference in speed, it can be determined that the Sycamore processor is roughly 1.5 Trillion times faster than Summit. This is one area in which the statement and data provided by Google could be biased which is important to take into consideration. However apart from the statement made by IBM in that Summit super computer could actually complete the same task in under 2.5 days, there has been no supporting evidence in terms of written documents to support this. Hence the following data relies on the statement made by Google.
Interpreting Data
It has been given that an estimate of number of FLOPS required per combination is 1000. With this estimate that was provided by Mohit Arora (2016).The following data calculates the difference in the time taken to Brute Force attack through AES 128.
Findings + Analysis + Supporting Simulations
Quantum and modern computers work in different ways however AES solely relies on the permutation and combination of data which are a simple process that can be performed on both computers, hence this is a valid comparison. The method of trial and error and Symmetric keys is the same no matter the type of computer. With the data in Fig 1.1, we can see that for both computers the time taken to crack a key for AES 128 is inefficient. Meaning that by the time the key would be cracked the data would be redundant. This is expected as the development of Quantum Computers is in the early years and Sycamore only contains a Qubit Volume of 54.
However, it cannot be ignored that the time taken does decrease dramatically, precisely by a factor of. As this data comes from processing speeds with Summit, it can be said that both modern-day computers and supercomputers are far from being able to crack AES 128, this is simply because modern-day computers do not have enough processing power to be able to trial and error all of the possible values. This is important as this means that currently, AES 128 provides a sufficient amount of security, of course in terms of protection against a brute force attack.
This difference in time taken is due to the crucial physics phenomenon of the principle of superposition and how qubits work in comparison to regular bits. Conventional bits can either take the value of a 1 or a 0. However qubits work with photons, and the 1 or the 0 is determined by the direction of polarisation of the photon. For example, a vertical polarization will result in a value of 1 and a horizontal polarization will output a 0. However, these qubits can be polarised diagonally as well by ±45°(Nielsen, Michael A, 1974). When they are in this state they can take the value of both a 1 and 0. This is where the principle of superposition contributes to speed. As a result of the Quantum Physics phenomenon, the number of possibilities explored of N number of qubits is equal to 2^N .
Currently with Sycamore the value stands at 2^54 . However, with the increase of the qubit volume on a processor, the processing speeds and potential of Quantum Computers will increase at an exponential rate. Google is further working on a Quantum Computer that will contain 100 qubits. Furthermore, a qubit volume as large as this would be able to crack AES 128 in a reasonable amount of time. This means that the current AES 128 bit keys would not be enough for a post-quantum situation.
Furthermore, Grover’s Algorithm is a quantum specific algorithm that optimizes the efficiency of searching for data in a database format such as block cipher matrices in this case. This algorithm is capable of reducing the key size by a half (Samuel Jaques, et al, 2016) This means that AES 128 would have the same time taken as to AES 56. As a result of this, AES 128 would not be a post-quantum era method of encryption due to two factors. The exponential increase in processing speeds due to the larger volume of qubits per processor as well as the optimization of database searching with Grover’s algorithm reducing time to crack AES by half.
As for RSA, modern key lengths are both 1024 and 2048 bits. These key lengths are much larger because of the difference in creation of Asymmetric keys. These keys are generated through the product of PQ in which both values are primes. This means that the key is composed of a product of primes (Charles Mann, 2002). These numbers are generated through One-Way functions. These function are easy to do in one direction, however extremely difficult to be performed in the opposite direction. A common analogy for understanding is that, it is easy to crack and egg but nearly impossible to put it back together.
This straight away reduces all of the possible key combinations which are not product of primes, whereas in AES we can have any value for the key but for Asymmetric the number must be a product of two primes. Hence we need to use a much larger key length to increase the number of possibilities. As a result of this Asymmetric keys are much more intensive on computer resources as there are many more complex operations that need to be made for finding prime numbers compared with AES where the encryption is generated from substituting and permutating the bits in a block cipher (Mike Pound, 2019).
These numbers are so hard to factor because these products of primes can be up to 500 digits long and then finding the two prime factors that multiply to get the 500 digit number is impractically difficult. According to Damien Giry (2020), RSA 2048 has the equivalent strength to AES 112 in terms of number of possible keys . This estimate can be made due to the connection through how many possible products of primes there could be in between the numbers 0 and 2^2048.
Which is enough for standard computers as they still would not be able to factor these numbers in an amount of time that would result in relevant data. Hence with the usage of quantum computers, Shor’s algorithm can be used that provides more efficiency in finding prime numbers and as a result, drastically reducing the time to crack RSA. This is a more efficient method of password cracking as Shor’s algorithm analyses qubits and eliminates numbers that are more and less probable to be the product of primes (Shor Citation).
However even if you were to trial and error every prime number between 0 and 2^2048 〖(2〗^112 Possible Values) then it would be possible, but still a large amount of time would need to be taken. With the combinations per second used for Sycamore. Note that this is with 54 qubits and that even with 60 qubits this time could be shortened down exponentially to weeks. This means that RSA is put at risk due to the lack of possibilities and the possibility of increasing qubit volume resulting in a great decrease in time taken.
In conclusion with AES, the maximum reduction in the time taken to perform a Brute force attack can only be reduced by half. Which does put AES 128 as risk if these algorithms could be used on quantum computers today. However quantum computers are not yet at that advancement. Despite this an alternative or an improvement will need to be ready in place for such a circumstance. As for RSA it is also currently safe however by a much smaller amount, as if we would have a quantum computer equivalent to Sycamore that could run Shor’s algorithm the RSA 1024 keys could be broken in 0.73 years as shown in the comparison to AES keys calculation. Furthermore this time would greatly with more qubits which is likely to happen in the near future. Hence an alternative needs to be in place.
References
- The Future of Encryption: International Perspectives on Encryption Policy in the United States and Abroad
- Encryption – Wikipedia
- Quantum Cryptanalysis of NTRU-Based Key Encapsulation Mechanism Kyber by Coppersmith’s Method on GPUs Using OpenCL
- An Efficient Recovery of RSA Key for YASHE Encryption Scheme in Bounded Recovery Model Using LLL Algorithm
- A quantum theorem-efficient public key encryption under noisy and repeated quantum access to the random oracle
