1. bookVolume 2017 (2017): Issue 4 (October 2017)
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year
access type Open Access

Provably Secure Anonymous-yet-Accountable Crowdsensing with Scalable Sublinear Revocation

Published Online: 10 Oct 2017
Page range: 384 - 403
Received: 28 Feb 2017
Accepted: 02 Jun 2017
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year

Group signature schemes enable anonymous-yet-accountable communications. Such a capability is extremely useful for applications, such as smartphone-based crowdsensing and citizen science. However, the performance of modern group signature schemes is still inadequate to manage large dynamic groups. In this paper, we design the first provably secure verifier-local revocation (VLR) - based group signature scheme that supports sublinear revocation, named Sublinear Revocation with Backward unlinkability and Exculpability (SRBE). To achieve this performance gain, SRBE introduces time bound pseudonyms for the signer. By introducing low-cost short-lived pseudonyms with sublinear revocation checking, SRBE drastically improves the efficiency of the group-signature primitive. The backward-unlinkable anonymity of SRBE guarantees that even after the revocation of a signer, her previously generated signatures remain unlinkable across epochs. This behavior favors the dynamic nature of real-world crowdsensing settings. We prove its security and discuss parameters that influence its scalability. Using SRBE, we also implement a prototype named GroupSense for anonymous-yet-accountable crowdsensing, where our experimental findings confirm GroupSense’s scalability. We point out the open problems remaining in this space.


[1] Mu Lin, Nicholas D. Lane, Mashfiqui Mohammod, Xiaochao Yang, Hong Lu, Giuseppe Cardone, Shahid Ali, Afsaneh Doryab, Ethan Berke, Andrew T. Campbell, and Tanzeem Choudhury. Bewell+: multi-dimensional wellbeing monitoring with community-guided user feedback and energy optimization. In Wireless Health ’12, pages 1–8, 2012.Search in Google Scholar

[2] Eiman Kanjo. Noisespy: A real-time mobile phone platform for urban noise monitoring and mapping. Mobile Networks and Applications, 15(4):562–574, 2010.Search in Google Scholar

[3] Bei Pan, Yu Zheng, David Wilkie, and Cyrus Shahabi. Crowd sensing of traffic anomalies based on human mobility and social media. In SIGSPATIAL ’13, pages 344–353, 2013.Search in Google Scholar

[4] R. K. Ganti, F. Ye, and H. Lei. Mobile crowdsensing: current state and future challenges. IEEE Communications Magazine, 49(11):32–39, 2011.10.1109/MCOM.2011.6069707Open DOISearch in Google Scholar

[5] Raluca Ada Popa, Andrew J. Blumberg, Hari Balakrishnan, and Frank H. Li. Privacy and accountability for location-based aggregate statistics. In ACM CCS ’11, pages 653–666, 2011.Search in Google Scholar

[6] Delphine Christin. Privacy in mobile participatory sensing: Current trends and future challenges. Journal of Systems and Software, 116:57–68, 2016.Search in Google Scholar

[7] Leyla Kazemi and Cyrus Shahabi. A privacy-aware framework for participatory sensing. SIGKDD, 13(1):43–51, 2011.Search in Google Scholar

[8] Facebook urged to tighten privacy settings after harvest of user data. www.theguardian.com/technology/2015/aug/09/facebook-privacy-settings-users-mobile-phone-number, August 2015. [Online; accessed 16-May-2016].Search in Google Scholar

[9] NSA Prism program taps in to user data of Apple, Google and others. http://www.theguardian.com/world/2013/jun/06/us-tech-giants-nsa-data, June 2013. [Online; accessed 16-May-2016].Search in Google Scholar

[10] Facebook admits year-long data breach exposed 6 million users. http://www.reuters.com/article/net-us-facebook-security-idUSBRE95K18Y20130621, June 2013. [Online; accessed 16-May-2016].Search in Google Scholar

[11] Vireshwar Kumar, He Li, Jung-Min “Jerry” Park, Kaigui Bian, and Yaling Yang. Group signatures with probabilistic revocation: A computationally-scalable approach for providing privacy-preserving authentication. In ACM CCS ’15, pages 1334–1345, 2015.Search in Google Scholar

[12] Anna Lysyanskaya, Ronald L. Rivest, Amit Sahai, and Stefan Wolf. Pseudonym systems. In SAC’99, pages 184–199, 1999.Search in Google Scholar

[13] David Chaum. Security without identification: Transaction systems to make big brother obsolete. Commun. ACM, 28(10):1030–1044, 1985.Search in Google Scholar

[14] David Chaum and Eugène van Heyst. Group signatures. In EUROCRYPT ’91, pages 257–265, 1991.Search in Google Scholar

[15] Aggelos Kiayias, Yiannis Tsiounis, and Moti Yung. Traceable signatures. In EUROCRYPT 2004, pages 571–589, 2004.Search in Google Scholar

[16] Dan Boneh and Hovav Shacham. Group signatures with verifier-local revocation. In ACM CCS ’04, pages 168–177, 2004.Search in Google Scholar

[17] Maxim Raya and Jean-Pierre Hubaux. Securing vehicular ad hoc networks. Journal of Computer Security, 15(1):39–68, 2007.10.3233/JCS-2007-15103Open DOISearch in Google Scholar

[18] Xiaodong Lin, Xiaoting Sun, Pin-Han Ho, and Xuemin Shen. GSIS: A secure and privacy-preserving protocol for vehicular communications. IEEE Trans. Vehicular Technology, 56(6):3442–3456, 2007.Search in Google Scholar

[19] Giuseppe Ateniese, Jan Camenisch, Marc Joye, and Gene Tsudik. A practical and provably secure coalition-resistant group signature scheme. In CRYPTO 2000, pages 255–270, 2000.Search in Google Scholar

[20] Mihir Bellare, Daniele Micciancio, and Bogdan Warinschi. Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions. In EUROCRYPT ’03, pages 614–629, 2003.Search in Google Scholar

[21] Daniel Slamanig, Raphael Spreitzer, and Thomas Unterluggauer. Group signatures with linking-based revocation: A pragmatic approach for efficient revocation checks. In MyCrypt 2016, 2016. to appear.Search in Google Scholar

[22] Julien Bringer and Alain Patey. Backward unlinkability for a VLR group signature scheme with efficient revocation check. IACR Cryptology ePrint Archive, 2011:376, 2011.Search in Google Scholar

[23] Toru Nakanishi, Hiroki Fujii, Yuta Hira, and Nobuo Funabiki. Revocable group signature schemes with constant costs for signing and verifying. In PKC 2009, pages 463–480, 2009.Search in Google Scholar

[24] Mark Manulis, Nils Fleischhacker, F Gunther, K Franziskus, and Bertram Poettering. Group signatures: Authentication with privacy. Bundesamt fur Sicherheit in der Informationstechnik. Tech. Rep, 2012.Search in Google Scholar

[25] Dan Boneh and Xavier Boyen. Short signatures without random oracles and the SDH assumption in bilinear groups. J. Cryptology, 21(2):149–177, 2008.Search in Google Scholar

[26] Patrik Bichsel, Jan Camenisch, Gregory Neven, Nigel P. Smart, and Bogdan Warinschi. Get shorty via group signatures without encryption. In Security and Cryptography for Networks SCN ’10, pages 381–398, 2010.Search in Google Scholar

[27] Stylianos Gisdakis, Thanassis Giannetsos, and Panos Papadimitratos. SPPEAR: security & privacy-preserving architecture for participatory-sensing applications. In WiSec ’14, pages 39–50, 2014.Search in Google Scholar

[28] Cory Cornelius, Apu Kapadia, David Kotz, Dan Peebles, Minho Shin, and Nikos Triandopoulos. Anonysense: Privacyaware people-centric sensing. In MobiSys ’08, pages 211–224, 2008.Search in Google Scholar

[29] Ioannis Boutsis and Vana Kalogeraki. Privacy preservation for participatory sensing data. In IEEE Pervasive Computing and Communications (PerCom) ’13, pages 103–113, 2013.Search in Google Scholar

[30] Emiliano De Cristofaro and Claudio Soriente. Extended capabilities for a privacy-enhanced participatory sensing infrastructure (PEPSI). IEEE Trans. Information Forensics and Security, 8(12):2021–2033, 2013.Search in Google Scholar

[31] Leyla Kazemi and Cyrus Shahabi. TAPAS: trustworthy privacy-aware participatory sensing. Knowl. Inf. Syst., 37(1):105–128, 2013.10.1007/s10115-012-0573-yOpen DOISearch in Google Scholar

[32] Keita Emura and Takuya Hayashi. A light-weight group signature scheme with time-token dependent linking. In Lightweight Cryptography for Security and Privacy 2015, pages 37–57, 2015.Search in Google Scholar

[33] Citizen Science Alliance. http://www.citizensciencealliance.org/. [Online; accessed 04-August-2016].Search in Google Scholar

[34] Seung Geol Choi, Kunsoo Park, and Moti Yung. Short traceable signatures based on bilinear pairings. In IWSEC 2006, pages 88–103, 2006.Search in Google Scholar

[35] Vicente Benjumea, Seung Geol Choi, Javier Lopez, and Moti Yung. Fair traceable multi-group signatures. In Financial Cryptography and Data Security, 2008, pages 231–246, 2008.Search in Google Scholar

[36] Jan Camenisch and Anna Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In CRYPTO ’04, pages 56–72, 2004.Search in Google Scholar

[37] Benoît Libert and Moti Yung. Efficient traceable signatures in the standard model. In Pairing-Based Cryptography - Pairing 2009, pages 187–205, 2009.Search in Google Scholar

[38] Benoît Libert, Thomas Peters, and Moti Yung. Short group signatures via structure-preserving signatures: Standard model security from simple assumptions. In CRYPTO ’15, pages 296–316, 2015.Search in Google Scholar

[39] Jung Yeon Hwang, Sokjoon Lee, Byung-Ho Chung, Hyun Sook Cho, and DaeHun Nyang. Group signatures with controllable linkability for dynamic membership. Inf. Sci., 222:761–778, 2013.Search in Google Scholar

[40] Daniel Slamanig, Raphael Spreitzer, and Thomas Unterluggauer. Adding controllable linkability to pairing-based group signatures for free. In Information Security - 17th International Conference, ISC 2014, pages 388–400, 2014.Search in Google Scholar

[41] Essam Ghadafi. Efficient distributed tag-based encryption and its application to group signatures with efficient distributed traceability. In LATINCRYPT 2014, pages 327–347, 2014.Search in Google Scholar

[42] Toru Nakanishi and Nobuo Funabiki. Efficient revocable group signature schemes using primes. JIP, 16:110–121, 2008.Search in Google Scholar

[43] Jan Camenisch and Anna Lysyanskaya. Dynamic accumulators and application to efficient revocation of anonymous credentials. In CRYPTO 2002, pages 61–76, 2002.Search in Google Scholar

[44] Jorn Lapon, Markulf Kohlweiss, Bart De Decker, and Vincent Naessens. Performance analysis of accumulator-based revocation mechanisms. In Security and Privacy - Silver Linings in the Cloud - 25th IFIP TC-11 International Information Security Conference, SEC 2010, Held as Part of WCC 2010, pages 289–301, 2010.Search in Google Scholar

[45] Chun-I Fan, Ruei-Hau Hsu, and Mark Manulis. Group signature with constant revocation costs for signers and verifiers. In Cryptology and Network Security CANS 2011, pages 214–233, 2011.Search in Google Scholar

[46] Jan Camenisch, Manu Drijvers, and Jan Hajny. Scalable revocation scheme for anonymous credentials based on n-times unlinkable proofs. In Proceedings of the 2016 ACM on Workshop on Privacy in the Electronic Society, WPES ’16, pages 123–133, New York, NY, USA, 2016. ACM.Search in Google Scholar

[47] Markulf Kohlweiss and Ian Miers. Accountable metadata-hiding escrow: A group signature case study. PoPETs, 2015(2):206–221, 2015.Search in Google Scholar

[48] Cheng-Kang Chu, Joseph K. Liu, Xinyi Huang, and Jianying Zhou. Verifier-local revocation group signatures with time-bound keys. In ACM ASIACCS ’12, pages 26–27, 2012.Search in Google Scholar

[49] Toru Nakanishi and Nobuo Funabiki. Verifier-local revocation group signature schemes with backward unlinkability from bilinear maps. IEICE Transactions, 90-A(1):65–74, 2007.Search in Google Scholar

[50] Jens Groth and Amit Sahai. Efficient non-interactive proof systems for bilinear groups. In EUROCRYPT 2008, pages 415–432, 2008.Search in Google Scholar

[51] Benoît Libert, Thomas Peters, and Moti Yung. Scalable group signatures with revocation. In EUROCRYPT 2012, pages 609–627, 2012.Search in Google Scholar

[52] Benoît Libert, Thomas Peters, and Moti Yung. Group signatures with almost-for-free revocation. In CRYPTO 2012, pages 571–589, 2012.Search in Google Scholar

[53] Nuttapong Attrapadung, Keita Emura, Goichiro Hanaoka, and Yusuke Sakai. A revocable group signature scheme from identity-based revocation techniques: Achieving constantsize revocation list. In Applied Cryptography and Network Security - 12th International Conference, ACNS 2014, pages 419–437, 2014.Search in Google Scholar

[54] Kazuma Ohara, Keita Emura, Goichiro Hanaoka, Ai Ishida, Kazuo Ohta, and Yusuke Sakai. Shortening the libert-peters-yung revocable group signature scheme by using the random oracle methodology. IACR Cryptology ePrint Archive, 2016:477, 2016.Search in Google Scholar

[55] Wouter Lueks, Gergely Alpár, Jaap-Henk Hoepman, and Pim Vullers. Fast revocation of attribute-based credentials for both users and verifiers. In IFIP ’15, pages 463–478, 2015.Search in Google Scholar

[56] Eric R. Verheul. Practical backward unlinkable revocation in fido, german e-id, idemix and u-prove. IACR Cryptology ePrint Archive, 2016:217, 2016.Search in Google Scholar

[57] Katie Shilton, Jeffrey A Burke, Deborah Estrin, Mark Hansen, and Mani Srivastava. Participatory privacy in urban sensing. In International Workshop on Mobile Device and Urban Sensing (MODUS), 2008.Search in Google Scholar

[58] Apu Kapadia, David Kotz, and Nikos Triandopoulos. Opportunistic sensing: Security challenges for the new paradigm. In 2009 First International Communication Systems and Networks and Workshops, pages 1–10. IEEE, 2009.Search in Google Scholar

[59] Stylianos Gisdakis, Thanassis Giannetsos, and Panos Papadimitratos. Security, privacy & incentive provision for mobile crowd sensing systems. IEEE IoT, 2016.Search in Google Scholar

[60] Gang Wang, Bolun Wang, Tianyi Wang, Ana Nika, Haitao Zheng, and Ben Y. Zhao. Defending against sybil devices in crowdsourced mapping services. In MobiSys ’16, 2016.Search in Google Scholar

[61] Dan Boneh and Xavier Boyen. Short signatures without random oracles. In Christian Cachin and Jan Camenisch, editors, EUROCRYPT’04, volume 3027 of Lecture Notes in Computer Science, pages 56–73, 2004.Search in Google Scholar

[62] Liqun Chen and Jiangtao Li. VLR group signatures with indisputable exculpability and efficient revocation. IJIPSI, 1(2/3):129–159, 2012.Search in Google Scholar

[63] Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the weil pairing. J. Cryptology, 17(4):297–319, 2004.Search in Google Scholar

[64] Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In EUROCRYPT 2003, pages 416–432, 2003.Search in Google Scholar

[65] Danfeng Yao and Roberto Tamassia. Compact and anonymous role-based authorization chain. ACM Trans. Inf. Syst. Sec., 12(3):15:1–15:27, 2009.Search in Google Scholar

[66] Dan Boneh and Matthew K. Franklin. Identity-based encryption from the weil pairing. SIAM J. Comput., 32(3):586–615, 2003.10.1137/S0097539701398521Open DOISearch in Google Scholar

[67] Saman Zarandioon, Danfeng (Daphne) Yao, and Vinod Ganapathy. K2C: cryptographic cloud storage with lazy revocation and anonymous access. In SecureComm 2011, pages 59–76, 2011.Search in Google Scholar

[68] Danfeng Yao, Nelly Fazio, Yevgeniy Dodis, and Anna Lysyanskaya. Id-based encryption for complex hierarchies with applications to forward security and broadcast encryption. In ACM CCS 2004, pages 354–363, 2004.Search in Google Scholar

[69] Dan Boneh, Xavier Boyen, and Hovav Shacham. Short group signatures. In CRYPTO ’04, pages 41–55, 2004.Search in Google Scholar

[70] Hovav Shacham. New paradigms in signature schemes. PhD thesis, Stanford University, 2005.Search in Google Scholar

[71] Steven D. Galbraith, Kenneth G. Paterson, and Nigel P. Smart. Pairings for cryptographers. Discrete Applied Mathematics, 156(16):3113 – 3121, 2008. Applications of Algebra to Cryptography.Search in Google Scholar

[72] Atsuko Miyaji, Masaki Nakabayashi, and Shunzou Takano. New explicit conditions of elliptic curve traces for FR-reduction. IEICE transactions on fundamentals of electronics, communications and computer sciences, 84(5):1234–1243, 2001.Search in Google Scholar

[73] Xiaoyan Zhu, Haotian Chi, Shunrong Jiang, Xiaosan Lei, and Hui Li. Using dynamic pseudo-IDs to protect privacy in location-based services. In IEEE ICC ’14, pages 2307–2312, 2014.Search in Google Scholar

[74] Francesco Restuccia, Sajal K. Das, and Jamie Payton. Incentive mechanisms for participatory sensing: Survey and research challenges. ACM Trans. Sen. Netw., 12(2):13:1–13:40, 2016.Search in Google Scholar

[75] L. Cheng, L. Kong, C. Luo, J. Niu, Y. Gu, W. He, and S. Das. False data detection and correction framework for participatory sensing. In IWQoS ’15, pages 213–218, 2015.Search in Google Scholar

[76] John R. Douceur. The sybil attack. In Peter Druschel, M. Frans Kaashoek, and Antony I. T. Rowstron, editors, IPTPS ’02, volume 2429 of Lecture Notes in Computer Science, pages 251–260, 2002.Search in Google Scholar

[77] Ben Lynn. Pbc (pairing-based cryptography) library. https://crypto.stanford.edu/pbc/, 2016. [Online; accessed 16-May-2016].Search in Google Scholar

[78] Angelo De Caro and Vincenzo Iovino. jpbc: Java pairing based cryptography. In IEEE ISCC ’11, pages 850–855. IEEE, 2011.Search in Google Scholar

[79] Kenji Koyama and Yukio Tsuruoka. Speeding up elliptic cryptosystems by using a signed binary window method. In CRYPTO ’92, pages 345–357, 1992.Search in Google Scholar

[80] Klaus Potzmader and Johannes Winter et al. Group signatures on mobile devices: Practical experiences. In Trust and Trustworthy Computing, pages 47–64, 2013.Search in Google Scholar

[81] David Pointcheval and Jacques Stern. Security arguments for digital signatures and blind signatures. J. Cryptology, 13(3):361–396, 2000.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo