In recent years, substantial progress has been made in the field of quantum computing - a computing paradigm which leverages quantum mechanics to solve mathematical problems that are difficult and often intractable on conventional machines. Quantum computers are capable of solving certain problems classical computers are incapable of solving in any feasible amount of time by encoding information into quantum bits (qubits). Each qubit doubles the amount of memory space available to execute algorithms, leading to vast improvements in computational time and performance.

Quantum computing

In November 2021 IBM unveiled a 127-qubit quantum processor, improving over its 65-qubit processor from the previous year. IBM plans to scale its quantum processors to over 1000 qubits by the end of 2023 with plans to eventually roll-out quantum processors wielding millions of qubits.

Public-key cryptography is at risk

Public-key cryptography is particularly vulnerable to quantum computers. Two particularly prevalent families of public-key cryptography are elliptic-curve cryptography (ECC) and the RSA cryptosystem. ECCs security depends on the difficulty of computing discrete logarithms of groups of points over elliptic curves while the RSA cryptosystem relies on the difficulty of factoring large prime numbers. Both ECC and RSA are vulnerable to attacks via quantum computers.

Shor’s algorithm

Shor’s algorithm is a quantum algorithm for efficiently finding the prime factors of sufficiently large integers - the very problem ECC and RSA rely on as being difficult to solve. This opens up attack vectors to a number of applications using public-key cryptography, such as Transport Layer Security (TLS), S/MIME, PGP, GPG, and digital signatures. If Shor’s algorithm were executed on a quantum computer with a sufficient number of qubits it would be capable of breaking the Elliptic Curve Digital Signature Algorithm (ECDSA), the public-key signature algorithm underlying Bitcoin, Ethereum, and many other blockchains. Therefore, Qbyte is here to provide an overview of quantum computing and the time estimation for building a large enough quantum computer to break current cryptosystems based on research results.