In our daily lives, people or devices frequently need to learn their location for many reasons as some services depend on the absolute location or the proximity. The outcomes of positioning systems can have critical effects e.g., on military, emergency. Thus, the security of these systems is quite important. In this thesis, we concentrate on many security aspects of position in cryptography. The first part of this thesis focuses on the theory of distance bounding. A distance bounding protocol is a two-party authentication protocol between a prover and a verifier which considers the distance of the prover as a part of his/her credential. It aims to defeat threats by malicious provers who try to convince that they are closer to the verifier or adversaries which seek to impersonate a far-away prover. In this direction, we first study the optimal security bounds that a distance bounding protocol can achieve. We consider the optimal security bounds when we add some random delays in the distance computation and let the prover involve distance computation. Then, we focus on solving the efficiency problem of public-key distance bounding because the public-key cryptography requires much more computations than the symmetric-key cryptography. We construct two generic protocols (one without privacy, one with) which require fewer computations on the prover side compared to the existing protocols while keeping the highest security level. Then, we describe a new security model involving a tamper-resistant hardware. This model is called the secure hardware model (SHM). We define an all-in-one security model which covers all the threats of distance bounding and an appropriate privacy notion for SHM. The second part of this thesis is to fill the gap between the distance bounding and its real-world applications. We first consider contactless access control. We define an integrated security and privacy model for access control using distance bounding (DB) to defeat relay attacks. We show how a secure DB protocol can be converted to a secure contactless access control protocol. Regarding privacy (i.e., keeping anonymity in a strong sense to an active adversary), we show that the conversion does not always preserve privacy, but it is possible to study it on a case by case basis. Then, we consider contactless payment systems. We design an adversarial model and define formally the contactless payment security against malicious cards and malicious terminals. Accordingly, we design a contactless payment protocol and show its security in our security model. The last part of this thesis focuses on positioning. We consider two problems related to positioning systems: localization and proof of location. In localization, a user aims to find its position by using a wireless network. In proof of location, a user wants to prove his/her position e.g., to have access to a system or authorize itself. We first formally define the problem of localization and construct a formal security model. We describe algorithms and protocols for localization which are secure in our model. Proof of location has been considered formally by Chandran et al. in CRYPTO 2009 and it was proved that achieving security is not possible in the vanilla model. By integrating the localization and the secure hardware model, we obtain a model where we can achieve proof of location.
In our daily lives, people or devices frequently need to learn their location for many reasons as some services depend on the absolute location or the proximity. The outcomes of positioning systems can have critical effects e.g., on military, emergency. Thus, the security of these systems is quite important. In this thesis, we concentrate on many security aspects of position in cryptography. The first part of this thesis focuses on the theory of distance bounding. A distance bounding protocol is a two-party authentication protocol between a prover and a verifier which considers the distance of the prover as a part of his/her credential. It aims to defeat threats by malicious provers who try to convince that they are closer to the verifier or adversaries which seek to impersonate a far-away prover. In this direction, we first study the optimal security bounds that a distance bounding protocol can achieve. We consider the optimal security bounds when we add some random delays in the distance computation and let the prover involve distance computation. Then, we focus on solving the efficiency problem of public-key distance bounding because the public-key cryptography requires much more computations than the symmetric-key cryptography. We construct two generic protocols (one without privacy, one with) which require fewer computations on the prover side compared to the existing protocols while keeping the highest security level. Then, we describe a new security model involving a tamper-resistant hardware. This model is called the secure hardware model (SHM). We define an all-in-one security model which covers all the threats of distance bounding and an appropriate privacy notion for SHM. The second part of this thesis is to fill the gap between the distance bounding and its real-world applications. We first consider contactless access control. We define an integrated security and privacy model for access control using distance bounding (DB) to defeat relay attacks. We show how a secure DB protocol can be converted to a secure contactless access control protocol. Regarding privacy (i.e., keeping anonymity in a strong sense to an active adversary), we show that the conversion does not always preserve privacy, but it is possible to study it on a case by case basis. Then, we consider contactless payment systems. We design an adversarial model and define formally the contactless payment security against malicious cards and malicious terminals. Accordingly, we design a contactless payment protocol and show its security in our security model. The last part of this thesis focuses on positioning. We consider two problems related to positioning systems: localization and proof of location. In localization, a user aims to find its position by using a wireless network. In proof of location, a user wants to prove his/her position e.g., to have access to a system or authorize itself. We first formally define the problem of localization and construct a formal security model. We describe algorithms and protocols for localization which are secure in our model. Proof of location has been considered formally by Chandran et al. in CRYPTO 2009 and it was proved that achieving security is not possible in the vanilla model. By integrating the localization and the secure hardware model, we obtain a model where we can achieve proof of location.
Location (or distance) information of a device plays a significant role in current location-based systems. How to determine the location of a device or verify the location claims made by a device is challenging, as devices are untrusted and may have an incentive to claim a false location. In secure localization and positioning system, the trusted verifier(s) interact with the untrusted prover to determine its location or validate its location claim. In this thesis, we mainly focus on one of the prominent areas of such systems: distance bounding. Distance (upper) bounding (DUB) allows a verifier to verify whether a proving party is located within a certain distance bound. DUB protocols have many applications in secure authentication and location-based services. This thesis has two main contributions. The first is that we consider the dual problem of distance lower bounding (DLB), where the prover proves it is outside a distance bound from the verifier. We motivate this problem through a number of application scenarios and model security against distance fraud (DF), Man-in-the-Middle (MiM), and collusion fraud (CF) attacks. We prove impossibility of security against these attacks without making physical assumptions. We propose approaches to the construction of secure protocols under reasonable physical assumptions and give detailed design of a DLB protocol with security analysis using our proposed model. This is the first treatment of the DLB problem in the untrusted prover setting with a number of applications, raising new research directions and opportunities in location based services. We discuss our results and propose directions for future research. One of the main assumptions which DUB protocols rely on is that the time that the prover spends in receiving the challenge, processing, and sending the response is negligible compared to the propagation time of the signal between the prover and verifier. This strict requirement poses difficulties on the implementation of DUB protocols and limits the possible development of applications for distance bounding as well. The second contribution in this thesis is that we design a novel one-round DUB protocol that uses one-way transmission time to estimate the distance instead of round-trip time, so that the assumption of negligible processing time is not required any longer. In order to prove the security, we formalize the notion of time in a distributed environment with adversarial users. In this model, time is implemented by a trusted party broadcasting unpredictable timestamps at a high frequency. We show that the timestamp is proved to be fresh and unpredictable. We then extend the time model to formalize DUB protocols and define corresponding attacks. Finally, we prove the security of our proposed distance bounding protocol and discuss potential issues when implementing such protocol. Besides these two main contributions, we also have the following two contributions: (1) we identify and analyze a new attack: false rejection attack, which poses serious threat to proximity-based authentications that uses distance bounding protocol for proximity evaluation; (2) We investigate the feasibility of replay attack in context-based proximity authentication using real-world data.
In this thesis, we initiate the study of cryptographic protocols where the identity, or other credentials and inputs, of a party are derived from its geographic location.
We start by considering the central task in this setting, i.e., securely verifying the position of a device. Despite much work in this area, we show that in the Vanilla (or standard) model, this above task (i.e., of secure positioning) is impossible to achieve, even if we assume that the adversary is computationally bounded. In light of the above impossibility result, we then turn to Dziembowski's Bounded Retrieval Model (a variant of Maurer's Bounded Storage Model) and formalize and construct information theoretically secure protocols for two fundamental tasks: Secure Positioning; and Position-Based Key Exchange.
We then show that these tasks are in fact universal in this setting—we show how we can use them to realize Secure Multi-Party Computation.
The main contribution of this thesis is threefold: to place the problem of secure positioning on a sound theoretical footing; to prove a strong impossibility result that simultaneously shows the insecurity of previous attempts at the problem; and to present positive results showing that the bounded-retrieval framework is a fruitful one to study the foundations of position-based cryptography.
This thesis is based on joint works with Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky.
In this paper, we initiate the theoretical study of cryptographic protocols where the identity, or other credentials and inputs, of a party are derived from its geographic location. We start by considering the central task in this setting, i.e., securely verifying the position of a device. Despite much work in this area, we show that in the vanilla (or standard) model, the above task (i.e., of secure positioning) is impossible to achieve, even if we assume that the adversary is computationally bounded. In light of the above impossibility result, we then turn to Dziembowski's bounded retrieval model (a variant of Maurer's bounded storage model) and formalize and construct information theoretically secure protocols for two fundamental tasks: secure positioning and position-based key exchange. We then show that these tasks are in fact universal in this setting---we show how we can use them to realize secure multiparty computation. Our main contribution in this paper is threefold: to place the problem of secure positioning on a sound theoretical footing; to prove a strong impossibility result that simultaneously shows the insecurity of previous attempts at the problem; and to present positive results showing that the bounded-retrieval framework is a fruitful one to study the foundations of position-based cryptography.
Chandran, et al. introduce the direction of position based cryptography at CRYPTO 2009. In position based cryptography, the position of a party is used to be its unique “credential” in order to realize the cryptographic tasks, such as position based encryption, position based signature, position based key exchange and so on. Position based key exchange, as a basic primitive in position based cryptography, can be used to establish a shared key based on the position of the participant. To begin with, this paper presents the notions of the prover-to-verifier mode and the prover-to-prover mode for position based key exchange. In the prover-to-verifier mode, a secret key can be shared between a prover and the verifiers according to the position of the prover. While in the prover-to-prover mode, two provers located at the valid positions can negotiate a shared key with the help of the verifiers and any other party whose position is illegal cannot obtain the shared key. At the same time, this paper formalizes two security definitions against colluding adversaries: position based prover-to-verifier key exchange and position based prover-to-prover key exchange. Then, this paper introduces the bounded retrieval model and the implementations of position based key exchange in two modes based on the bounded retrieval model. Finally, this paper discusses the position based key exchange protocols in two modes from both security and performance perspectives.
In this work, we investigate the security of interactive computations. The main emphasis is on the mathematical methodology that is needed to formalise and analyse various security properties. Differently from many classical treatments of secure multi-party computations, we always quantify security in exact terms. Although working with concrete time bounds and success probabilities is technically more demanding, it also has several advantages. As all security guarantees are quantitative, we can always compare different protocol designs. Moreover, these security guarantees also have a clear economical interpretation and it is possible to compare cryptographic and non-cryptographic solutions. The latter is extremely important in practice, since cryptographic techniques are just one possibility to achieve practical security. Also, working with exact bounds makes reasoning errors more apparent, as security proofs are less abstract and it is easier to locate false claims. The choice of topics covered in this thesis was guided by two principles. Firstly, we wanted to give a coherent overview of the secure multi-party computation that is based on exact quantification of security guarantees. Secondly, we focused on topics that emerged from the author's own research. In that sense, the thesis generalises many methodological discoveries made by the author. As surprising as it may seem, security definitions and proofs mostly utilise principles of hypothesis testing and analysis of stochastic algorithms. Thus, we start our treatment with hypothesis testing and its generalisations. In particular, we show how to quantify various security properties, using security games as tools. Next, we review basic proof techniques and explain how to structure complex proofs so they become easily verifiable. In a nutshell, we describe how to represent a proof as a game tree, where each edge corresponds to an elementary proof step. As a result, one can first verify the overall structure of a proof by looking at the syntactic changes in the game tree and only then verify all individual proof steps corresponding to the edges. The remaining part of the thesis is dedicated to various aspects of protocol design. Firstly, we discuss how to formalise various security goals, such as input-privacy, output-consistency and complete security, and how to choose a security goal that is appropriate for a specific setting. Secondly, we also explore alternatives to exact security. More precisely, we analyse connections between exact and asymptotic security models and rigorously formalise a notion of subjective security. Thirdly, we study in which conditions protocols preserve their security guarantees and how to safely combine several protocols. Although composability results are common knowledge, we look at them from a slightly different angle. Namely, it is irrational to design universally composable protocols at any cost; instead, we should design computationally efficient protocols with minimal usage restrictions. Thus, we propose a three-stage design procedure that leads to modular security proofs and minimises usage restrictions.
Randomness plays a central role in computer science, in particular cryptography. Almost all cryptographic primitives depend crucially on randomness because randomness and unpredictability in secret keys provides the means for security. Usually one assumes that perfect randomness, a sequence of independently and uniformly distributed bits, are accessible to algorithms. This is a strong assumption. Physical sources of randomness are neither uniformly random, nor produce necessarily independent bits. Therefore, the aim of this thesis is to start from a realistic model of randomness, investigate notions of secrecy and their randomness requirements and finally find practical methods for generation of randomness that matches the requirements of cryptographic primitives. We consider a model of random source where the source output follows one distribution from a set of possible distributions, each with the property that the maximum probability of symbols is bounded and can not be arbitrarily close to 1. This model does not assume independence or uniformity of the output symbols, and is considered to be a realistic model of randomness. From this point, the thesis can be divided into two main parts: In the first part, considering various notions of information theoretic secrecy, a fundamental problem is to find the properties of randomness needed to achieve security in these notions. Traditional cryptographic protocols simply assume perfect randomness and build on this assumption. We explore the results that show secrecy can not be based on imperfect randomness that is not uniform or independent. Thus a line of work attempts to relax notions of secrecy in such a way that they can be constructed with non-perfect sources, and possibly require smaller key sizes. Yet they should match real life applications. An important work in this context is entropic security where the key size could be smaller than the message depending on message distribution. Inspired by this, we propose two relaxed notions of secrecy that are motivated by practical applications. In the first notion, motivated by an application in biometrics authentication, we propose guessing secrecy where the probability of guessing the message for a computational unbounded adversary with the best strategy remains the same when a ciphertext is given or when it is not. We compare the randomness requirements of guessing secrecy with stronger notions and show that in some cases such as key length, the requirements are the same. For key distribution however, we found a family of distributions that provide guessing secrecy but not perfect secrecy. In the second notion, we investigate randomness requirements of multiple message encryption. Considering a natural extension of secrecy definition to multiple messages, we show that independent keys are needed to encrypt each message. We then propose a relaxed notion in which the security of last message is more important than past messages, although the leakage of past messages is bounded using entropic security. By this assumption, we achieve smaller key length compared to indistinguishability, and comparable to key length for entropic security. This notion has applications such as location privacy. In the second part of the thesis, since secrecy crucially depends on perfect randomness, we investigate how perfect randomness can be practically generated, specifically from human game-play. Unlike many random number generators that assume independent or uniform random bits in the random source, we base our work on the realistic model of randomness. Our main observation is that human game-play has an element of randomness coming from the errors in their game-play which is the main entertaining factor of the game. We also observed that this game-play can distinguish among a group of people if the right features are collected from the game-play. We incrementally changed our game design until the distinguishability among a small population is maximized, and then run the experiments required to show the viability of this approach over a larger population. This approach can also provide a hard to delegate authentication property where a human could not emulate the behavior of another human even given statistical information about their game-play.