Tree-Based Revocation for Certificateless Authentication in Vehicular Ad-Hoc Networks


This work proposes authentication based on identity as a way to increase the efficiency and security of communications in vehicular ad-hoc networks. When using identity-based cryptography to achieve certificateless authentication, membership revocation is not a trivial problem. Thus, in order to improve the performance of revocation in such networks, the use of a dynamic authenticated data structure based on perfect k-ary hash trees combined with a duplex version of the new standard SHA-3 is here presented. Efficient algorithms in the used revocation trees allow reaching a refresh rate of at most simple updates per inserted node. Consequently, the proposal is especially useful for situations with frequent revocations, which are foreseeable when vehicular ad- hoc networks are widely deployed.

Share and Cite:

Caballero-Gil, P. , Martín-Fernández, F. and Caballero-Gil, C. (2014) Tree-Based Revocation for Certificateless Authentication in Vehicular Ad-Hoc Networks. Journal of Computer and Communications, 2, 14-21. doi: 10.4236/jcc.2014.29003.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] ETSI (2012) Intelligent Transport Systems. http://
[2] Blake-Wilson, S. (2000) Information Security, Mathematics, and Public-Key Cryptography. Designs, Codes and Cryptography, 19, 77-99.
[3] Hubaux, J.P., Capkun, S. and Luo, J. (2004) The Security and Privacy of Smart Vehicles. IEEE Security and Privacy, 2, 49-55.
[4] Raya, M. and Hubaux, J.P. (2007) Securing Vehicular Ad Hoc Networks. Computer Security, 15, 39-68.
[5] IEEE-1609 (2006) Family of Standards for Wireless Access in Vehicular Environments (WAVE). US Department of Transportation.
[6] Kocher, P. (1998) On Certificate Revocation and Validation. FC’98. LNCS 1465, 172-177.
[7] Merkle, R. (1980) Protocols for Public Key Cryptosystems. IEEE Security and Privacy, 1109, 122-134.
[8] Jakobsson, M., Leighton, T., Micali, S. and Szydlo, M. (2003) Fractal Merkle Tree Representation and Traversal. CT- RSA. LNCS 2612, 314-326.
[9] Goodrich, M., Shin, M., Tamassia, R. and Winsborough, W. (2003) Authenticated Dictionaries for Fresh Attribute Cre- dentials. Trust Management, LNCS 2692, 332-347.
[10] Cormen, T., Leiserson, C. and Rivest, R. (1990) Introduction to Algorithms. MIT Press.
[11] Goodrich, M., Tamassia, R., Triandopoulos, N. and Cohen, R. (2003) Authenticated Data Structures for Graph and Geometric Searching. CT-RSA. LNCS 2612, 295-313.
[12] Chang, S., Perlner, R., Burr, W., Turan, M., Kelsey, J., Paul, S. and Bassham, L. (2012) Third-Round Report of the Sha-3 Cryptographic Hash Algorithm Competition. NIST.
[13] Bertoni, G., Daemen, J., Peeters, M. and Assche, G.V. (2010) Keccak Sponge Function Family Main Document Version 2.1, Updated Submission to NIST (Round 2).
[14] Bertoni, G., Daemen, J., Peeters, M. and Assche, G.V. (2008) On the Indifferentiability of the Sponge Construction. Eurocrypt, LNCS 4965, 181-197.
[15] Bertoni, G., Daemen, J., Peeters, M. and Assche, G.V. (2012) Duplexing the Sponge: Single-Pass Authenticated Encryption and Other Applications. Selected Areas in Cryptography, LNCS 7118, 320-337.
[16] Shamir, A. (1985) Identity-Based Cryptosystems and Signature Schemes. Crypto, LNCS 196, 47-53.
[17] Boneh, D. and Franklin, M. (2001) Identity-Based Encryption from the Weil Pairing. Crypto, LNCS 2139, 213-229.
[18] Joux, A. (2002) The Weil and Tate Pairings as Building Blocks for Public Key Cryptosystems. Algorithmic Number Theory Symposium, LNCS 2369, 20-32.
[19] Miller, V. (1986) Short Programs for Functions on Curves. Unpublished Manuscript, 97, 101-102.
[20] Ganan, C., Munoz, J., Esparza, O., Mata-Diaz, J. and Alins, J. (2012) Toward Revocation Data Handling Efficiency in VANETs. Communication Technologies for Vehicles, LNCS 7266, 80-90.
[21] Jakobsson, M. and Wetzel, S. (2004) Efficient Attribute Authentication with Applications to Ad Hoc Networks. ACM Workshop on Vehicular Ad Hoc Networks, 38-46.

Copyright © 2021 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.