Ideally, one would want to base the security of standard cryptographic primitives (such as pseudorandom generators) on widely believed worst-case complexity assumptions like P does not equal NP. However, it is currently not known if this is possible, and several obstacles have been pointed out in the last few years. We propose to study relaxed definitions of cryptographic primitives where some of the honest parties may be given more resources than the adversary. While such definitions are useless for common cryptographic applications, they may shed more light on the relation between worst-case complexity, average-case complexity, and cryptography. As an initial step, we show that "quasi-one-way functions" may be realized from worst-case assumptions such as P does not equal NP, but standard techniques to turn these into "quasi-pseudorandom generators" fail in our setting. Joint work with Kunal Talwar and Andrew Wan.

Date:	10:40-11:20, Monday, March 23, 2009

Venue:	FIT Building 1-315, Tsinghua University

Title:	Quasi-cryptography

Speaker:	Andrej Bogdanov

Biography:	Andrej Bogdanov received his Ph.D. in Computer Science from University of California, Berkeley in 2005. He had been postdoctoral researcher in the school of MathematITCS Institute for Advanced Study in Princeton from 2005 to 2006, in DIMACS in Rutgers University from 2006 to 2007 and in ITCS of Tsinghua University from 2007 to 2008. Now he is an assistant professor in Department of Computer Science and Engineering of the Chinese University of Hong Kong.

Abstract:	Ideally, one would want to base the security of standard cryptographic primitives (such as pseudorandom generators) on widely believed worst-case complexity assumptions like P does not equal NP. However, it is currently not known if this is possible, and several obstacles have been pointed out in the last few years. We propose to study relaxed definitions of cryptographic primitives where some of the honest parties may be given more resources than the adversary. While such definitions are useless for common cryptographic applications, they may shed more light on the relation between worst-case complexity, average-case complexity, and cryptography. As an initial step, we show that "quasi-one-way functions" may be realized from worst-case assumptions such as P does not equal NP, but standard techniques to turn these into "quasi-pseudorandom generators" fail in our setting. Joint work with Kunal Talwar and Andrew Wan.