Cryptography and the P vs NP Question

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Cryptography and the P vs NP Question
Speaker:Andrej Bogdanov
Affiliation:IAS
Date:Tuesday, January 31
Time/Room:10:30am - 12:30pm/S-101

A fundamental question in cryptography is whether the existence of hard on average problems can be based solely on the assumption that P not equal to NP (more precisely, NP not in BPP). The commonly held belief that average-case hardness requires stronger assumptions than NP hardness was challenged in the mid 1990s by the construction of cryptosystems whose security follows from a worst-case intractability assumption. Despite many efforts, however, it is not known whether the assumption P not equal to NP is necessary for cryptography. In this talk I will review some of the contrasting evidence with respect to this question.