Abstract
In recent years, a large number of spectrum mechanisms have been proposed, but these mechanisms ignore the security issues that arise during the design of the mechanism. In this paper, two secure models for sealed-bid spectrum auction are given based on Wang’s generic spectrum auction mechanism. One is the basic model and another improved model based on the basic model is proposed, which maximizes Social welfare while it is a Privacy-preserving Spectrum auction mechanism with public Verification namely SPSV. The SPSV scheme achieves the properties of maximizing the social welfare but also, by using the double paillier cryptosystem, it is privacy-preserving for bidders’ bids without revealing any sensitive information to auctioneer or agent during the entire spectrum auction. Oblivious transfer is applied to ensure the anonymity of bidders. Furthermore, the use of inequality comparison proof also provides the public verification of winner group to verify the comparison relationship between winner groups and losing groups. At last, the performance analysis are given.
Introduction
Nowadays, with the rapid development of globalization of the information technology and economic markets, there is an increasing demand for wireless communication services. However, the traditional, expensive and inefficient spectrum allocation of government makes the radio spectrum to become a kind of scarce resource. According to the survey [1], the large amount of licensed spectrum resources allocated by the government have not been used for a long time. Therefore, more and more attention has been paid to how to efficiently use radio spectrum resources in time and spatial dimensions, which is crucial for the redistribution of idle radio spectrum. On one hand, owners of spectrum rent or sell unused spectrum to increase revenue; on the other hand, users who purchase or rent unused spectrum can make full use of spectrum resources and improve spectrum utilization. Such as the open market of Spectrum Bridge [2], which can provide services for buying and selling, leasing idle spectrum channels.
Because of the efficiency and impartiality of the electronic auction itself, auction mechanisms which is based on wireless spectrum allocation came into being [3–7]. According to its microeconomics [8–10], spectrum auctions have become an effective way to solve the problem of spectrum allocation and reuse [4–6, 11]. Moreover, spectrum auction mechanisms are different from the traditional auction of items. There are two basic requirements should be taken into consideration [12]. First, the reusability in time and spatial dimensions which is a unique feature of spectrum auctions [13]. Second, it’s better to be truthful for spectrum auction. In recent years, many truthful spectrum auction are proposed [5, 28], which can stimulate bidders to bid truthfully and reveal their true spectrum valuations. However, this kind of truthful spectrum auctions may cause potential security threats and become untruthful once bidders reveal their true spectrum valuations[23–25].
So far, a large number of spectrum auction mechanisms have been proposed in recent years. For instance, [5, 26] achieve the spectrum allocation mechanism which provide the characteristic of strategy-proof [30]. Moreover, [16, 29] also do some research not only satisfying the strategy-proof but also focusing on maximizing the social efficiency. However, theses spectrum auction mechanisms ignore the security issues that arise during the design of the mechanism. More seriously, the sensitive information of bidders is usually leaked to the malicious parties. Therefore, researchers do more extensive work to try to solve theses problems and possible potential security hazards. A number of spectrum auction schemes [12, 30–37] are proposed focusing on bidder privacy preserving nowadays.
According to the above-mentioned security schemes for spectrum auctions, most of them ensure the users’ bid privacy or provide an auction outcome while satisfying the properties of spectrum auctions. In this paper, SPSV is proposed and contributions are made in this paper as follow:
Two models for sealed-bid spectrum auction are proposed. One is a basic model and another is an improved model called SPSV, which maximize the social welfare, privacy-preserving spectrum auction scheme with public verification. Moreover, SPSV enables the spectrum auction to be calculated, implemented completely in a ciphertext environment and obtains the auction results only. SPSV also provides the public verification of winner group to determine the comparison relationship between winner groups and losing groups, which achieves the public verification of the correctness result of the winner group. Finally performance analysis of our proposed scheme SPSV is given.
The remainder of this paper is organized as follows. In Section II, there are some preliminaries and in Section III, Cryptographic technologies that used in our spectrum auction scheme are introduced. In Section IV, a basic model and an improved model SPSV are proposed. In Section V, performance analysis of SPSV is provided. Finally, conclusion is made in our paper in Section VII.
Preliminaries
In this section, the design of spectrum auction framework is first briefly proposed and some essential concepts that related to mechanism design are reviewed. Finally, Wang’s generic spectrum auction is introduced.
Spectrum auction framework
Our proposed spectrum auction framework is shown as Fig. 1. To implement our spectrum auction successfully, the spectrum auction framework concludes three parts: auctioneer, agent and a group of bidders. The auctioneer may be a specialized third-party platform. There is also a trust-third party called agent who communicates the auctioneer and bidders. It is assumed that the agent is a honest-but-curious [38], which stores the encrypted data and cooperates with the auctioneer to determine the spectrum winners and spectrum price.

Spectrum auction framework.
In spectrum auction mechanism, there is a set of orthogonal and homogenous channels C = {c1, c2, …, c m }. Different from other traditional goods auctions, bidders in spectrum auction could bid and work on the same channel simultaneously as long as they do not interfere with each other.
There is also a set of bidders B ={ 1, 2, …, n } and each bidder i ∈ n has his profile denoted as I = {b i , d i , v i , p i , L i }, where b i is the bid of i, d i is the number of the channels that each bidder i wants to buy. In spectrum auction, any bidder can bid single or multiple channels which is different from the traditional goods auction. In this paper, d i = 1. v i and p i denote the private valuation of bidder i and the charge of bidder i that pay for the channel respectively. L i is the geography location of i.
In this subsection, some essential concepts that related to our secure spectrum auction design are reviewed.
Truthful in Expectation [39]: a randomized mechanism is truthful in expectation if, for each bidder i, the equation that E [u i (v i , b-i)] ⩾ E [u i (u i , b-i)] holds for any b i when fixing b-i. where b-i and u i separately represent the bidders’ except bidder i and the utility (also called profit) of each bidder i.
Bid-monotone [34]: spectrum allocation in spectrum auction mechanism is bid-monotone if the bidder i bids b
i
and always wins the auction satisfying the inequality
Conflict Graph [40–43]: a conflict graph G (N, E), Where E denotes the all edges [41]. If two bidders x and y are conflict with each other when they use the same channel simultaneously, the edge (x, y) belongs to E. Let N (x) be the bidders that interfere with x. In other words, N (x) denotes the neighboring nodes of x in G. According to the protocol interference [40, 43], conflict graph is used to solve the spectrum allocation problem and conflict graph is known by the auctioneer in advance [42].
Improved Wang’s spectrum auction mechanism algorithm
Wang’s scheme is a truthful in expectation spectrum auction mechanism and its allocation algorithm of mechanism is bid-monotone. The details of Wang’s scheme are shown in [44]. In this subsection, an improved spectrum auction mechanism algorithm based on Wang’s scheme is proposed. the improved algorithm conclude two parts: the spectrum winner algorithm and the spectrum price algorithm.
The spectrum winner algorithm
The spectrum winner algorithm is the same as the Wang’s spectrum algorithm for determining the winner. When agent receives all bidders’ bids and their geography location from bidders, agent divides theses bidders in to non-conflicting groups according to the conflict graph.
The spectrum auction mechanism is based on an integer programming problem (LP solutions) which achieves maximum social welfare and is also bid-monotone(details are shown in [44]).
A group bid sum S x for each group g x ∈ G is calculated as
All bidder groups are ranked by their group bid sums in non-increasing order:
Therefore, bidders from the group
In spectrum Wang’s auction mechanism, bidder i bid its bid b
i
and there is a critical value c
i
, which is the minimum bid to win the spectrum auction. the relationship between c
i
and b
i
satisfies the following equation:
In order to determine the payment P, agent selects winner í randomly and its bid is
Obviously, the Wang’s scheme show that when
According to the analyze of the Wang’s scheme above, an improved spectrum price algorithm is proposed. The improve spectrum price mechanism can not only find the payment price P effectively and reduce computation overhead but also implement easily in a secure and encrypted environment.
When agent randomly selects winner bidder í and its bid
In order to find the payment P, the agent continues to randomly select winner bidder j and its bid b j in the winner group. Still set payment p i = 0 of the bidder j and rearrange the groups again. If the winner group fails to bid and , the value of P i will affect the winning or losing of the spectrum auction. ∃c i ∈ [0, b j ]. b j is the price of the bidder j winning the auction, which is the payment price of the spectrum. Therefore, p i = b j . Finally, each winner is charged the price p = b j /|g x |.
In this section, three cryptographic technologies are introduced including paillier cryptosystem, inequality comparison and oblivious transferrespectively.
Paillier cryptosystem
Paillier cryptosystem is an additive homomophic cryptosystem which is invented by Pascal Paillier in 1999 [45]. Paillier encryption scheme [47] concludes three parts: Key Generation, Encryption phase and Decryption phase. Details of the scheme are shown in Table 1. The additive homomorphism properties is shown in Table 2.
Paillier encryption scheme
Paillier encryption scheme
Additive homomorphism properties of paillier cryptosystem
The inequality comparison proof of paillier cryptosystem is shown as follows [38–46]:
Given two ciphertexts C x = E (x) and C y = E (y) and prove P can verify that x ⩾ y without revealing any information about x and y, where x, y ∈ [0, 2 t ), 2 t < 2/ - N.
To prove x ⩾ y, prover P and verifier V calculate the E (x - y) = E (x) × E-1 (y) mod n2 and P can prove V that 0 < x - y < 2 t < N/2, by test set(TS) and range protocol.
A valid test set TS is used, which is a set of paillier’s ciphetext: TS ={ C1 = E (m1, r1) , …, C t = E (m t , r t ) } and any plaintext is m i = 2 i . The elements of the TS are randomly ordered to ensure the privacy of m i . By using of TS and given C x = E (x, r x ), the prover P proves that x < 2 t < N/2 as follows:
Range protocol: Set x = 2
t
1
+ … +2
t
j
. P selects the encryption set C
x
={ C
t
1
, …, C
t
j
} from TS to get the ciphertext set of the plaintext 2
t
1
, …, 2
t
j
. Corresponding random values r
t
1
… , r
t
j
and r
x
are used to calculate a new value:
V receives the proof to calculate the equation: E-1 (x, r x ) · C t 1 · … · C t m ( mod n2) = E (0, r*) and V can verify and deduce that x < 2 t < 2/ - N.
Therefore, conclusion is made that given three cihpertexts: E (x) , E (y) , E [(x - y) mod n] = E (x) · E-1 (y). P could proves V that x ⩾ y by checking the inequations: x < 2 t < N/2, y < 2 t < N/2, (x1 - x2) mod N < 2 t < N/2.
In our spectrum auction, inequality comparison proof of paillier cryptosystem [46, 47] is used for public verification of the winner group to verify comparison relationship between winner group and losing group without revealing plaintext.
Oblivious transfer
The design of the 1-out-of-n oblivious transfer protocol, which is proposed by Tzeng [48, 49] is shown in the Table 3. q is a large prime and G q is a cyclic group of order q. Z q denotes as a finite additive group of q elements and (g, h) is two generators of G q . Oblivious transfer is used in our scheme to achieve the anonymity of bids.
oblivious transfer protocol
In this section, two sealed-bid spectrum auction models are proposed. One is the basic model that can only protect users’ bids at the bidding phase, and the other is an improved model called SPSV.
Basic model
The basic model for sealed-bid spectrum auction is introduced and works in three steps as follows.
Before running the basic model, necessary system parameters are needed. auctioneer generates its public key Key pk , private key Key sk respectively using paillier cryptosystem.
Each bidder i bids his b
i
while using paillier cryptosystem from auctioneer to encrypt his bid.
Where r i is a random and generated by agent.
Each bidder sends E (b i , r i ) and its geography location L i to agent until agent receives all the encrypted bids from bidders. Then the auctioneer opens his private key Key sk .
Agent groups the bids from bidders using conflict graph and bidders are divided into non-conflicting groups. Then run the spectrum auction mechanism that mention in Section II. The flow char of the basic model is shown in Fig. 2.

Flow char of the basic model.
However, the basic model only protects privacy of bidders at bidding phase.
In this part, the improved model called SPSV is proposed based on the basic model. The scheme SPSV also concludes three steps: initialization, bidding and spectrum allocation, determining winners and spectrum price.
Necessary system parameters are set up firstly and SPSV generates a set of possible bid value as
Where z is an integer. Each i bids b i ∈ α and i′s possible bid value in set α denoted as α x requires that α x ∈ [0, 2 t ). Moreover, the elements of set α satisfy the equation:
SPSV employs a key encryption scheme using paillier cryptosystem. Auctioneer holds a private key a u . s k, and the matching public key a u . p k. Agent generates its private key a g . s k, public key a g . p k. Agent also needs to initialize the parameters of oblivious transfer: (g, h, G q ) where q is a large prime and (g, h) is two generators of G q which is a cyclic group of order q.
Each bidder i ∈ n chooses a bid b
i
= α
x
∈ α according to his affordability from agent through the
i randomly picks r ∈ Z q and sends the y = g r h x to agent.
The agent replies c ={ c1, c2, …, c
z
} in which
The bidder picks c
x
= (d, f) from c and computes
After all bidders get their bids through the oblivious transfer, bidder i encrypts b
i
and its negative value -b
i
using the agent’s public key a g . p k and auctioneer’s public key a u . p k:
Where
After collecting all the encrypted double bids and negative values from bidders, agent groups the bidders using conflict graph and divides bidders into non-conflicting groups according to geography location. The non-conflicting groups is shown in the Table 4.
Non-conflicting groups that public for agent
In the Table 4. id
j
i
is denoted as the ith member bidder in group g
j

Flow chart for SPSV of initialization, bidding and spectrum allocation.
1. Determining winners algorithm
For each double encrypted group g
j
∈ G, the auctioneer decrypts the double encrypted bids, the corresponding double encrypted negative bids with private key a u . s k and gets the encrypted group
Auctioneer calculates the each encrypted group bid sum E (S j ) and its corresponding negative bid sum E (- S j ), 1 ⩽ j ⩽ l for each group g j ∈ G using the additive homomorphism properties of paillier cryptosystem.
Then auctioneer gets all the groups of encrypted bid sum set {E (S1) , E (S2) , … , E (S l ) }, corresponding the encrypted negative bid sum set { (E (S1)) -1, (E (S2)) 1, … , (E (S l )) -1 }. The group which is the maximum of group bid sum is the winner. Therefore, auctioneer and agent should cooperate with each other to find the maximum group. Algorithm 1 Table 5 shows shows the SPSV-determining winner group procedure.
Table5
Then, auctioneer sends the
Set {E (difi,j) = E (S
i
- S
j
) |1 ⩽ i < l, 1 < j ⩽l, i, j are integers } to agent. Agent decrypts values in set with private key a g . s k and gets the original values to compare the size relationship between groups to judge if S
i
- S
j
< 0 or S
i
- S
j
> 0.
are integers.
Therefore, agent sorts all the bid sum groups by comparison and ranked in non-increasing order:
Bidders from the highest of bid sum group Smax are spectrum auction winners.
2. Determining spectrum price algorithm
After determining the winner, the agent will get the ID of each bidder in the winner group Smax. The set of bidders’ ID from winner group Smax is denoted as:
In order to determine the spectrum price P, agent uses the random algorithm R (·) to select a bidder idmax,i, 1 ⩽ i ⩽ | max | from winners and its double encrypted bid value is denoted as E′ (bmax, rmax′). Agent set the bidder idmax,i’s double encrypted bid E′ (P i ) = 0. Then the previous bid value is replaced with the bidder idmax,i biding double encrypted E′ (P i ) = 0 in non-conflicting groups while the other bidders’ encrypted bids do not change and rearrange the groups and still rank the groups in a non-increasing order.
If the new Smax is not rank fist, the spectrum price P = bmax is determined, otherwise, set P = 0.
The spectrum price P = decrypt ((E′ (bmax, rmax′) , a u . s k) , a g . s k), and each winner is charged the price p = bmax/|Smax|.
Each bidder in losing groups can use the inequality comparison proof of paillier cryptosystem to publicly verify that whether the winner group is the largest group or not. When auctioneer determines the winner group, the winner group g win , encrypted winner group bid sum E (S win ) and the each losing group g lose i , each encrypted losing group bid sum E (S lose i ) is on public.
Then auctioneer computes
E (dif) is sent to agent and agent decrypts it to get original value dif.
Prover P as an agent can prove to V which are bidders from losing groups that dif < 2 t < N/2.
Agent uses its public key a g . s k and select a random
Computation overhead of SPSV protocol
In this section, the computational overhead of auctioneer, agent and a group of bidders is calculated. For convenience of description, assume there are n bidders and the conflict graph that obtained for each bidder’s geographic location is known. n bidders can be divided into g groups and winner group w g ∈ g has w winners. MUL indicates large number multiplication and DIV indicates large number divisor respectively. POW means power exponent operation, MOD means modular operation, EX means modular exponentiation operation respectively. And also set GCD as the greatest common divisor operation and LCM as the minimum common multiple operation respectively.
The computational overhead of auctioneer, agent and each bidder at initialization phases, bidding and spectrum allocation phase, determining winners and spectrum price phase is shown in Table 6.
The computational overhead of auctioneer, agent and each bidder
The computational overhead of auctioneer, agent and each bidder
Through the analysis of the SPSV protocol performance, the main computational overhead of the protocol is the implementation of paillier’s homomorphic encryption algorithm. Therefore, the experimental simulation uses the JAVASE-1.7 with the java.util and java.math packages to write the original 512-bit paillier homomorphic encryption algorithm. For the sake of simplicity, this experiment was tested on a computer with the followingenvironment: Intel(R) Core(TM) i7-4790 CPU, 3.60 gHz, 4GB RAM, windows7 64-bit operating system.
According to the simulation of SPSV protocol, auctioneer and the agent execute 1MUL + 1DIV + 1GCD + 1LCM + 1EX respectively for preparing public and private keys, which takes 10ms in initialization phase. In bidding and allocation phase, each bidder uses oblivious transfer for transmitting its bids. POW operation takes 0.005ms and 6POW take 0.0065ms for oblivious transfer. Then, bidders use paillier cryptosystem for double encryption, which takes 4.4ms for 2 (2POW + 1MOD). In determining winner phase and determining spectrum phases, MUL and decryption for auctioneer and agent should be done, which take 0.005ms and 2.2ms respectively.
As shown in Table 6, the number of bidders n, the group g and the number of winners w in winner group w g affect the computational overhead of auctioneer. Similarly, the group g and the number of winners w affect the computational overhead of agent.
Through the simulation experiments, the maximum number of bidders n that SPSV protocol bears within 1000ms is n = 100 and the maximum group is g = 30. (a),(b),(c),(d) of Fig. 4 respectively indicate that when n = 50,100,150,200,the relationship between computational overhead of each participant and group g.

The relationship between computational overhead of each participant and group g.
As can be seen from the analysis in Fig. 4, When n is constant, the group g affects the agent’s computational overhead. When the group g increases, the computational overhead of agent is also shown an increasing trend. However, unlike the agent, computational overhead of auctioneer is within a certain range without any drastic fluctuations. Therefore, the group g does not affect the computational overhead of the auctioneer and group g not a major factor affecting the auctioneer’s computational overhead and the auctioneer’s computational overhead is related to the value of n.
(a), (b), (c), (d) of Fig. 5 respectively indicate that when g = 5,10,15,20 the relationship between computational overhead of each participant and the number of bidders n.

The relationship between computational overhead of each participant and the number of bidders n.
As can be seen from the analysis in Fig. 5, When g is constant, the number of the bidders n affects the auctioneer’s computational overhead. When n increases, the computational overhead of auctioneer is also shown an increasing trend. However, unlike the auctioneer, computational overhead of agent is within a certain range without any drastic fluctuations. Therefore, n does not affect the computational overhead of the agent.
In this paper, two models for sealed-bid spectrum auction are proposed based on Wang’s generic spectrum auction mechanism. One is a basic model and another is an improved model called SPSV. SPSV uses double paillier encryption to protect the privacy of the bidders’ bids. Oblivious transfer is also used to ensure the anonymity of bidders. The scheme realizes the data separation that only auctioneer and agent cooperate to restore the original bid values and neither auctioneer or agent can recover the encrypted bids alone. Furthermore, inequality comparison proof is applied to the scheme and SPSV achieves the public verification of the winner group. Finally, the performance analysis are given.
Footnotes
Acknowledgments
The authors thank the editors and the anonymous reviewers for their valuable comments. This study is supported by the National Science foundation of China (No. 61472074, U1708262), the Fundamental Research Funds for the Central Universities (No.N172304023), the Foundation of Science and Technology on Information Assurance Laboratory (No. KJ-17-001).
