Date:  10:4011:20, Monday, March 23, 2009 
Venue:  FIT Building 1315, Tsinghua University 
Title:  Quasicryptography 
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 worstcase 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 worstcase complexity, averagecase complexity, and cryptography. As an initial step, we show that "quasioneway functions" may be realized from worstcase assumptions such as P does not equal NP, but standard techniques to turn these into "quasipseudorandom generators" fail in our setting.
Joint work with Kunal Talwar and Andrew Wan.
