Quantum Threat to Blockchains: Shor’s and Grover’s Algorithms
A blockchain is secured by two major mechanisms: 1) encryption via asymmetric cryptography and 2) hashing. Recently, I discussed how the development of true quantum computing could pose security risks to today’s blockchains and concluded that blockchain technology will likely have bolstered its defenses by the time a true quantum computer is developed.
Below, I am going to discuss two quantum algorithms that a true quantum computer could use to challenge asymmetric cryptography and hashing, respectively.
Shor’s Algorithm and Its Challenge to Asymmetric Cryptography
The public and private keys used to secure blockchain transactions are both very large numbers, hashed into a group of smaller numbers. Asymmetric cryptography algorithms depend on computers being unable to find the prime factors of these enormous numbers.
Shor’s Algorithm is a conceptual quantum computer algorithm optimized to solve for prime factors. It takes a factor (a number), n, and outputs its factors. It’s magic lies in reducing the number of steps necessary to find a number’s prime factors (thereby potentially cracking public and private keys).
The algorithm is broken up into two parts:
- A reduction of the factoring problem to the problem of order-finding (which can be performed today on a classical computer)
- A quantum algorithm to solve the order-finding problem (which is ineffective today due to the lack of quantum computing capabilities)
Using the most common encryption standard, it takes a classical computer 2128, that is to say 340,282,366,920,938,463,463,374,607,431,768,211,456 basic operations, to find the private key associated with a public key. On a quantum computer, it would take 1283(ie only 2,097,152) basic operations to find the private key associated with a public key.
This is why conceptually the development of true quantum computing could pose a threat to today’s blockchain encryption. Of course, this threat is yet to materialize. Today, due to the lack of development in quantum computing, Shor’s Algorithm cannot be used in any serious way.
Grover’s Algorithm and Its Challenge to Hashing
Cryptographic hashing is much harder for a potential quantum computer to crack (compared to asymmetric cryptography). However, there is also a quantum algorithm that could potentially make it significantly easier (but still very difficult) to break cryptographic hashing.
Grover’s Algorithm allows a user to search through an unordered list for specific items.
Grover’s Algorithm is probabilistic: it gauges the probabilities of various potential states of the system.
Here’s how it works:
Imagine being given an unordered list of a certain number of elements and asked to find the element among them that satisfies a certain condition. You could use a classical computer to go through each element to find the one that satisfies the condition.
However, quantum computing uses superposition to test multiple inputs simultaneously. A quantum computer would use Grover’s Algorithm to conduct several rounds of computation.Through each round of computation, the probability of certain items having the desired condition increases. The algorithm narrows down selections as it progresses, and spits out one high probability result at the end.
You would require 2256(which is a 78 digit number) of basic operations with a classical computer to find the correct hash. For a quantum computer using Grover’s Algorithm, it would only take 2128 (which a 39 digit number, broken out above in the Shor’s Algorithm section) of basic operations to solve for the correct hash.
Conclusion
If true, powerful quantum computers existed today, they would likely pose a serious threat to asymmetric encryption but not to hashing. They could use Shor’s Algorithm to significantly reduce the number of steps to factor big numbers, thus more easily revealing the private key associated with a given public key. They could also use Grover’s Algorithm to attempt to break cryptographic hashing more easily than a classical computer can today, but this task would still be next to impossible. Luckily, given the primitive state of quantum computing today, we cannot expect any serious challenge to blockchain security mechanisms from either of these algorithms.
—
Follow Lansaar Research on Medium for the latest in emerging technologies and new business models.
Further Reading: What Is The Quantum Internet?
✉️ Subscribe to CodeBurst’s once-weekly Email Blast, 🐦 Follow CodeBurst on Twitter, view 🗺️ The 2018 Web Developer Roadmap, and 🕸️ Learn Full Stack Web Development.
