research-article

PPS: Privacy-Preserving Strategyproof Social-Efficient Spectrum Auction Mechanisms

Authors:

Liusheng HuangAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 26, Issue 5

Pages 1393 - 1404

https://doi.org/10.1109/TPDS.2014.2315200

Published: 01 May 2015 Publication History

Abstract

Many spectrum auction mechanisms have been proposed for spectrum allocation problem, and unfortunately, few of them protect the bid privacy of bidders and achieve good social efficiency. In this paper, we propose PPS, a Privacy Preserving Strategyproof spectrum auction framework. We design two schemes based on PPS separately for 1) the single-unit auction model (SUA), where only single channel will be sold in the spectrum market; and 2) the multi-unit auction model (MUA), where the primary user subleases multi-unit channels to the secondary users and each of the secondary users wants to access multi-unit channels either. Since the social efficiency maximization problem is NP-hard in both auction models, we present allocation mechanisms with approximation factors of (1 + ε) and 32 separately for SUA and MUA, and further judiciously design strategyproof auction mechanisms with privacy preserving based on them. Our extensive evaluations show that our mechanisms achieve good social efficiency and with low computation and communication overhead.

References

[1]

G. Aggarwal, N. Mishra, and B. Pinkas, “Secure computation of the kth -ranked element”, Proc. Adv. Cryptology, 2004, pp. 40–55.

[2]

M. Al-Ayyoub, and H. Gupta, “Truthful spectrum auctions with approximate revenue”, Proc. IEEE Conf. Comput. Commun., 2011, pp. 2813–2821.

[3]

F. Brandt, and T. Sandholm, “On the existence of unconditionally privacy-preserving auction protocols”, ACM Trans. Inf. Syst. Secur., vol. 11, no. 2article 6, Mar. 2008.

[4]

C. Cachin, “Efficient private bidding and auctions with an oblivious third party”, Proc. 6th ACM Conf. Comput. Commun. Security, 1999, pp. 120– 127.

Digital Library

[5]

I. Damgård, M. Geisler, and M. Krøigaard, “Efficient and secure comparison for on-line auctions”, Proc. 12th Australasian Conf. Inf. Security Privacy, 2007, pp. 416 –430.

Digital Library

[6]

I. Damgård, M. Geisler, and M. Krøigaard, “Homomorphic encryption and secure comparison”, Int. J. Appl. Cryptography, vol. 1, no. 1, pp. 22 –31, 2008.

Digital Library

[7]

L. Deek, X. Zhou, K. Almeroth, and H. Zheng, “To preempt or not: Tackling bid and time-based cheating in online spectrum auctions”, Proc. IEEE Conf. Comput. Commun., 2011, pp. 2219–2227.

[8]

M. Dong, G. Sun, X. Wang, and Q. Zhang, “Combinatorial auction with time-frequency flexibility in cognitive radio networks”, Proc. IEEE Conf. Comput. Commun., 2012, pp. 2282–2290.

[9]

W. Du, and M. J. Atallah, “Secure multi-party computation problems and their applications: A review and open problems”, Proc. Workshop New Security Paradigms, 2001, pp. 13–22.

[10]

A. Gopinathan, and Z. Li, “Strategyproof wireless spectrum auctions with interference”, Proc. IEEE Global Telecommun. Conf., 2010, pp. 1–5.

[11]

A. Gopinathan, Z. Li, and C. Wu, “Strategyproof auctions for balancing social welfare and fairness in secondary spectrum markets”, Proc. IEEE Conf. Comput. Commun., 2011, pp. 2813–2821.

[12]

H. Huang, Y. Sun, X.-Y. Li, Z. Chen, W. Yang, and H. Xu, “Near-optimal truthful spectrum auction mechanisms with spatial and temporal reuse in wireless networks”, Proc. 14th ACM Int. Symp. Mobile Ad Hoc Netw. Comput., 2013, pp. 237 –240.

[13]

Q. Huang, Y. Tao, and F. Wu, “SPRING: A strategy-proof and privacy preserving spectrum auction mechanism”, Proc. IEEE Conf. Comput. Commun., 2013, pp. 851–859 .

[14]

H. Hunt III, M. Marathe, V. Radhakrishnan, S. Ravi, D. Rosenkrantz, and R. Stearns, “NC-approximation schemes for NP-and PSPACE-hard problems for geometric graphs”, J. Algorithms, vol. 26, no. 2, pp. 238– 274, 1998.

[15]

J. Jia, Q. Zhang, Q. Zhang, and M. Liu, “Revenue generation for truthful spectrum auction in dynamic spectrum access”, Proc. 10th ACM Int. Symp. Mobile Ad Hoc Netw. Comput., 2009, pp. 3 –12.

[16]

T. Jung and X.-Y. Li, “Collusion-tolerable privacy-preserving sum and product calculation without secure channel,” IEEE Trans. Dependable Secure Comput, 2014.

[17]

T. Jung, X.-Y. Li, and S. Tang, “Privacy-preserving data aggregation without secure channel: Multivariate polynomial evaluation”, Proc. IEEE Conf. Comput. Commun., 2013, pp. 2634–2642.

[18]

T. Jung, X.-Y. Li, Z. Wan, and M. Wan, “Privacy preserving cloud data access with multi-authorities”, Proc. IEEE Conf. Comput. Commun., 2013, pp. 2625–2633.

[19]

V. Krishna, Auction Theory, San Diego, CA, USA: Academic, 2009.

[20]

K. Lai, and M. Goemans, “The knapsack problem and fully polynomial time approximation schemes (FPTAS)”, Retrieved November, vol. 3, pp. 2012–, Mar. 2006.

[21]

Q. Li, and G. Cao, “Providing privacy-aware incentives for mobile sensing”, Proc. IEEE Int. Conf. Pervasive Comput. Commun., 2013, pp. 76– 84.

[22]

X.-Y. Li, and T. Jung, “Search me if you can: Privacy-preserving location query service”, Proc. IEEE Conf. Comput. Commun., 2013, pp. 2760–2768 .

[23]

X.-Y. Li, and Y. Wang, “Simple approximation algorithms and PTASs for various problems in wireless ad hoc networks”, J. Parallel Distrib. Comput., vol. 66, no. 4, pp. 515 –530, 2006.

Digital Library

[24]

M. Naor, B. Pinkas, and R. Sumner, “Privacy preserving auctions and mechanism design”, Proc. 1st ACM Conf. Electron. Commerce, 1999, pp. 129–139.

Digital Library

[25]

N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Algorithmic Game Theory, Cambridge, U.K.: Cambridge Univ. Press, 2007.

[26]

M. Pan, J. Sun, and Y. Fang, “Purging the back-room dealing: Secure spectrum auction leveraging paillier cryptosystem”, IEEE J. Sel. Areas Commun., vol. 29, no. 4, pp. 866 –876, Apr. 2011.

Digital Library

[27]

X. Sui, and C. Boutilier, “Efficiency and privacy tradeoffs in mechanism design”, Proc. IEEE 25th AAAI Conf. Artif. Intell., 2011, pp. 738– 744.

[28]

S. G. Wang, P. Xu, X. H. Xu, S. J. Tang, X. Y. Li, and X. Liu, “TODA: Truthful online double auction for spectrum allocation in wireless networks”, Proc. IEEE Symp. New Frontiers Dyn. Spectr., 2010, pp. 1–10.

[29]

W. Wang, B. Li, and B. Liang, “District: Embracing local markets in truthful spectrum double auctions”, Proc. 8th Annu. IEEE Commun. Soc. Conf. Sensor, Mesh Ad Hoc Commun. Netw., 2011, pp. 521–529.

[30]

F. Wu, and N. Vaidya, “SMALL: A strategy-proof mechanism for radio spectrum allocation”, Proc. IEEE Conf. Comput. Commun., 2011, pp. 3020–3028.

[31]

H. Xu, J. Jin, and B. Li, “A secondary market for spectrum ”, Proc. IEEE Conf. Comput. Commun., 2010, pp. 1–5.

[32]

P. Xu, X. Y. Li, and S. Tang, “Efficient and strategyproof spectrum allocations in multichannel wireless networks”, IEEE Trans. Comput., vol. 60, no. 4, pp. 580– 593, Apr. 2011.

Digital Library

[33]

P. Xu, S. G. Wang, and X. Y. Li, “SALSA: Strategyproof online spectrum admissions for wireless networks”, IEEE Trans. Comput., vol. 59, no. 12, pp. 1691– 1702, Dec. 2010.

Digital Library

[34]

P. Xu, X. Xu, S. Tang, and X.-Y. Li, “Truthful online spectrum allocation and auction in multi-channel wireless networks”, Proc. IEEE Conf. Comput. Commun., 2011, pp. 26–30.

[35]

Andrew Chi-Chih Yao, “Protocols for secure computations ”, Proc. 23rd Annu. Symp. Found. Comput. Sci., 1982, pp. 160– 164.

Digital Library

[36]

S. Yin, D. Chen, Q. Zhang, M. Liu, and S. Li, “Mining spectrum usage data: A large-scale spectrum measurement study”, IEEE Trans. Mobile Comput., vol. 11, no. 6, pp. 1033 –1046, Jun. 2012.

Digital Library

[37]

Z. Zheng, F. Wu, and G. Chen, “SMASHER: Strategy-proof combinatorial auction mechanisms for heterogeneous channel redistribution”, Proc. 14th ACM Int. Symp. Mobile Ad Hoc Netw. Comput., 2013, pp. 305 –308.

[38]

X. Zhou, S. Gandhi, S. Suri, and H. Zheng, “eBay in the sky: Strategy-proof wireless spectrum auctions”, Proc. 14th ACM Int. Conf. Mobile Comput. Netw., 2008, pp. 2– 13.

[39]

X. Zhou, and H. Zheng, “TRUST: A general framework for truthful double spectrum auctions”, Proc. IEEE Conf. Comput. Commun., 2009, pp. 999–1007 .

[40]

Y. Zhu, B. Li, and Z. Li, “Truthful spectrum auction design for secondary networks”, Proc. IEEE Conf. Comput. Commun., 2012, pp. 873–881 .

[41]

Y. Zhu, B. Li, and Z. Li, “Core-selecting combinatorial auction design for secondary spectrum markets”, Proc. IEEE Conf. Comput. Commun., 2013, pp. 1986–1994.

Cited By

Abozariba RAsaduzzaman MPatwary MNaeem MNawaz SSharma S(2022)Secondary spectrum allocation framework via concurrent auctions for 5G and beyond networksWireless Networks10.1007/s11276-022-02896-z28:4(1489-1504)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1007/s11276-022-02896-z
Hu YZhang R(2019)Differentially-Private Incentive Mechanism for Crowdsourced Radio Environment Map ConstructionIEEE INFOCOM 2019 - IEEE Conference on Computer Communications10.1109/INFOCOM.2019.8737512(1594-1602)Online publication date: 29-Apr-2019
https://dl.acm.org/doi/10.1109/INFOCOM.2019.8737512
Cui JSun YHuang HGuo HDu YYang WLi M(2018)TCAM: A truthful combinatorial auction mechanism for crowdsourcing systems2018 IEEE Wireless Communications and Networking Conference (WCNC)10.1109/WCNC.2018.8377240(1-6)Online publication date: 15-Apr-2018
https://dl.acm.org/doi/10.1109/WCNC.2018.8377240
Show More Cited By

Index Terms

PPS: Privacy-Preserving Strategyproof Social-Efficient Spectrum Auction Mechanisms

Index terms have been assigned to the content through auto-classification.

Recommendations

Differentially private spectrum auction with approximate revenue maximization
MobiHoc '14: Proceedings of the 15th ACM international symposium on Mobile ad hoc networking and computing

Dynamic spectrum redistribution---under which spectrum owners lease out under-utilized spectrum to users for financial gain---is an effective way to improve spectrum utilization. Auction is a natural way to incentivize spectrum owners to share their idle ...
Adaptive Auction Framework for Spectrum Market in Cognitive Radio Networks

For the recent decade, cognitive radio networks have received much attention as an alternative to the traditional static spectrum allocation policy since the licensed spectrum channels are not being used efficiently. The most critical issue of the ...
Approximately-strategyproof and tractable multi-unit auctions
EC '03: Proceedings of the 4th ACM conference on Electronic commerce

We present an approximately-efficient and approximately-strategyproof auction mechanism for a single-good multi-unit allocation problem. The bidding language in our auctions allows marginal-decreasing piecewise constant curves. First, we develop a fully ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 26, Issue 5

May 2015

291 pages

ISSN:1045-9219

Issue’s Table of Contents

Copyright © 2014.

Publisher

IEEE Press

Publication History

Published: 01 May 2015

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Abozariba RAsaduzzaman MPatwary MNaeem MNawaz SSharma S(2022)Secondary spectrum allocation framework via concurrent auctions for 5G and beyond networksWireless Networks10.1007/s11276-022-02896-z28:4(1489-1504)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1007/s11276-022-02896-z
Hu YZhang R(2019)Differentially-Private Incentive Mechanism for Crowdsourced Radio Environment Map ConstructionIEEE INFOCOM 2019 - IEEE Conference on Computer Communications10.1109/INFOCOM.2019.8737512(1594-1602)Online publication date: 29-Apr-2019
https://dl.acm.org/doi/10.1109/INFOCOM.2019.8737512
Cui JSun YHuang HGuo HDu YYang WLi M(2018)TCAM: A truthful combinatorial auction mechanism for crowdsourcing systems2018 IEEE Wireless Communications and Networking Conference (WCNC)10.1109/WCNC.2018.8377240(1-6)Online publication date: 15-Apr-2018
https://dl.acm.org/doi/10.1109/WCNC.2018.8377240
Chen ZChen SZhong HChen LTian M(2018)PP-MCSA: Privacy Preserving Multi-channel Double Spectrum AuctionInformation and Communications Security10.1007/978-3-030-01950-1_15(248-267)Online publication date: 29-Oct-2018
https://dl.acm.org/doi/10.1007/978-3-030-01950-1_15
Errapotu SWang JLu ZLi WPan MHan Z(2016)Bidding Privacy Preservation for Dynamic Matching Based Spectrum Trading2016 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOCOM.2016.7841629(1-6)Online publication date: 4-Dec-2016
https://dl.acm.org/doi/10.1109/GLOCOM.2016.7841629

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents