Summary | Rationale | Powerpoint
| JPG Slide | JPG Image
| Credits | Comments
| All Nuggets
Security with Certainty
A future algorithmic breakthrough could render insecure all electronic commerce protocols currently in use. However, theoretical computer scientists expect to remove this threat one day --- by designing protocols that have unconditional proofs of security.
Summary
Modern research in cryptography has transformed a significant portion of computer security from an art into a science. Instead of merely hoping that a clever adversary will not find a way to break the system, we can now prove the security of cryptographic protocols (encryption, digital signatures, etc.) on precise computational conjectures. For example, we can construct algorithms for encrypting messages so that it is computationally infeasible for anyone other than the intended recipient to learn anything about the message from its encryption, under the assumption that there are no fast algorithms for factoring large integers.
However, these conjectures can turn out to be false, as was discovered in 2004 for the widely used hash function MD5, which had been conjectured to be "collision-resistant" (i.e. it should be infeasible to find two inputs that hash to the same value). If a similar discovery were made in the future and kept secret, devastating damage could be inflicted on the electronic economy and cyberinfrastructure before the vulnerability is noticed. Thus, an important research challenge is to eliminate the need for conjectures in cryptography. Achieving this goal will require major advances in theoretical computer science, including resolving the famous P vs. NP question. Along the way, researchers continue to improve our understanding of the conjectures on which cryptography is based, thereby putting computer security on firmer foundations.
Rationale
Most electronic transactions on the Internet are protected by cryptography, which is the subfield of theoretical computer science that develops protocols for communication and computation that maintain secrecy and correctness in the face of adversarial attacks. For example, an encryption algorithm aims to encode data in such a way that only the intended recipient (in possession of a "decryption key") can recover the data, but an adversary
listening in learns nothing about the data from seeing only its encoded form. Encryption has the longest history of cryptographic concepts (dating at least back to the time of Caesar), but modern cryptography now includes providing security for a vast array of much more complex tasks than communication (such as auctions, datamining, voting, and electronic cash).
Historically, the security of encryption was largely a battle of wits between the designers and the attackers. A scheme might last a few years, until a clever attacker came along and found a way to break it, after which a new scheme would be designed to prevent that particular attack (but with no guarantee of security against future attacks). It was not until the development of modern theoretical computer science (TCS) in the 1970's that it finally became conceivable to escape this cycle of attacks and countermeasures. TCS demonstrated that there are computational problems that are inherently intractable --- they require inordinate computational resources to solve, no matter how sophisticated or clever an algorithm is used. Thus, we could try to design encryption algorithms such that "breaking" the code could be mathematically proven to be one of these computationally intractable problems.
Cryptography was enormously successful in this effort during the 80's and 90's, providing not only encryption algorithms but protocols achieving goals that had not even been imagined before (public-key encryption, privacy-preserving datamining, secure multiparty
computation, zero-knowledge proofs). However, these protocols were not proven
to be secure unconditionally, but rather it was shown that breaking the protocols is as hard as solving some computational problem that is conjectured to be intractable (such
as factoring large integers). Thus, there is still the possibility that some of these conjectures will turn out to be incorrect and an attacker will be able to break the protocols that protect our cyberinfrastructure.
Thus, a grand challenge for cryptography is to design protocols that can be proven secure without relying on conjectures. This is indeed a lofty goal, because proving the security of cryptographic protocols (in standard communication settings) requires resolving the famous "P vs. NP Question," which is the foremost open problem of theoretical computer science. Providing "Security with Certainty" as described here is but one of many reasons that P vs. NP Question is so important, and will continue to receive substantial effort by researchers in the decades ahead.
Along the way, there are numerous interim goals that theoretical computer scientists are continuing to make progress on and can increase society's confidence in the security of the cryptography we use every day. Below are some examples.
- As mentioned above, resolving the P vs. NP question (specifically proving NP != P) is necessary for proving security, but it is not known to be sufficient and thus cryptographers currently need to rely on assumptions that are stronger than NP != P. An important goal is to understand whether we can build cryptographic protocols whose security relies only on the answer to the P vs. NP question.
- Some cryptographic primitives seem to require stronger conjectures than other ones. For example, "public-key cryptography," which enables secure communication between parties who have never met before, seems to require intractable problems with a lot of structure, for which there are relatively few candidates (such as factoring large integers). But traditional "private-key cryptography," for communication between parties who share a secret key in advance, does not require this and can be based on any "one-way function" (a function that is easy to compute but hard to invert), for which there are many candidates. Can this gap be closed? More generally, we should try to base cryptographic protocols on assumptions that are as general as possible, so as to maximize the number of alternative instantiations if some are broken.
- Some protocols can only be analyzed when certain components of the protocol are treated in an idealized way. For instance, cryptographic hash functions such as SHA-256 are often assumed to behave as a so-called "random oracle" would. These idealizations leave gaps in our understanding of how security can arise computationally. At the same time, intriguingly few attacks are known against real-world systems that are analyzed with such idealizations. Thus, it is important to try to both eliminate the need for such idealizations, while at the same time trying to gain a better understanding for why these idealized analyses often seem to be resilient to attack.
- Another concern with the "structured" problems currently used in public-key cryptography is that many of these would be easy to break if scalable "quantum computers" can be built. Thus, another goal is to find more candidates for public-key cryptography that withstand quantum attacks.
- There are currently two general flavors of building blocks used to build cryptographic protocols. There are mathematically "natural" problems, such as factoring large integers, which have been well-studied by computer scientists and mathematicians for many years, giving us significant confidence in their intractability. On the other hand, there are "man-made" primitives, such as the "block ciphers" DES and AES and the "hash functions" MD5 and SHA-1, which result in extremely fast cryptography but for which we have much less understanding of their security. Can we achieve the best of both worlds, and obtain very fast cryptography from natural computational problems?
- Can we get a better understanding of the relationship between the various computational problems we use to build cryptographic protocols? For example, the Factoring problem and Discrete Logarithm problem seem to have a "hidden connection" that we do not yet understand. We have no results showing that the computational difficulties of these two problems are related, yet progress on one seems to always be accompanied by similar progress on the other. Uncovering the hidden connection at work here would likely have significant consequences for both cryptography and pure mathematics.
Contributors and Credits
Boaz Barak, Cynthia Dwork, Dick Lipton, Kristin Rozier, Amit Sahai, Salil Vadhan
Image Ideas
a safe or a lock come to mind, but perhaps these are overused for cryptography - definitely open to other suggestions. Nevertheless here are some images I had lying around:
Comments
- to give feedback on this nugget, just add another bullet to this list
- Such protocols may have a less impressive utility than, say, RSA. I think, the efforts to lessen dependence on assumptions may be broadened to include protocols that depend on less specific assumptions, such as, e.g., the use of an arbitrary one-way functions without additional properties. -Leonid Levin.
- Indeed, moving from specific to general assumptions is one of the "intermediate steps" I planned to describe in the rationale (cf. "do public-key crypto from OWF"). Also, to clarify - in this nugget I am *not* talking about alternative models (like the bounded-storage model) where unconditional security is already possible, but rather standard complexity-based crypto. Thus, this nugget is a simply another way of stating the grand (long-term) challenge "prove the existence of one-way functions". - Salil
- Edited nugget based on comments from Kristin, and added Rationale. - Salil
- In the summary, I think "It is plausible..." is too weak; suggest changing to "Achieving this goal will require..."; in the rationale, I wonder if a couple of the bullets can be combined and/or their relation clarified by having (perhaps not completely rigorous) ordered lists of assumptions (ordered by strength) and cryptographic tasks (ordered similarly). - Tim
- I like this nugget. A minor correction: Caeser->Caesar. --Luis.
- Thanks, Tim and Luis, I made the concrete edits you suggested, but I need to think some more about a good way to clarify/combine the bullets. - Salil
- Note from designer Elaine Park: This one is certainly easy to explain, as these ideas go. Just a heavy duty safe with extra protection and a solid looking military font to dress it up.
- Added a bullet point in the rationale about random oracles. Tim, I think there might be just too many different assumptions and cryptographic tasks (even central ones), and their relationship (in terms of strength) is just too complex... - Amit
- Can the tagline be shortened a bit and be put in the form of a question to indicate that there are problems to be solved. -- Richard
- Breakout group decided to keep tagline as is (unless someone offers a specific more compelling alternative), but if there's time later, we may try to shorten the summary (also suggested by Richard). - Salil
