Theoretical Cryptography

Cryptographers are always looking over their shoulders, sure that no matter how clever the puzzles they have designed, someone else is surely working to break them and may eventually succeed.

Microsoft Research cryptographer Ramarathnam Venkatesan, Venkie to his friends, sees cryptography as the art of posing puzzles no one can solve for the next 20 years. Venkie trained as a mathematician in probability theory and complexity theory; hes interested in finding a way to measure the difficulty of problems, solved and unsolved.

One thing he knows is that no one has ever proved that a given problem is unsolvable, or a given cryptosystem unbreakable. The heart of cryptography is the one-way function where by a series of mathematical exercises the product Y is derived from X, but the problem cant be worked backward to discover what X is from Y.

Cryptographers have designed some pretty good one-way functions the Rivest-Shamir-Adleman public key encryption algorithm, built on the tremendous difficulty of factoring large integers, is one that people have bet a lot of money on. So far, it has resisted all efforts to break it through sheer computational power.

But every cryptographer knows theres no guarantee that some smart person wont figure out a formula that allows them to work backward from Y to get X, to work backward from the public key to get the private one. All the algorithms we think are one way, could be broken. Venkie says.

Venkie and his colleagues Peter Montgomery, Kristin Lauter and Dan Simon assume that, someday, RSA may be broken. When that day comes, the world will need a new one-way function to replace it. We religiously believe that a true one-way function exists, says Venkie. We pray to God daily that a one-way function exists, because without one there is no cryptography. Digital signatures, stream ciphers, block ciphers, message authentication, all depend on the existence of a one-way function.

So whats he got up his sleeve? I have one that may work, he says. It may be ready in one or two years.