  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.
