Cloud Hosting

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