Creative Destruction in Cryptography

Public Key (PK) Cryptography is a field that’s been getting a lot of attention in the last few years. Comprised of a pair of a visible public key and a secret public key, public key cryptosystems offer unique benefits and weaknesses compared to the traditional symmetric key architectures of the past few hundred years. Famous programs and algorithms such as PGP (Pretty Good Privacy), Diffie-Hellman*,  and RSA have pushed PK ciphers into the mainstream and out of white papers and academic documents. For many of these developments, their resistance to serious cryptoanalytic attacks comes from our inability to factor large prime numbers. This security is no longer bulletproof though, thanks to the advent of quantum computers – computers based on quantum “qubits” that hold state thanks to the maddening physics of quantum mechanics.

The security of the Diffie-Hellman algorithm is an excellent example of this. Often used for exchanging temporary keys, Diffie-Hellman’s safety comes from mathematics’ current inability solve the Discrete Log Problem – extracting and solving for a, b in a function such as G^ab mod P where G and P are sufficiently large and relatively prime. In DH, a and b are the secret keys of both parties. If we had the ability to take a “Discrete Log” and solve for either of these numbers relatively quickly, Diffie-Hellman would be in trouble.

This is no trivial matter: cracking algorithms like Diffie Hellman and RSA would be a huge blow to both corporate security and national security. Everything from credit cards to nuclear launch codes could be fair game for a malicious mathematician who could rip apart ciphers in polynomial time. As Dr. David Mermin of Cornell University notes in his lectures on the topic:

“Any computer that can efficiently f[actor for large primes] would be an enormous threat to the security of both military and commercial communications. This is
why research into the feasibility of quantum computers is a matter of considerable interest in the worlds of war and business.” [1]

With the advent of quantum computing, our current public key cryptosystems are officially screwed. Compared to contemporary digital computers, quantum computers are able to hold more states than the familiar binary 1’s and 0’s thanks to quantum phenomena such as superposition. Quantum computing algorithms such as Shor’s Algorithm are able to factor prime numbers much faster than our current techniques. The difference in speed is striking. Using Shor’s Algorithm and some number theory, even RSA’s keypairs can be solved for in a comparatively short amount of time (a few months compared to not at all). This development seems to be the death knell for PK security. If the only security for private keys in a public key system is in their inability to be efficiently factored, that security’s days are numbered.

While it might seem like the death of public key infrastructure is imminent (or, even if so, is a bad thing), I’m not so sure that’s the case. The effects of this “technological development” of a quantum computing algorithm are not unlike the effects of the development of the computer or the rifle. These are all cases of technological development destroying a market. For the computer, it was the typewriter. For the rifle, it was the bow and arrow. For quantum computing and Shor’s Algorithm, it’s public key cryptography. Still, though the market for typewriters just ‘ain’t what it used to be, we as a society are undoubtably far better off. In fact, the creation of the computer has spawned a whole slew of new markets that have created products with superior and cheaper functionality than that of the typewriter – markets that we didn’t imagine when the first computer premiered.  This phenomena in economics is called Creative Destruction.

Joseph Shumpeter, a brilliant young economist who helped found the field of Industrial Organization, coined the phrase in his treatise on political economics called Capitalsim, Socialism and Democracy. In his text, Shumpeter describes the capitalist industrial process as a fluid process of internal revolution. This revolution is not bloodless; markets die at the expense of other markets being created, and certainly if you aren’t equipped to deal with change you’ll be thrown under the tracks. Still, society is better off with positive technological advancement because these new markets are of products and processes vastly superior in ways that aren’t immediately clear when they’re created.

Says Shumpeter on Creative Destruction:

The opening up of new markets, foreign or domestic, and the organizational development from the craft shop and factory to such concerns as [the ones faced by] U.S. Steel illustrate the same process of industrial mutation–if I may use that biological term–that incessantly revolutionizes the economic structure from within, incessantly destroying the old one, incessantly creating a new one. This process of Creative Destruction is the essential fact about capitalism. It is what capitalism consists in and what every capitalist concern has got to live in. [2]

This is very relevant to quantum computing and cryptography. Though contemporary public key infrastructures may be rendered invalid after the advent of workable and practical quantum computers and cryptoanalytic algorithms, we may very well discover a new means of cryptography that gives us the benefits of PK with a suitably superior means of protection other than primality. The same qubits that can be used to break RSA can be used as a means of storing and operating new encryption and decryption schemes. Already, algorithms such as the BB84 encryption scheme are being developed to profit off of the increased number of states available for generating ciphertext (encrypted messages) [3].

One of the things I’ve learned in studying computer science and economics is that predicting the development of technology is a decidedly hard job. I don’t think anyone can tell you exactly what’s going to come out of quantum computing and cryptography. But I’m sure that though public key may be on the way out, we’re going to get something far superior and far more robust in its place.

Like Alan Turing says, we really “only can see a short distance into the future.”

Sources:

1. David Mernin, “III: Breaking RSA with a Quantum Computer: Shor’s Factoring Algorithm”, CS483 Lecture Notes – Cornell University, 3-28-06, http://people.ccmr.cornell.edu/~mermin/qcomp/chap3.pdf.
2. Joseph Shumpeter, Capitalism, Socialism and Democracy (New York: Harper, 1975) [orig. pub. 1942], pp. 82-85.
3. C. H. Bennet and G. Brassard, “Quantum Cryptography: Public key distribution and coin tossing”, in Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing, Bangalore, p. 175 (1984)

*Notes:

• Diffie-Hellman is technically a public-key algorithm. Both G and P in G^(ab) mod P are public. Even if they’re privately agreed upon by both parties before encryption, by Kirchoff’s Principle we have to assume that an attacker is able to compromise and discover G and P.
• “Faster” is in reference to the complexity of prime factorization algorithms. Most of the O(n) for non-quantum prime factorization techniques such as sieve algorithms take place somewhere between polynomial and exponential time (e.g.: General Number Sieve Algorithm). Shor’s Algorithm is approximately O(N^3).