CAREER: Strengthening Cryptography by Reducing Assumptions about the Adversary

Columbia University, New York NY

Investigators

Abstract

Cryptographic security models are defined in terms of the capabilities of the adversary, including computational limitations and what access he is allowed to the system. The security of protocols is then proven with respect to such adversaries, in a well-defined, rigorous and quantifiable way (typically relying on some computational hardness assumption). However, traditional models are often not adequate, especially in light of the widespread use of cryptography today. Since we cannot predict everything the adversary can do a priori, it is important to reduce the assumptions about the adversary's (in)capabilities as much as possible. Here, we propose to expand the traditional cryptographic foundations so as to withstand attacks by stronger, more realistic adversaries. In particular, we challenge the classical assumption that the adversary has no access whatsoever to the legitimate parties' secret keys. We will study the strongest existing models, design new models, develop protocols, and explore the limits of what is possible to achieve, for the following types of attacks: Chosen ciphertext attack: can we achieve CCA security from any scheme satisfying only standard semantic security? What are the relations among the different notions of security for public key encryption? Tampering attacks: can we achieve security for various cryptographic applications when the adversary can tamper with the secret key, e.g. through fault attacks? Key exposure attacks: can we achieve security when the adversary can obtain the secret key? how to design and instantiate key evolving schemes with optimal security and efficiency to limit damage caused by key exposure? We will seek both positive and negative results in the above areas, in order to better understand the relevant implications and requirements, and to obtain optimal solutions.