Quantum Computing and its Potential Threat to Blockchain

**Blockchain** technology has been implemented across multiple industries in various
ways. Ten years ago, blockchain made its first appearance, as the technology lying
behind bitcoin protocol. A blockchain is a time-stamped series of immutable records of
data that is being managed by a cluster of computers that are not being owned by a
single entity. Each of these blocks of data is referred to as a ‘block’ and each block is
bound to other blocks and is secured using various cryptographic principles that are
being referred to as ‘chains’.

A Blockchain carries no transaction cost and is an
ingenious yet simple way to pass data from A to B in an automated and secure
manner. Each block is being verified by thousands of computers present in the network.
Then after verification, the verified block gets added to the chain. It is then being stored
across the internet creating a unique record with a unique history, which implicitly
means that making any changes or falsifying a single record would require to change
and alter the information of the entire chain in all the instances present in the network,
which is next to impossible.

However, in June 2017, a study published by Mitre Corporation showed how an
emerging technology, known as

**Quantum Computing**, will effortlessly undo the layers
of encryption of blockchain, making data susceptible to manipulation, and the day is not
far when Quantum computing will compromise the cryptographic architecture of
blockchain protocol.

So, let’s understand what quantum computing is and how it is different from its classical
counterpart. Quantum computers work on the principles of quantum mechanics and are
exponentially more powerful than its classical counterpart, it outperforms the most
advanced type of modern digital computers. Quantum computers work on quantum bits
(qubits) which are fundamentally different from the classical bits, as, classical bits hold
values of either a 0 or a 1, but, qubits, on the other hand, can be in a superposition of 0
and 1 at the same instance of time.

Since blockchain is a distributed mathematical structure which is being designed to
secure data using sophisticated asymmetric cryptographic algorithms and hash
functions. It is being assumed that quantum computers has the potential to compromise
the integrity of blockchain using two quantum computing algorithms namely:

**Shor’s Algorithm:** The prime idea behind asymmetric cryptographic algorithms
is prime factorization and uses multi-digit numbers as public and private keys.
Then those numbers are being hashed into a set of smaller numbers and work
on the fact that classical computers are unable to find the prime factors of large
integers as multiplying two prime numbers is really easy but a number which is a
product of two unknown prime numbers is very hard to factorize. For example,
25980376026529 is a 45 bit number which is a product of two prime numbers
566557 and 45856597. And, the complexity of the prime factorization problem
grows exponentially with the key length. But, the curse of prime factorization
complexity was solved by an eminent scientist Peter Shor in 1994, who proposed
the famous quantum algorithm called Shor’s algorithm which is a polynomial-time
quantum computer algorithm which is used for integer factorization. The efficient
nature of Shor’s algorithm is due to the efficient nature of quantum Fourier
transform and modular exponentiation by repeated squaring. And, so Shor’s
algorithm gives a potential threat to the classical sophisticated asymmetric
cryptographic algorithms and hence poses an underlying threat to the blockchain
protocol.

**Grover’s Algorithm:** The cryptographic hash functions are generally trickier and
make it difficult for classical computers to crack them. In 1996, an eminent
scientist, Lov Grover proposed a quantum computing algorithm named Grover’s
algorithm which can efficiently search an unsorted database with N entries in
O(√N) time using O(log N) space and provides a quadratic speedup over
classical searching algorithms. And, hence it has the potential to break
cryptographic algorithms which will allow users to search for an item through an
unordered list in no time. Impending a serious threat to the blockchain.

The blockchain community is already aware of the impending threat of quantum
computing and is working on a number of solutions to make the cryptographic
algorithms quantum resistant. But, the day is not far when current blockchain
technology will be of no use and the security architecture of it will be fully compromised.