SPEAKER: Yevgeniy Vahlis TITLE: Two Is A Crowd? A Black-Box Separation Of One-Wayness and Security Under Correlated Inputs Authors: Yevgeniy Vahlis ABSTRACT: A family of trapdoor functions is one-way under correlated inputs if no efficient adversary can invert it even when given the value of the function on multiple correlated inputs. This powerful primitive was introduced at TCC 2009 by Rosen and Segev, who use it in an elegant black box construction of a chosen ciphertext secure public key encryption. In this talk I will present a proof that there is no black box construction of correlation secure injective trapdoor functions from classic trapdoor permutations, even if the latter is assumed to be one-way for inputs from a high entropy, rather than uniform distribution. Our negative result holds for all input distributions where each $x_{i}$ is determined by the remaining $n-1$ coordinates. The techniques we employ for proving lower bounds about trapdoor permutations were subsequently used to obtain other black box separations. I will describe some of these results, if time permits. LINKS: http://www.cs.toronto.edu/~evahlis/cor_prod_imp_final_pre3.pdf