2009/10/29 by Joan Feigenbaum, Aaron D. Jaggard, Feigenbaum, Joan +3
Computer Science · #Computer Science and Game Theory (cs.GT) #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Internet Traffic Analysis and Secure E-voting #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.0910.5714
openalex publication_date 2009/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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,...,2k-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.