Cryptography in radio frequency identification and fair exchange protocols

This PhD thesis focuses on fair exchange protocols and radio frequency identification protocols. Fair exchange stems from a daily life problem: how can two people exchange objects (material or immaterial) fairly, that is, without anyone being hurt in the exchange? More formally, if Alice and Bob each have objects mA and mB respectively, then the exchange is fair if, at the end of the protocol, both Alice and Bob have received mB and mA respectively, or neither Alice nor Bob have received the expected information, even partially. Ensuring fairness in an exchange is impossible without introducing additional assumptions. Thus, we propose two approaches to overcome this problem. The first consists in attaching to each person, a guardian angel, that is, a security module conceived by a trustworthy authority and whose behavior cannot deviate from the established rules. In such a model, the fairness of the exchange can be ensured with a probability as close to 1 as desired, implying however a communication complexity cost. We then use results from the distributed algorithm to generalize this approach for n people. Finally, we propose a second approach that consists in no more considering the exchange in an isolated manner, but to replace it in its context, in the heart of a network, where each person in the pair has a few honest neighbors. In this framework, fairness can lie on these neighbors, who are solicited only in the case of a conflict during the exchange. We then look into Radio Frequency Identification (RFID), which consists in remotely identifying objects or subjects having a transponder. The great achievements that radio frequency identification has made today, lies essentially on the willingness to develop low cost and small size transponders. Consequently, they have limited computation and storage capabilities. Due to this reason, many questions have been asked regarding RFID's potential and limitations, more precisely in terms of security and privacy. Since this is a recent problem, the works presented in this document first outline completely the framework by introducing certain basic concepts. In particular, we present and classify threats, we show the link between traceability and the communication model, and we analyze existing RFID protocols. We also present the complexity issues due to key management. We show that the solution proposed by Molnar and Wagner has weaknesses and we propose another solution based on time-memory trade-offs. Finally, we continue our time-memory trade-off analysis by proposing a method based on checkpoints, which allows detecting false alarms in a probabilistic manner.