The blockchain is protected by two main mechanisms: asymmetric encryption and hashing. Not so long ago, we published material that looked at how the development of real quantum computing could create a security risk for today's blockchains, and concluded that blockchain technology would likely become more secure by the time a real quantum computer appears.
This article discusses two quantum algorithms that a real quantum computer could use to crack asymmetric encryption and hashing.
Shor's algorithm and asymmetric encryption
The public and private keys that are used to secure blockchain transactions are very large numbers, converted by hashing into a group of small numbers. Asymmetric encryption algorithms are useful because computers cannot factorize these large numbers.
Shor's algorithm is a conceptual algorithm for quantum computers, optimized for factorization. He takes the factor (number) n and decomposes it into prime factors. The essence of the algorithm is to reduce the number of steps required to find prime factors of a number (which makes it possible to find out the public and private keys).
The algorithm is divided into two parts :
- Transformation of the factorization task into the task of finding an order (which can be performed on an ordinary modern computer).
- Quantum algorithm for solving the problem of finding the order (ineffective today due to the lack of opportunities for quantum computing).
The most common encryption standard is used, in which a classic computer makes 2128 (340 282 366 920 938 463 463 374 607 431 768 211 456) basic operations for finding the private key associated with the public key. A quantum computer will require 1283 (only 2,097,152) basic operations to calculate the private key associated with the public key).
That is why, in theory, the development of true quantum computing could pose a threat to modern blockchain encryption. Of course, this threat does not yet exist. Today, due to the lack of development in the field of quantum computing, Shor’s algorithm cannot be fully utilized.
Grover's algorithm and hashing
It is much more difficult for a potential quantum computer to crack cryptographic hashing than asymmetric encryption. Nevertheless, there is a quantum algorithm, which theoretically can greatly simplify the breaking of cryptographic hashing, although this process still remains time consuming.
Grover’s algorithm allows the user to search for specific bullet points.
Grover’s algorithm has a probability property: it measures the probability of various possible states of a system.
Here is how it works.
Suppose there is a bulleted list of a certain number of items. Among them it is necessary to find an element that satisfies certain conditions. You can use a regular computer and consider each element to meet these conditions.
However, quantum computers simultaneously test a variety of input data using superposition. A quantum computer could use Grover’s algorithm to carry out several computational cycles. After each cycle of calculations, the probability that certain elements correspond to the specified conditions increases. The algorithm narrows the sample as it works and at the end produces one most likely result.
On a classic computer, finding the correct hash would require 2,256 (78-digit) basic operations. The Grover algorithm running on a quantum computer would use only 2128 basic operations (a 39-digit number divided in the Grover algorithm section) to find the correct hash.
Conclusion
If powerful quantum computers existed today, most likely, they would represent a serious threat to asymmetric encryption, but not hashing. They could use Shor's algorithm to significantly reduce the number of steps to factor large numbers and simplify the process of finding a private key associated with an existing public key.
They could also use Grover’s algorithm to more efficiently attempt to break into cryptographic hashing than modern conventional computers, but their efforts would still be almost futile.
Fortunately, today, due to the meager developments in the field of quantum computing, these algorithms do not pose any serious threat to the security mechanisms of the blockchain.
Publication date 20/05/2019
Share this material on social networks and leave your opinion in the comments below.
