|COMPUTER SCIENCE/DISCRETE MATH II|
|Topic:||Cryptography and the P vs NP Question|
|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.