PP-VCA: A Privacy-Preserving and Verifiable Combinatorial Auction Mechanism

Abstract

Combinatorial auctions can be employed in the fields such as spectrum auction, network routing, railroad segment, and energy auction, which allow multiple goods to be sold simultaneously and any combination of goods to be bid and the maximum sum of combinations of bidding prices to be calculated. However, in traditional combinatorial auction mechanisms, data concerning bidders’ price and bundle might reveal sensitive information, such as personal preference and competitive relation since the winner determination problem needs to be resolved in terms of sensitive data as above. In order to solve this issue, this paper exploits a privacy-preserving and verifiable combinatorial auction protocol (PP-VCA) to protect bidders’ privacy and ensure the correct auction price in a secure manner, in which we design a one-way and monotonically increasing function to protect a bidder’s bid to enable the auctioneer to pick out the largest bid without revealing any information about bids. Moreover, we design and employ three subprotocols, namely, privacy-preserving winner determination protocol, privacy-preserving scalar protocol, and privacy-preserving verifiable payment determination protocol, to implement the combinatorial auction with bidder privacy and payment verifiability. The results of comprehensive experimental evaluations indicate that our proposed scheme provides a better efficiency and flexibility to meet different types of data volume in terms of the number of goods and bidders.

This work is licensed under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

1. Introduction

1.1. Backgrounds

Combinatorial auctions allow multiple goods to be sold simultaneously and any combination of goods to be bid, which provides a vivid and wide auction application on the Internet with the online e-commerce enabling consumers to complete a variety of complex activities, such as bank account deposit withdrawal, commodity trading service, and transaction information inquiry [1]. The auction is gradually changing from traditional auction to electronic auction and becoming an important part of e-commerce. For example, spectrum [2, 3] and energy [4] can be auctioned through the networks. The electronic auction system generally consists of an auctioneer, several sellers, and bidders. The seller entrusts the auctioneer to arrange the auction, accept the bids, and declare the winner [6]. Combinatorial auction is an important part of electronic auction, which is more scalable and can adapt to more complex demands. In a single auctioneer combinatorial auction, the auctioneer sells multiple heterogeneous goods simultaneously and bidders bid on any combination of the goods (called bundle or set) instead of just ones [7], which have been researched extensively because of the generality and scalability of on-growing applications [8].

Privacy-preserving combinatorial auction protocols usually employ the cryptographic technique to protect bidders’ private information. When the auction terminates, only the auction outcomes, i.e., who are winners and the corresponding payments, are revealed. In the auction process, the losers’ bids and bundles are kept private since the auctioneers might use losers’ bids to maximize their revenues in future auctions [6]. For example, the average value of losers’ bids can motivate auctioneers to increase the starting price in future auction of similar goods. In addition, private information of bidders, such as bundle and bids, can be used to disclose personal preference and competitive relationship. In an auction system, there is serious competition between bidders, and this information is vital and needs to be protected.

1.2. Scenario and Application

Assume that an auctioneer publishes the information of some goods simultaneously on the Internet. Product numbers are labelled from #1 to #10. Every bidder chooses the sequence of the good number that he wants to own (i.e., bundle) and then provides the price that he is willing to pay (i.e., bid). The chosen list is described in Table 1.

Table 1

Scenario of combinatorial auction.

ID	Bundle	Bid	Bidding price
$$b_1$$	(#1, #7, #8)	10000	3333
$$b_2$$	(#2, #4, #10)	15000	5000
$$b_3$$	(#4, #7)	15500	7750
$$b_4$$	(#1, #5, #9, #10)	14500	3625
$$b_5$$	(#3, #6, #7, #9, #10)	17000	3400
$$b_6$$	(#2, #8, #9)	13000	4333
$$b_7$$	(#5, #9)	9000	4500
$$b_8$$	(#6, #8, #9)	14000	4667

Every bidder computes $\text{average}\text{value}=\text{Bid}/\mid \text{Bundle}\mid$, where $\mid \text{Bundle}\mid$ is the number of products in the bundle. The auctioneer picks out the largest average value 7750 and finds that #4 and #7 are still available, which means $b_3$ is the winner of the first round. In the second round, the auctioneer finds that ${b_2}^{\prime }$ average value is the largest. However, ${b_2}^{\prime }$ bundle contains one good that is already auctioned (#4), which means $b_2$ cannot be a winner. The auctioneer will choose all the winners in this way.

In private-preserving combinatorial auction, a crucial issue to be solved is how to pick out a set of disjoint goods under the price value of which is the maximized. Actually, this problem can be classified as an optimization problem. In [9], Zhang et al. proposes a privacy-preserving optimization for distributed fractional knapsack, which uses the greedy algorithm to find an optimal solution. Suzuki and Yokoo [10, 11] introduce dynamic programming to solve the winner determination problem on finding the shortest path of the directed graph [12]. However, the schemes in [10–12] may lead to a superpolynomial run time when the combinatorial auction parameters, i.e., the number of bidders and the number of goods, increase rapidly [13].

Threshold secret sharing schemes can also be used to solve the privacy-preserving problem in combinatorial auctions. For example, Kikuchi and Thorpe [14] proposed a privacy-preserving combinatorial auction protocol which employed a Shamir secret sharing scheme to share bids between multiple auctioneers, which allows any entity to detect misbehavior of bidders and auctioneers. Considering the high communication cost in [14], Hu et al. [15] provided an authentication property without increasing the communication cost in combinatorial auctions. Homomorphic encryption provides an available approach to protect each bidding value with a vector of ciphertext and then guarantees the auctioneer to figure out the maximum value securely [16–20]. In order to improve the performance, Xu et al. [21] give the comparison of different sorting algorithms and show that different sorting algorithms may have great effect on the performance of the protocol.

1.3. Organization

The remainder of this paper is organized as follows: We provide an overview of related work and background in Section 2. In Section 3, we introduce some terms used in the paper and provide the system framework, adversary model, and security requirement. In Section 4, we introduce the technology used in the paper. We provide our concrete scheme in Section 5 and give the security analysis in Section 6. The feature comparison and performance analysis are presented in Section 7. Finally, we draw our conclusion in Section 8.

2. Background and Related Work

2.1. Backgrounds of Combinatorial Auction

The traditional combinatorial auction includes one auctioneer and $N$ bidders, as shown in Figure 1. The auctioneer is responsible for arranging the auction, accepting the bids, and declaring the winner. This process consists of two steps. Firstly, the auctioneer will send the information of goods to be auctioned to $N$ bidders. Bidders give the sequence of goods that they want to obtain (called bundle) and quotation for bundle (called bid). The auctioneer selects the winner and announces the results according to some mechanism. Then, the auctioneer determines the price that the winner should pay. Notice that the winner’s bid and payment are not necessarily equal.

[figure omitted; refer to PDF]

When the auctioneer picks out the winners, the main goal is to maximize social welfare, which is the sum of the winners’ bids. In this process, we should ensure that no information about the others’ bundles and bids are released. Also, the winner’s payment determination should be verifiable [22].

In order to reduce the losses caused by collusion and cheating among bidders, the famous Generalized Vickrey Auction (GVA) strikes a balance between risk and profit, in which the GVA is a sealed bid auction where auction goods are sold to bidders at the second highest price, which guarantees the authenticity of the auction while maximizing the interests of the auctioneer and bidders. However, the implementation of GVA is NP-hard even under the assumption of single-minded bidders. Zhang et al. [23] investigated the impact on such mechanisms of replacing exact solutions by approximate ones and proposed a particular greedy optimization method, which could guarantee the truthfulness of the auction.

2.2. Related Work

Currently, there exist several approaches to achieve privacy-preserving secure combinatorial auction, such as dynamic programming, Shamir’s threshold secret sharing scheme, homomorphic encryption, and secure multiparty computation.

Sakurai et al. [24] and Sandholm [25] employed dynamic programming to combinatorial auction. However, with the increase of the number of bidders and goods, dynamic programming will lead to nonpolynomial computation cost. Kikuchi and Thorpe [14] proposed a privacy-preserving combinatorial auction using Shamir’s threshold secret sharing scheme, and through further improvements, Hu et al. [15] presented a method to reduce the communication cost and that could resist the collusion attack and passive attack.

Some combinatorial auction protocols are based on homomorphic encryption technique in ciphertext fields [16–20]. However, these protocols need a high computational cost. Palmer et al. [26] employed the technique of secure multiparty computation to implement privacy-preserving combinatorial auction, where the protocol is not scalable since the inputs of combinatorial auction cannot be predeterminated. In [9], Zhang et al. employed the inner product of matrix and cancellation with invertible matrix to achieve asymmetric scalar product preserving encryption. Instead of homomorphic encryption, Li et al. [27] used random noise to mask the bid values. By using a masking approach, the server only knows the noise, and the auctioneer only knows the auction results, which will decrease computational complexity in the combinatorial auction.

As an emerging decentralized security data management system, blockchain has gained much popularity recently and has been applied in electronic auction. As the participants in the conventional auction-based trading may collude or take selfish actions, [28] employed the Ethereum framework for trustless, secure, and distributed auctioning. [29] proposed a decentralized electricity transaction mode for microgrids based on blockchain and continuous double auction (CDA) mechanism, which could solve problems in traditional management, such as high operation cost and low transparency.

3. Model of Privacy-Preserving Combinatorial Auction

3.1. System Model

We first present our system model for privacy-preserving combinatorial auction, in which there are three kinds of participants, i.e., an auctioneer who wants to sell several products $G=g_1,\cdots ,g_m$ simultaneously, $N$ bidders $B=B_1,\cdots ,B_n$ who want to succeed in the auction, and a crypto service provider who is responsible for key distribution and collaborative computation. In the privacy-preserving combinatorial auction model, we suppose that there is a classical channel between any two participants. The symbols in this paper are shown in Table 2.

Table 2

Main notations.

Notations	Terms
$i$th bidder	$$B_i$$
$m$th goods	$$g_m$$
${B_i}^{\text{’}}$s bundle	$$S_i$$
${B_i}^{\text{’}}$s bid	$$b_i$$
$$k$$	System security parameter
($\mathbb{G},p,g$)	Finite group $\mathbb{G}$ of order $p$, generator $g$
${\mathcal{Z}}_p$, ${\mathcal{Z}}_p^{\ast }$	${\mathcal{Z}}_p=0,1,\cdots ,p-1$, ${\mathcal{Z}}_p^{\ast }={\mathcal{Z}}_p\backslash 0$
$$m$$	Ciphertext of message $m$
$$\mathcal{A}$$	Adversary algorithm
$$\text{negl}k$$	Negligible function in parameter $k$
$$\text{CSP}$$	Crypto service provider
$$\text{AUCT}$$	Auctioneer

As shown in Figure 2, during the auction, every bidder $B_i$ has his own bundle $S_i\in G$ that he expects to obtain and his bid $b_i$, i.e., the price $B_i$ he is willing to pay on his bundle $S_i$. During the auction, one product can only be auctioned to one bidder, and the auctioneer’s goal is to maximize social welfare. So, the winners are chosen by the auctioneer as follows:$$\begin{array}{}\text{(1)}& W=B_i\in B\mid \text{argmax}\sum _{B_i}{b}_i{S}_i\text{s}.\text{t}.\bigcap _{B_i}{S}_i=\varnothing ,\end{array}$$i.e., a set of conflict-free bidders whose total bid is maximized, and $A={\cup }_{B_i\in W}{S}_i$ is winners’ bundle. After that, the auctioneer will determine the price that the winner should pay according to some mechanism. Besides, CSP will generate a blind signature for bidders’ bid and bundle, which will be used to verify the correctness of the result later.

[figure omitted; refer to PDF]

By Figures 4 and 5, it is easy to see that the auctioneer’s computation overhead will increase logarithmically with the increasing of the value of max bid and will increase linearly with the increasing of the amount of total bidders and total goods. Firstly, the larger the value of max bid, the larger the average value ${\phi }_i$. So, $f{\phi }_i$ obtained by one-way and monotonically increasing function is larger, which will increase the auctioneer’s computation overhead to select the largest $f{\phi }_i$. Secondly, the increase of the amount of total bidders and total goods will inevitably increase the auctioneer’s computation overhead. Figures 5 and 6 demonstrate that, in our protocol, the auctioneer’s computation overhead grows with small constant factors linearly.

Meanwhile, Figures 4 and 5 indicate that the value of max bid and the amount of total bidders do not have a big impact on bidder’s computation overhead, since each bidder calculates the average values ${\phi }_i$, $f{\phi }_i$ and encrypts the bundle locally. The increase of the number of total goods will increase the bidder’s encryption time $T_{\text{enc}}$, but Figure 6 illustrates that the bidder’s computation overhead grows with small constant factors linearly as well.

7.3. Comparison with Peer Works

We compare scalability of our PP-VCA protocol with peer works in Table 3. Considering the actual running time of our protocol with peer works, we notice that our protocol’s run time increases logarithmically with the increasing of the max bid and increases linearly with the increasing of total bidders and total goods. We improve the performance to a linear growth and logarithmic growth, which illustrates that our PP-VCA protocol provides a better scalability in the practice.

Table 3

Comparison of computation overhead.

Variable	Our PP-VCA	[26]	[10]	[11]	[16]
Max bid	Logarithmic	Logarithmic	Linear	Linear	Linear
$\#$ of bidders	Linear	Linear	Linear	Linear	Linear
$\#$ of goods	Linear	Exponential	Logarithmic	Logarithmic	Logarithmic

8. Conclusion

In this work, we proposed an effective, scalable, and flexible privacy-preserving combinatorial auction scheme to protect bidder’s privacy and ensure the correctness and verifiability of the bidding price. We employed a monotonically increasing one-way function to ensure the auctioneer to pick out the largest bid without disclosing the bidding price. In addition, we put forward a privacy-preserving verifiable payment determination protocol to confirm the payment that the winner should pay. Furthermore, we used a blind signature scheme to succeed in allowing all bidders to verify the payment without knowing the real sensitive bidding price. Performance analysis and experimental results indicate that our scheme provides a better performance and scalability in combinatorial auction systems.

Additional Points

This is the extended and full version of [5].

Acknowledgments

This work is supported by the National Natural Science Foundation of China under grant 62072134 and 61672010, the Open Research Project of State Key Laboratory of Cryptology of China, the Key projects of Guangxi Natural Science Foundation under grant 2019JJD170020, and the Open Fund Program for State Key Laboratory of Information Security of China under Grant 2020-MS-05.

References

[1] M. Zhang, Y. Yao, B. Li, C. Tang, "Accountable mobile e-commerce scheme in intelligent cloud system transactions," Journal of Ambient Intelligence and Humanized Computing, vol. 9 no. 6, pp. 1889-1899, DOI: 10.1007/s12652-017-0672-4, 2018.

[2] Y. Chen, Z. Ma, Q. Wang, J. Huang, X. Tian, Q. Zhang, "Privacy-preserving spectrum auction design: challenges, solutions, and research directions," IEEE Wireless Communications, vol. 5, pp. 142-150, 2019.

[3] Q. Wang, J. Huang, Y. Chen, X. Tian, Q. Zhang, "Privacy-preserving and truthful double auction for heterogeneous spectrum," IEEE/ACM Transactions on Networking, vol. 27 no. 2, pp. 848-861, DOI: 10.1109/TNET.2019.2903879, 2019.

[4] J. Lin, M. Pipattanasomporn, S. Rahman, "Comparative analysis of auction mechanisms and bidding strategies for P2P solar transactive energy markets," Applied energy, vol. 255,DOI: 10.1016/j.apenergy.2019.113687, 2019.

[5] M. Zhang, B. Zhou, A verifiable combinatorial auction scheme with bidder's privacy protection, 2020.

[6] R. Alvare, M. Nojoumian, "Comprehensive survey on privacy-preserving protocols for sealed-bid auctions," Computers & Security, vol. 88, 2020.

[7] T. Jung, X. Li, "Enabling privacy-preserving auctions in big data," Journal of Parallel and auctioned Computing, vol. 73 no. 4, pp. 495-508, 2013.

[8] M. Zhou, C. Niu, Z. Zheng, F. Wu, G. Chen, "An efficient, privacy-preserving, and verifiable online auction mechanism for Ad exchanges," Globecom, IEEE Global Communications Conference, .

[9] M. Zhang, Y. Chen, Z. Xia, J. Du, W. Susilo, "PPO-DFK: a privacy-preserving optimization of distributed fractional knapsack with application in secure footballer configurations," IEEE Systems Journal, vol. 2020,DOI: 10.1109/JSYST.2020.2991928, 2020.

[10] K. Suzuki, M. Yokoo, "Secure combinatorial auctions by dynamic programming with polynomial secret sharing," Lecture Notes in Computer Sciene, vol 2357, 2002.

[11] M. Yokoo, K. Suzuki, "Secure multi-agent dynamic programming based on homomorphic encryption and its application to combinatorial auctions," Proceedings of the first international joint conference on Autonomous agents and multiagent systems, pp. 112-119, 2002.

[12] D. C. Parkes, M. O. Rabin, C. Thorpe, "Cryptographic combinatorial clock-proxy auctions," Lecture Notes in Computer Science, vol 5628, .

[13] M. Zhang, S. Zhang, L. Harn, "An efficient and adaptive data-hiding scheme based on secure random matrix," PLOS One, vol. 14 no. 10, article e0222892,DOI: 10.1371/journal.pone.0222892, 2019.

[14] H. Kikuchi, C. Thorpe, (m+1)st-prie auction protocol, vol 2339, 2002.

[15] C. Hu, R. Li, B. Mei, W. Li, A. Alrawais, R. F. Bie, "Privacy-preserving combinatorial auction without an auctioneer," EURASIP Journal on Wireless Communications and Networking, vol. 2018 no. 1, 2018.

[16] M. Pan, X. Zhu, Y. Fang, "Using homomorphic encryption to secure the combinatorial spectrum auction without the trustworthy auctioneer," Wireless Networks, vol. 18 no. 2, pp. 113-128, DOI: 10.1007/s11276-011-0390-3, 2012.

[17] M. Pan, J. Sun, Y. Fang, "Purging the back-room dealing: secure spectrum auction leveraging Paillie cryptosystem," IEEE Journal on Selected Areas in Communications, vol. 29 no. 4, pp. 866-876, 2011.

[18] M. Larson, R. Li, C. Hu, W. Li, X. Cheng, R. Bie, "A bidder-oriented privacy-preserving vcg auction scheme," International Conference on Wireless Algorithms, Systems, and Applications, pp. 284-294, .

[19] W. Gao, W. Yu, F. Liang, W. G. Hatcher, C. Lu, "Privacy-preserving auction for big data trading using homomorphic encryption," IEEE Transactions on Network Science Engineering, vol. 7, 2018.

[20] K. Xing, C. Hu, J. Yu, X. Cheng, F. Zhang, "Mutual privacy preserving $k$ -means clustering in social participatory sensing," IEEE Transactions on Industrial Informatics, vol. 13 no. 4, pp. 2066-2076, DOI: 10.1109/TII.2017.2695487, 2017.

[21] Y. Xu, Z. Chen, H. Zhong, Privacy-preserving double auction mechanism based on homomorphic encryption and sorting networks, 2019.

[22] M. Zhang, Y. Chen, J. Huang, "SE-PPFM: a searchable encryption scheme supporting privacy-preserving fuzzy multi-keyword in cloud systems," IEEE System Journal, vol. 2020,DOI: 10.1109/JSYST.2020.2997932, 2020.

[23] M. Zhang, Y. Chen, W. Susilo, "PPO-CPQ: a privacy-preserving optimization of clinical pathway query for e-healthcare systems," IEEE Internet of Things Journal, vol. 2020,DOI: 10.1109/JIOT.2020.3007518, 2020.

[24] Y. Sakurai, M. Yokoo, K. Kamei, An efficient approximate algorithm for winner determination in combinatorial auctions, 2001.

[25] T. Sandholm, "Algorithm for optimal winner determination in combinatorial auctions," Artificial Intelligence, vol. 135 no. 1-2,DOI: 10.1016/S0004-3702(01)00159-X, 2002.

[26] B. Palmer, K. Bubendorfer, I. Welch, Development and evaluation of a secure, privacy preserving combinatorial auction, 2011.

[27] W. Li, M. Larson, C. Hu, R. Li, X. Cheng, R. Bie, "Secure multi-unit sealed first-price auction mechanisms," Security Communication Networks, vol. 9 no. 16, pp. 3833-3843, DOI: 10.1002/sec.1522, 2016.

[28] T. Chen, A. Khan, G. Zheng, S. Lambotharan, "Blockchain secured auction-based user fffloading in heterogeneous wireless networks," IEEE Wireless Communication Letters,DOI: 10.1109/LWC.2020.2982634,2020, 2020.

[29] W. Jian, W. Qianggang, Z. Niancheng, "A novel electricity transaction mode of microgrids based on blockchain and continuous double auction," Energies, vol. 10 no. 12, 2017.

[30] Y. Zheng, R. Lu, J. Shao, "Achieving efficient and privacy-preserving k-NN query for outsourced eHealthcare data," Journal of Medical Systems, vol. 43 no. 5,DOI: 10.1007/s10916-019-1229-1, 2019.

[31] Y. Qi, B. Yang, Y. Yu, "Partial blind signatures based on Nyberg-Rueppel signature," Application Research Of Computers, vol. 1, pp. 251-253, 2008.

[32] W. Shi, J. Wang, J. Zhu, Y. Wang, D. Choi, "A novel privacy-preserving multi-attribute reverse auction scheme with bidder anonymity using multi-server homomorphic computation," Intelligent Automation Soft Computing, vol. 25 no. 1, pp. 171-181, 2019.