We recently hosted Dr. Ralph Merkle as a guest speaker for the Verisign Labs Distinguished Speaker Series. His talk, “Quantum Computers and Public-Key Cryptosystems,” was a great presentation on how molecular nanotechnology — the ability to economically manufacture most arrangements of atoms permitted by physical law — could fundamentally alter the world as we know it. Ralph’s and many others’ research on this topic has been groundbreaking and we are grateful he took the time to come and share his knowledge.
A little background: In 1974, Ralph, co-inventor of public-key cryptography, challenged conventional thinking on information security by proposing a way for two users who initially don’t share a secret key with each other (or anyone else) to protect the messages they exchange. How could they go from a state where they have no apparent way to protect their messages, to one where they do?
The answer is obvious now in hindsight, and we experience it every time we make a secure connection to a web server and in many other applications: two users can protect the messages they exchange using public-key cryptography. In public-key cryptography, keys come in pairs, a public key and a private key. Messages are encrypted with the public key, and decrypted with the corresponding private key. The two users thus only need to give each other their public keys (in a trusted way); they keep their private keys to themselves, so no secret keys are shared with anyone. They protect the messages they exchange by encrypting them with one another’s public keys. (In a typical implementation between a user and a web server, only the web server initially needs a key pair, which is enough to get an encrypted session started.)
Nearly four decades ago when the internet was in its infancy, public-key cryptography hadn’t yet been discovered, and it was inconceivable that a message could be protected between two users without someone sharing some secret keys. For an undergraduate project, Ralph thought about proving that no such method had these properties, and when a proof was not forthcoming, he set out to find a method that did.
In the method he discovered now known as Merkle’s Puzzles, two users agree on a shared secret key by taking the role of “puzzle maker” and “puzzle solver.” The puzzle maker creates N puzzles for some moderately large number N. It should be the case that it’s much easier to make a puzzle with a solution known in advance than to solve the puzzle. In particular, suppose that it takes about the same time to create N puzzles as to solve one. The puzzle maker keeps the solutions to the puzzles and sends the puzzles to the puzzle solver.
The puzzle solver then randomly chooses one of the puzzles and solves it. Let S be the solution. The puzzle solver then derives an encryption key from the solution S, encrypts a test message with the encryption key, and sends the result back to the puzzle maker.
The puzzle maker can verify which of the puzzles the puzzle solver has solved by seeing which of the solutions that it already knows produces an encryption key that correctly decrypts the encrypted test message. This is a trial-and-error process with at most N solutions, so will take on the same order of time as creating the N puzzles did. At this point, the puzzle creator and puzzle solver share a secret key!
Is this secure? Consider the view of an attacker who can only observe the messages exchanged by the two users. The attacker sees the puzzles and the encrypted test message, but the attacker doesn’t know which puzzle was solved. Therefore, the attacker may have to solve up to all N of them to get the possible encryption keys. This is about N times as much work as either user had to do, meaning that it’s N times as hard to break the system as to use it.
A factor of N margin is good, but not great, considering that N puzzles have to be exchanged. (If we wanted a margin of a billion, we’d need to exchange a billion puzzles.) Still, conceptually, Merkle’s Puzzles were a breakthrough: It demonstrated that secrets could be established from exchanges of public information.
The method was the first instance of public-key cryptography preceding the more general – and now better established – methods of later in the 1970s that are based on number theory. (More on those in a moment.)
Now in 2013, Ralph is again challenging conventional thinking that public-key cryptography as we know it is here to stay. There have always been suggestions that improvements in algorithms for factoring large numbers or solving other number-theory problems could break today’s public-key cryptography. That’s still the case, though there haven’t been any significant practical advances in improving these algorithms in years.
And for that last 20 years or so, there have been even more remarkable suggestions that a new kind of computer — a quantum computer — could break today’s public-key cryptography. That’s still the case, because algorithms for factoring large numbers and solving other number-theory problems with a quantum already exist — they just need a large enough quantum computer to run on.
And that’s the hard part. There haven’t been any significant practical advances in building these computers in years. The theory still looks good, but the practice is hard.
Ralph’s challenge to conventional thinking is not about whether a large-scale quantum computer will be built — many people already believe one will eventually be — but how.
The way it will be built, as he described in his talk, is with molecular manufacturing: the programmed construction of materials atom by atom, molecule by molecule.
By operating at this scale, Ralph observed, molecular manufacturing will be able to put together the quantum “gates” and “circuits” in the precise and stable way required for a quantum computer to work.
Molecular manufacturing also has the right economic incentives, because each iteration of the technology in principle will produce more valuable materials than any previous technology. This in turn enables new applications, thereby motivating further investment. When that investment reaches a tipping point where a molecularly manufactured device can manufacture itself, we’re in quite a different world. A quantum computer would be a rather ordinary outcome at that point.
Whether that future will play out is hard to tell. But from the vantage point of Merkle’s Puzzles nearly 40 years ago, wouldn’t one be having the same hesitation about the future of public-key cryptography?
Pioneers in one field are rare; pioneers in two even rarer still. Recipient of the ACM Kanellakis Award, the IEEE Kobayashi Award, the RSA Award in Mathematics, the IEEE Hamming Medal, and many other honors, it is not surprising that Ralph would complement his early leadership in public-key cryptography with later leadership in molecular manufacturing. The common denominator is his passionate pursuit of the long-term future.
One of his early inventions in cryptography, it turns out, is actually among the best prepared for a potential long-term future of quantum computing enabled by molecular manufacturing: Merkle Hash Signatures. Although covered only briefly, this method was the nexus of Ralph’s talk: an encouragement to industry, in light of the potential impact of quantum computing in the future, to put alternatives such as Merkle Hash Signatures in place today.
Public-key cryptography includes two main types of techniques: public-key encryption, where one user encrypts a message with a public key and the other decrypts it with the corresponding private key; and digital signatures, where one user signs a message with the private key, and the other verifies the signature with the corresponding public key.
As noted, the established methods for public-key cryptography of both types today are based on number theory, and are vulnerable to a quantum computer.
But Merkle Hash Signatures, which are based only on one-way hash functions, are what is called “post-quantum secure.”
A quantum computer enables only a modest (though still fundamental) improvement in general-purpose algorithms for breaking hash functions, which can be mitigated by making the size of the hash function output larger. This is not so with the number-theory-based public-key cryptosystems, which would be subject to a complete break by a quantum computer.
Moreover, if a special-purpose quantum algorithm were found for breaking a specific hash function, then there are many other alternative hash functions to choose from (as far as the current theory indicates). Indeed, hash functions have been readily replaced when attacks with conventional computers have been discovered: consider the transition from MD4 to MD5 to SHA-1, SHA-2 and SHA-3. On the other hand, few alternatives have emerged to today’s number-theory-based public-key cryptosystems even with the ongoing research quest of nearly four decades.
Describing Merkle Hash Signatures will be a good subject for another post. In the meantime, the interested reader may want to refer to Ralph’s landmark 1979 paper “A Certified Digital Signature,” or recent Internet-Drafts by David McGrew and Michael Curcio, and by Russ Housley (both of which are encouraging steps toward the standardization and ultimate adoption of this method).
The next 40 years will be interesting for molecular manufacturing, quantum computing and cryptography. I’m grateful to Ralph for motivating further reflection on a potential future through his valuable long-term perspective, given in his many years of research and in this talk.
What do you see as the future of these technologies?
