Computer Science – Cryptography and Security
Scientific paper
2009-10-29
Computer Science
Cryptography and Security
33 pages, seven figures, two tables. Changes in version 2 include an expanded discussion of other approaches to approximate pr
Scientific paper
Increasing use of computers and networks in business, government, recreation, and almost all aspects of daily life has led to a proliferation of online sensitive data about individuals and organizations. Consequently, concern about the privacy of these data has become a top priority, particularly those data that are created and used in electronic commerce. There have been many formulations of privacy and, unfortunately, many negative results about the feasibility of maintaining privacy of sensitive data in realistic networked environments. We formulate communication-complexity-based definitions, both worst-case and average-case, of a problem's privacy-approximation ratio. We use our definitions to investigate the extent to which approximate privacy is achievable in two standard problems: the second-price Vickrey auction and the millionaires problem of Yao. For both the second-price Vickrey auction and the millionaires problem, we show that not only is perfect privacy impossible or infeasibly costly to achieve, but even close approximations of perfect privacy suffer from the same lower bounds. By contrast, we show that, if the values of the parties are drawn uniformly at random from {0,...,2^k-1}, then, for both problems, simple and natural communication protocols have privacy-approximation ratios that are linear in k (i.e., logarithmic in the size of the space of possible inputs). We conjecture that this improved privacy-approximation ratio is achievable for any probability distribution.
Feigenbaum Joan
Jaggard Aaron D.
Schapira Michael
No associations
LandOfFree
Approximate Privacy: Foundations and Quantification does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Approximate Privacy: Foundations and Quantification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate Privacy: Foundations and Quantification will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-405542