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

Authors: Mingwu Zhang; Bingruolan Zhou
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## 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 aprivacy-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.


---

## Body

## 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 Table1.Table 1
Scenario of combinatorial auction.
IDBundleBidBidding priceb1(#1, #7, #8)100003333b2(#2, #4, #10)150005000b3(#4, #7)155007750b4(#1, #5, #9, #10)145003625b5(#3, #6, #7, #9, #10)170003400b6(#2, #8, #9)130004333b7(#5, #9)90004500b8(#6, #8, #9)140004667Every bidder computesaveragevalue=Bid/∣Bundle∣, where ∣Bundle∣ 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 b3 is the winner of the first round. In the second round, the auctioneer finds that b2′ average value is the largest. However, b2′ bundle contains one good that is already auctioned (#4), which means b2 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 Section2. 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.


## 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 Table1.Table 1
Scenario of combinatorial auction.
IDBundleBidBidding priceb1(#1, #7, #8)100003333b2(#2, #4, #10)150005000b3(#4, #7)155007750b4(#1, #5, #9, #10)145003625b5(#3, #6, #7, #9, #10)170003400b6(#2, #8, #9)130004333b7(#5, #9)90004500b8(#6, #8, #9)140004667Every bidder computesaveragevalue=Bid/∣Bundle∣, where ∣Bundle∣ 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 b3 is the winner of the first round. In the second round, the auctioneer finds that b2′ average value is the largest. However, b2′ bundle contains one good that is already auctioned (#4), which means b2 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 Section2. 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 andN 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 1
Traditional combinatorial auction.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.


## 2.1. Backgrounds of Combinatorial Auction

The traditional combinatorial auction includes one auctioneer andN 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 1
Traditional combinatorial auction.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 productsG=g1,⋯,gm simultaneously, N bidders B=B1,⋯,Bn 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.
NotationsTermsith bidderBimth goodsgmBi’s bundleSiBi’s bidbikSystem security parameter(G,p,g)Finite groupG of order p, generator gZp, Zp∗Zp=0,1,⋯,p−1, Zp∗=Zp\0mCiphertext of messagemAAdversary algorithmneglkNegligible function in parameterkCSPCrypto service providerAUCTAuctioneerAs shown in Figure2, during the auction, every bidder Bi has his own bundle Si∈G that he expects to obtain and his bid bi, i.e., the price Bi he is willing to pay on his bundle Si. 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:(1)W=Bi∈B∣argmax∑BibiSis.t.⋂BiSi=∅,i.e., a set of conflict-free bidders whose total bid is maximized, and A=∪Bi∈WSi 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 2
System model.


### 3.2. Attack Models and Security Requirements

Different from a previous work that assumes CSP is trustworthy, in this paper, we assume that the crypto service provider issemihonest. That is, CSP will follow the protocol steps honestly but tries to learn the bidders’ bundles and bids, i.e., “curious.” But CSP cannot collude with the auctioneer, i.e., noncooperative. Because CSP and the auctioneer are usually service providers with industry certification standards, if either party has any collusion or deception, it will greatly damage its reputation and interests.In the semihonest adversary model, the main idea is to limit the information exposed to the auctioneer and CSP. When the allocation terminates, the auctioneer is supposed to only know the winners, their bundles, and payments. Each bidder only knows whether he is a winner. The bidder will also be informed the price he should pay, if he is the winner. Each bidder does not know anything about others’ bundle or bid. CSP will help auctioneer to decrypt but know nothing about auction results.Also, the auctioneer is assumed to becurious, malicious, and ignorant, which is interested in bidders’ bundles and bids because this information will enable the auctioneer to have more advantage in future auction of similar goods, i.e., “curious.” Besides, bidders’ preferences and competitive relationship will be disclosed according to the bundles and bids. The auctioneer may also try to obtain secret key msk to decrypt bids or report a fake payment to the winners (i.e., “malicious”), but he is not aware of bidders’ bid for a specific product or preference on these goods (i.e., “ignorant”). The auctioneer may also report a fake payment to the winners, i.e., “malicious,” but he is not aware of bidders’ bid for a specific product or preference on these goods, i.e., “ignorant.” In our system, bidders are assumed to be noncooperative and curious. They will follow the scheme honestly but want to know others’ bundles and bids to help them make decision, i.e., “curious.” However, they will not collude with each other, i.e., “noncooperative.”In our scheme, the following security goals should be achieved:(i)
Privacy preservation: no one can obtain the others’ bundle and bid. Winner determination and payment determination should not arrive at the expense of revealing the losing bids and bundles(ii)
Verifiability and integrity: the winner should be able to verify whether the auctioneer gives a wrong payment to maximize social welfareOur scheme focuses on the confidentiality of losers’ bundle and bid since winners’ bundles and payments might be learned from the valid output of the auction.


### 3.3. Design Goal

Our design goal is to develop an efficient, verifiable, and privacy-preserving combinatorial auction scheme. In particular, the following four desirable objectives need to be considered:(i)
Fairness: all bidders should have the same advantage to win the auction(ii)
Security: the proposed scheme should meet the security requirements as above(iii)
Anonymity: the protocol should not reveal any indications about bidder-bid relation. In other words, the auctioneer cannot get bidder’s identity information from bid(iv)
Scalability: when the combinatorial auction parameters, such as the number of bidders and goods, increase rapidly, the protocol is still efficient in terms of both computation and communication cost


## 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 productsG=g1,⋯,gm simultaneously, N bidders B=B1,⋯,Bn 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.
NotationsTermsith bidderBimth goodsgmBi’s bundleSiBi’s bidbikSystem security parameter(G,p,g)Finite groupG of order p, generator gZp, Zp∗Zp=0,1,⋯,p−1, Zp∗=Zp\0mCiphertext of messagemAAdversary algorithmneglkNegligible function in parameterkCSPCrypto service providerAUCTAuctioneerAs shown in Figure2, during the auction, every bidder Bi has his own bundle Si∈G that he expects to obtain and his bid bi, i.e., the price Bi he is willing to pay on his bundle Si. 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:(1)W=Bi∈B∣argmax∑BibiSis.t.⋂BiSi=∅,i.e., a set of conflict-free bidders whose total bid is maximized, and A=∪Bi∈WSi 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 2
System model.


## 3.2. Attack Models and Security Requirements

Different from a previous work that assumes CSP is trustworthy, in this paper, we assume that the crypto service provider issemihonest. That is, CSP will follow the protocol steps honestly but tries to learn the bidders’ bundles and bids, i.e., “curious.” But CSP cannot collude with the auctioneer, i.e., noncooperative. Because CSP and the auctioneer are usually service providers with industry certification standards, if either party has any collusion or deception, it will greatly damage its reputation and interests.In the semihonest adversary model, the main idea is to limit the information exposed to the auctioneer and CSP. When the allocation terminates, the auctioneer is supposed to only know the winners, their bundles, and payments. Each bidder only knows whether he is a winner. The bidder will also be informed the price he should pay, if he is the winner. Each bidder does not know anything about others’ bundle or bid. CSP will help auctioneer to decrypt but know nothing about auction results.Also, the auctioneer is assumed to becurious, malicious, and ignorant, which is interested in bidders’ bundles and bids because this information will enable the auctioneer to have more advantage in future auction of similar goods, i.e., “curious.” Besides, bidders’ preferences and competitive relationship will be disclosed according to the bundles and bids. The auctioneer may also try to obtain secret key msk to decrypt bids or report a fake payment to the winners (i.e., “malicious”), but he is not aware of bidders’ bid for a specific product or preference on these goods (i.e., “ignorant”). The auctioneer may also report a fake payment to the winners, i.e., “malicious,” but he is not aware of bidders’ bid for a specific product or preference on these goods, i.e., “ignorant.” In our system, bidders are assumed to be noncooperative and curious. They will follow the scheme honestly but want to know others’ bundles and bids to help them make decision, i.e., “curious.” However, they will not collude with each other, i.e., “noncooperative.”In our scheme, the following security goals should be achieved:(i)
Privacy preservation: no one can obtain the others’ bundle and bid. Winner determination and payment determination should not arrive at the expense of revealing the losing bids and bundles(ii)
Verifiability and integrity: the winner should be able to verify whether the auctioneer gives a wrong payment to maximize social welfareOur scheme focuses on the confidentiality of losers’ bundle and bid since winners’ bundles and payments might be learned from the valid output of the auction.


## 3.3. Design Goal

Our design goal is to develop an efficient, verifiable, and privacy-preserving combinatorial auction scheme. In particular, the following four desirable objectives need to be considered:(i)
Fairness: all bidders should have the same advantage to win the auction(ii)
Security: the proposed scheme should meet the security requirements as above(iii)
Anonymity: the protocol should not reveal any indications about bidder-bid relation. In other words, the auctioneer cannot get bidder’s identity information from bid(iv)
Scalability: when the combinatorial auction parameters, such as the number of bidders and goods, increase rapidly, the protocol is still efficient in terms of both computation and communication cost


## 4. Preliminaries

We first introduce the primitives and terms that will be used in our scheme.


### 4.1. ElGamal Cryptosystem

The ElGamal encryption scheme provides a multiplicative homomorphic encryption that comprises the algorithms as key generation, encryption algorithm, and decryption algorithm that are described as follows.(i)
ElGamal.KeyGen: randomly select a large prime numberp and at random select a generator g∈Zp∗. At random, select a number x∈Zp∗. Calculate y=gxmodp. The public key is pk=y,g,p, and the private key is sk=x(ii)
ElGamal.Encrypt: to encrypt a messagem∈G, at first, select a random number k, which is relatively prime with p−1, and then calculate C1=gkmodp, C2=m·ykmodp. The ciphertext is set as ct=C1,C2(iii)
ElGamal.Decrypt: on input a ciphertextct=C1,C2 and a private key sk=x, output the plaintext m by computing(2)m=C2C1sk=yk·mgkx=yk·mykmodpHomomorphic multiplication: letm be the ciphertext of plaintext m. We have(3)m1·m2=m1·m2.


### 4.2. The Monotonically Increasing and One-Way Function

In this section, we give the notation of monotonically increasing and one-way function [30], which will serve as the building block of combinatorial auction with privacy preservation in our scheme.Suppose thatD=x1,x2,⋯,xl, where xi∈Z+ and xi≤U for i=1,2,⋯,l, where D is an l-dimensional dataset and U is the upper bound of all data values in D. Meanwhile, we denote a set of Euclidean distance by ED, where(4)ED≔dist2x,y=∑i=1lxi−yi2x,y∈D.Then, we construct a functionf, which maps each element d2∈ED to fd2. In particular, for each d2∈ED, fd2=a1d2modΔ+a2d2modΔ2+⋯+and2modΔn+e, where Δ=l·U2, each coefficient ai is an integer, and ai>Δi for i=1,2,⋯,n. In addition, e is a noise and randomly chosen from Δ,a1+a2+⋯+an.Obviously, the functionf is a monotonically increasing function, that is,(5)fd12>fd22for∀d12,d22∈ED∧d12>d22.Moreover, the functionf is also a one-way function. That is, it is infeasible to recover d2 from fd2 for any d2∈ED.Both security and computation overhead need to be considered to determine the degree of functionf. With the increasing of n, the computation overhead of function f will be increasing. Thus, an optimal value n should be chosen according to the balance of security and efficiency. In our protocol, we set the degree of f to be N, which is equal to the number of bidders.


### 4.3. Blind Signature

In the PP-VCA scheme, we employ a blind signature to guarantee that a signer can create a signature for bidder’s bid and bundle without knowing the real bid price. Concretely, in the blind signature scheme, the signer can generate the signature of bidding pricem without knowing m. In our scheme, we utilize a blind signature to ensure the authenticity and reliability of the combinatorial auction and verify whether the payment price is correctly calculated. By analyzing the inherent disadvantages of the blinded Nyberg-Rueppel scheme, Qi et al. [31] gave an improved scheme by adding hash function in the signature, which enables the signature scheme to be against changing agreed information attack. We give the concrete blinded Nyberg-Rueppel scheme in Scheme 1.Scheme 1.
Blinded Nyberg-Rueppel scheme (BNR).BNR.SysPara: at random, select a multiplicative groupG∈Zp∗ of prime order q and its generator g, where q is a prime factor of prime number p. Select a hashing function h:0,1∗⟶Zp.BNR.KeyGen: letc be information agreed by the signer and the signee in advance. Compute Tc=2k−1+2h1c+1, where h1· is a one-way function. The signer picks a random number x∈Zq and keeps x·Tc secret and publishes the public parameters as g and gx·Tcmodp.BNR.Signing: signer blindly signs signee’s messagem.1: The signer randomly selectsk^∈Zq and sends r^=gk∧modp to the signee2: The signee randomly selectsα∈Zq, β∈Zq, computes r=hm,cgαr∧βmodp and m^=rβ−1modp until m^∈Zp∗. Then, he sends m^ to the signer3: The signer computess^=m^x·Tc+k^modp and sends s^ to the signee4: The signee computess=s^β+αmodq5: Set the signature asσ=r,s,cBNR.Verify: the verifier checks whetherhm,c=g−syrrmodp and accepts the signature if the equation holds.


## 4.1. ElGamal Cryptosystem

The ElGamal encryption scheme provides a multiplicative homomorphic encryption that comprises the algorithms as key generation, encryption algorithm, and decryption algorithm that are described as follows.(i)
ElGamal.KeyGen: randomly select a large prime numberp and at random select a generator g∈Zp∗. At random, select a number x∈Zp∗. Calculate y=gxmodp. The public key is pk=y,g,p, and the private key is sk=x(ii)
ElGamal.Encrypt: to encrypt a messagem∈G, at first, select a random number k, which is relatively prime with p−1, and then calculate C1=gkmodp, C2=m·ykmodp. The ciphertext is set as ct=C1,C2(iii)
ElGamal.Decrypt: on input a ciphertextct=C1,C2 and a private key sk=x, output the plaintext m by computing(2)m=C2C1sk=yk·mgkx=yk·mykmodpHomomorphic multiplication: letm be the ciphertext of plaintext m. We have(3)m1·m2=m1·m2.


## 4.2. The Monotonically Increasing and One-Way Function

In this section, we give the notation of monotonically increasing and one-way function [30], which will serve as the building block of combinatorial auction with privacy preservation in our scheme.Suppose thatD=x1,x2,⋯,xl, where xi∈Z+ and xi≤U for i=1,2,⋯,l, where D is an l-dimensional dataset and U is the upper bound of all data values in D. Meanwhile, we denote a set of Euclidean distance by ED, where(4)ED≔dist2x,y=∑i=1lxi−yi2x,y∈D.Then, we construct a functionf, which maps each element d2∈ED to fd2. In particular, for each d2∈ED, fd2=a1d2modΔ+a2d2modΔ2+⋯+and2modΔn+e, where Δ=l·U2, each coefficient ai is an integer, and ai>Δi for i=1,2,⋯,n. In addition, e is a noise and randomly chosen from Δ,a1+a2+⋯+an.Obviously, the functionf is a monotonically increasing function, that is,(5)fd12>fd22for∀d12,d22∈ED∧d12>d22.Moreover, the functionf is also a one-way function. That is, it is infeasible to recover d2 from fd2 for any d2∈ED.Both security and computation overhead need to be considered to determine the degree of functionf. With the increasing of n, the computation overhead of function f will be increasing. Thus, an optimal value n should be chosen according to the balance of security and efficiency. In our protocol, we set the degree of f to be N, which is equal to the number of bidders.


## 4.3. Blind Signature

In the PP-VCA scheme, we employ a blind signature to guarantee that a signer can create a signature for bidder’s bid and bundle without knowing the real bid price. Concretely, in the blind signature scheme, the signer can generate the signature of bidding pricem without knowing m. In our scheme, we utilize a blind signature to ensure the authenticity and reliability of the combinatorial auction and verify whether the payment price is correctly calculated. By analyzing the inherent disadvantages of the blinded Nyberg-Rueppel scheme, Qi et al. [31] gave an improved scheme by adding hash function in the signature, which enables the signature scheme to be against changing agreed information attack. We give the concrete blinded Nyberg-Rueppel scheme in Scheme 1.Scheme 1.
Blinded Nyberg-Rueppel scheme (BNR).BNR.SysPara: at random, select a multiplicative groupG∈Zp∗ of prime order q and its generator g, where q is a prime factor of prime number p. Select a hashing function h:0,1∗⟶Zp.BNR.KeyGen: letc be information agreed by the signer and the signee in advance. Compute Tc=2k−1+2h1c+1, where h1· is a one-way function. The signer picks a random number x∈Zq and keeps x·Tc secret and publishes the public parameters as g and gx·Tcmodp.BNR.Signing: signer blindly signs signee’s messagem.1: The signer randomly selectsk^∈Zq and sends r^=gk∧modp to the signee2: The signee randomly selectsα∈Zq, β∈Zq, computes r=hm,cgαr∧βmodp and m^=rβ−1modp until m^∈Zp∗. Then, he sends m^ to the signer3: The signer computess^=m^x·Tc+k^modp and sends s^ to the signee4: The signee computess=s^β+αmodq5: Set the signature asσ=r,s,cBNR.Verify: the verifier checks whetherhm,c=g−syrrmodp and accepts the signature if the equation holds.


## 5. Our Proposed Scheme

Before submitting the combinatorial auction, all bidders blind sign their bundleSi and average value φi through the crypto service provider. As we deploy the blind signature scheme, CSP will not attain any relevant information about the real message Si and φi. Also, we can combine the auction scheme with anonymization techniques to protect bidders’ identity information [32]. In our protocol, bidders’ personally identifiable information will be protected by anonymous techniques, which keeps the bidder-bid relation private. Our framework of proposed PP-VCA is described in Figure 3, in which we employ three subprotocols, namely, privacy-preserving winner determination protocol (PPWD), privacy-preserving scalar protocol (PPSP), and privacy-preserving verifiable payment determination protocol (PPVPD), to implement the combinatorial auction with bidder privacy and payment verifiability.Figure 3
Framework and construction of the PP-VCA scheme.


### 5.1. Privacy-Preserving Winner Determination

At first, we give a greedy winner determination protocol in Algorithm1. Note that in order to protect the privacy information Si and bi of the bidder, AUCT cannot directly sort Bi on the plaintext and select the winner (see Step 2), because the comparison and sorting will reveal the private information Si and bi of the bidders. So, we use a monotonically increasing and one-way function to protect the bidder’s bi, which enables the auctioneer to pick out the largest one without knowing any information about bi.Algorithm 1: Greedy winner determination (GWD).
Input: each Bii=1,⋯,n has bundle Si and bid bi.Output: AUCT obtains the winner set W and bundle set A.1:Bi:(a) Compute average valueφi=bi/Si(b) Sendφi to AUCT2: AUCT:(a) InitializeA=∅, W=∅(b) SortBi in a nonincreasing order according to the value of φi. That is, the bigger the φi, the former the Bi. The sorted sequence is called L(c) CheckBi in L and test whether A∩Si=∅. If true, update A with A∪Si, W with W∪BiThe above GWD algorithm needs to check whetherBi′s bundle contains the goods that has already been auctioned, which can be solved by privacy-preserving scalar product. We utilize m-dimensional binary vector A→ to represent the auction status of m goods, where the kth bit ak=1 if the kth goods gk have already been auctioned and ak=0 otherwise. Similarly, we utilize another m-dimensional binary vector S→i to represent Bi’s bundle Si, where kth bit si,k=1 if the kth goods gk∈Si and si,k=0 if the kth goods gk∉Si.IfBi’s bundle Si does not contain the goods that has already been auctioned, then(6)A→·S→i=0⇔∑k=1mak·si,k=0.If the scalar product isθ, that means Bi’s bundle Si includes θ already-auctioned goods. During this process, both S→i and A→ are private information and have to be protected. Besides, the auctioneer E will obtain side information about S→i from θ, because E can guess which θ goods Bi wants to get according to A→. Similarly, Bi is able to gain some side information about A→ from θ. During this process, it is easy to see that θ and S→i are Bi’s privacy information, which should be kept from the auctioneer AUCT. Besides, θ and A→ are AUCT’s privacy information, which should be kept private from Bi. We design Algorithm 2 to solve the product calculation of two vectors while protecting the privacy and check whether the result is equal to 0.Algorithm 2: Privacy-preserving scalar product (PPSP).
Input: CSP has a pair of Elgamal key: mpk=h1=gs1,h2=gs2,⋯,hm=gsm, msk=S→=s1,s2,⋯,sm.The auctioneer AUCT hasA→=a1,a2,⋯,am; Bii=1,⋯,n has S→i=si,1,si,2,⋯,si,m.Output: AUCT obtains gS→i·A→.1: AUCT: sendA→=a1,a2,⋯,am to CSP2: CSP:(a) Computesky=S→·A→=s1a1+s2a2+⋯+smam(b) Sendsky to AUCT3: For eachBi:(a) Pick a random numberri and encrypt S→i=si,1,si,2,⋯,si,m to compute ci,1=h1rigsi,1,ci,2=h2rigsi,2,⋯,ci,m=hmrigsi,m,ci,m+1=gri(b) Sendci,1,ci,2,⋯,ci,m,ci,m+1 to the auctioneer AUCT4: AUCT: compute∏j=1mci,jaj/ci,m+1sky=gS→i·A→IfgS→i·A→=1, AUCT will explicitly know that Bi’s bundle Si does not contain the goods that have already been auctioned, and otherwise, the final output is indistinguishable from a random number in Zn from the auctioneer’s perspective. Combining Algorithms 1 and 2, we give a privacy-preserving winner determination model (Algorithm 3), which can be regarded as a black-box algorithm and only outputs the winner and the corresponding bundle.Algorithm 3: Privacy-preserving winner determination (PPWD).
Input: CSP has a pair of ElGamal key: mpk=h1=gs1,h2=gs2,⋯,hm=gsm, msk=S→=s1,s2,⋯,sm; the auctioneer AUCT has A→=a1,a2,⋯,am; Bii=1,⋯,n has S→i=si,1,si,2,⋯,si,m and bi.Output: AUCT obtains the winner set W and corresponding bundle set A.1: CSP:(a) Select a large numberU, calculate Δ=l·U2, and select a1,a2,⋯,an s.t. ai>Δii=1,2,⋯,n(b) Randomly choose noisee from Δ,a1+a2+⋯+an(c) Senda1,a2,⋯,an, e and Δ to Bi2:Bi:(a) Compute the average valueφi=bi/Si(b) Computefφi=a1φimodΔ+a2φimodΔ2+⋯+anφimodΔn+e(c) Sendfφi to AUCT3: AUCT andBi jointly perform:(a) AUCT picks the largestfφi and records the corresponding bidder as Bi. S→i is the bundle of Bi(b) On input (mpk, msk, A→, S→i), perform privacy-preserving scalar product protocol (PPSP) to obtain gS→i·A→(c) AUCT receivesgS→i·A→4: AUCT:(a) IfgS→i·A→=1, Bi is the winner. Inform Bi to send fφi, bundle Si and SignSi and put Bi into the winner set W and mark Bi’s bundle as auctioned in A(b) Otherwise, removeBi from biddersRepeat Steps 3–4 until no set can be updatedIn Algorithm3, Bii=1,⋯,n computes the average value φi=bi/Si and calculates fφi using the parameters provided by CSP. Because fφi is a one-way increasing function, the auctioneer AUCT is able to pick out the largest fφi by comparing the value of fφi, which is equivalent to picking the largest φi. Futhermore, AUCT asks the corresponding Bi to execute Algorithm 2 together, in which Bi will not reveal any information about Si. AUCT verifies whether Bi’s bundle contains the goods that have already been auctioned through judging whether gS→i·A→ is equal to 1. If gS→i·A→=1, that means compared with other bidders, the average value of Bi is the largest one, and the corresponding bundle is also available, which means Bi is the winner of this round. The auctioneer will inform Bi to submit fφi, bundle Si and SignSi, and then update A and W to continue the search for the next winner. fφi can prove the identity of Bi, and the signature SignSi can guarantee the integrity of Si. If gS→i·A→≠1, that means the bundle of Bi contains at least one good that has been auctioned, so AUCT will remove Bi from bidders and enter the next round of selection.


### 5.2. Privacy-Preserving Verifiable Payment Determination

We propose a privacy-preserving verifiable payment determination protocol that is shown in Algorithm4. AUCT determines the payment that the winner Bi should pay by the following algorithm: Among the bidders whose bundle would have been allocated if Bi were not the winner, AUCT finds out Bj whose average value is maximum, i.e., the candidate of Bi. Then, Bi’s payment is pi=bj/SjSi, where bj/Sj is the average value of Bj.In our scheme, the winnerBi’s payment is determined by his candidate Bj’s average value bj/Sj. In Algorithm 2, AUCT cannot know any information about the bundle of Bj. As a result, AUCT also cannot know any information about bj from bj/Sj. Similarly, the winner Bi cannot obtain any information about Bj’s bundle Sj and bj, and Bi even does not know who is Bj.Algorithm 4: Privacy-preserving and verifiable payment determination (PPVPD).
Input: the auctioneer AUCT has A→ and the winner’s Si and SignSi.Output:Bi obtains the payment pi.1: AUCT removes the winnerBi from bidders and modifies A to A−Si, where A is the set of auctioned goods and Si is the bundle of Bi. Then, through Algorithm 3, AUCT chooses a freshful winner Bj, who is the candidate of Bi. AUCT notifies Bj to send average value φj=bj/Sj and Signφj to AUCT2: If the candidate ofBj can be successfully found, AUCT computes pi=bj/SjSi and sends pi and Signφj to Bi. If no candidate is found, AUCT sets pi as the agreed default value and notifies Bj that pi is the default value3: Ifpi is not the default value, Bi can recover φj from pi/Si and verify whether φj is correct through Signφj. If they are not equal to each other, Bi knows that the payment is not correct


## 5.1. Privacy-Preserving Winner Determination

At first, we give a greedy winner determination protocol in Algorithm1. Note that in order to protect the privacy information Si and bi of the bidder, AUCT cannot directly sort Bi on the plaintext and select the winner (see Step 2), because the comparison and sorting will reveal the private information Si and bi of the bidders. So, we use a monotonically increasing and one-way function to protect the bidder’s bi, which enables the auctioneer to pick out the largest one without knowing any information about bi.Algorithm 1: Greedy winner determination (GWD).
Input: each Bii=1,⋯,n has bundle Si and bid bi.Output: AUCT obtains the winner set W and bundle set A.1:Bi:(a) Compute average valueφi=bi/Si(b) Sendφi to AUCT2: AUCT:(a) InitializeA=∅, W=∅(b) SortBi in a nonincreasing order according to the value of φi. That is, the bigger the φi, the former the Bi. The sorted sequence is called L(c) CheckBi in L and test whether A∩Si=∅. If true, update A with A∪Si, W with W∪BiThe above GWD algorithm needs to check whetherBi′s bundle contains the goods that has already been auctioned, which can be solved by privacy-preserving scalar product. We utilize m-dimensional binary vector A→ to represent the auction status of m goods, where the kth bit ak=1 if the kth goods gk have already been auctioned and ak=0 otherwise. Similarly, we utilize another m-dimensional binary vector S→i to represent Bi’s bundle Si, where kth bit si,k=1 if the kth goods gk∈Si and si,k=0 if the kth goods gk∉Si.IfBi’s bundle Si does not contain the goods that has already been auctioned, then(6)A→·S→i=0⇔∑k=1mak·si,k=0.If the scalar product isθ, that means Bi’s bundle Si includes θ already-auctioned goods. During this process, both S→i and A→ are private information and have to be protected. Besides, the auctioneer E will obtain side information about S→i from θ, because E can guess which θ goods Bi wants to get according to A→. Similarly, Bi is able to gain some side information about A→ from θ. During this process, it is easy to see that θ and S→i are Bi’s privacy information, which should be kept from the auctioneer AUCT. Besides, θ and A→ are AUCT’s privacy information, which should be kept private from Bi. We design Algorithm 2 to solve the product calculation of two vectors while protecting the privacy and check whether the result is equal to 0.Algorithm 2: Privacy-preserving scalar product (PPSP).
Input: CSP has a pair of Elgamal key: mpk=h1=gs1,h2=gs2,⋯,hm=gsm, msk=S→=s1,s2,⋯,sm.The auctioneer AUCT hasA→=a1,a2,⋯,am; Bii=1,⋯,n has S→i=si,1,si,2,⋯,si,m.Output: AUCT obtains gS→i·A→.1: AUCT: sendA→=a1,a2,⋯,am to CSP2: CSP:(a) Computesky=S→·A→=s1a1+s2a2+⋯+smam(b) Sendsky to AUCT3: For eachBi:(a) Pick a random numberri and encrypt S→i=si,1,si,2,⋯,si,m to compute ci,1=h1rigsi,1,ci,2=h2rigsi,2,⋯,ci,m=hmrigsi,m,ci,m+1=gri(b) Sendci,1,ci,2,⋯,ci,m,ci,m+1 to the auctioneer AUCT4: AUCT: compute∏j=1mci,jaj/ci,m+1sky=gS→i·A→IfgS→i·A→=1, AUCT will explicitly know that Bi’s bundle Si does not contain the goods that have already been auctioned, and otherwise, the final output is indistinguishable from a random number in Zn from the auctioneer’s perspective. Combining Algorithms 1 and 2, we give a privacy-preserving winner determination model (Algorithm 3), which can be regarded as a black-box algorithm and only outputs the winner and the corresponding bundle.Algorithm 3: Privacy-preserving winner determination (PPWD).
Input: CSP has a pair of ElGamal key: mpk=h1=gs1,h2=gs2,⋯,hm=gsm, msk=S→=s1,s2,⋯,sm; the auctioneer AUCT has A→=a1,a2,⋯,am; Bii=1,⋯,n has S→i=si,1,si,2,⋯,si,m and bi.Output: AUCT obtains the winner set W and corresponding bundle set A.1: CSP:(a) Select a large numberU, calculate Δ=l·U2, and select a1,a2,⋯,an s.t. ai>Δii=1,2,⋯,n(b) Randomly choose noisee from Δ,a1+a2+⋯+an(c) Senda1,a2,⋯,an, e and Δ to Bi2:Bi:(a) Compute the average valueφi=bi/Si(b) Computefφi=a1φimodΔ+a2φimodΔ2+⋯+anφimodΔn+e(c) Sendfφi to AUCT3: AUCT andBi jointly perform:(a) AUCT picks the largestfφi and records the corresponding bidder as Bi. S→i is the bundle of Bi(b) On input (mpk, msk, A→, S→i), perform privacy-preserving scalar product protocol (PPSP) to obtain gS→i·A→(c) AUCT receivesgS→i·A→4: AUCT:(a) IfgS→i·A→=1, Bi is the winner. Inform Bi to send fφi, bundle Si and SignSi and put Bi into the winner set W and mark Bi’s bundle as auctioned in A(b) Otherwise, removeBi from biddersRepeat Steps 3–4 until no set can be updatedIn Algorithm3, Bii=1,⋯,n computes the average value φi=bi/Si and calculates fφi using the parameters provided by CSP. Because fφi is a one-way increasing function, the auctioneer AUCT is able to pick out the largest fφi by comparing the value of fφi, which is equivalent to picking the largest φi. Futhermore, AUCT asks the corresponding Bi to execute Algorithm 2 together, in which Bi will not reveal any information about Si. AUCT verifies whether Bi’s bundle contains the goods that have already been auctioned through judging whether gS→i·A→ is equal to 1. If gS→i·A→=1, that means compared with other bidders, the average value of Bi is the largest one, and the corresponding bundle is also available, which means Bi is the winner of this round. The auctioneer will inform Bi to submit fφi, bundle Si and SignSi, and then update A and W to continue the search for the next winner. fφi can prove the identity of Bi, and the signature SignSi can guarantee the integrity of Si. If gS→i·A→≠1, that means the bundle of Bi contains at least one good that has been auctioned, so AUCT will remove Bi from bidders and enter the next round of selection.


## 5.2. Privacy-Preserving Verifiable Payment Determination

We propose a privacy-preserving verifiable payment determination protocol that is shown in Algorithm4. AUCT determines the payment that the winner Bi should pay by the following algorithm: Among the bidders whose bundle would have been allocated if Bi were not the winner, AUCT finds out Bj whose average value is maximum, i.e., the candidate of Bi. Then, Bi’s payment is pi=bj/SjSi, where bj/Sj is the average value of Bj.In our scheme, the winnerBi’s payment is determined by his candidate Bj’s average value bj/Sj. In Algorithm 2, AUCT cannot know any information about the bundle of Bj. As a result, AUCT also cannot know any information about bj from bj/Sj. Similarly, the winner Bi cannot obtain any information about Bj’s bundle Sj and bj, and Bi even does not know who is Bj.Algorithm 4: Privacy-preserving and verifiable payment determination (PPVPD).
Input: the auctioneer AUCT has A→ and the winner’s Si and SignSi.Output:Bi obtains the payment pi.1: AUCT removes the winnerBi from bidders and modifies A to A−Si, where A is the set of auctioned goods and Si is the bundle of Bi. Then, through Algorithm 3, AUCT chooses a freshful winner Bj, who is the candidate of Bi. AUCT notifies Bj to send average value φj=bj/Sj and Signφj to AUCT2: If the candidate ofBj can be successfully found, AUCT computes pi=bj/SjSi and sends pi and Signφj to Bi. If no candidate is found, AUCT sets pi as the agreed default value and notifies Bj that pi is the default value3: Ifpi is not the default value, Bi can recover φj from pi/Si and verify whether φj is correct through Signφj. If they are not equal to each other, Bi knows that the payment is not correct


## 6. Security Analysis

### 6.1. Bidder’s Privacy Preservation

In the PP-VCA protocol, neither the crypto service provider CSP nor the auctioneer AUCT can learn the full information of bidders. CSP is only responsible for key distribution and blind signature, so it cannot obtain any information about bidders’ private data. The auctioneer only knows the winners and their bundles and payments. As to auction losers, we give Theorems1-4 to prove that the auctioneer and other bidders cannot obtain any information about losers’ bundles and bids, even their real identity.(7)advmsk=Prmsk∣S,Output⟵Aour1k−Prmsk∣Output⟵Ablackneglκ.(8)advbj=Prbj∣S,Output⟵Aour1k−Prbj∣Output⟵Ablackneglk.Theorem 1.
An adversarial auctioneerE’s advantage abvmsk is negligible.Proof.
If the auctioneerE wants to construct A skillfully to obtain msk, for example, let A=1,0,⋯,0, and E will obtain sky=s1+sm+1. Due to the discrete logarithms, an adversarial E cannot obtain s1 or sm+1. Similarly, an adversarial E cannot obtain any information about sii=1,2,⋯,m+1. Therefore, we haveTheorem 2.
An adversarial auctioneer AUCT’s advantageadvSi is negligible for all losers.Proof.
Every winner’s bundleSi is given to AUCT; therefore, we have advSi=PrSi∣S,Output⟵Aour1k−PrSi∣Output⟵Ablack=0 if Bi is a winner of the auction. Further, we assume that the ElGamal encryption algorithm is semantically secure, during the privacy-preserving scalar product PPSP protocol (see Algorithm 2), an adversarial AUCT learns whether there exists a feasible bundle which is negligible, and this reveals nothing about losers’ Sj; therefore the adversary’s view on losers’ bundle in our PP-VCA is the same as the one in an ideal black-box algorithm. Therefore, advSj=PrSj∣S,Output⟵Aour1k−PrSj∣Output⟵Ablackneglk is negligible in security parameter k, where Bj is a loser and negl· is a negligible function.Theorem 3.
An adversarial auctioneer AUCT’s advantageadvbj is negligible for all losers.Proof.
In the payment determination model of the winnerBi, the candidate Bj’s average value φj is disclosed to AUCT. Because of the privacy-preserving scalar product PPSP, AUCT knows nothing about Sj, so he does not learn bj from φj=bj/Sj. We haveTheorem 4.
An adversarial bidderBk’s advantage advSi and advbj are negligible for all i≠k.Proof.
For all adversarial bidders, no matter he is a winner or not, all he learns from the PP-VCA protocol is a valid auction outputOutput. We have demonstrated in Section 5.2, and then, the winner cannot obtain any information about the candidate’s Sj and bj.As a result, in a collusion-free case, our proposed combinatorial auction scheme can protect the information of bidders.


### 6.2. Payment Verification

In Algorithm4, the winner’s payment is determined by his candidate’s average value. Since AUCT and Bi use a blind signature Signφj generated by CSP, AUCT to convince that Bj provides the correct φj, and Bi can easily verify whether AUCT the data are modified pi to maximize social welfare, while protecting the plaintext itself in the signature.


## 6.1. Bidder’s Privacy Preservation

In the PP-VCA protocol, neither the crypto service provider CSP nor the auctioneer AUCT can learn the full information of bidders. CSP is only responsible for key distribution and blind signature, so it cannot obtain any information about bidders’ private data. The auctioneer only knows the winners and their bundles and payments. As to auction losers, we give Theorems1-4 to prove that the auctioneer and other bidders cannot obtain any information about losers’ bundles and bids, even their real identity.(7)advmsk=Prmsk∣S,Output⟵Aour1k−Prmsk∣Output⟵Ablackneglκ.(8)advbj=Prbj∣S,Output⟵Aour1k−Prbj∣Output⟵Ablackneglk.Theorem 1.
An adversarial auctioneerE’s advantage abvmsk is negligible.Proof.
If the auctioneerE wants to construct A skillfully to obtain msk, for example, let A=1,0,⋯,0, and E will obtain sky=s1+sm+1. Due to the discrete logarithms, an adversarial E cannot obtain s1 or sm+1. Similarly, an adversarial E cannot obtain any information about sii=1,2,⋯,m+1. Therefore, we haveTheorem 2.
An adversarial auctioneer AUCT’s advantageadvSi is negligible for all losers.Proof.
Every winner’s bundleSi is given to AUCT; therefore, we have advSi=PrSi∣S,Output⟵Aour1k−PrSi∣Output⟵Ablack=0 if Bi is a winner of the auction. Further, we assume that the ElGamal encryption algorithm is semantically secure, during the privacy-preserving scalar product PPSP protocol (see Algorithm 2), an adversarial AUCT learns whether there exists a feasible bundle which is negligible, and this reveals nothing about losers’ Sj; therefore the adversary’s view on losers’ bundle in our PP-VCA is the same as the one in an ideal black-box algorithm. Therefore, advSj=PrSj∣S,Output⟵Aour1k−PrSj∣Output⟵Ablackneglk is negligible in security parameter k, where Bj is a loser and negl· is a negligible function.Theorem 3.
An adversarial auctioneer AUCT’s advantageadvbj is negligible for all losers.Proof.
In the payment determination model of the winnerBi, the candidate Bj’s average value φj is disclosed to AUCT. Because of the privacy-preserving scalar product PPSP, AUCT knows nothing about Sj, so he does not learn bj from φj=bj/Sj. We haveTheorem 4.
An adversarial bidderBk’s advantage advSi and advbj are negligible for all i≠k.Proof.
For all adversarial bidders, no matter he is a winner or not, all he learns from the PP-VCA protocol is a valid auction outputOutput. We have demonstrated in Section 5.2, and then, the winner cannot obtain any information about the candidate’s Sj and bj.As a result, in a collusion-free case, our proposed combinatorial auction scheme can protect the information of bidders.


## 6.2. Payment Verification

In Algorithm4, the winner’s payment is determined by his candidate’s average value. Since AUCT and Bi use a blind signature Signφj generated by CSP, AUCT to convince that Bj provides the correct φj, and Bi can easily verify whether AUCT the data are modified pi to maximize social welfare, while protecting the plaintext itself in the signature.


## 7. Performance and Evaluation

We give the performance analysis and evaluation of our combinatorial auction scheme PP-VCA in terms of communication overhead and computation overhead.


### 7.1. Communication Cost

In our PP-VCA combinatorial auction scheme, each bidder needs to transferm+1 ciphertext, so N bidders need to transfer a total of N·m+1 ciphertext, and the auctioneer needs to return the result. The security parameter used in our scheme is k, and the length of the ciphertext of Elgamal is 2k. Because the length of the result is relatively small compared to k, so it can be ignored. Therefore, in our combinatorial auction scheme, the communication overhead is N·m+1·2k=2kNm+1.


### 7.2. Benchmark and Computational Overhead

To evaluate the computation overhead, we conducted an experiment, which was in Windows 8 with a 64-bit operating system, RAM 4 G, Intel® Core™ i5-4210U CPU @ 1.70 GHz. In order to exclude the communication I/O during the simulation, we generated all strings in the communication and conducted the computation in the local instance. Security parameterk is 128-bit, and every operation is run 1000 times to evaluate the average running time.In the winner determination protocol,Tenc is the time which the bidder spends on encrypt S→i using CSP’s pk, and Tf is the time which the bidders take to calculate fφi using the parameters provided by CSP. Tauc is the total time that the auctioneer spends on the decryption of the ciphertext, selection of the winner, and update of A and W. In terms of different goods and bidders, we give the performance and analysis of computational cost in the winner determination protocol that is shown in Figures 4–6, respectively.Figure 4
Computation overhead with different max bids withbidders=10, goods=10.Figure 5
Computation overhead with different total bidders withgoods=10, maxbid=10000.Figure 6
Computation overhead with different total goods withbidders=10, maxbid=10000.By Figures4 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 φi. So, fφi obtained by one-way and monotonically increasing function is larger, which will increase the auctioneer’s computation overhead to select the largest fφ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, Figures4 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 φi, fφi and encrypts the bundle locally. The increase of the number of total goods will increase the bidder’s encryption time Tenc, 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 Table3. 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.
VariableOur PP-VCA[26][10][11][16]Max bidLogarithmicLogarithmicLinearLinearLinear# of biddersLinearLinearLinearLinearLinear# of goodsLinearExponentialLogarithmicLogarithmicLogarithmic


## 7.1. Communication Cost

In our PP-VCA combinatorial auction scheme, each bidder needs to transferm+1 ciphertext, so N bidders need to transfer a total of N·m+1 ciphertext, and the auctioneer needs to return the result. The security parameter used in our scheme is k, and the length of the ciphertext of Elgamal is 2k. Because the length of the result is relatively small compared to k, so it can be ignored. Therefore, in our combinatorial auction scheme, the communication overhead is N·m+1·2k=2kNm+1.


## 7.2. Benchmark and Computational Overhead

To evaluate the computation overhead, we conducted an experiment, which was in Windows 8 with a 64-bit operating system, RAM 4 G, Intel® Core™ i5-4210U CPU @ 1.70 GHz. In order to exclude the communication I/O during the simulation, we generated all strings in the communication and conducted the computation in the local instance. Security parameterk is 128-bit, and every operation is run 1000 times to evaluate the average running time.In the winner determination protocol,Tenc is the time which the bidder spends on encrypt S→i using CSP’s pk, and Tf is the time which the bidders take to calculate fφi using the parameters provided by CSP. Tauc is the total time that the auctioneer spends on the decryption of the ciphertext, selection of the winner, and update of A and W. In terms of different goods and bidders, we give the performance and analysis of computational cost in the winner determination protocol that is shown in Figures 4–6, respectively.Figure 4
Computation overhead with different max bids withbidders=10, goods=10.Figure 5
Computation overhead with different total bidders withgoods=10, maxbid=10000.Figure 6
Computation overhead with different total goods withbidders=10, maxbid=10000.By Figures4 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 φi. So, fφi obtained by one-way and monotonically increasing function is larger, which will increase the auctioneer’s computation overhead to select the largest fφ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, Figures4 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 φi, fφi and encrypts the bundle locally. The increase of the number of total goods will increase the bidder’s encryption time Tenc, 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 Table3. 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.
VariableOur PP-VCA[26][10][11][16]Max bidLogarithmicLogarithmicLinearLinearLinear# of biddersLinearLinearLinearLinearLinear# of goodsLinearExponentialLogarithmicLogarithmicLogarithmic


## 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.



---

*Source: 8888284-2020-10-20.xml*