Biblio

Locally Linear Embedding (LLE) is a popular approach to dimensionality reduction as it can effectively represent nonlinear structures of high-dimensional data. For dimensionality reduction, it computes a nearest neighbor graph from a given dataset where edge weights are obtained by applying the Lagrange multiplier method, and it then computes eigenvectors of the LLE kernel where the edge weights are used to obtain the kernel. Although LLE is used in many applications, its computation cost is significantly high. This is because, in obtaining edge weights, its computation cost is cubic in the number of edges to each data point. In addition, the computation cost in obtaining the eigenvectors of the LLE kernel is cubic in the number of data points. Our approach, Ripple, is based on two ideas: (1) it incrementally updates the edge weights by exploiting the Woodbury formula and (2) it efficiently computes eigenvectors of the LLE kernel by exploiting the LU decomposition-based inverse power method. Experiments show that Ripple is significantly faster than the original approach of LLE by guaranteeing the same results of dimensionality reduction.

Most of the existing authentication protocols are based on either asymmetric cryptography like public-key infrastructure (PKI) or symmetric cryptography. The PKI-based authentication protocols are strongly recommended for solving security issues in VANETs. However, they have following shortcomings: (1) lengthy certificates lead to transmission and computation overheads, and (2) lack of privacy-preservation due to revealing of vehicle identity, communicated in broadcasting safety-message. Symmetric cryptography based protocols are faster because of a single secret key and simplicity; however, it does not ensure non-repudiation. In this paper, we present an Efficient, Scalable and Privacy-preserving Authentication (ESPA) protocol for secure vehicular ad hoc networks (VANETs). The protocol employs hybrid cryptography. In ESPA, the asymmetric PKI based pre-authentication and the symmetric hash message authentication code (HMAC) based authentication are adopted during vehicle to infrastructure (V2I) and vehicle to vehicle (V2V) communications, respectively. Extensive simulations are conducted to validate proposed ESPA protocol and compared with the existing work based on PKI and HMAC. The performance analysis showed that ESPA is more efficient, scalable and privacy-preserving secured protocol than the existing work.