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.