research-article

Revocation games in ephemeral networks

Authors:

Mohammad Hossein Manshaei,

Márk Félegyhazi,

Jean-Pierre HubauxAuthors Info & Claims

CCS '08: Proceedings of the 15th ACM conference on Computer and communications security

Pages 199 - 210

https://doi.org/10.1145/1455770.1455797

Published: 27 October 2008 Publication History

Abstract

A frequently proposed solution to node misbehavior in mobile ad hoc networks is to use reputation systems. But in ephemeral networks - a new breed of mobile networks where contact times between nodes are short and neighbors change frequently - reputations are hard to build. In this case, local revocation is a faster and more efficient alternative. In this paper, we define a game-theoretic model to analyze the various local revocation strategies. We establish and prove the conditions leading to subgame-perfect equilibria. We also derive the optimal parameters for voting-based schemes. Then we design a protocol based on our analysis and the practical aspects that cannot be captured in the model. With realistic simulations on ephemeral networks we compare the performance and economic costs of the different techniques.

References

[1]

http://trans.epfl.ch.

[2]

Standard Specification for Telecommunications and Information Exchange Between Roadside and Vehicle Systems -- 5 GHz Band Dedicated Short Range Communications (DSRC) Medium Access Control (MAC) and Physical Layer (PHY) Specifications. ASTM E2213-03, 2003.

[3]

IEEE P1609.2 Version 1 -- Standard for Wireless Access in Vehicular Environments -- Security Services for Applications and Management Messages. In development, 2006.

[4]

R. Anderson and T. Moore. The economics of information security. Science, 314(5799):610--613, Oct. 2006.

[5]

G. Arboit, C. Crepeau, C.R. Davis, and M. Maheswaran. A localized certificate revocation scheme for mobile ad hoc networks. Ad Hoc Networks, 6(1):17--31, January 2008.

Digital Library

[6]

A. Boldyreva, C. Gentry, A. O'Neill, and D. H. Yum. Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing (extended abstract). In Proceedings of CCS'07.

Digital Library

[7]

D. Boneh. A brief look at pairings based cryptography. In Proceedings of FOCS'07.

Digital Library

[8]

D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In Proceedings of EUROCRYPT'03, volume 2656 of LNCS, pages 416--432.

[9]

D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing. Journal of Cryptology, 17(4):297--319, 2004.

Digital Library

[10]

S. Buchegger and J.-Y. Le Boudec. A robust reputation system for P2P and mobile ad-hoc networks. In Proceedings of P2PEcon'04.

[11]

S. Buchegger and J.-Y. Le Boudec. Self-policing mobile ad hoc networks by reputation systems. Communications Magazine, IEEE, 43(7):101--107, 2005.

Digital Library

[12]

J. Burgess, G. D. Bissias, M. Corner, and B. N. Levine. Surviving attacks on disruption-tolerant networks without authentication. In Proceedings of MobiHoc'07.

Digital Library

[13]

L. Buttyan and J.-P. Hubaux. Security and Cooperation in Wireless Networks. Cambridge University Press, 2007. http://secowinet.epfl.ch.

Digital Library

[14]

G. Calandriello, P. Papadimitratos, A. Lioy, and J.-P. Hubaux. Efficient and robust pseudonymous authentication in VANET. In Proceedings of VANET'07.

Digital Library

[15]

J. Camenisch, S. Hohenberger, and M. O. Pedersen. Batch verification of short signatures. In Proceedings of EUROCRYPT'07, volume 4515 of LNCS, pages 246--263.

Digital Library

[16]

S. Capkun, L. Buttyan, and J.P. Hubaux. Self-organized public-key management for mobile ad hoc networks. IEEE Transactions on Mobile Computing, 2(1):52--64, 2003.

Digital Library

[17]

H. Chan, V. D. Gligor, A. Perrig, and G. Muralidharan. On the distribution and revocation of cryptographic keys in sensor networks. IEEE Transactions on Dependable and Secure Computing, 2(3):233--247, 2005.

Digital Library

[18]

R. Dingledine and P. Syverson. Reliable mix cascade networks through reputation. In Proceedings of FC'02, volume 2357 of LNCS, pages 253--268.

[19]

K. Fall. A delay-tolerant network architecture for challenged internets. In Proceedings of SIGCOMM'03.

Digital Library

[20]

D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1991.

[21]

S. Ganeriwal and M. Srivastava. Reputation-based framework for high integrity sensor networks. In Proceedings of SASN'04.

Digital Library

[22]

P. Golle, D. Greene, and J. Staddon. Detecting and correcting malicious data in VANETs. In Proceedings of VANET'04.

Digital Library

[23]

J. Katz. Bridging game theory and cryptography: Recent results and future directions. In Proceedings of TCC'08, volume 4948 of LNCS, pages 251--272.

[24]

H. Luo, J. Kong, P. Zerfos, S. Lu, and L. Zhang. URSA: ubiquitous and robust access control for mobile ad hoc networks. IEEE/ACM Transactions on Networking, 12(6):1049--1063, December 2004.

Digital Library

[25]

R. Mahajan, M. Rodrig, D. Wetherall, and J. Zahorjan. Experiences applying game theory to system design. In Proceedings of PINS'04, 2004.

Digital Library

[26]

S. Marti, T.J. Giuli, K. Lai, and M. Baker. Mitigating routing misbehavior in mobile ad hoc networks. In Proceedings of MobiCom'00.

Digital Library

[27]

A. Mishra, K. Nadkarni, and A. Patcha. Intrusion detection in wireless ad hoc networks. IEEE Wireless Communications, 11(1):48--60, Feb. 2004.

Digital Library

[28]

T. Moore, J. Clulow, S. Nagaraja, and R. Anderson. New strategies for revocation in ad-hoc networks. In Proceedings of ESAS'07.

[29]

T. Moore, M. Raya, J. Clulow, P. Papadimitratos, R. Anderson, and J.-P. Hubaux. Fast exclusion of errant devices from vehicular networks. In Proceedings of SECON'08.

[30]

D. Peleg. Local majorities, coalitions and monopolies in graphs: a review. Theoretical Computer Science, 282(2):231--257, Jun. 2002.

Digital Library

[31]

M. Raya and J.-P. Hubaux. The security of vehicular ad hoc networks. In Proceedings of SASN'05.

Digital Library

[32]

M. Raya, P. Papadimitratos, V. Gligor, and J.-P. Hubaux. On data--centric trust establishment in ephemeral ad hoc networks. In Proceedings of INFOCOM'08.

[33]

M. Scott, N. Costigan, and W. Abdulwahab. Implementing cryptographic pairings on smartcards. In Proceedings of CHES'06, volume 4249 of LNCS, pages 134--147.

[34]

Q. Xu, T. Mak, J. Ko, and R. Sengupta. Vehicle-to-vehicle safety messaging in DSRC. In Proceedings of VANET'04.

Digital Library

[35]

H. Yang, H. Luo, F. Ye, S. Lu, and L. Zhang. Security in mobile ad hoc networks: challenges and solutions. Wireless Communications, IEEE, 11(1):38--47, 2004.

Digital Library

[36]

S. Yi and R. Kravets. MOCA: Mobile certificate authority for wireless ad hoc networks. In Proceedings of PKI'03.

[37]

P. Zheng. Tradeoffs in certificate revocation schemes. SIGCOMM Computing Communication Review, 33(2):103--112, 2003.

Digital Library

Cited By

Gaiduk PRanjan KBasmer TTschorsch F(2020)Privacy-Preserving Public Key Infrastructure for Vehicular Networks2020 IEEE 45th Conference on Local Computer Networks (LCN)10.1109/LCN48667.2020.9314787(154-163)Online publication date: 16-Nov-2020
https://doi.org/10.1109/LCN48667.2020.9314787
Wang ZZhang MXu HXu GLi CWu Z(2020)Artificial Intelligence and Game Theory Based Security Strategies and Application Cases for Internet of VehiclesCommunications, Signal Processing, and Systems10.1007/978-981-13-9409-6_38(322-329)Online publication date: 4-Apr-2020
https://doi.org/10.1007/978-981-13-9409-6_38
Behfarnia AEslami A(2019)Local Voting Games for Misbehavior Detection in VANETs in Presence of Uncertainty2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)10.1109/ALLERTON.2019.8919734(480-486)Online publication date: 24-Sep-2019
https://dl.acm.org/doi/10.1109/ALLERTON.2019.8919734
Show More Cited By

Index Terms

Revocation games in ephemeral networks
1. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

A game-theoretic approach to advertisement dissemination in ephemeral networks

In ephemeral networks, disseminating advertisements faces two dilemmatic problems: on the one hand, disseminators own the limited resources and have privacy concerns, thus, often preferring to avoid disseminating advertisements without enough incentives; ...
On the Distribution of Revocation Information in Ad Hoc Networks
ICWMC '07: Proceedings of the Third International Conference on Wireless and Mobile Communications

This paper proposes a simple, scalable and robust scheme for the distribution of revocation information in mobile ad hoc networks (MANETs); the MRL scheme. A MRL is a revocation list for a specific MANET instantiation. The scheme is designed for ...
Proxy Signature with Revocation
Proceedings, Part II, of the 21st Australasian Conference on Information Security and Privacy - Volume 9723

Proxy signature is a useful cryptographic primitive that allows signing right delegation. In a proxy signature scheme, an original signer can delegate his/her signing right to a proxy signer or a group of proxy signers who can then sign documents on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '08: Proceedings of the 15th ACM conference on Computer and communications security

October 2008

590 pages

ISBN:9781595938107

DOI:10.1145/1455770

General Chair:
Peng Ning
North Carolina State University, USA
,
Program Chairs:
Paul Syverson
Naval Research Laboratory, USA
,
Somesh Jha
University of Wisconsin, USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 October 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS08

Sponsor:

CCS08: 15th ACM Conference on Computer and Communications Security 2008

October 27 - 31, 2008

Virginia, Alexandria, USA

Acceptance Rates

CCS '08 Paper Acceptance Rate 51 of 280 submissions, 18%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
794
Total Downloads

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

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gaiduk PRanjan KBasmer TTschorsch F(2020)Privacy-Preserving Public Key Infrastructure for Vehicular Networks2020 IEEE 45th Conference on Local Computer Networks (LCN)10.1109/LCN48667.2020.9314787(154-163)Online publication date: 16-Nov-2020
https://doi.org/10.1109/LCN48667.2020.9314787
Wang ZZhang MXu HXu GLi CWu Z(2020)Artificial Intelligence and Game Theory Based Security Strategies and Application Cases for Internet of VehiclesCommunications, Signal Processing, and Systems10.1007/978-981-13-9409-6_38(322-329)Online publication date: 4-Apr-2020
https://doi.org/10.1007/978-981-13-9409-6_38
Behfarnia AEslami A(2019)Local Voting Games for Misbehavior Detection in VANETs in Presence of Uncertainty2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)10.1109/ALLERTON.2019.8919734(480-486)Online publication date: 24-Sep-2019
https://dl.acm.org/doi/10.1109/ALLERTON.2019.8919734
Behfarnia AEslami A(2019)Misbehavior Detection in Ephemeral Networks: A Local Voting Game in Presence of UncertaintyIEEE Access10.1109/ACCESS.2019.29610597(184629-184642)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2961059
Etesami SBaşar T(2019)Dynamic Games in Cyber-Physical Security: An OverviewDynamic Games and Applications10.1007/s13235-018-00291-y9:4(884-913)Online publication date: 1-Jan-2019
https://doi.org/10.1007/s13235-018-00291-y
Chakraborty TJajodia SPark NPugliese ASerra ESubrahmanian V(2018)Hybrid adversarial defenseJournal of Computer Security10.3233/JCS-17109426:5(615-645)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.3233/JCS-171094
Troncoso CIsaakidis MDanezis GHalpin H(2017)Systematizing Decentralization and Privacy: Lessons from 15 Years of Research and DeploymentsProceedings on Privacy Enhancing Technologies10.1515/popets-2017-00562017:4(404-426)Online publication date: 10-Oct-2017
https://doi.org/10.1515/popets-2017-0056
Seo SKim JKim JChung J(2017)Reconfiguration time and complexity minimized trust-based clustering scheme for MANETsEURASIP Journal on Wireless Communications and Networking10.1186/s13638-017-0938-82017:1Online publication date: 18-Sep-2017
https://doi.org/10.1186/s13638-017-0938-8
Taie STaha S(2017)A novel secured traffic monitoring system for VANET2017 IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops)10.1109/PERCOMW.2017.7917553(176-182)Online publication date: Mar-2017
https://doi.org/10.1109/PERCOMW.2017.7917553
Alabdel Abass AMandayam NGajic Z(2017)An Evolutionary Game model for threat revocation in ephemeral networks2017 51st Annual Conference on Information Sciences and Systems (CISS)10.1109/CISS.2017.7926128(1-5)Online publication date: Mar-2017
https://doi.org/10.1109/CISS.2017.7926128
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents