Quantum Computation Algorithms

To understand the effects of quantum computing in the context of blockchain, we outline two fundamental quantum algorithms, which are known as Grover’s and Shor’s algorithms.

Grover’s algorithm

Blockchain-based systems rely on the costly computation of hashes in order to provide security against modification of previous transactions. The past blocks are secured by the Proof-of-Work scheme, which requires a computational effort in order to recompute the chain of blocks in case of any block being manipulated, thus maintaining an ordered history of transactions. Moreover, a single block is secured by the difficulty of finding a collision of the hash of its header.

Grover’s algorithmLov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC’96, pages 212-19, New York, NY, USA, 1996. ACM. addresses searching a dataset by querying the records $x$ in order to find a specified $f(x)$. In the context of cryptography, Grover’s algorithm aims at finding a valid preimage $x$ of a hash function $H$ with an $n$-bit fingerprint $y$ such that $H(x)=y$, or to search the secret key of key-length $n$ of a symmetric cipher. While these problems can’t be solved in classical computation in fewer than $\mathcal{O}(n)$ input evaluations, Grover’s algorithm has a quadratic speed-up to $\mathcal{O}(\sqrt{n})$ evaluation, thus weakening the security levels of any hash functions and symmetric crypto schemes. For example, the security level of 256 bits of AES-256 is lowered to 128 bit.

Shor’s algorithm

A much more drastic impact than Grover’s algorithm has Shor’s algorithmPeter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484-509, October 1997., which provides an exponential speed-up over the classical computation schemes considering the efficiency of factoring composite numbers and computing discrete logarithms, thus enabling a polynomial-time attack against classical public-key cryptosystems, such as RSA, DSA, and ECDSA, which are deployed for digital signatures. According to Proos and Zalka (2003)John Proos and Christof Zalka. Shor’s discrete logarithm quantum algorithm for elliptic curves. Quantum Info. Comput., 3(4):317-44, July 2003, a 256-bit ECC key could be broken on a quantum computer using 1500 qubits. Thus, once large quantum computers will be available, they will break actual signature algorithms by using Shor’s algorithm.