Seminars‎ > ‎

Some impossibility results for secure sampling

Prof. Vinod Prabhakaran


Time: 2 PM
Tesla room 53-125, ENG.IV


The goal of secure computation is for nodes in a network to compute and output (potentially randomized) functions of their inputs in such a way that subsets of nodes may not infer anything more about other nodes' inputs and outputs than what their own inputs and outputs reveal. Such problems arise in a variety of settings such as privacy-preserving data mining, online auctions, games etc. 

A special class of such problems, which includes the secret key agreement problem, is secure sampling where the functions are randomized and do not take inputs. It is known that, in general, information theoretically secure sampling requires stochastic resources like noisy channels or distributed sources. The question of how to perform information theoretically secure sampling efficiently (in terms of stochastic resources consumed) remains open in general. In this talk, we will present some impossibility results for the two user setting and its generalization to the multiple user case. The key tool will be a family of functions of jointly distributed random variables whose members possess a monotonicity property for secure protocols. 

Joint work with Manoj Prabhakaran, UIUC.