Grand Challenges for the Foundations of Cryptography

Boaz Barak

Cryptography or secret writing seems to have almost as long a history as writing itself. Throughout this history many "unbreakable codes" were announced, only to be later broken. This may breed a healthy skepticism that there is no such thing as an unbreakable code - if you're smart you can come up with a code that will take a few years to break, and hopefully by the time it is broken you will come up with a new code.

Nonetheless in the 1970's we saw that the skeptics may be wrong. We saw the construction of new schemes (i.e., Diffie-Hellman and RSA) that instead of being based on obscure and complicated constructions (e.g., think the "Enigma") were actually based on simple number theoretic problems. In the time passed, these schemes and the number theoretic problems underlying them have received more attention and attacks than any of the schemes in previous history and they still remain unbroken. Even more amazingly, these schemes were not just more secure but actually had the property that they allow secret communication without shared secret information (so called "public key cryptography") - in the thousands of years of practicing crypto people never imagined that they could have such a property and still maintain security.

The big question for crypto is the following: are these schemes (or similar others) unbreakable or are they simply yet unbroken?

We now have the language to formulate this question as a precise conjecture that can be proven using mathematical tools. Thus the first grand challenge is to come up with an encryption scheme (even a private key one) that is proven to be unbreakable within any feasible amount of time.

This is indeed a grand challenge, as in particular showing such a scheme will require separating NP from P (and to be on the safe side, even from BQ-SUBEXP).

A second question is about public key encryption schemes. Currently we have wonderful theory and applications using the assumed hardness of very few particular problems. It's not just public key encryption but in fact in principle essentially any cryptographic task imaginable can be performed in an unbreakable way (if these problems are really hard). The catch is that we're not sure whether the same structure that these specific computational problems possess that makes them so useful, can not be used to actually solve the problems efficiently and break the schemes. In fact, there is already a quantum polynomial algorithm for the factoring and discrete log problems, and we don't have good evidence that there is no such classical (i.e., running on standard "non-quantum" computers) algorithm.

This raises a very disturbing possibility: could it be that all this beautiful concept of public key cryptography is just a "fluke": something that existed in the short window of opportunity between the discovery of these schemes and the discovery of the algorithms breaking the underlying problems? The way to rule out this possibility would be to give a generic construction of a public key encryption scheme from a private key scheme. This is the second grand challenge suggested.

If such a generic construction is found, then even if a polynomial-time factoring algorithm is found (and some would perhaps rightly say that we already found one), we wouldn't lose public key cryptography. Rather it would turn out that the factoring problem was a "crutch" that helped us develop this concept but is now no longer needed.