21 February 2001

Provably unbreakable cryptography

Well, this is the most interesting thing I’ve heard about in a while: someone’s come up with a provably unbreakable encryption scheme that’s actually practical to implement.

There’s an article in the New York Times about it; basically, the scheme goes as follows:

  • Someone sets up a satellite to generate a stream of truly random numbers, synchronized to some appropriate time code.

  • The sender and recipient exchange a secret using an existing public-key encryption scheme, or using some other secure channel. The secret is a time code value.

  • At the pre-arranged time, the sender uses the random number stream from the satellite to encrypt the data, and the recipient temporarily caches the same chunk of random data in RAM.

  • When the recipient receives the encrypted message, he decrypts it with the cached data, then throws that data away.

What makes the system unbreakable is that unless you know the secret before the message is sent, you don’t know what part of the random number stream is going to be used—and it’s infeasible to store the entire stream indefinitely. What’s more, once the message has been decrypted, neither the sender nor the recipient has the means to decrypt it again.

The NYT article has some dismissive comments from people like Bruce Schneier, pointing out that even with breakable cryptography, there’s usually an easier way to get the data. But I think this new development is still valuable, because it’s a workable system of “rubber hose resistant cryptography”. That is, it’s a system where you can’t force the recipient to divulge the key and decrypt the message, because he provably can’t do it.

With today’s cryptosystems, if you log all a person’s messages over the course of years you can potentially one day get access to all of them—either by obtaining the single key used, or by breaking the cipher. This new system is equivalent to one-time pad, which is known to be unbreakable, and there’s no way to get access to messages after the fact.

I wonder how long it’ll be before someone sets up an implementation of this? Perhaps the NSA already use it…

© mathew 2017