Why is the hash public key not resistant to quantum computing threats?

Compile: Hash Pie – Adeline

Source: Hash

The private key in the Bitcoin system is generated by a random generator, and the public key and address are derived by a one-way and irreversible algorithm such as an elliptic curve algorithm (discrete logarithm problem of elliptic curve), a hash function, and the like. So in theory , the hash public key can resist the threat of quantum computing . Even if the address and public key are exposed on the network, the private key cannot be derived. The possession of the private key is equivalent to owning the ownership of the bitcoin.

 

• Inside the ICBC internal digital wallet: China leads the currency trend for 3000 years
• Jianan Zhizhi prospectus full interpretation: 99% of revenue comes from mining machines and related sales, future growth bets on AI chips
• David Marcus: Libra's anti-money laundering standard is higher than other payment networks

The relationship between public key, private key and address

But in fact, the crypto asset is only protected by the hash function before it is traded, because when using the P2PKH or P2WPKH transaction standard (using the public key and the public key hash as a script) to trade the cryptocurrency , the public key will Exposed.

In the post-quantum (PQ) era, the widely used discrete logarithm-based public key cryptosystem is considered to be cracked . Quantum devices are capable of processing all possible 2^n variants of a data set at a time. Based on this, the quantum-based Shor algorithm can easily decompose large integer factors in polynomial time.

That is, when you broadcast a transaction to the network and it has not been accepted by the blockchain, then these transactions are vulnerable. The window of this attack is limited, but theoretically possible. If the processing power of QC (quantum computer) is strong enough, then the hacker using QC can be executed legally according to the exposed public key. Previously brute force the private key, then use its signature to create a conflicting transaction, sending the cryptocurrency in the transaction to their own address.

Even more frightening is that if the hacker is a miner himself, then in addition to calculating the private key based on the public key to steal the cryptocurrency, they can also refuse to confirm the transaction that does not send the cryptocurrency to them.

This is undoubtedly a worrying situation, but people also feel comforted at the same time: the public key will only be exposed to the ledger after participating in the transaction (the cryptocurrency is spent) , which happens only in a very small number of accounts.

In fact, this number should not be underestimated: more than 5.5 million bitcoins are being traded in the case of public key exposure. Some of these public keys are used because of the P2PK address for transaction output, and some because the user reuses an address, and the public key is exposed when the previous transaction is signed.

Based on this figure, we can imagine that if the powerful computing power of quantum computers breaks through the security of the Internet, the hacker can steal these numbers by using the exposed public key to calculate the private key before the transaction is confirmed. Amazing bitcoin, even destroying the bitcoin economy, makes it worthless.

More than just blockchains, cryptocurrency tools and wallets also have problems with public key exposure . In current cryptocurrency tools and wallets, no software treats public keys as private information, and most people don't realize how quantum computing will affect Bitcoin.

Many wallets do this by sending the parent extension public key to the server so that the server can monitor the transaction and send the data back to the client. All people who use these wallets, even if only temporarily, will send their parent key to the server. It is possible for the service provider to calculate the private key based on these public keys and derive all other sub-private keys. The disclosure of the private key makes the cryptocurrency assets of those who have used these wallets no longer secure and at risk of being stolen at any time.

Bitcoin's extended public key

There are also problems with complex scripts and contracts for public keys. A typical example of using a script to implement a programmable transaction is the multi-signature technique Multisigs, which does not hash-encrypt the public key. In the contract, not all contract participants must trust each other, which means that one of the participants can be malicious. Once a malicious participant appears, he can obtain all the public keys involved in the contract (via scripts) to steal the cryptocurrency associated with those public keys. Existing public key hashes do not protect this.

All in all, in addition to trading, there are still many ways to expose the public key , and we may have exposed the public key just because of the use of the wallet.

The threat of quantum computer to the elliptic curve discrete logarithm problem (ECDLP) may prompt the encryption community to transition to post-quantum cryptography. All of our current systems using public key cryptography need to be changed to cryptosystems that can cope with quantum attacks.

If quantum computing develops slowly, the encryption system has the time to switch to a stronger function and re-sign all assets. However, if the elliptic cipher curve is suddenly cracked and the system cannot detect it in time, then all signatures that rely on the ECDLP signature algorithm (ECDSA and Schnorr) can be soft-segmented to lock all cryptocurrencies. The user can claim ownership of the private key by providing a non-exposed or zero-knowledge proof of quantum impedance based on the public key.

For example, users can prove their ownership through the BIP32 seed they own.

HD wallet defined by the BIP0032 standard

The BIP32 seed is the standard followed by a hierarchical deterministic wallet. It is a system that generates a tree structure from a single seed to store multiple sets of keypairs (private keys and public keys). We only need to save one seed to derive All other subkeys. Due to the nature of zero-knowledge proof, the seeds themselves are not exposed (seeds are not part of the public key, the private key, they do not have shared common components). For now, this approach is relatively safe.

Therefore, although the one-way secret mechanism of the hash algorithm makes the encryption process irreversible, when the public key is exposed and the equivalent sub-calculation ability is strong enough, millions of bitcoins will be stolen, and the hash can only provide a false A sense of security, existing solutions cannot cope with upcoming threats.

Of course, all of this is based on our assumption that "the quantum computer's computing power is strong enough to calculate the private key through the public key, and we are not aware of the power of this technology, failing to upgrade the corresponding system in time."

In fact, every step of the quantum computer progresses in the "all eyes". Before the quantum computer is powerful enough to break the discrete logarithm problem ECDLP on the elliptic curve, Bitcoin has enough time to perform the anti-quantum signature algorithm soft segmentation. Fork, in the end, the signature that relies on ECDLP will be replaced.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!