Is Crypto Currency truly at risk due to Quantum Computers,  and what can you do about it?

There is no denying that the Quantum revolution is coming. Security protocols for the internet, banking, telecommunications, etc... are all at risk, and your Bitcoins (and alt-cryptos) are next!

This article is not really about quantum computers[i], but, rather, how they will affect the future of cryptocurrency, and what steps a smart investor will take.  Since this is a complicated subject, my intention is to provide just enough relevant information without being too “techy.” 

The Quantum Evolution

In 1982, Nobel winning physicist, Richard Feynman, hypothesized how quantum computers[ii] would be used in modern life.

Just one year later, Apple released the “Apple Lisa”[iii] – a home computer with a 7.89MHz processor and a whopping 5MB hard drive, and, if you enjoy nostalgia, it used 5.25in floppy disks.

Today, we walk around with portable devices that are thousands of times more powerful, and, yet, our modern day computers still work in a simple manner, with simple math, and simple operators[iv]. They now just do it so fast and efficient that we forget what’s happening behind the scenes.

No doubt, the human race is accelerating at a remarkable speed, and we’ve become obsessed with quantifying everything - from the everyday details of life to the entire universe[v]. Not only do we know how to precisely measure elementary particles, we also know how to control their actions!

Yet, even with all this advancement, modern computers cannot “crack” cryptocurrencies without the use of a great deal more computing power, and since it’s more than the planet can currently supply, it could take millions, if not billions, of years.

However, what current computers can’t do, quantum computers can!

So, how can something that was conceptualized in the 1980’s, and, as of yet, has no practical application, compromise cryptocurrencies and take over Bitcoin?

To best answer this question, let’s begin by looking at a bitcoin address.

What exactly is a Bitcoin address?

Well, in layman terms, a Bitcoin address is used to send and receive Bitcoins, and looking a bit closer (excuse the pun), it has two parts:[vi]

1. A public key that is openly shared with the world to accept payments. 
2. A private key that is derived from the public key. 

The private key is made up of 256 bits of information in a (hopefully) random order. This 256 bit code is 64 characters long (in the range of 0-9/a-f) and further compressed into a 52 character code (using RIPEMD-160).

NOTE: Although many people talk about Bitcoin encryption, Bitcoin does not use Encryption. Instead, Bitcoin uses a hashing algorithm (for more info, please see endnote below[vii]).

Now, back to understanding the private key:

The Bitcoin address “1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm” translates to a private key of “5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAnchuDf” which further translates to a 256 bit private key of “0000000000000000000000000000000000000000000000000000000000000001” (this should go without saying, but do not use this address/private key because it was compromised long ago.) Although there are a few more calculations that go behind the scenes, these are the most relevant details.

Now, to access a Bitcoin address, you first need the private key, and from this private key, the public key is derived. With current computers, it’s classically impractical to attempt to find a private key based on a public key. Simply put, you need the private key to know the public key.

However, it has already been theorized (and technically proven) that due to private key compression, multiple private keys can be used to access the same public key (aka address). This means that your Bitcoin address has multiple private keys associated with it, and, if someone accidentally discovers or “cracks” any one of those private keys, they have access to all the funds in that specific address.

There is even a pool of a few dedicated people hunting for these potential overlaps[viii], and they are, in fact, getting very efficient at it. The creator of the pool also has a website listing every possible Bitcoin private key/address in existence[ix], and, as of this writing, the pool averages 204 trillion keys per day! 

But wait! Before you get scared and start panic selling, the probability of finding a Bitcoin address containing funds (or even being used) is highly unlikely – nevertheless, still possible!

However, the more Bitcoin users, the more likely a “collision” (finding overlapping private/public key pairs)! You see, the security of a Bitcoin address is simply based on large numbers! How large? Well, according to my math, 1.157920892373x1077 potential private keys exist (that number represents over 9,500 digits in length! For some perspective, this entire article contains just over 14,000 characters.  Therefore, the total number of Bitcoin addresses is so great that the probability of finding an active address with funds is infinitesimal.

So, how do Quantum Computers present a threat?

At this point, you might be thinking, “How can a quantum computer defeat this overwhelming number of possibilities?” Well, to put it simple; Superposition and Entanglement[x].

Superposition allows a quantum bit (qbit) to be in multiple states at the same time. Entanglement allows an observer to know the measurement of a particle in any location in the universe. If you have ever heard Einstein’s quote, “Spooky Action at a Distance,” he was talking about Entanglement!

To give you an idea of how this works, imagine how efficient you would be if you could make your coffee, drive your car, and walk your dog all at the same time, while also knowing the temperature of your coffee before drinking, the current maintenance requirements for your car, and even what your dog is thinking! In a nutshell, quantum computers have the ability to process and analyze countless bits of information simultaneously – and so fast, and in such a different way, that no human mind can comprehend!

At this stage, it is estimated that the Bitcoin address hash algorithm will be defeated by quantum computers before 2028 (and quite possibly much sooner)! The NSA has even stated that the SHA256 hash algorithm (the same hash algorithm that Bitcoin uses) is no longer considered secure, and, as a result, the NSA has now moved to new hashing techniques, and that was in 2016! Prior to that, in 2014, the NSA also invested a large amount of money in a research program called “Penetrating Hard Targets project”[xi] which was used for further Quantum Computer study and how to break “strong encryption and hashing algorithms.” Does NSA know something they’re not saying or are they just preemptively preparing?

Nonetheless, before long, we will be in a post-quantum cryptography world where quantum computers can crack crypto addresses and take all the funds in any wallet.

What are Bitcoin core developers doing about this threat?

Well, as of now, absolutely nothing. Quantum computers are not considered a threat by Bitcoin developers nor by most of the crypto-community. I’m sure when the time comes, Bitcoin core developers will implement a new cryptographic algorithm that all future addresses/transactions will utilize. However, will this happen before post-quantum cryptography[xii]?

 Moreover, even after new cryptographic implementation, what about all the old addresses? Well, if your address has been actively used on the network (sending funds), it will be in imminent danger of a quantum attack. Therefore, everyone who is holding funds in an old address will need to send their funds to a new address (using a quantum safe crypto-format). If you think network congestion is a problem now, just wait…

Additionally, there is the potential that the transition to a new hashing algorithm will require a hard fork (a soft fork may also suffice), and this could result in a serious problem because there should not be multiple copies of the same blockchain/ledger. If one fork gets attacked, the address on the other fork is also compromised. As a side-note, the blockchain Nebulas[xiii] will have the ability to modify the base blockchain software without any forks. This includes adding new and more secure hashing algorithms over time! Nebulas is due to be released in 2018.

Who would want to attack Bitcoin?

Bitcoin and cryptocurrency represent a threat to the controlling financial system of our modern economy. Entire countries have outright banned cryptocurrency[xiv] and even arrested people[xv], and while discrediting it, some countries are copying cryptocurrency to use (and control) in their economy[xvi]!

Furthermore, Visa[xvii], Mastercard[xviii],  Discover[xix], and most banks act like they want nothing to do with cryptocurrency, all the while seeing the potential of blockchain technology and developing their own[xx]. Just like any disruptive technology, Bitcoin and cryptocurrencies have their fair share of enemies!

As of now, quantum computers are being developed by some of the largest companies in the world, as well as private government agencies.

No doubt, we will see a post-quantum cryptography world sooner than most realize. By that point, who knows how long “3 letter agencies” will have been using quantum technology - and what they’ll be capable of!

What can we do to protect ourselves today?

Of course, the best option is to start looking at how Bitcoin can implement new cryptographic features immediately, but it will take time, and we have seen how slow the process can be just for scaling[xxi].

The other thing we can do is use a Bitcoin address only once for outgoing transactions. When quantum computers attack Bitcoin (and other crypto currencies), their first target will be addresses that have outgoing transactions on the blockchain that contain funds.

This is due to the fact that when computers first attempt to crack a Bitcoin address, the starting point is when a transaction becomes public. In other words, when the transaction is first signed – a signed transaction is a digital signature derived from the private key, and it validates the transaction on the network. Compared to classical computers, quantum computers can exponentially extrapolate this information.

Initially, Bitcoin Core Software might provide some level of protection because it only uses an address once, and then sends the remaining balance (if any) to another address in your keypool. However, third party Bitcoin wallets can and do use an address multiple times for outgoing transactions. For instance, this could be a big problem for users that accept donations (if they don’t update their donation address every time they remove funds). The biggest downside to Bitcoin Core Software is the amount of hard-drive space required, as well as diligently retaining an up-to-date copy of the entire blockchain ledger.

Nonetheless, as quantum computers evolve, they will inevitably render SHA256 vulnerable, and although this will be one of the first hash algorithms cracked  by quantum computers, it won’t be the last!

Are any cryptocurrencies planning for the post-quantum cryptography world?

Yes, indeed, there are! Here is a short list of ones you may want to know more about:

• IOTA[xxii]
  IOTA uses Winternitz one-time signatures[xxiii]. As the name suggests, an address is considered compromised once it signs a transaction on the network, and, therefore, you can only send from an address one time before it’s compromised.
• ADA (Cardano)[xxiv]
  The Cardano roadmap lists quantum resistant signatures using “BLISS.” While BLISS is a strong hashing method, it has an estimated lifespan with classical computers of 6000 signatures (usages)[xxv] but this number could be significantly reduced with quantum tech.
• Ethereum[xxvi]
  The Ethereum network, as well as many more blockchain networks, use the SHA3[xxvii] hash algorithm which is superior to SHA256. Although this is considered by some to be resistant, it is not technically quantum resistant. There is talk of using Lamport Signatures[xxviii] in the future of Ethereum. Although it is not definite at this point, it’s great to see the developers proactive.
• QRL (Quantum Resistant Ledger)[xxix]
  This blockchain concept was conceived in 2016 and is currently in beta testing. Using XMSS (Extended Merkle Signature Scheme) trees combined with Winternitz one-time signatures (but not one time!), it’s fast, salable and truly quantum resistant. If you have not yet checked out this project, I highly suggest you do. To understand why this project is truly post-quantum cryptography ready, do your own due diligence and read the QRL whitepaper.   

Full disclosure: 

Although I am in no way associated with any project listed above, I do hold coins in all.

The thoughts above are based on my personal research, but I make no claims to being a quantum scientist or cryptographer. So, don’t take my word for anything. Instead, do your own research and draw your own conclusions. I’ve included many references below, but there are many more to explore.

In conclusion, the intention of this article is not to create fear or panic, nor any other negative effects. It is simply to educate. If you see an error in any of my statements, please, politely, let me know, and I will do my best to update the error.

Thanks for reading!

References

• [i] – A great video explaining quantum computers.   
• [ii] https://www.doc.ic.ac.uk/~nd/surprise_97/journal/vol4/spb3/ - A brief history of quantum computing.   
• [iii] https://en.wikipedia.org/wiki/Apple_Lisa - More than you would ever want to know about the Apple Lisa.   
• [iv] - Want to learn more about computer science? Here is a great crash course for it!   
• [v] https://www.collinsdictionary.com/dictionary/english/quantify - What does quantify mean?   
• [vi] https://en.bitcoin.it/wiki/Private_key - More info about Bitcoin private keys.   
• [vii] https://www.securityinnovationeurope.com/blog/page/whats-the-difference-between-hashing-and-encrypting - A good example of the deference between Hash and Encryption   
• [viii] https://lbc.cryptoguru.org/stats - The Large Bitcoin Collider.   
• [ix] http://directory.io/ - A list of every possible Bitcoin private key. This website is a clever way of converting the 64 character uncompressed key to the private key 128 at a time. Since it is impossible to save all this data in a database and search, it is not considered a threat! It’s equated with looking for a single needle on the entire planet.   
• [x] https://uwaterloo.ca/institute-for-quantum-computing/quantum-computing-101#Superposition-and-entanglement – Brief overview of Superposition and Entanglement.  
• [xi] https://www.washingtonpost.com/world/national-security/nsa-seeks-to-build-quantum-computer-that-could-crack-most-types-of-encryption/2014/01/02/8fff297e-7195-11e3-8def-a33011492df2_story.html?utm_term=.e05a9dfb6333 – A review of the Penetrating Hard Targets project.   
• [xii] https://en.wikipedia.org/wiki/Post-quantum_cryptography - Explains post-quantum cryptography.   
• [xiii] https://www.nebulas.io/ - The nebulas project has some amazing technology planned in their roadmap. They are currently in testnet stage with initial launch expected taking place in a few weeks. If you don’t know about Nebulas, you should check them out.   [xiv] https://en.wikipedia.org/wiki/Legality_of_bitcoin_by_country_or_territory - Country’s stance on crypto currencies.   
• [xv] https://www.cnbc.com/2017/08/30/venezuela-is-one-of-the-worlds-most-dangerous-places-to-mine-bitcoin.html - Don’t be a miner in Venezuela!   
• [xvi] http://www.newsweek.com/russia-bitcoin-avoid-us-sanctions-cryptocurrency-768742 - Russia’s plan for their own crypto currency.   
• [xvii] http://www.telegraph.co.uk/technology/2018/01/05/visa-locks-bitcoin-payment-cards-crackdown-card-issuer/ - Recent attack from visa against crypto currency.   
• [xviii] https://www.ccn.com/non-government-digital-currency-junk-says-mastercard-ceo-rejecting-bitcoin/ - Mastercards position about Bitcoin.   
• [xix] http://www.livebitcoinnews.com/discover-joins-visa-mastercard-barring-bitcoin-support/ - Discovers position about Bitcoin.   
• [xx] http://fortune.com/2017/10/20/mastercard-blockchain-bitcoin/ - Mastercard is making their own blockchain.   
• [xxi] https://bitcoincore.org/en/2015/12/21/capacity-increase/ - News about Bitcoin capacity. Not a lot of news…   
• [xxii] https://learn.iota.org/faq/what-makes-iota-quantum-secure - IOTA and quantum encryption.   
• [xxiii] https://eprint.iacr.org/2011/191.pdf - The whitepaper of Winternitz One-Time Signature Scheme 
• [xxiv] https://cardanoroadmap.com/ - The Cardano project roadmap.   
• [xxv] https://eprint.iacr.org/2017/490 - More about the BLISS hash system.  
• [xxvi] https://www.ethereum.org/ - Home of the Ethereum project.   
• [xxvii] https://en.wikipedia.org/wiki/SHA-3#Security_against_quantum_attacks – SHA3 hash algorithm vs quantum computers.   
• [xxviii] https://en.wikipedia.org/wiki/Lamport_signature - Lamport signature information.   
• [xxix] https://theqrl.org/ - Home of the Quantum Resistant Ledger project.