Here is an introduction to the hot topic of “Post-quantum cryptography”.
It is worth noting that quantum computing principally poses a threat to public-key cryptographic algorithms which are used in applications such as establishing secure connections across the Internet. The problem is that these algorithms rely on trapdoor functions, which are easy to compute knowing the input, but intractably difficult to discover the input which will produce a given output from the function. Quantum computing makes it possible to invert many of these functions in polynomial time, rendering them vulnerable to being broken. Quantum computing does not, however, threaten symmetrical encryption algorithms such as the Advanced Encryption System (AES) or hashing functions such the Secure Hash Algorithm 2 (SHA-2), provided key and hash lengths are sufficiently long. Cryptocurrency private keys are related to public addresses via these hash functions, and thus are not believed to be at risk from quantum computing and algorithms as currently foreseen.
3 Likes
I guess I need to review this. Not what I thought I understood.
1 Like
Here is a detailed explanation of how Bitcoin addresses are generated, “How to Generate a Bitcoin Address — Step by Step”, which includes a worked example you can run from the Linux command line using utilities such as openssl and xxd.
A Bitcoin address is generated by starting with a randomly-selected 256 bit seed. This is then used to generate a public and private key using the elliptic curve (secp256k1) algorithm. This algorithm is vulnerable to quantum computing attacks, with an estimated 2330 qubits needed to break a 256 bit modulus.
With the private and public key generated, the next step is to take the public key and hash it twice, first through sha256 and then running its output through ripemd160. This produces a 160 bit hash of the public key, which is then encoded to form the Bitcoin address in a variety of equivalent formats.
To “break Bitcoin” is to solve the problem of, given a known Bitcoin address that appears on the Blockchain, find the private key to which it corresponds. This would require “un-hashing” the public address, which means discovering the public key from which it is generated. It is generally believed that due to the mathematical structure of hashing algorithms, a quantum computer would have no advantage in solving this problem. At least, no quantum algorithm is known which would do it (which doesn’t mean one might not be discovered—Shor’s algorithm for factoring by a quantum computer was only discovered in 1994). As long as the hash algorithms used to construct the public address remain secure against quantum computing, Bitcoin remains safe.
Ethereum addresses and those of most other cryptocurrencies are computed in a similar manner. Different algorithms are used in the public and private key generation and hashing, but the effect on a quantum attack is the same.
1 Like
This would require “un-hashing” the public address, which means discovering the public key from which it is generated.
It seems to me that connecting public keys to bitcoin addresses would likely be done in the opposite direction. That is, start with every known public key and generate it’s corresponding bitcoin address. Once the mapping of keys-to-addresses is built, it should be trivial to reverse the mapping.
There are 2^{256}\sim 10^{77} possible private keys. If you had a machine which could generate a trillion (10^{12}) addresses per second from them, it would take 10^{65} seconds to tabulate them all, which is around 3\times 10^{57} years. This is 2\times 10^{47} times the present age of the universe.
That’s what they mean by “computationally intractable”.
1 Like
There are 2^56 ∼10^77 possible private keys.
I’m confused, probably because everything I know about compromising a bitcoin address I learned from your single post. You said in the previous post that the problem was “discovering the public key from which it is generated”. Therefore, I understood the problem to solve as mapping a bitcoin address to a public key. And I presume that these public keys are public knowledge. At least, it would not be proper to consider their obscurity as any real advantage to an attacker. In any case, the final step of recovering a private key from a public key is the very problem that quantum computing will eventually solve, right? So how do bitcoin addresses avoid being compromised by quantum decryption?
It’s because the Bitcoin address is not the public key but rather a double hash of the public key. There is no known quantum speed-up for the hashing process or way to find an input which will produce a given hash. Consequently, discovering the public key which produced a given Bitcoin address that appears on the blockchain is intractable. This step would have to be done before you could benefit from a quantum speed-up in breaking the elliptic curve step and recover the private key.
If the hash functions used are found to vulnerable to a classical or quantum attack, that would compromise the security of the hash step and leave only the quantum-vulnerable elliptic curve step left. This is a genuine concern, because several hash algorithms previously believed secure have been found to have flaws and are now recommended against.
1 Like
So, how do signatures computed with the private key get verified if the public key is not available? What ties a transaction signature to that public address in a verifiable way?
