Quantum Algorithms. Post-Quantum Encrypter.
Recent advances in Quantum Computers pose a clear threat to current Cybersecurity systems, that is, to the data used daily in Information Technologies. The security of data, files, and communication protocols used everyday are now at risk.
|
|
Quantum Algorithms according to IBM
|
Currently, there are two of the most important quantum algorithms that have a clear impact on current Cybersecurity systems.
Shor's Algorithm
The first is Shor's Algorithm. It was created by mathematician Peter Williston Shor in 1994. Later, in 1996, he made small changes to the algorithm's document.
Presently, is a resident at the Massachusetts Institute of Technology (MIT).
|
|
|
|
Mr. Peter Shor
|
|
First page of his algorithm
|
Read the Shor's Algorithm (PDF)
This algorithm runs on Quantum Computers and allows for extremely fast and efficient finding of prime numerical values, that is, the prime factors that make up an enormous, multi-digit number to be analyzed.
This difficult mathematical process of factoring large numbers is the basis of the security of many current encryption systems, including the well-known RSA algorithm.
The process of decomposing large numbers into prime factors could also be done using classical computers, but it would require extremely long computing times, even reaching a century and in some cases even longer.
Let's take an example: Let N be a very large integer, with hundreds or thousands of digits. Let's assume that N has two prime factors, p and q.
Thus, N can be represented as the product of p by q, that is, N = p.q. The computational problem lies in finding the values of p and q when N is very large.
- Using Shor's Algorithm, the prime factors of a huge number are found in just a matter of hours or minutes.
Grover's Algorithm
The second is Grover's Algorithm, which also poses a threat to the Cybersecurity of data used in several Information Technologies.
Its creator was mathematician Lov K. Grover in 1996, who was then a resident at Bell Labs.
|
|
|
|
Mr. Lov Kumar Grover
|
|
First page of his algorithm
|
Read the Grover's Algorithm (PDF)
The purpose of this quantum algorithm is to find a particular piece of data among an ocean of data contained in a large database. This difficulty is compounded by the fact that such data completely lacks internal structure; that is, they are distributed randomly, in a disordered manner, without following any pattern.
The fundamental advantage of this quantum algorithm is also the very significant reduction in the analysis time compared to time required by conventional computers to find the data sought.
Simply put, if the database had 10N elements, a classical procedure would require a huge number of operations, analyzing each piece of data one by one. The time required would then be extremely long, proportional to the enormous number of elements.
- Using Grover's Algorithm, it would be only needed a number of operations proportional to 10 to the square root of N.
Let's take an example: We have a database containing 1025 elements, meaning the database would have a 1 followed by 25 zeros elements, all completely disordered.
Using Grover's algorithm, from that enormous number we would have to spend a radically shorter time, this time proportional to 105.
- Note that the new exponent, 5, is the square root of the old exponent, 25.
