Efficient And Secure Communication For Vanets And Secure Pattern Matching

Cryptography is the foundation of information security, so people take advan-tage of cryptography to ensure the security of the sensitive information. As the main method for cryptography to protect the security of the sensitive information, crypto-graphic protocol has attracted more and more attention. A cryptographic protocol[1] is a distributed algorithm defined by a sequence of steps precisely specifying the actions required of two or more entities to achieve a specific security objective.In general, all cryptographic system, such as key distribution system, the digital signature authentication system, the secret sharing system, may be called cryptographic protocols. Cryptographic protocols provide security services for the network, which is the basic protection for network security. In recent years, with the rapid development of Internet, more and more network data transmission and trading need protection and support from cryptographic protocols.Our study consists of two aspects. First we realize a set of protocols for vehicle ad-hoc network that can satisfy the requirement of security and is more efficient than previous schemes for vehicle ad-hoc network. And we also present a set of protocols for secure two-party pattern matching problem. Certainly the efficiency and security are also better than previous schemes. Our research in these two aspects are very important in practical application.1. Efficient and Secure Communication for VANETsVehicular Ad Hoc Network (VANET) has been attracting more and more atten-tions from both industry and academia. It is a critical component of the Intelligent Transportation Systems (ITSs)[2] which aims at enhancing driving safety through inter-vehicle communications or communications with roadside infrastructure. In a typical VANET, each vehicle is assumed to have an on-board unit (OBU) and there are road-side units (RSU) installed along the roads. A trusted authority (TA) and maybe some other application servers are installed in the backbone. The OBUs and RSUs commu-nicate using the Dedicated Short Range Communications (DSRC) protocol[3] over the wireless channel while the RSUs, TA, and the application servers communicate using a secure fixed network. Based on this, each vehicle can periodically broadcast safety information[4] containing its current speed, location, road condition and traffic acci-dent information etc. With the received information, other drivers can make an early response in case of exceptional situations. With multi-hop forwarding, the messages will be either terminated by an RSU or dropped when exceeding their lifetimes. The RSU may also inform the traffic control center to adjust traffic lights to avoid possi-ble traffic congestion. VANET also provides a platform for a group of known vehicles (e.g. police chasing a bank robber) to establish a secure communication channel (group communication).Like other communication networks, security issues have to be well-addressed. For example, message integrity must be guaranteed, and the message senders should be authenticated. Otherwise, an attacker can replace the safety message from a vehicle or even impersonate a vehicle to transmit a fake safety message which in turn can cause accidents or even loss of life. In addition, user privacy concerns must also be well mitigated, where the identity, the position, and the trajectory of a specific vehicle should not be obtained by a third party. Otherwise, one may not be willing to use this new type of network. Thus an anonymous and secure communication protocol is vital to VANET. Being motivated by these, we propose an efficient HMAC-based secure communication protocol in this thesis.Our scheme is composed of three schemes:1. We use only simple HMAC and symmetric cipher to replace the complicated Elliptic Curve Cryptography (ECC) approach to achieve secure communications between Vehicles and RSUs. This is very efficient and can satisfy all the secu- rity requirements of VANETs. Based on our simulation study, we show that our schemes are effective and the delay caused is much lower compared with the pre-vious schemes. The average delay caused by our scheme is nearly thousands of times lower than previous schemes. Meanwhile we can prove that our protocols can satisfy the security requirements for Vehicle Ad-hoc Network.2. Without using the complicated ECC, we propose the one-to-one secure com-munications scheme among group members with simple symmetric cipher and HMAC based on a shared key. As we know, any vehicle can form a group with other vehicles after an initial handshaking phase with a nearby RSU and then can authenticate and communicate with one another securely without the inter-vention of RSU. Our schemes are effective and the delay caused is much lower. The average delay caused by our scheme is0.312ms, while the delay caused by prior scheme is12.3ms. Meanwhile our protocols can satisfy the security requirement for Vehicle Ad-hoc Network.3. We define a one-to-one secure communications scheme among vehicles who do not know each other in advance. There is no such scheme in all existing solutions, and our scheme supplements this shortcoming. We also use simple HMAC and symmetric cipher to replace the complicated Elliptic Curve Cryptographic (ECC) approach to achieve this protocol. Based on our simulation study, the average delay caused by our scheme is0.312ms, but the delay caused by prior scheme is about9s. Meanwhile our protocols can satisfy the security requirement for Vehicle ad-hoc network.2. Efficient and Secure Pattern MatchingOur research is about the highly motivated problem of secure two-party pattern matching:party A holds a text t{0,1}n of length n, while party B has a pattern p∈{0,1}m of length m. The goal is for B to learn where his pattern occurs in the text of T. Certainly we need to extend it to any Q-ary alphabet, especially about the DNA sequences i.e. t,p∈{A, T, C, G}.Pattern Matching algorithms i.e. string searching algorithms, sometimes called string matching algorithms, are an important class of string algorithms. The impor- tance of these algorithms should be obvious to anyone who uses a computer. Some of these algorithms can be used in word processors, in utilities such as grep on Unix, in textual information retrieval programs such as Medline, Lexis, or Nexis, in library catalog searching programs, in internet browsers and crawlers, in internet news read-ers that can search the articles for topics of interest, in the giant digital libraries, in electronic journals, in telephone directory assistance. In molecular biology there are several hundreds of specialized databases holding DNA, RNA, and other strings.There are also several variations of the secure pattern matching problem:The pattern may contain wildcards. This problem has been widely studied by researchers with the aim of generalizing the basic searching model to searching with errors and it can be solved in O(n+m) time[7]. The matches may be approximated, such as Hamming distance less than some threshold τ. A recent algorithm for solving this problem without considering privacy is proposed by Amir et al.[6] which introduced a solution in time O(n (?)).With the development of the society and science and technology, security has attracted more and more attention. For example in molecular biology, the information of specialized databases holding DNA, RNA, and other strings is very important for personal privacy. So pattern matching protocols that can protect the privacy has become the requirement for people's concern and our protocol is based on this.Our cryptography protocols for the secure pattern matching consist of three pro-tocols as below:1. We use suffix tree to design an effective protocols for basic pattern matching with constant-rounds, linear communication and linear computational costs in theory. Our research is about the highly motivated problem of secure two-party pattern matching:party A holds a text t∈{0,1}n of length n, while party B has a pattern p∈{0,1}m of length m. The goal is for B to learn where his pattern occurs in the text of t. We require that no wildcard is included in p and t, the communication complexity and the computational complexity is O(n+m) in theory. More over due to the good properties of suffix tree, our scheme is much better than previous schemes in practice, especially when the length n of the string t is much larger than the length m of the pattern p, which fits the requirement in practice. This protocol can guarantee full simulation in the presence of malicious, polynomial-time adversaries.2. We use the Boneh-Goh-Nissim scheme that is homomorphic to arbitrary addi-tions and one multiplication to design an effective protocols for the problem of pattern matching with wildcard. We reduce the complexity of the protocol of pattern matching with wildcard from O(mn)[10] or O(n log m)[11] to O(m+n). The limitation of our scheme is that we need a trusted party to deal with the key generating progress. The security of our scheme can guarantee full simulation in the presence of malicious, polynomial-time adversaries.3. We use the Boneh-Goh-Nissim scheme to design an effective protocols for the problem of the approximate pattern matching problem. We reduce the complexity of the approximate pattern matching problem from O(mn)[10] or O(n log m)[11] to O(nτ). The limitation of our scheme is that we need a trusted party to deal with the key generating progress. The security of our scheme can guarantee full simulation in the presence of malicious, polynomial-time adversaries.