Friday, November 14th, 2008
| 11:30 - 12:30 | INVITED TALK "Beyond Complexity-Based Cryptography -- An Overview" Serge Fehr |
| ABSTRACT | |
| The security of most of the cryptographic schemes used in practice relies on unproven complexity assumptions (like the assumed hardness of factoring large numbers) in combination with the assumption that an attacker does not have overwhelming computing power. This approach leads to very practical schemes but obviously has its downsides. Not only might the underlying complexity assumption be broken from one day to another (e.g. by an efficient factoring algorithm being discovered), but also with the increasing advances in computer technology it is likely that a ciphertext that cannot be broken today will eventually reveal the message it is supposed to hide once computer technology has advanced sufficiently. Furthermore, a quantum computer would make most of the commonly used cryptographic schemes insecure. This clearly poses a serious threat to long-term highly-sensitive data. | |
| In this talk I give an overview of the approaches that have been suggested to design cryptographic schemes that offer information-theoretic security, which means they withstand even computationally unbounded attacks. Unfortunately, this high level of security does not come "for free", but can only be obtained in certain models which pose some new restriction on the attacker. I explain the four most prominent models considered so far: the noisy-information model, the bounded-storage model, the quantum model, and the bounded-quantum-storage model. For each model, I discuss the (im)possibility results for key-agreement (which then implies encryption) and for 2-party computation (on the example of oblivious transfer). | |