|
Abstract:
Due to proliferation of online sensitive data about individuals and
organizations, concern about their privacy of has become a top priority. For
several formal definitions privacy, unfortunately, many negative results exist
about the feasibility of maintaining privacy of sensitive data in realistic
networked environments. We use communication-complexity based definitions
of privacy-aproximation ratio to
investigate the extent to which approximate privacy is achievable in two
standard problems: the 2nd-price
Vickrey auction and the millionaires problem of
Yao. We show for both problems, that even close approximations of perfect
privacy are impossible or infeasibly costly to achieve. By contrast, if the
values of the parties are drawn uniformly at random from 2k
values, then, for both problems, simple and natural communication protocols have
privacy-approximation ratios that are linear in k. We conjecture that the
uniform distribution over inputs is actually the worst case from the point of
view of the protocol designer and hence that this improved privacy-approximation
ratio is achievable for any probability distribution.
(Joint work with Aaron Jaggard and Michael Schapira.)
|
Joan Feigenbaum is the Grace Murray Hopper Professor of Computer Science at Yale
University. Her research interests include Internet algorithms, computational
complexity, security and privacy, and digital copyright. Between finishing her
Ph.D. at Stanford in 1986 and starting at Yale in 2000, she was with AT&T,
participating very broadly in the company's Information-Sciences research
agenda. At Yale, she has been a principal in several high-profile activities
funded by NSF and ONR. She currently serves on the Scientific Council of the
Web Sciences Research Institute, on the Executive-Committee of the ACM Special
Interest Group on Algorithms and Computational Theory, as Vice Chair of the ACM
Special Interest Group on Electronic Commerce (Sigecom), and as a
Program-Committee Member of the 2009 ACM Symposium on Principles of Distributed
Computing (PODC'09) and the Internet Monetization Track of the 2009 World Wide
Web conference (WWW'09). Professor Feigenbaum is a Fellow of the ACM.