Crypto news: Vanish

One of the recent USENIX Security papers has been getting quite a bit of buzz: Vanish: Increasing Data Privacy with Self-Destructing Data. It's really a very clever paper, proposing a way to do something apparently impossible: ensuring that data (like email) 'disappears' after a certain period of time.

The core idea is this: the data doesn't really disappear, it just becomes unreadable. Specifically, the paper proposes that:

1. The data in question be encrypted with a fresh key,
2. That the key be split into many parts, using a secret-sharing scheme,
3. That these shares be stored at random locations on some peer-to-peer network (specifically, a distributed hash table), and
4. That instead of sending the data, you send the encrypted data and a list of where to find the key-shares

The underlying assumption is that people will drop out of the peer-to-peer network at some measurable rate, and that when they do, any shares they have will disappear with them. And the security of the key-splitting scheme tells us that when enough key-shares disappear, the key becomes unrecoverable.

(And what's more, the scheme can even be simplified a bit. Technically speaking, the encryption is just for convenience-- you can get away without it by splitting the data itself rather then the key.)

It's a very nice little scheme. It's already gone through one round of attack-and-patch, but that's not what really caught my interest. Instead, I was charmed by how it used secret-splitting schemes in a new and interesting way. I'm a fan of such schemes, you see, for the following reason: they are one of only three cryptographic schemes in the universe that we know to be secure.

It's a dirty little secret of the cryptographic world, but most of what we do ultimately rests on a wing and a prayer. We believe that our schemes are secure, mostly because we believe the underlying mathematical problems are intractable. (I.e., computationally secure.) But we don't know that-- no one has actually proved it. By and large, any cryptographic scheme in actual use could be broken tomorrow. In fact, it is conceivable that someone could figure out how to break all of them. (We call this the 'smart grad-student attack' and we try not to think about it very much.)

However, secret-sharing is different. Along with one-time pads and something called the Carter-Wegman hash functions, it is actually known to be unbreakable (i.e., information-theoretically secure). No matter what else falls, we will still have these three things. So, I always like to see these three algorithms used. It reassures me that even if the world changes tomorrow and computational security is revealed to be mirage, we will still have some small pieces of crypto left to play with.