Enabling Privacy-preserving Auctions in Big Data
This work addresses privacy and efficiency issues in auction mechanisms for big data applications, though it appears incremental as it builds on existing methods with specific improvements.
The paper tackles the problem of designing privacy-preserving auctions for big data by addressing challenges like variety, velocity, volume, and veracity, resulting in improved asymptotic performance from exponential to linear and linear to logarithmic growth in overhead.
We study how to enable auctions in the big data context to solve many upcoming data-based decision problems in the near future. We consider the characteristics of the big data including, but not limited to, velocity, volume, variety, and veracity, and we believe any auction mechanism design in the future should take the following factors into consideration: 1) generality (variety); 2) efficiency and scalability (velocity and volume); 3) truthfulness and verifiability (veracity). In this paper, we propose a privacy-preserving construction for auction mechanism design in the big data, which prevents adversaries from learning unnecessary information except those implied in the valid output of the auction. More specifically, we considered one of the most general form of the auction (to deal with the variety), and greatly improved the the efficiency and scalability by approximating the NP-hard problems and avoiding the design based on garbled circuits (to deal with velocity and volume), and finally prevented stakeholders from lying to each other for their own benefit (to deal with the veracity). We achieve these by introducing a novel privacy-preserving winner determination algorithm and a novel payment mechanism. Additionally, we further employ a blind signature scheme as a building block to let bidders verify the authenticity of their payment reported by the auctioneer. The comparison with peer work shows that we improve the asymptotic performance of peer works' overhead from the exponential growth to a linear growth and from linear growth to a logarithmic growth, which greatly improves the scalability.