A privacy-preserving spectrum auction scheme using paillier cryptosystem with public verification

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.

Keywords

Spectrum auction social welfare privacy-preserving public verification

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

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

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

Fig.1

Spectrum auction framework.

In spectrum auction mechanism, there is a set of orthogonal and homogenous channels C = {c₁, c₂, …, 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.

2.2 Some essential concepts

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 $b_{i}^{'} > b_{i}$ .

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

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

2.3.1 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. $\begin{matrix} G = {g_{1}, g_{2}, \dots g_{l}}, \\ i \neq j, \forall g_{i}, g_{j} \in G, g_{i} \cap g_{j} = \emptyset . \end{matrix}$ (1)

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

$S_{x} = \sum_{j = 1}^{| g_{x} |} {b_{j} | b_{j} \in g_{x}}$ , b_j is denoted as any bid value in g_x.

All bidder groups are ranked by their group bid sums in non-increasing order: $G^{'} = {S_{1}^{'}, S_{2}^{'}, \dots S_{l}^{'}}, S_{1}^{'} > S_{2}^{'} > \dots > S_{l}^{'}$ (2)

Therefore, bidders from the group $S_{1}^{'}$ are winners.

2.3.2 The spectrum price algorithm

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: ${\begin{matrix} b_{i} > c_{i} win the spectrum auction . \\ b_{i} < c_{i} lose the spectrum auction . \end{matrix}$ (3)

In order to determine the payment P, agent selects winner í randomly and its bid is $b_{i}^{'}$ in winner group. Set payment variable $p_{i} \in [0, b_{i}^{'}]$ and rearrange the group according to the changed group bid sum value of winner group with bidder í bidding p_i. While, the others do bidders’ bids not change. The payment P is as follows: $P = {\begin{matrix} p_{i} = b_{i}^{'} winner group bid failed, find the payment \\ p_{i} = 0 otherwise, {couldn}^{'} t find the payment \end{matrix}$ (4)

Obviously, the Wang’s scheme show that when $P = p_{i} = b_{i}^{'}$ , $b_{i}^{'}$ is the price which makes bidder i′ wins the spectrum auction. This price $b_{i}^{'}$ is the payment and $\exists c_{i} \in [0, b_{i}^{'}]$

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 $b_{i}^{'}$ in winner group, set payment variable p_i = 0, p_i takes the minimum value of $p_{i} \in [0, b_{i}^{'}]$ . Rearrange the groups according to the changed bid sum value with the bidder i bidding P_i = 0. The others’ bids do not change. If the new winner group $S_{1}^{"}$ still wins the auction and $S_{1}^{"} > S_{2}^{'}$ , the value of p_i does not affect the auction result, and $c_{i} \notin [0, b_{i}^{'}]$ . in other words, no matter how many times the payment variable p_i is randomly selected, no critical c_i value will be found. It can be seen that $b_{i}^{'}$ is not the price that win the spectrum auction, P = 0 and no payment price P can be found.

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 $S_{1}^{"} > S_{2}^{'}$ , 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|.

3 Cryptographic technologies

In this section, three cryptographic technologies are introduced including paillier cryptosystem, inequality comparison and oblivious transferrespectively.

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

Table 1
Paillier encryption scheme

Key Generation: Let p and q be two large primes, compute

N = pq, $g \in Z_{N^{2}}^{}$ and L (x) = (x - 1)/N, public key pk = (N, g),

private key sk = λ (N) = lcm* (p - 1, q - 1).

Encryption phase: select any plaintext m ∈ Z_N, select random

$r \in Z_{N}^{*}$ , the ciphertext

c = E_pk (m, r) = g^mr^N mod N²

Decryption phase: decrypt the ciphertext and the plaintext

m = D_sk (c) = L (c^λ(N) mod N²)/L (g^λ(N) mod N²) mod N.

Key Generation: Let p and q be two large primes, compute
Encryption phase: select any plaintext m ∈ Z_N, select random
$r \in Z_{N}^{*}$ , the ciphertext
c = E_pk (m, r) = g^mr^N mod N²
Decryption phase: decrypt the ciphertext and the plaintext
m = D_sk (c) = L (c^λ(N) mod N²)/L (g^λ(N) mod N²) mod N.

Table 2

Additive homomorphism properties of paillier cryptosystem

E (m₁r₁) = g^{m
₁}r_1^N mod N², E (m₂, r₂) = g^m2r_2^N mod N²

E (m₁ + m₂, r) = g^m₁+m₂r^N mod N²

E (m₁) · E (m₂) = (g^{m
₁}r_1^N mod N²) · (g^{m
₂}r_2^N mod N²)

= g^m₁+m₂r_1^Nr_2^N mod N² = E (m₁ + m₂, r₁ · r₂)

(E (m₁, r₁)) ^-1 = E (- m₁) = g^-m₁r_1^N mod N²

D (E (m₁ + m₂, r)) = D (g^m₁+m₂r^N mod N²)

= D (g^m₁+m₂r_1^Nr_2^N mod N²) = D (E (m₁, r₁) · E (m₂, r₂))

3.2 Inequality comparison proof 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 n² 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 ={ C₁ = E (m₁, r₁) , …, C_t = E (m_t, r_t) } and any plaintext is m_i = 2ⁱ. 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
₁} + … +2^{t
_j}. P selects the encryption set C_x ={ C_{t
₁}, …, C_{t
_j} } from TS to get the ciphertext set of the plaintext 2^{t
₁}, …, 2^{t
_j}. Corresponding random values r_{t
₁} … , r_{t
_j} and r^x are used to calculate a new value: $r^{*} = (r_{x}^{- 1} \times r_{t_{1}} \dots \times r_{t_{j}}) (mod n) .$ Therefore, the two items set C_x and r^* are packaged as the proof, which is sent to the verifier V.

V receives the proof to calculate the equation: E^-1 (x, r_x) · C_{t
₁} · … · C_{t
_m} ( mod n²) = 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, (x₁ - x₂) 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.

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

Table 3
${OT}_{1}^{n}$ oblivious transfer protocol

1-out-of-n ( ${OT}_{1}^{n}$ )oblivious transfer protocol

Initialization:

Parameters input: (g, h, G_q);

Senders’ input: s₁, s₂ … s_n ∈ G_q;

Receivers’ choice: ɛ ∈ [1, n];

Each receiver can get only one element of senders’ input and

senders can not known which one he gets.

(1) Receiver sends: ɛ and y = g^rh^ɛ, r ∈ _RZ_q;

(2) Senders replies: c_j = (g^{t
_j}, s_j (y/h^j) ^{t
_j}) , t_j ∈ _RZ_q, 1 ⩽ j ⩽ n;

(3) c_ɛ = (d, f), sender computes s_ɛ = f/d^r.

1-out-of-n ( ${OT}_{1}^{n}$ )oblivious transfer protocol
Initialization:
Parameters input: (g, h, G_q);
Senders’ input: s₁, s₂ … s_n ∈ G_q;
Receivers’ choice: ɛ ∈ [1, n];
Each receiver can get only one element of senders’ input and
senders can not known which one he gets.
(1) Receiver sends: ɛ and y = g^rh^ɛ, r ∈ _RZ_q;
(2) Senders replies: c_j = (g^{t _j}, s_j (y/h^j) ^{t _j}) , t_j ∈ _RZ_q, 1 ⩽ j ⩽ n;
(3) c_ɛ = (d, f), sender computes s_ɛ = f/d^r.

4 Proposed scheme

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.

4.1 Basic model

The basic model for sealed-bid spectrum auction is introduced and works in three steps as follows.

Step 1. initialization

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.

Step 2. bidding and opening

Each bidder i bids his b_i while using paillier cryptosystem from auctioneer to encrypt his bid. $\begin{matrix} E (b_{i}, r_{i}) = b_{i} {Key}_{pk} \\ = g^{b_{i}} r_{i}^{N} mod N^{2}, \\ 1 ⩽ i ⩽ n, r_{i} \in Z_{N}^{*} \end{matrix}$ (5)

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.

Step 3 determining winners and spectrum price

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.

Fig.2

Flow char of the basic model.

However, the basic model only protects privacy of bidders at bidding phase.

4.2 Improved model SPSV

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.

Step 1. initialization

Necessary system parameters are set up firstly and SPSV generates a set of possible bid value as $α = {α_{1}, α_{2}, \dots, α_{z}}, α_{1} < α_{2} \dots < α_{z}$ (6)

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:

$α_{1} + α_{2} \dots + α_{z} < 2^{t} < \frac{N}{2}$ (7)

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.

Step 2. bidding and spectrum allocation

Each bidder i ∈ n chooses a bid b_i = α_x ∈ α according to his affordability from agent through the ${OT}_{1}^{n}$ oblivious transfer. Transmission details are as follows:

i randomly picks r ∈ Z_q and sends the y = g^rh^x to agent.

The agent replies c ={ c₁, c₂, …, c_z } in which $c_{j} = (g^{k_{j}}, α_{j} {(y / h^{j})}^{k_{j}}), k_{j} \in_{R} Z_{q}, 1 ⩽ j ⩽ z .$ (8)

The bidder picks c_x = (d, f) from c and computes $\begin{matrix} b_{i} = \frac{f}{d^{r}} = \frac{α_{x} {(y / h^{x})}^{k_{x}}}{{(g^{k_{x}})}^{r}} \\ = \frac{α_{x} {(g^{r} h^{x} / h^{x})}^{k_{x}}}{{(g^{k_{x}})}^{r}} = α_{x} \end{matrix}$ (9)

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: $\begin{matrix} E (b_{i}, r_{i}) = Encrypt (b_{i}, a g . p k, r_{i}) \\ E (- b_{i}, r_{i}) = {(E (b_{i}, r_{i}))}^{- 1} \end{matrix}$ (10) $\begin{matrix} E^{'} (b_{i}, r_{i}^{'}) = Encrypt ((E (b_{i}, r_{i}), a u . p k, r_{i}^{'})) \\ E^{'} (- b_{i}, r_{i}) = (E (- b_{i}, r_{i}), a u . p k, r_{i}^{'}) \end{matrix}$ (11)

Where $r_{i} \in Z_{N}^{*}$ is generated by agent., $r_{i}^{'} \in Z_{N}^{*}$ is generated by auctioneer.

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.

Table 4

Non-conflicting groups that public for agent

Group ID	Bidder ID	Double Encrypted Bid	Double Encrypted Negative Bid
1	id_1₁, id_1₂, …, id_{1_\|g₁\|}	$E_{1, 1}^{'}, E_{1, 2'}, \dots E_{1, \| g 1 \|'}$	${(E_{1, 1}^{'})}^{- 1}, {(E_{1, 2}^{'})}^{- 1}, \dots {(E_{1, \| g 1 \|}^{'})}^{- 1}$
2	id_2₁, id_2₂, …, id_{2_\|g₂\|}	$E_{2, 1}^{'}, E_{2, 2'}, \dots E_{2, \| g 2 \|'}$	${(E_{2, 1}^{'})}^{- 1}, {(E_{2, 2}^{'})}^{- 1}, \dots {(E_{2, \| g 2 \|}^{'})}^{- 1}$
…	…	…	…
l	id_{l ₁}, id_{l ₂}, …, id_{l _{\|g_l\|}}	$E_{l, 1}^{'}, E_{l, 2'}, \dots E_{l, \| g l \|'}$	${(E_{l, 1}^{'})}^{- 1}, {(E_{l, 2}^{'})}^{- 1}, \dots {(E_{l, \| g l \|}^{'})}^{- 1}$

In the Table 4. id_{j
_i} is denoted as the ith member bidder in group g_j $E_{j, 1}^{'}, E_{j, 2}^{'}, \dots, E_{j,}^{'} | g j |' {(E_{j, 1}^{'})}^{- 1}, {(E_{j, 2}^{'})}^{- 1}, \dots {(E_{j, | g j |}^{'})}^{- 1}$ are double encrypted bids, double encrypted negative bids from bidders in group g_j respectively. Agent sends theses non-conflicting groups to the auctioneer. The flow chart for SPSV of initialization, bidding and spectrum allocation is shown in Fig. 3.

Fig.3

Flow chart for SPSV of initialization, bidding and spectrum allocation.

Step 3. determining winners and spectrum price

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 $g_{j} = {E_{j, 1}, E_{j, 2}, \dots, E_{j, | g_{j} |}}$ (12) $\begin{matrix} E_{j, i} = decrypt (E_{j, i}^{'}, a u . s k) \\ = encrypt (b_{j, i}, a g . p k) \end{matrix}$ (13) $\begin{matrix} {(E_{j, i})}^{- 1} = decrypt ({(E_{j, i}^{'})}^{- 1}, a u . s k) \\ = encrypt (- b_{j, i}, a g . p k) \end{matrix}$ (14)

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.

$\begin{matrix} E (S_{j}) = E_{j, 1} E_{j, 2} \cdot \dots \cdot E_{j, | g_{j} |} \\ = encryct (\sum_{i = 1}^{| g_{j} |} {b_{i} | b_{i} \in g_{j}, 1 ⩽ i ⩽ | g_{j} |}, a g . p k) \\ = E (\sum_{i = 1}^{| g_{j} |} {b_{i} | b_{i} \in g_{j}, 1 ⩽ i ⩽ | g_{j} |}) \end{matrix}$ (15) $E (- S_{j}) = {(E_{j, 1})}^{- 1} \cdot {(E_{j, 2})}^{- 1} \cdot \dots \cdot {(E_{j, | g_{j} |})}^{- 1}$ (16)

Then auctioneer gets all the groups of encrypted bid sum set {E (S₁) , E (S₂) , … , E (S_l) }, corresponding the encrypted negative bid sum set { (E (S₁)) ^-1, (E (S₂)) ¹, … , (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.

Table 5

Table5

Algorithm 1.	SPSV- determining winner group procedure
1.	Input: set{ E (S₁) , E (S₂) , …, E (S_l) };
2.	for (i = 1 ; i < l ; i ++)
3.	{for (j = i + 1 ; i ⩽ l ; j ++)
{retrun E (dif_i,j) = E (S_i)· (E (S_j)) ^-1 = E (S_i - S_j) ; }
}
4.	Output: set{ E (dif_i,j) \|1 ⩽ i < l, 1 < j ⩽ l }

Then, auctioneer sends the

Set {E (dif_i,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. $\begin{matrix} {dif}_{i, j} = S_{i} - S_{j} \\ = decrypt (E ({dif}_{i, j}), a g . s k), \\ 1 ⩽ i < l, 1 < j ⩽ l, i, j \end{matrix}$

are integers.

Therefore, agent sorts all the bid sum groups by comparison and ranked in non-increasing order: $G' = {S_{1}^{'}, S_{2}^{'}, \dots S_{l}^{'}}, S_{\max} = S_{1}^{'} \geq S_{2}^{'}, \dots S_{l}^{'}$ (17)

Bidders from the highest of bid sum group S_max 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 S_max. The set of bidders’ ID from winner group S_max is denoted as: $ID = {{id}_{max, 1}, {id}_{max, 2}, \dots, {id}_{max, | max |}};$ (18)

In order to determine the spectrum price P, agent uses the random algorithm R (·) to select a bidder id_max,i, 1 ⩽ i ⩽ | max | from winners and its double encrypted bid value is denoted as E′ (b_max, r_max^′). Agent set the bidder id_max,i’s double encrypted bid E′ (P_i) = 0. Then the previous bid value is replaced with the bidder id_max,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 S_max is not rank fist, the spectrum price P = b_max is determined, otherwise, set P = 0.

The spectrum price P = decrypt ((E′ (b_max, r_max^′) , a u . s k) , a g . s k), and each winner is charged the price p = b_max/|S_max|.

4.3 The public verification of the winner group

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) = E (S_{win}) \cdot E^{- 1} (S_{{lose}_{i}}) = E (S_{win} - S_{{lose}_{i}})$ (19)

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 $r_{dif} \in Z_{n}^{*}$ to encrypt dif and gets the ciphertext C = E (dif, r_dif). Then, agent generates a certain test set TS_i publicly. The set of the ciphertext is TS_i = C = {C_{t
₁}, C_{t
₂} … , C_{t
_k}}, where . Agent sets dif = 2^{t
₁} + 2^{t
₂} + … +2^{t
_k} and calculates a new random $r_{i}^{*}$ , where $r_{i}^{*} = (r^{- 1} \times r_{t_{1}} \times r_{t_{2}} \dots \times r_{t_{k}}) (mod N)$ . Agent sends the $C, r_{i}^{*}$ to the bidders and bidders computes the equation: $E^{- 1} (dif, r) \cdot C_{t_{1}} \cdot \dots \cdot C_{t_{k}} (mod N^{2}) = E (0, r_{i}^{*})$ to decided whether to accept the verification or not. If the equation is established, agent can prove to those losing bidders and others that S_win > S_lose without leaking the original value publicly.

5 Performance analysis of SPSV protocol

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

Table 6
The computational overhead of auctioneer, agent and each bidder

auctioneer agent bidder

Initialization $\begin{matrix} 1 MUL, 1 DIV \\ 1 GCD, 1 LCM, 1 EX \end{matrix}$ $\begin{matrix} 1 MUL, 1 DIV \\ 1 GCD, 1 LCM, 1 EX \end{matrix}$

Bidding and spectrum allocation $\begin{matrix} 6 POW \\ 2 (2 POW + 1 MOD) \end{matrix}$

Determining winners $\begin{matrix} 2 n (3 DIV + 2 MOD + 2 POW), \\ [2 (n - g) + g (g - 1) / 2] MUL \end{matrix}$ $\begin{matrix} (3 DIV + 2 MOD + 2 POW) \\ \cdot [g (g - 1) / 2] \end{matrix}$

Determining spectrum price w ² MUL (w + 2) · (3DIV + 2MOD + 2POW)

auctioneer	agent	bidder
Initialization	$\begin{matrix} 1 MUL, 1 DIV \\ 1 GCD, 1 LCM, 1 EX \end{matrix}$	$\begin{matrix} 1 MUL, 1 DIV \\ 1 GCD, 1 LCM, 1 EX \end{matrix}$
Bidding and spectrum allocation	$\begin{matrix} 6 POW \\ 2 (2 POW + 1 MOD) \end{matrix}$
Determining winners	$\begin{matrix} 2 n (3 DIV + 2 MOD + 2 POW), \\ [2 (n - g) + g (g - 1) / 2] MUL \end{matrix}$	$\begin{matrix} (3 DIV + 2 MOD + 2 POW) \\ \cdot [g (g - 1) / 2] \end{matrix}$
Determining spectrum price	w ² MUL	(w + 2) · (3DIV + 2MOD + 2POW)

5.2 Analysis of simulation and results

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.

Fig.4

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.

Fig.5

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.

6 Conclusion and future work

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

References

Valenta ,

Maršálek ,

Baudoin , et al., Survey on spectrum utilization in Europe: Measurements, analyses and observations[C]//, Cognitive Radio Oriented Wireless Networks & Communications (CROWNCOM), 2010 Proceedings of the Fifth International Conference on IEEE, 2010, pp. 1–5.

Sepctrum Bridge,Inc, http://www.spectrumbridge.com

Gandhi ,

Buragohain ,

Cao , et al., A general framework for wireless spectrum auctions[C], New Frontiers in Dynamic Spectrum Access Networks, 2007 DySPAN 2007 2nd IEEE International Symposium on IEEE, 2007, pp. 22–33.

Wu ,

Wang ,

K.J.R.

Liu , et al., A multi-winner cognitive spectrum auction framework with collusion-resistant mechanisms[C], New Frontiers in Dynamic Spectrum Access Networks, 2008 DySPAN 2008 3rd IEEE Symposium on IEEE, 2008, pp. 1–9.

Zhou ,

Gandhi ,

Suri , et al., eBay in the sky: Strategy-proof wireless spectrum auctions[C], Proceedings of the 14th ACM International Conference on Mobile Computing and Networking ACM, 2008, pp. 2–13.

G.S.

Kasbekar and

Sarkar , Spectrum auction framework for access allocation in cognitive radio networks[J], IEEE/ACM Transactions on Networking (TON)18(6) (2010), 1841–1854.

Cramton , Spectrum auction design[J], Review of Industrial Organization42(2) (2013), 161–190.

Sengupta and

Chatterjee , An economic framework for dynamic spectrum access and service pricing[J], IEEE/ACM Transactions on Networking17(4) (2009), 1200–1213.

Pan ,

Chen ,

Yin , et al., Fair profit allocation in the spectrum auction using the shapley value[C], Global Telecommunications Conference, 2009 GLOBECOM 2009 IEEE IEEE, 2009, pp. 1–6.

10.

Zhang and

Zhang , Stackelberg game for utility-based cooperative cognitiveradio networks[C], Proceedings of the Tenth ACM International Symposium on Mobile ad Hoc Networking and Computing ACM, 2009, pp. 23–32.

11.

Zhou and

Zheng , Trust: A general framework for truthful double spectrum auctions[C], Infocom 2009, IEEE IEEE, 2009, pp. 999–1007.

12.

Wang ,

Ji ,

Zhou , et al., A Privacy Preserving Truthful Spectrum Auction Scheme Using Homomorphic Encryption[C], Global Communications Conference (GLOBECOM), 2015 IEEE IEEE, 2015, pp. 1–6.

13.

I.F.

Akyildiz ,

W.Y.

Lee ,

M.C.

Vuran , et al., Next generation/dynamic spectrum access/cognitive radio wireless networks: A survey[J], Computer Networks50(13) (2006), 2127–2159.

14.

Al-Ayyoub and

Gupta , Truthful spectrum auctions with approximate revenue, in INFOCOM’11, 2011.

15.

L.B.

Deek ,

Zhou ,

K.C.

Almeroth and

Zheng , To preempt or not: Tackling bid and time-based cheating in online spectrum auctions, in INFOCOM’11, 2011.

16.

Dong ,

Sun ,

Wang and

Zhang , Combinatorial auction with time-frequency flexibility in cognitive radio networks, in INFOCOM’12, 2012.

17.

Feng ,

Chen ,

Zhang ,

Zhang and

Li , TAHES: Truthful double auction for heterogeneous spectrums, in INFOCOM’12, 2012.

18.

Wang ,

Li ,

Xu ,

Gao and

H.-H.

Chen , Spectrum sharing in cognitive radio networks – an auction-based approach, IEEE Transactions on System, Man and Cybernetics–Part B: Cybernetics40(3) (2010), 587–596.

19.

Wu and

Vaidya , SMALL: A strategy-proof mechanism for radio spectrum allocation, in INFOCOM’11, 2011.

20.

Xu ,

X.-Y.

Li ,

Tang and

Zhao , Efficient and strategyproof spectrum allocations in multichannel wireless networks, IEEE Transactions on Computers60(4) (2011), 580–593.

21.

Xu ,

Tang and

X.-Y.

Li , Truthful online spectrum allocation and auction in multi-channel wireless networks, in INFOCOM’11, 2011.

22.

Zhou and

Zheng , TRUST: A general framework for truthful double spectrum auctions, in INFOCOM’09, 2009.

23.

McSherry and

Talwar , Mechanism design via differential privacy[C], Foundations of Computer Science, 2007 FOCS’07 48th Annual IEEE Symposium on IEEE, 2007, pp. 94–103.

24.

Pan ,

Sun and

Fang , Purging the back-room dealing: Secure spectrum auction leveraging paillier cryptosystem[J], IEEE Journal on Selected Areas in Communications29(4) (2011), 866–876.

25.

Naor ,

Pinkas and

Sumner , Privacy preserving auctions and mechanism design[C], Proceedings of the 1st ACM Conference on Electronic Commerce ACM, 1999, pp. 129–139.

26.

Xu ,

J.C.

Lui and

D.-M,

Chiu , On oligopoly spectrum allocation game in cognitive radio networks with capacity constraints.

27.

Gopinathan and

Li , Strategyproof wireless spectrum auctions with interference, In IEEE GLOBECOM, 2010, pp. 1–5.

28.

Huang ,

Y.-E.

Sun ,

X.-Y.

Li ,

Chen ,

Yang and

Xu , Near-optimal truthful spectrum auction mechanisms with spatial and temporal reuse in wireless networks, In ACM MOBIHOC, 2013.

29.

Zhu ,

Li and

Li , Truthful spectrum auction design for secondary networks, In IEEE INFOCOM, 2012, pp. 873–881.

30.

Huang ,

Tao and

Wu , Spring: A strategy-proof and privacy preserving spectrum auction mechanism[C], INFOCOM, 2013 Proceedings IEEE IEEE, 2013, pp. 827–835.

31.

Zhu ,

Li ,

Wu , et al., Differentially private spectrum auction with approximate revenue maximization[C], Proceedings of the 15th ACM International Symposium on Mobile ad hoc Networking and Computing ACM, 2014, pp. 185–194.

32.

Chen ,

Huang ,

Li , et al., PS-TRUST: Provably secure solution for truthful double spectrum auctions[C], INFOCOM, 2014 Proceedings IEEE IEEE, 2014, pp. 1249–1257.

33.

Li ,

Guo , et al., PPER: Privacy-preserving economic-robust spectrum auction in wireless networks[C], Computer Communications (INFOCOM), 2015 IEEE Conference on IEEE, 2015, pp. 909–917.

34.

Huang ,

X.Y.

Li ,

Sun , et al., PPS: Privacy-preserving strategyproof social-efficient spectrum auction mechanisms[J], IEEE Transactions on Parallel and Distributed Systems26(5) (2015), 1393–1404.

35.

Wu ,

Huang ,

Tao , et al., Towards privacy preservation in strategy-proof spectrum auction mechanisms for noncooperative wireless networks[J], IEEE/ACM Transactions on Networking (TON)23(4) (2015), 1271–1285.

36.

Chen ,

Huang , et al., Towards secure spectrum auction: Both bids and bidder locations matter: Poster[C], Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing ACM, 2016, pp. 361–362.

37.

Abdelhadi ,

Shajaiah and

Clancy , A multitier wireless spectrum sharing system leveraging secure spectrum auctions[J], IEEE Transactions on Cognitive Communications and Networking1(2) (2015), 217–229.

38.

Zhou ,

Niu ,

Zheng , et al., An Efficient, Privacy-Preserving, and Verifiable Online Auction Mechanism for Ad Exchanges[C], Global Communications Conference (GLOBECOM), 2015 IEEE IEEE, 2015, pp. 1–6.

39.

Feng ,

Chen ,

Zhang ,

Zhang and

Li , TAHES: A truthful double auction mechanism for heterogeneous spectrums.

40.

Gupta and

P.R.

Kumar , The capacity of wireless networks, IEEE Trans inf Theory46(2) (2000), 388–404.

41.

Jain ,

Padhye ,

V.N.

Padmanabhan and

Qiu , Impact of interference on multi-hop wireless network performance, in Proc ACMMOBICOM, 2003, PP. 66–80.

42.

Zheng ,

Wu ,

Tang and

Chen , Unknown combinatorial auction mechanisms for heterogeneous spectrum redistribution, in Proceedings of the 15th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Philadelphia, PA, USA, 2014.

43.

Nian ,

Roughgarden ,

Tardos and

V.V.

Vazirani , Algorithmic Game Theory, Cambridge, U.K.: Cambridge Univ Press, 2007.

44.

Wang ,

Ye ,

Xu , et al., Approximately truthful mechanisms for radio spectrum allocation[J], IEEE Transactions on Vehicular Technology64(6) (2015), 2615–2626.

45.

Paillier , Public-key cryptosystems based on composite degree residuosity classes, In: International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 1999, pp. 223–238.

46.

D.C.

Parkes ,

M.O.

Rabin ,

S.M.

Shieber , et al., Practical secrecy-preserving, verifiably correct and trustworthy auctions[J], Electronic Commerce Research and Applications7(3) (2008), 294–312.

47.

48.

M.O.

Rabin , How to exchange secrets with oblivious transfer[J], IACR Cryptology ePrint Archive 2005 (2005), 187.

49.

W.G.

Tzeng , Efficient 1-out-of-n oblivious transfer schemes with universally usable parameters[J], IEEE Transactions on Computers53(2) (2004), 232–240.

Group ID	Bidder ID	Double Encrypted Bid	Double Encrypted Negative Bid
1	id_1₁, id_1₂, …, id_{1_\|g₁\|}	$E_{1, 1}^{'}, E_{1, 2'}, \dots E_{1, \| g 1 \|'}$	${(E_{1, 1}^{'})}^{- 1}, {(E_{1, 2}^{'})}^{- 1}, \dots {(E_{1, \| g 1 \|}^{'})}^{- 1}$
2	id_2₁, id_2₂, …, id_{2_\|g₂\|}	$E_{2, 1}^{'}, E_{2, 2'}, \dots E_{2, \| g 2 \|'}$	${(E_{2, 1}^{'})}^{- 1}, {(E_{2, 2}^{'})}^{- 1}, \dots {(E_{2, \| g 2 \|}^{'})}^{- 1}$
…	…	…	…
l	id_{l ₁}, id_{l ₂}, …, id_{l _{\|g_l\|}}	$E_{l, 1}^{'}, E_{l, 2'}, \dots E_{l, \| g l \|'}$	${(E_{l, 1}^{'})}^{- 1}, {(E_{l, 2}^{'})}^{- 1}, \dots {(E_{l, \| g l \|}^{'})}^{- 1}$