Is Bitcoin Safe from Shor’s Algorithm or Grover’s Algorithm?
(FinanceYahoo) Crypto investors invariably worry about quantum computing’s potential to undermine encryption. Quantum computers alone do not pose such a mortal threat, however.
It’s their capacity to exploit Shor’s algorithm that makes them formidable. Shor’s algorithm can factor large prime numbers, the security behind asymmetric encryption.
Another quantum algorithm can potentially undermine the blockchain as well. Grover’s algorithm helps facilitate quantum search capabilities, enabling users to quickly find values among billions of unstructured data points at once. Unlike Shor’s algorithm, Grover’s algorithm is more of a threat to cryptographic hashing than encryption. When cryptographic hashes are compromised, both blockchain integrity and block mining suffer.
One-way hash functions help to make a blockchain cryptographically secure. Classical computers cannot easily reverse-engineer them. They would have to find the correct arbitrary input that maps to a specific hash value.
Using Grover’s algorithm, a quantum attacker could hypothetically find two inputs that produce the same hash value. This phenomenon is known as a hash collision.
A somewhat easier attack to pull off using Grover’s algorithm involves proof-of-work mining. Using Grover’s search algorithm, a quantum miner can mine at a much faster rate than a traditional miner.
A quantum miner might also use Grover’s search algorithm to help facilitate the guessing of a nonce. The nonce is the number that blockchain miners are solving for, in order to receive cryptocurrency. That’s because Grover’s algorithm provides a quadratic speedup over a classical computer.
Grover’s algorithm may ultimately help make Proof-of-Work obsolete. That’s because “there is no possible PoW system that is not susceptible to Grover speed-up.” In the end, “quantum actors will always have an advantage over classical ones in PoW-based blockchains.
Quantum Resistant Ledger (QRL) will ultimately offer protection against both.
