Using Range-Revocable Pseudonyms to Provide Backward Unlinkability in the Edge
Pages 3018 - 3032
Abstract
In this paper we propose a novel abstraction that we have named Range-Revocable Pseudonyms (RRPs). RRPs are a new class of pseudonyms whose validity can be revoked for any time-range within its original validity period. The key feature of RRPs is that the information provided to revoke a pseudonym for a given time-range cannot be linked with the information provided when using the pseudonym outside the revoked range. We provide an algorithm to implement RRPs using efficient cryptographic primitives where the space complexity of the pseudonym is constant, regardless of the granularity of the revocation range, and the space complexity of the revocation information only grows logarithmically with the granularity; this makes the use of RRPs far more efficient than the use of many short-lived pseudonyms. We have used RRPs to design EDGAR, an access control system for VANET scenarios that offers backward unlinkability. The experimental evaluation of EDGAR shows that, when using RRPs, the revocation can be performed efficiently (even when using time slots as small as 1 second) and that users can authenticate with low latency (0.5-3.5ms ).
References
[1]
American Association of State Highway and Transportation Officials. 2014. National Connected Vehicle Field Infrastructure Footprint Analysis, Final Report. https://ntlrepository.blob.core.windows.net/lib/52000/52600/52602/Cnct_Veh_Footprint_20181017.pdf Retrieved 2022-11-28 from
[2]
Giuseppe Ateniese, Dawn Song, and Gene Tsudik. 2002. Quasi-Efficient Revocation of Group Signatures. In Proceedings of the International Conference on Financial Cryptography. Southampton, Bermuda.
[3]
AT&T. 2022. Cybersecurity Insights Report: Securing the Edge. https://cdn-cybersecurity.att.com/docs/industry-reports/cybersecurity-insights-report-eleventh-edition.pdf Retrieved 2022-11-28 from
[4]
Man Au, Patrick Tsang, and Apu Kapadia. 2008. PEREA: Practical TTP-Free Revocation of Repeatedly Misbehaving Anonymous Users. ACM Transactions on Information and System Security (2008), 1--34.
[5]
Kassem Bagher and Shangqi Lai. 2023. SGX-Stream: A Secure Stream Analytics Framework In SGX-enabled Edge Cloud. Journal of Information Security and Applications, Vol. 72 (2023).
[6]
Alastair Beresford and Frank Stajano. 2004. Mix Zones: User Privacy in Location-Aware Services. In Proceedings of the IEEE Conference on Pervasive Computing and Communications Workshops. Orlando, FL, USA.
[7]
Daniel Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. 2012. High-speed high-security signatures. Journal of cryptographic engineering (2012), 77--89.
[8]
Dan Boneh and Matthew. Franklin. 2001. Identity-Based Encryption from the Weil Pairing. In Proceedings of the Annual International Cryptology Conference. London, UK.
[9]
Dan Boneh and Hovav Shacham. 2004. Group Signatures with Verifier-Local Revocation. In Proceedings of the ACM conference on Computer and communications security. Washington, DC, USA.
[10]
Ernie Brickell. 2003. An efficient protocol for anonymously providing assurance of the container of a private key. Submitted to the Trusted Computing Group (2003).
[11]
Julien Bringer and Alain Patey. 2011. Backward Unlinkability for a VLR Group Signature Scheme with Efficient Revocation Check. Cryptology ePrint Archive (2011).
[12]
Jo Bulck, Daniel Moghimi, Michael Schwarz, Moritz Lippi, Marina Minkin, Daniel Genkin, Yuval Yarom, Berk Sunar, Daniel Gruss, and Frank Piessens. 2020. LVI: Hijacking Transient Execution through Microarchitectural Load Value Injection. In Proceedings of the IEEE Symposium on Security and Privacy. San Francisco, California.
[13]
Jan Camenisch and Anna Lysyanskaya. 2002. Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials. In Proceedings of the International Cryptology Conference. Santa Barbara, California, USA.
[14]
Camp, LLC. 2016. Security Credential Management System Proof-of-Concept Implementation-EE Requirements and Specifications Supporting SCMS Software Release 1.1. Technical Report. Vehicle Safety Communications Consortium.
[15]
Cheng-Kang Chu, Joseph Liu, Xinyi Huang, and Jianying Zhou. 2012. Verifier-Local Revocation Group Signatures with Time-Bound Keys. In Proceedings of the ACM Symposium on Information, Computer and Communications Security. Seoul, Korea.
[16]
Graham Cormode and Shan Muthukrishnan. 2005. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms (2005), 58--75.
[17]
Cláudio Correia, Miguel Correia, and Luís Rodrigues. 2020. Omega: A Secure Event Ordering Service for the Edge. In Proceedings of the IEEE/IFIP International Conference on Dependable Systems and Networks. València, Spain.
[18]
Cláudio Correia, Miguel Correia, and Luís Rodrigues. 2023. Using Range-Revocable Pseudonyms to Provide Backward Unlinkability in the Edge (Extended Version). arXiv preprint hrefhttps://arxiv.org/abs/2308.03402arXiv:2308.03402 (2023).
[19]
Marco Correia, Jo ao Almeida, Paulo Bartolomeu, José Fonseca, and Joaquim Ferreira. 2022. Performance Assessment of Collective Perception Service Supported by the Roadside Infrastructure. Electronics (2022), 347.
[20]
Crash Avoidance Metrics Partners LLC (CAMP). 2021. Technical Publications. https://www.campllc.org/ Retrieved 2022-11-28 from
[21]
Dark Reading. 2021. Cybercriminals Take Aim at Connected Car Infrastructure. https://www.darkreading.com/attacks-breaches/cybercriminals-take-aim-at-connected-car-infrastructure Retrieved 2022-11-28 from
[22]
C. Dwork, N. Lynch, and L. Stockmeyer. 1988. Consensus in the Presence of Partial Synchrony. J. ACM (1988), 288--323.
[23]
Sebastián Echeverría, Dan Klinedinst, Keegan Williams, and Grace Lewis. 2016. Establishing Trusted Identities in Disconnected Edge Environments. In Proceedings of the IEEE/ACM Symposium on Edge Computing. Washington, DC, USA.
[24]
Keita Emura, Takuya Hayashi, and Ai Ishida. 2017. Group Signatures with Time-Bound Keys Revisited: A New Model, an Efficient Construction, and its Implementation. IEEE Transactions on Dependable and Secure Computing (2017), 292--305.
[25]
European Telecommunications Standards Institute. 2015. ETSI TS 103 097 V1.2.1:Intelligent Transport Systems (ITS); Security; Security header and certificate formats. https://www.etsi.org/deliver/etsi_ts/103000_103099/103097/01.02.01_60/ts_103097v010201p.pdf Retrieved 2022-11-28 from
[26]
European Telecommunications Standards Institute. 2018. ETSI TR 103 415 V1.1.1: Intelligent Transport Systems (ITS); Security; Pre-standardization study on pseudonym change management. https://www.etsi.org/deliver/etsi_tr/103400_103499/103415/01.01.01_60/tr_103415v010101p.pdf Retrieved 2022-11-28 from
[27]
European Telecommunications Standards Institute. 2021. ETSI TS 102 941 V1.4.1: Intelligent Transport Systems (ITS); Security; Trust and Privacy Management. https://www.etsi.org/deliver/etsi_ts/102900_102999/102941/01.04.01_60/ts_102941v010401p.pdf Retrieved 2022-11-28 from
[28]
Bin Fan, Dave Andersen, Michael Kaminsky, and Michael Mitzenmacher. 2014. Cuckoo Filter: Practically Better Than Bloom. In Proceedings of the ACM International on Conference on emerging Networking Experiments and Technologies. Sydney, Australia.
[29]
David Förster, Frank Kargl, and Hans Löhr. 2014. PUCA: A Pseudonym Scheme with User-Controlled Anonymity for Vehicular Ad-Hoc Networks (VANET). In Proceedings of the IEEE Vehicular Networking Conference (VNC). Paderborn, Germany.
[30]
Freedom of Information and Privacy Association (FIPA). 2019. The Connected Car: who is in the driver's seat? https://fipa.bc.ca/wp-content/uploads/2018/01/CC_report_lite.pdf Retrieved 2022-11-28 from
[31]
Julien Freudiger, Maxim Raya, Márk Félegyházi, Panos Papadimitratos, and Jean-Pierre Hubaux. 2007. Mix-Zones for Location Privacy in Vehicular Networks. In Proceedings of the ACM Workshop on Wireless Networking for Intelligent Transportation Systems. Vancouver, Canada.
[32]
Carlos Ganán, Jose Munoz, Oscar Esparza, Jorge Mata-Díaz, and Juanjo Alins. 2015. EPA: An efficient and privacy-aware revocation mechanism for vehicular ad hoc networks. Pervasive and Mobile Computing (2015), 75--91.
[33]
Raghu Ganti, Fan Ye, and Hui Lei. 2011. Mobile Crowdsensing: Current State and Future Challenges. IEEE communications Magazine (2011), 32--39.
[34]
Jason Haas, Yih-Chun Hu, and Kenneth Laberteaux. 2011. Efficient Certificate Revocation List Organization and Distribution. IEEE Journal on Selected Areas in Communications (2011), 595--604.
[35]
Ryan Henry and Ian Goldberg. 2011. Formalizing Anonymous Blacklisting Systems. In Proceedings of the IEEE Symposium on Security and Privacy. Oakland, California, USA, 81--95.
[36]
Yun Hu, Milan Patel, Dario Sabella, Nurit Sprecher, and Valerie Young. 2015. Mobile Edge Computing - A key technology towards 5G. ETSI white paper, Vol. 11, 11 (2015).
[37]
Maged Ibrahim. 2016. Octopus: An Edge-Fog Mutual Authentication Scheme. International Journal of Network Security (2016), 1089--1101.
[38]
Intel Corporation. 2017. Intel Software Guard Extensions SSL. https://github.com/intel/intel-sgx-ssl Retrieved 2022-11-28 from
[39]
Intelligent Transportation Systems Joint Program Office. 2021. Connected Vehicle Pilot Deployment Program. https://www.its.dot.gov/pilots/overview.htm Retrieved 2022-11-28 from
[40]
Ai Ishida, Yusuke Sakai, Keita Emura, Goichiro Hanaoka, and Keisuke Tanaka. 2018. Fully Anonymous Group Signature with Verifier-Local Revocation. In Proceedings of the International Conference on Security and Cryptography for Networks. Amalfi, Italy.
[41]
Kaggle. 2015. Data Set ECML/PKDD 15: Taxi Trajectory Prediction. https://www.kaggle.com/c/pkdd-15-predict-taxi-service-trajectory-i/ Retrieved 2022-11-28 from
[42]
Mohammad Khodaei and Panos Papadimitratos. 2018. Efficient, Scalable, and Resilient Vehicle-Centric Certificate Revocation List Distribution in VANETs. In Proceedings of the ACM conference on security & privacy in wireless and mobile networks. Stockholm, Sweden.
[43]
Leslie Lamport, Robert Shostak, and Marshall Pease. 1982. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems (1982), 203--226.
[44]
James Larisch, David Choffnes, Dave Levin, Bruce Maggs, Alan Mislove, and Christo Wilson. 2017. CRLite: A Scalable System for Pushing All TLS Revocations to All Browsers. In Proceedings of the IEEE Symposium on Security and Privacy. San Jose, CA, USA.
[45]
Mu Lin, Nicholas Lane, Mashfiqui Mohammod, Xiaochao Yang, Hong Lu, Giuseppe Cardone, Shahid Ali, Afsaneh Doryab, Ethan Berke, Andrew Campbell, et al. 2012. BeWell Multi-dimensional Wellbeing Monitoring with Community-guided User Feedback and Energy Optimization. In Proceedings of the conference on Wireless Health. 1--8.
[46]
Bozhen Liu and Jeff Huang. 2018. D4: Fast Concurrency Debugging with Parallel Differential Analysis. ACM SIGPLAN Notices (2018), 359--373.
[47]
Lailong Luo, Deke Guo, Richard Ma, Ori Rottenstreich, and Xueshan Luo. 2018. Optimizing Bloom Filter: Challenges, Solutions, and Comparisons. IEEE Communications Surveys & Tutorials (2018), 1912--1949.
[48]
Anna Lysyanskaya, Ronald Rivest, Amit Sahai, and Stefan Wolf. 1999. Pseudonym Systems. In Proceedings of the International Workshop on Selected Areas in Cryptography. Ontario, Canada.
[49]
Simone Mangiante, Guenter Klas, Amit Navon, Zhuang GuanHua, Ju Ran, and Marco Silva. 2017. VR is on the Edge: How to Deliver 360° Videos in Mobile Networks. In Proceedings of the Workshop on Virtual Reality and Augmented Reality Network. Los Angeles, CA, USA.
[50]
Ed Markey. 2015. Tracking & Hacking: Security & Privacy Gaps Put American Drivers at Risk. Congressional Report (2015).
[51]
David Meyer. 2018. What the GDPR will mean for companies tracking location. https://iapp.org/news/a/what-the-gdpr-will-mean-for-companies-tracking-location/ Retrieved 2022-11-28 from
[52]
Mounira Msahli, Nancy Cam-Winget, William Whyte, Ahmed Serhrouchni, and Houda Labiod. 2020. RFC 8902 TLS Authentication Using Intelligent Transport System (ITS) Certificates. https://www.hjp.at/doc/rfc/rfc8902.pdf Retrieved 2022-11-28 from
[53]
Toru Nakanishi and Nobuo Funabiki. 2005. Verifier-Local Revocation Group Signature Schemes with Backward Unlinkability from Bilinear Maps. In Proceedings of the International conference on the theory and application of cryptology and information security. Chennai, India.
[54]
National Highway Traffic Safety Administration. 2017. Department of Transportation (DOT), Federal Motor Vehicle Safety Standards; V2V Communications. https://www.federalregister.gov/documents/2017/01/12/2016-31059/federal-motor-vehicle-safety-standards-v2v-communications Retrieved 2022-11-28 from
[55]
Kazuma Ohara, Keita Emura, Goichiro Hanaoka, Ai Ishida, Kazuo Ohta, and Yusuke Sakai. 2019. Shortening the Libert--Peters-Yung Revocable Group Signature Scheme by Using the Random Oracle Methodology. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (2019), 1101--1117.
[56]
Bei Pan, Yu Zheng, David Wilkie, and Cyrus Shahabi. 2013. Crowd Sensing of Traffic Anomalies based on Human Mobility and Social Media. In Proceedings of the ACM international conference on advances in geographic information systems. Orlando, Florida.
[57]
Orson Peters and Viktor Szakats. 2013. Portable C implementation of Ed25519. https://github.com/orlp/ed25519 Retrieved 2022-11-28 from
[58]
Raluca Popa, Andrew Blumberg, Hari Balakrishnan, and Frank Li. 2011. Privacy and Accountability for Location-Based Aggregate Statistics. In Proceedings of the ACM conference on computer and communications security. Chicago, IL, USA.
[59]
Sazzadur Rahaman, Long Cheng, Danfeng Yao, He Li, and Jung-Min Park. 2017. Provably Secure Anonymous-yet-Accountable Crowdsensing with Scalable Sublinear Revocation. In Proceedings of the Privacy Enhancing Technologies. Minneapolis, USA.
[60]
Mina Remeli, Szilvia Lestyán, Gergely Acs, and Gergely Biczók. 2019. Automatic Driver Identification from In-Vehicle Network Logs. In Proceedings of the IEEE Intelligent Transportation Systems Conference. Auckland, New Zealand.
[61]
Giovanni Rigazzi, Andrea Tassi, Robert Piechocki, Theo Tryfonas, and Andrew Nix. 2017. Optimized Certificate Revocation List Distribution for Secure V2X Communications. In Proceeding of the IEEE Vehicular Technology Conference. Sydney, Australia.
[62]
Florian Schaub, Frank Kargl, Zhendong Ma, and Michael Weber. 2010. V-Tokens for Conditional Pseudonymity in VANETs. In Proceedings of the IEEE Wireless Communication and Networking Conference. Sydney, Australia.
[63]
Daniel Slamanig, Raphael Spreitzer, and Thomas Unterluggauer. 2016. Linking-Based Revocation for Group Signatures: A Pragmatic Approach for Efficient Revocation Checks. In Proceedings of the International Conference on Cryptology in Malaysia. Kuala Lumpur, Malaysia.
[64]
Victor Sucasas, Georgios Mantas, Joaquim Bastos, Francisco Damião, and Jonathan Rodriguez. 2020. A Signature Scheme with Unlinkable-yet-Acountable Pseudonymity for Privacy-Preserving Crowdsensing. IEEE Transactions on Mobile Computing (2020), 752--768.
[65]
Yipin Sun, Rongxing Lu, Xiaodong Lin, Xuemin Shen, and Jinshu Su. 2010. An Efficient Pseudonymous Authentication Scheme With Strong Privacy Preservation for Vehicular Communications. IEEE Transactions on Vehicular Technology (2010), 3589--3603.
[66]
Tech Monitor. 2021. Data from your connected car could be sold to the highest bidder. https://techmonitor.ai/policy/privacy-and-data-protection/connected-vehicle-data-apply-carplay Retrieved 2022-11-28 from
[67]
Patrick Tsang, Man Ho Au, Apu Kapadia, and Sean Smith. 2007. Blacklistable Anonymous Credentials: Blocking Misbehaving Users without TTPs. In Proceedings of the ACM conference on Computer and communications security. Alexandria, Virginia, USA.
[68]
Patrick P Tsang, Apu Kapadia, Cory Cornelius, and Sean W Smith. 2009. Nymble: Blocking Misbehaving Users in Anonymizing Networks. IEEE Transactions on Dependable and Secure Computing, Vol. 8, 2 (2009).
[69]
United States Government Accountability Office. 2017. Vehicle Data Privacy. https://www.gao.gov/assets/gao-17-656.pdf Retrieved 2022-11-28 from
[70]
Luis Vaquero and Luis Rodero-Merino. 2014. Finding Your Way in the Fog: Towards a Comprehensive Definition of Fog Computing. ACM SIGCOMM Computer Communication Review (2014), 27--32.
[71]
Eric Verheul, Christopher Hicks, and Flavio Garcia. 2019. IFAL: Issue First Activate Later Certificates for V2X. In Proceedings of the IEEE European Symposium on Security and Privacy. Stockholm, Sweden.
[72]
Nico Weichbrodt, Anil Kurmus, Peter Pietzuch, and Rüdiger Kapitza. 2016. AsyncShock: Exploiting Synchronisation Bugs in Intel SGX Enclaves. In Proceedings of the European Symposium on Research in Computer Security. Heraklion, Greece.
[73]
William Whyte, André Weimerskirch, Virendra Kumar, and Thorsten Hehn. 2013. A Security Credential Management System for V2V Communications. In Proceedings of the IEEE Vehicular Networking Conference. Boston, MA, USA.
[74]
Jiale Zhang, Bing Chen, Yanchao Zhao, Xiang Cheng, and Feng Hu. 2018. Data Security and Privacy-Preserving in Edge Computing Paradigm: Survey and Open Issues. IEEE Access (2018), 18209--18237.
Index Terms
- Using Range-Revocable Pseudonyms to Provide Backward Unlinkability in the Edge
Recommendations
Post-quantum secure group signature with verifier local revocation and backward unlinkability
AbstractGroup signature supports users to generate signatures on behalf of the group. Verifier local revocation (VLR) is an important method to revoke a misbehaving user in group signature, which has attracted many researchers’ attention. However, the ...
Highlights- We propose a new dynamic group signature scheme with backward unlinkability.
- A phased update of revocation tokens will provide higher security for signatures.
- The secret key size and signature size are independent of the number of ...
A Short Verifier-Local Revocation Group Signature Scheme with Backward Unlinkability
Previously Verifier-Local Revocation (VLR) group signature schemes from bilinear maps were proposed. In VLR schemes, only verifiers are involved in the revocation of a member, while signers are not. Thus, the VLR schemes are suitable for mobile ...
Group Signatures with Verifier-Local Revocation and Backward Unlinkability in the Standard Model
CANS '09: Proceedings of the 8th International Conference on Cryptology and Network SecurityGroup signatures allow users to anonymously sign messages in the name of a group. Membership revocation has always been a critical issue in such systems. In 2004, Boneh and Shacham formalized the concept of group signatures with <em>verifier-local ...
Comments
Information & Contributors
Information
Published In
November 2023
3722 pages
ISBN:9798400700507
DOI:10.1145/3576915
- General Chairs:
- Weizhi Meng,
- Christian D. Jensen,
- Program Chairs:
- Cas Cremers,
- Engin Kirda
Copyright © 2023 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 November 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Fundação para a Ciência e a Tecnologia
- IAPMEI
- European Union
Conference
CCS '23
Sponsor:
CCS '23: ACM SIGSAC Conference on Computer and Communications Security
November 26 - 30, 2023
Copenhagen, Denmark
Acceptance Rates
Overall Acceptance Rate 1,261 of 6,999 submissions, 18%
Upcoming Conference
CCS '25
- Sponsor:
- sigsac
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 307Total Downloads
- Downloads (Last 12 months)307
- Downloads (Last 6 weeks)51
Reflects downloads up to 06 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in