Mobile computing is growing at an incredible pace in the world around us. With the ubiquity of personal mobile devices, new application areas continue to emerge in the wireless networking domain. One emerging area that has recently been the focus of extensive research is location-based

applications. For such applications, the idea of authentication includes verification of the physical location of the node, in addition to verifying its cryptographic identity.Although mobile entities are equipped with mechanisms like GPS to find their own locations,

a location-based application cannot trust a node to report its true location. Due to the privileges associated with the physical location, there is incentive for a node to claim a false location. Therefore, there must be a mechanism in place to determine the location of a possibly malicious node without trusting it.

Secure localization protocols enable a group of mutually trusted nodes (called verifiers) to collectively determine the location of a possibly malicious node (called prover). In this dissertation, we consider time-based secure localization protocols. Two important criteria must be satisfied in the design of such protocols: correctness and proper timing resolution. The correctness criteria is satisfied when we ensure that the protocol is secure against location cheating, and that the localization algorithm is executed as designed. The timing resolution criteria is satisfied when we ensure that the protocol can be implemented in the target system, and the accuracy of the computed location meets the accuracy requirement of the location-based application. The target system considered in this dissertation is an 802.11-based network and the target accuracy is on the order of a few meters.

Prior works on this topic either focus on the issue of correctness,

or on the issue of proper timing resolution. None of the existing protocols addresses both the criteria simultaneously. Furthermore, none of the existing protocols have been designed for, or implemented with 802.11-compatible entities. In this dissertation, we propose a new time-based localization protocol called ``Elliptical

Multilateration", which simultaneously satisfies both the criteria:

correctness and timing resolution. Our protocol also conforms to the 802.11 standard, and can be implemented with off-the-shelf 802.11-compatible hardware. In the first part of the dissertation, we identify the challenges faced in designing secure time-based localization protocols for 802.11-based networks. We introduce a new protocol that addresses these challenges. Through formal analysis, we prove that our protocol addresses the correctness criterion. The second part of the dissertation focuses on the issue of proper timing resolution.

We identify the factors which have so far prevented implementation of

time-based localization protocols in 802.11-based networks. We explain why the 802.11 standard does not support time-based localization with accuracy on the order of a few meters. We address this issue by proposing the addition of required architectural support.

Next, we quantify the effect of clock synchronization on accuracy of time-based localization. We show how to use statistical averaging to improve accuracy beyond the limits imposed by the physical layer hardware. In secure localization it is desirable to complete the localization process fast, over minimum number of message exchanges. We propose a new algorithm which leverages the maximum likelihood method for speedy localization. Our method reduces the number of message exchanges required in hyperbolic multilateration by at least 50%, and often more, in comparison to the conventional method, without compromising accuracy.

Overall, we show that it is possible to design time-based secure localization protocols that can be implemented with 802.11-compatible entities, such that the positioning accuracy is on the order of a few meters.

Time-based secure localization protocols allow a group of mutually trusted entities called verifiers to cooperatively determine the location of an untrusted and possibly malicious stranger entity called the prover. Many applications associate certain privileges with the true physical location of an entity, therefore there is an incentive for a prover to claim a more "valuable" location, different from its true location. A well known threat to time-based localization protocols is distance fraud where a malicious prover misrepresents its location by intentionally changing its response time across a series of bilateral dialogues with individual verifiers. To address this threat, secure localization protocols must use a technique called "simultaneous multilateration".

A recently introduced protocol used simultaneous challenges by multiple verifiers, over separate RF channels, to defend against distance fraud. The authors also claimed that simultaneous multilateration by using simultaneous challenges, is optimal in the sense of achieving the maximal security that can be provided by any time-based localization protocol. In the first part of this thesis, we show that the structure of this newly proposed protocol is unnecessary, and significantly more complex than existing protocols. We propose a new protocol named Elliptical Multilateration (EM) that does not use simultaneous challenges. Instead, our EM protocol achieves simultaneity in multilateration by using multiple passive receivers to observe the prover's response. Our EM protocol requires fewer resources, provides commensurate security against distance fraud, and is inherently more accurate.

The second part of this thesis focuses on the issues related to practical implementation of time-based localization protocols. Most existing works focus on cryptographic aspects of time-based secure localization protocols. We found that the existing literature does not

address the issues that arise when these time-based protocols are implemented on real systems. For example, many authors have designed protocols based on single-bit exchanges (which is non-conformant with standard networking protocols and hardware, and extremely difficult to implement), ignore inevitable measurement errors etc. In this thesis, we show that the amount and magnitude of measurement errors depend largely on the structure of a protocol, and differ significantly across the known localization protocols. We investigate whether measurements can be made with sufficient accuracy to achieve localization on the order of a few meters. To the best of our knowledge, this thesis is the first work that attempts to analyze measurement error in practical realization of different localization protocols. The factors influencing the measurement errors, which are highlighted in this thesis, are significant and cannot be ignored.

We show that taking into account the significance of message structure and the factors influencing the measurement error, can lead to new protocols that are no worse in terms of security, need fewer message exchanges, and achieve better accuracy in comparison to existing time-based localization protocols.