Yevgeniy Vahlis

Two Is A Crowd? A Black-Box Separation Of One-Wayness and Security Under Correlated Inputs

Yevgeniy Vahlis

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.