Bitcoin Blockchain in the Quantum computing era

Question

The design and the evolution of quantum computers has been one of the "hot" topics during the last 20 years.

My question is about the possible consequences of the rise of quantum computers (through concrete realizations of quantum computers) on the level of the Bitcoin blockchain architecture.

Given the fact, that the Bitcoin blockchain is strongly based on digital signatures generated through public-key cryptography schemes based on the hardness of prime factorization and that furthermore, the anonymity (and thus "identity") of the users is based on private keys, it is reasonable to think that quantum computers -which are expected to solve in polynomial time problems related to the prime factorization and thus to "break" those public cryptoschemes (like RSA) which base their security on the (classically) exponential hardness of prime factorization- will dramatically affect the technologies underlying Bitcoin (and other cryptocurrencies) as well.

A first thought I had, was that the rise of the computational power (relative to the problems described above) could easily be compensated -inside the present blockchain structure- by simply using "longer" private keys (with their "length" suitably chosen so that whatever the total hashing power available, going back from the public to the private will remain practically infeasible -as it is today). At the same time, the difficulty of the mathematical problem to be solved for the mining to occur, will also be rescaled so that the 10-min interval for producing a new block will remain unaltered. Is it that simple (in principle) or am I oversimplyfying? Are there some other important details one should take into account?

P.S. 1: See also: https://manage.kmail-lists.com/subscriptions/web-view?c=yMWFtj&r=5F9DLpu&m=wYXDhP&k=1dc8ecb6243f9dced47626ac0221f800 for a relevant discussion.

P.S. 2: this question is partially related to What effects would a scalable Quantum Computer have on Bitcoin?

Answer 1

If quantum computers become viable and the approach of factorization of numbers which has been theoretically presented works, this means that Bitcoin will have to use a different way of signing transactions as through the use of quantum computers, it becomes easy (only polynomial time required) to calculate a private key from a public key.

Simply increasing the key length doesn't work. If you double the key length, a classical computer has to work twice as hard to encrypt or decrypt the message but it becomes much, much harder than twice as hard as before to crack the encryption. Signing, in this case, really is just encrypting a hash of a message. However, for a quantum computer, the problem of cracking the encryption, only becomes twice as hard. So you can't keep up with using longer and longer keys because then the increase in effort an attacker has to put in only increases as fast as the increase of effort you have to put into using the keys.

However, there are ways to approach the problem of the signatures currently in use being rendered useless by the advent of quantum computers. Namely, quantum digital signatures.

Because quantum computers aren't faster than classical computers but reduce some exponential problems to polynomial problems, and cryptographic hashes can't be broken using quantum computers, their advent won't impact the difficulty to find a new block.

Answer 2

Signing of transactions in bitcoin is based on addition in elliptic curves, relatively easy to perform, like modular exponentiation (like in RSA), but hard to invert with a classical computer. In both cases, essentially the same quantum algorithm (Shor's algorithm) can be used to invert this operation on a quantum computer in polynomial time with high enough probability to be practical. This is what UTF-8 already wrote.

The proof of work algorithm involves computing a cryptographic hash. This operation is designed in such a way that computing the hash of a string is easy, but finding a string mapping to a given hash is hard. A good hashing algorithm avoids any kind of (exploitable) structure in the definition. Where in the case of RSA and elliptic curve cryptography it is known how the structure of the operation can be exploited by a quantum computer, for SHA256 this is not the case.

For an unstructured search (i.e. one in which you simply have to look case by case) quantum computer still vastly outperform classical computers (using Grover's algorithm) but now the speedup is only quadratic, not exponential. That means that you can find a hash that starts with 2n zeroes in the same number of operations which would allow you to find one starting with n zeroes on a classical computer (with high probability). This would be solved by just adjusting the difficulty.