In complexity theory based cryptography, the goal is to devise cryptographic schemes which can be proven secure (under some well defined notion of security) using some assumption about the intractability of a computational problem. Usually this is done via a reduction that given an hypothetical attack to the cryptographic scheme builds an algorithm to solve the assumed intractable problem. The ultimate goal is to find the most efficient scheme, which satisfies a very strong definition of security, under the weakest possible computational assumption. In the past 25 years, complexity theory based cryptography has produced several impressive results, at least under the two last measures: very strong notions of security for tasks like encryption, signatures, psedorandom generation etc. can be achieved under minimal computational assumptions, even though often (but not always) by schemes that are too inefficient to be used in practice. Bridging this gap between “provable security” and “efficiency” has been a main focus of more recent cryptographic research. In the first part of the talk I will survey several results that point out that if we want to prove security under minimal computational assumptions (such as the existence of one-way functions) then inefficiency might be intrinsically unavoidable. These “lower bounds” hold for a large class of constructions and proof techniques. The second part of the talk will survey alternative approaches to achieve efficient and yet provably secure cryptographic algorithms.
Speaker Biography
Rosario Gennaro received his Ph.D. in Electrical Engineering and Computer Science from the Massachusetts Institute of Technology in 1996.