Yesterday we learned from new Snowden leaks that the NSA is working to build a quantum computer. The Washington Post broke the story with the rather sensationalist headline, NSA seeks to build quantum computer that could crack most types of encryption.

Naturally, this raised much concern among the new Bitcoiners on Reddit and Facebook. The reality, however, is there wasnt much disclosed that people didnt already know or expect. Weve known that the NSA has openly sponsored quantum computing projects in the past. The fact that it has an in-house project called Penetrating Hard Targetsis new, but not really unexpected. We learned this project has a $79.7 million budget, but quite frankly that isnt that much. And as The Post notes, the documents dont reveal how far along they are in their research andIt seems improbable that the NSA could be that far ahead of theopen world without anybody knowing it.

Nevertheless, this seems like a good time to discuss the implications of quantum computing with respect to the future of Bitcoin.

Lets start with a little primer for those who are unfamiliar with quantum computing.Todays computers encode information into bits binary digits, either 0 or 1. These bits are usually stored on your computers hard disk by changing the polarity of magnetization on a tiny section of a magnetic disk, or stored in RAM or flash memory represented by two different levels of charge in a capacitor. Strings of bits can be combined to produce data that is readable by humans. For example, 01000001 represents the letter A in theextended ASCII table. Any calculations that need to be performed with the bits are done one at a time.

Quantum computers, on the other hand, use the various states of quantum particles to represent quantum bits (qubits). For example, a photon spinning vertically could represent a 1, while a photon spinning horizontally could represent a 0. But photons can also exist in a rather weird state called superposition. That is,while they can spin vertically, horizontally, and diagonally, they can also spin in all those directionsat the same time. Dont ask me how thats possible, its the bizarro world of quantum mechanics.

What this means for practical purposes is while a traditional computer can perform only one calculation at a time, a quantum computer could theoretically perform millions of calculations all at once, improving computing performance by leaps and bounds.

Now when journalists write things like, In room-size metal boxes secure against electromagnetic leaks, the National Security Agency is racing to build a computer that could break nearly every kind of encryption used to protect banking, medical, business and government records around the world, it naturally makes people think its the end of cryptography as we know it. But that isnt the case.

Lets consider the type attack most people think of when hear of quantum computersa brute force attack. This is where you just keep checking different keys until you eventually find the right one. Given enough time, you could brute force any encryption key. The problem is it would take billions or trillions of years for a modern computer to brute force a long encryption key. But surely quantum computers could do this right? This is from Bruce Schneiers 1996 book, Applied Cryptography:

One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant. (Stick with me; the physics lesson is almost over.)

Given that k = 1.3810-16erg/Kelvin, and that the ambient temperature of the universe is 3.2Kelvin, an ideal computer running at 3.2K would consume 4.410-16ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.

Now, the annual energy output of our sun is about 1.211041ergs. This is enough to power about 2.71056single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2192. Of course, it wouldnt have the energy left over to perform any useful calculations with this counter.

But thats just one star, and a measly one at that. A typical supernova releases something like 1051ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will beunfeasibleuntilcomputers are built from something other than matter and occupy something other than space.

To recap, if you could harness all the energy from a supernova and channel it into an ideal computer, you still couldnt brute force a typical encryption key. Needless to say, if you are going to break commercial encryption algorithms youre going to have to attack the underlying math.

Today, most public-key encryption algorithms rely on either the difficulty of integer factorization (RSA) or the difficulty of discrete logarithm problems (DSA/El Gamal, and Elliptic Curve Cryptography).In 1994, mathematician Peter Shor demonstrated an efficient quantum algorithm for factoring and calculating discrete logarithms that would break public-key encryption when used with a quantum computer. This wouldnt break all types of cryptography, however. Traditional symmetric-key cryptography and cryptographic hash functions would still be well out of range of quantum search algorithms.

Impact on Bitcoin

Bitcoin uses several cryptographic algorithmsThe Elliptic Curve Digital Signature Algorithm (ECDSA) for signing transactions and the hash functions SHA-256 and RIPEMD160. If the NSA succeeds in developing a cryptologically useful quantum computer, ECDSA would fall while SHA-256 and RIPEMD160 would remain secure.

The good news is that ECDSA should be relatively easy to swap out if/when it becomes compromised. It would be much worse if SHA-256 were to go down. If youre not in tune to the mechanics of Bitcoin, SHA-256 is used in Bitcoin mining. At the moment, billions of dollars have been spent on custom computer chips that do nothing but perform SHA-256 calculations. If SHA-256 were to go down, those custom chips would turn into expensive paperweights. If that happened suddenly (as opposed to allowing for a smooth transition to another hash function), it would be pretty catastrophic. The security in bitcoin relies on the fact that it would be too difficult and expensive for an attacker to command 51% of the processing power in the network. A sudden switch to another hash function would significantly compromise security and likely cause the price to tank. But as I mentioned, Bitcoiners can rest easy because SHA-256 isnt threatened by quantum computers (although that doesnt mean someone wont find a feasible attack in the future).

Back to ECDSA. This algorithm generates a public/private key pair. In Bitcoin, you keep the private key secret and use it sign your transactions, proving to the network that you own the bitcoins associated with a particular bitcoin address. The network verifies your signature by using the corresponding public key. A functioning quantum computer would allow the NSA to derive anyones private key from their public key. So do this mean that the NSA would be able to steal everyones bitcoins? Not exactly.

Heres the thing, in Bitcoin your public key isnt (initially) made public. While you share your Bitcoin address with others so that they can send you bitcoins, your Bitcoin address is only a hash of your public key, not the public key itself. What does that mean in English? A hash function is a one-way cryptographic function that takes an input and turns it into a cryptographic output. By one-way I mean that you cant derive the input from the output. Its kind of like encrypting something then losing the key. To demonstrate, lets calculate the RIPEMD160 hash of Hello World.

A Bitcoin address is calculated by running your public key through several hash functions as follows:

All of that is a complicated way of saying that while an attacker with a quantum computer could derive the private key from the public key, he couldnt derive the public key from the Bitcoin address since the public key was run through multiple quantum-resistant one-way hash functions.

However, you do have to broadcast your public key to the network to make a transaction, otherwise there is no way to verify your signature. What this implies is that in the face of an NSA quantum computer all Bitcoin addresses would have to be considered one-time use addresses. Whenever you make a transaction you would have to send any excess bitcoin to a newly generated address as change. If you didnt remove the entire balance from your address, the NSA could steal the remainder.While this is inconvenient, it would buy the developers enough time to swap out ECDSA for a quantum-resistant digital signature scheme.

Post-Quantum Digital Signatures

This section is going to be a little technical but hopefully not too difficult for beginners to follow. There are several different types of post-quantum public-key encryption systems: lattice-based, code-based, multivariate-quadratic, and hash-based. As I already mentioned, cryptographic hash functions are presumed to be quantum-resistant. Given that, it should be possible to build a replacement digital signature scheme for ECDSA using only hash functions. Lets take a look at these hash-based systems since they are easy to understand and the hash functions theyre based on are already widely used.

Lamport One-Time Signature Scheme (LOTSS)

To begin, were going to want to use a hash function with at least a 160-bit output to provide adequate security. RIPEMD160 or SHA-1 should work. To generate the public/private key pair, well start by generating 160 pairs of random numbers (320 numbers total). This set of random numbers will serve as the private key.

To generate the public key well take the RIPEMD160 hash of each of the 320 random numbers. (Note: Im going to have to cut the numbers in half to fit them in this table)

Now to sign a message with a Lamport signature well first create a message digest by hashing the message with RIPEMD160 (in Bitcoin we would hash the transaction) then converting the output to binary. Well once again use Hello World as an example.

Next, well match up each binary digit with each pair in our private key. If the bit is 0 we will add the first number in the pair to our signature, if it is 1 well add the second.

Finally to verify the signature is valid, youll first create a message digest using the same process as above. Then hash each of the 160 numbers in the signature with RIPEMD160. Finally, check to make sure these hashes match the hashes in the public key that correspond with the message digest.

So there you have it, a quantum-resistant digital signature scheme using only hash functions. Only the person in possession of the 320 random numbers in the private key could have generated a signature that hashes to the public key when compared to the digest. However, while his scheme does in fact work, it isnt without problems. First, as the name suggests, LOTSS signatures can only be used once. The reason for this is because you are essentially releasing half of your private key with each signature. If you were to sign multiple messages, your private key would be completely compromised. If this were used in Bitcoin, you still could only use each Bitcoin address once.

Equally problematic, the key sizes and signatures are ridiculously large. The private and public keys are 6,400 bytes compared to 32 and 64 for the ECDSA private and public keys. And the signature is 3,200 bytes compared to 71-73 bytes. Bitcoin already has issues with scalability, increasing the key and signature sizes by that much would make the problems much worse.

The Lamport private key can be dramatically reduced in size by generating the random numbers from a single random seed. To do this you would just take RIPEMD160(seed + n) where n starts at 1 and gets incremented to 320. Unfortunately, the size of the private key isnt so much the problem as is the size of the public key and signature. There is another one-time signature scheme called Winternitz signatures that has the potential to reduce key size but at the cost of hash operations. Fortunately, we arent done yet.

Merkle-Signature Scheme (MSS)

The Merkle Signature Scheme combines the one-time signature scheme (either Lamport or Winternitz) with a Merkle tree (also called a hash tree). This allows us to use one public key to sign many messages without worrying about compromising security. Lets see how this works.

Well start by generating a number of Lamport key pairs. The number well generate will be equal to the number of signatures we want to get out of a single public key. Lets just say eight as an example. Next well calculate a Merkle tree using each of the eight Lamport public keys. To do this, the public keys are paired together, hashed, then the hashes are concatenated together and hashed again. This process is repeated until something looking like an NCAA Tournament bracket is formed.

The hash at the very top of the tree (the Merkle root) is the Merkle public key. This massively reduces the public key size from 6,400 bytes in the Lamport signature to only 20 bytes, the length of a single RIPEMD160 hash.

To calculate a signature, you select one of your Lamport key pairs and sign the message digest just like before. This time, the signature will be the Lamport signature plus each one of leafs in the Merkle tree leading from the public key to the root.

In the above diagram the signature would be:

To verify the Merkle signature one would just verify the Lamport signature, then check to make sure the leafs hash to the Merkle public key. If so, the signature is valid.

There are several advantages of the MSS over LOTSS. First, the public and private keys are reduced to 20 bytes from 6,400 bytes. Also, you can create multiple signatures per public key. But there is still a major draw back. The more messages you want to sign with your public key, the larger the Merkle tree needs to be. The larger the tree, the larger the signature. Eventually the signature starts to become impractically large, especially for use in Bitcoin. This leads us to the final post-quantum signature schemes well discuss.

CMSS And GMSS

MSS has been known for over 30 years and has remained essentially unscathed despite extensive cryptanalysis. However, most of the improvements to it have come in the last five years or so. In my brief survey of the literature, it seems a couple signature schemes by Buchmann, Dahmen, Klintsevich, et. al., are the most promising of the lot. These are the Improve Merkle Signature Scheme (CMSS) and Generalized Merkle Signature Scheme (GMSS) (Links to the academic papers can be found here and here). Two of the cryptographers behind this signature scheme are authors of a textbook on post-quantum cryptography.

Both CMSS and GMSS offer substantially improved signature capacity with reasonable signature lengths and verification times. GMSS in particular offers virtually unlimited signature capacity at 280 signatures but with slower performance in others areas compared to CMSS. They accomplishes this by breaking the system up into separate Merkle trees of 2n leafs. A signature from the root tree is used to sign the public key of the tree below it which signs the tree below it and so on.

So it seems to me that either of these signature schemes would be a serious candidate to replace Bitcoins ECDSA in a post-quantum world. But why not just go ahead and implement it now and rather than wait until the NSA springs a surprise on us? Lets do a little comparison and take a look at the time (t) and memory (m) requirements for each. CMSS variants have signature capacities of 220, 230, and 240 while GMSS has signature capacities of 240 and 280. I would assume that 240 if not 230 would be plenty for Bitcoin as I cant imagine someone would make more than a billion or trillion transactions from a single address. Also, GMSS can be optimized for faster verification times but at the expense of a 25% larger signature.

So from the table we can see that CMSS and GMSS actually perform better than ECDSA in public key size and signature time. However, in the critical variable that will affect scalability, signature size, they dont perform nearly as well. Verification time for CMSS is actually better than ECDSA which would actually improve scalability and the optimized variant of GMSS is relatively close, but signature size for both would definitely be an issue. Consider some very rough estimates: the average transactions size is currently about 500 bytes, either CMSS or GMSS would push it up over 4000 bytes. That means you could be looking at an increase in the size of the block chain of upwards of 700%. The block chain is currently at 12.7 gigabytes. Had Bitcoin employed either of these signature schemes from the beginning, it would be over 100 gigabytes right now. Signature and key size isnt a problem that is unique to hash-based signature schemes either, most of the others are in the same ballpark.

Also, note the insane keygen time for GMSS. If you left your computer running for 24 straight hours you would have only generated 3 bitcoin address and thats using the optimized variant with larger signatures! I suspect, however, that an ASIC hardware wallet would significantly improve that performance. Keygen for CMSS isnt that bad.

So in other words, Bitcoin cant adopt one of these signature schemes at the moment if we want to scale beyond present capacity. However, by the time quantum computers become viable, Moores law will likely have brought the cost of storage and processing power down to the point where CMSS, GMSS or one of the other types of post-quantum signature schemes could easily be merged into Bitcoin. Until then, lets not lose any sleep over Penetrating Hard Targets.

Original content by Chris, copyleft, tips welcome

Related

Excerpt from:

Bitcoin vs. The NSAs Quantum Computer Bitcoin Not Bombs

- How Quantum Computers Work - May 3rd, 2018
- This is what a 50-qubit quantum computer looks like - January 15th, 2018
- Inside Microsofts quantum computing world | InfoWorld - January 1st, 2018
- Microsoft Takes Path Less Traveled to Build a Quantum ... - December 13th, 2017
- Researchers create new type of quantum computer | Harvard Gazette - December 12th, 2017
- Microsoft releases quantum computing development kit preview ... - December 12th, 2017
- Intel moves towards production quantum computing with new 17 ... - October 11th, 2017
- Quantum computer a possibility in 10 years - News.com.au - NEWS.com.au - September 7th, 2017
- Scientists Propose a New Kind of Quantum Computer, But What ... - Gizmodo - September 7th, 2017
- Quantum detectives in the hunt for the world's first quantum computer - Phys.Org - September 7th, 2017
- Scientists Just Found A Use For The Hashtag In Quantum Computing - Gizmodo Australia - September 4th, 2017
- The Future of AI: From Quantum Computing to the Internet of Things - Outer Places - September 4th, 2017
- We're About to Cross The 'Quantum Supremacy' Limit in Computing - ScienceAlert - September 2nd, 2017
- Explaining the Most Recent Record for Quantum Computing: A 51-Qubit Quantum Computer Array - All About Circuits - September 2nd, 2017
- USRA Upgrades D-Wave Quantum Computer to 2000 Qubits - insideHPC - September 1st, 2017
- Quantum encrypted box hints at unhackable communication - Wired.co.uk - September 1st, 2017
- Quantum Computer Programming: What You Need to Learn to Get ... - TrendinTech - September 1st, 2017
- Google's John Martinis Believes Quantum Computing Threat to Be Long Way Off - Bitcoin News (press release) - August 31st, 2017
- Australian quantum computing outfit goes commercial - Networks Asia - August 31st, 2017
- Elusive Majorana Particle Takes Major Step Towards Quantum Computing - IEEE Spectrum - August 29th, 2017
- Australia gets quantum computing company - ACS (registration) - August 28th, 2017
- Quantum Computing and Financial Trading - LeapRate - August 28th, 2017
- Russians Lead the Quantum Computer Race With 51-Qubit Machine - Edgy Labs (blog) - August 28th, 2017
- qBitcoin: A Way of Making Bitcoin Quantum-Computer Proof? - IEEE Spectrum - August 26th, 2017
- Hype and cash are muddying public understanding of quantum ... - Phys.Org - August 26th, 2017
- Silicon Quantum Computing launched to commercialise UNSW ... - ZDNet - August 23rd, 2017
- IEEE Approves Standards Project for Quantum Computing ... - Business Wire (press release) - August 23rd, 2017
- Introducing Australia's first quantum computing hardware company - CIO Australia - August 23rd, 2017
- What is quantum computer? - Definition from WhatIs.com - August 22nd, 2017
- Hype and cash are muddying public understanding of quantum computing - The Conversation AU - August 22nd, 2017
- Finns chill out quantum computers with qubit refrigerator to cut out errors - ZDNet - August 22nd, 2017
- UNSW joins with government and business to keep quantum computing technology in Australia - The Australian Financial Review - August 22nd, 2017
- 'Tools of DESTRUCTION' Quantum computers WILL wreak havoc ... - Express.co.uk - August 19th, 2017
- Quantum computing comes of age - Alphr - August 14th, 2017
- No, Quantum Teleportation Won't Let Us Send Instant Messages to Alpha Centauri - Air & Space Magazine - August 12th, 2017
- Google on track for quantum computer breakthrough by end of ... - August 11th, 2017
- Closing In On Quantum Computing | WIRED - August 11th, 2017
- World's Leading Physicist Says Quantum Computers Are Tools of Destruction, Not Creation - Futurism - August 10th, 2017
- Will you be able to trust a quantum computer? - Digital Journal - August 9th, 2017
- New Methods of Controlling Electrons Could be Major in Quantum Computing - TrendinTech - August 5th, 2017
- Exactly what could quantum computers do? - Electronics Weekly - August 4th, 2017
- What is quantum computing and why does the future of Earth depend on it? - Alphr - August 2nd, 2017
- The Age of Quantum Computers is upon us! - Gizbot - August 2nd, 2017
- Ultracold molecules hold promise for quantum computing | MIT News - MIT News - August 1st, 2017
- Clarifiying complex chemical processes with quantum computers - Phys.Org - August 1st, 2017
- When Will Quantum Computers Be Consumer Products? - Futurism - August 1st, 2017
- Quantum Computers Just Moved a Step Closer to Reality - NBCNews.com - August 1st, 2017
- A New Breakthrough in Quantum Computing is Set to Transform Our ... - Futurism - August 1st, 2017
- Quantum computers compete for supremacy - Salon - July 10th, 2017
- Quantum Computers Compete for "Supremacy" - Scientific American - July 5th, 2017
- Less is more for Canadian quantum computing researchers - ITworld - July 4th, 2017
- New method could enable more stable and scalable quantum ... - Phys.Org - July 4th, 2017
- Volkswagen buys D-Wave quantum computers which sell for $15 million each - Robotics and Automation News (press release) (registration) - July 2nd, 2017
- 6 Things Quantum Computers Will Be Incredibly Useful For - Singularity Hub - July 1st, 2017
- Quantum Machine Learning Computer Hybrids at the Center of New Start-Ups - TrendinTech - June 20th, 2017
- Israel Enters Quantum Computer Race, Placing Encryption at Ever-Greater Risk - Sputnik International - June 20th, 2017
- Prototype device enables photon-photon interactions at room ... - Phys.Org - June 20th, 2017
- The Quantum Computer Factory That's Taking on Google and IBM - WIRED - June 20th, 2017
- Toward optical quantum computing - MIT News - June 17th, 2017
- Get ahead in quantum computing AND attract Goldman Sachs - eFinancialCareers - June 16th, 2017
- KPN CISO details Quantum computing attack dangers - Mobile World Live - June 16th, 2017
- Quantum Computing Technologies markets will reach $10.7 billion by 2024 - PR Newswire (press release) - June 14th, 2017
- From the Abacus to Supercomputers to Quantum Computers - Duke Today - June 13th, 2017
- Quantum Computers Will Analyze Every Financial Model at Once - Singularity Hub - June 13th, 2017
- Are Enterprises Ready to Take a Quantum Leap? - IT Business Edge - June 13th, 2017
- Scientists May Have Found a Way to Combat Quantum Computer Blockchain Hacking - Futurism - June 13th, 2017
- Microsoft and Purdue work on scalable topological quantum computer - Next Big Future - June 13th, 2017
- Doped Diamonds Push Practical Quantum Computing Closer to Reality - Motherboard - June 3rd, 2017
- Team develops first blockchain that can't be hacked by quantum computer - Siliconrepublic.com - June 3rd, 2017
- D-Wave partners with U of T to move quantum computing along - Financial Post - June 2nd, 2017
- Telstra just wants a quantum computer to offer as-a-service - ZDNet - June 1st, 2017
- Microsoft, Purdue Tackle Topological Quantum Computer - HPCwire - HPCwire (blog) - June 1st, 2017
- MIT Just Unveiled A Technique to Mass Produce Quantum Computers - Futurism - June 1st, 2017
- Here's How We Can Achieve Mass-Produced Quantum Computers - ScienceAlert - June 1st, 2017
- Research collaborative pursues advanced quantum computing - Phys.Org - June 1st, 2017
- AI and Quantum Computers Are Our Best Weapons Against Cyber Criminals - Futurism - June 1st, 2017
- Scientists claim to have invented the world's first quantum-proof ... - ScienceAlert - June 1st, 2017
- Google Plans to Demonstrate the Supremacy of Quantum ... - IEEE Spectrum - May 25th, 2017
- Top 5: Things to know about quantum computers - TechRepublic - May 25th, 2017
- Is the US falling behind in the race for quantum computing? - AroundtheO - May 25th, 2017

## Recent Comments