Trust establishment protocols for communicating devices

With the advent of self-organizing systems such as ad hoc networks or pervasive computing, security protocols have to meet a new requirement for establishing trust among parties that have no a priori relationship such as a shared naming structure or a common organization. Trust establishment in this context calls for a new paradigm with respect to classical scenarios whereby entities build trust based on some existing security association. This thesis suggests cryptographic protocols through which some party can build trust based on the history of its interactions with other parties. Those protocols allow a party to get a proof of history, i.e. the evidence that it was involved in some interaction with another party. During further interactions, other parties consider the prover trustworthy based on the verification of the history. Privacy is an essential requirement for such a protocol since providing a proof of history to several parties without privacy would severely expose the behavior of the prover. In this work, we propose a dedicated scheme for unlinkable credentials that ensures the anonymity of the prover and the unlinkability of its interactions. This scheme is an extension of group signatures and enables the prover to choose which part of his history is disclosed when submitting a proof. Another approach consists of using evidence of physical location as a means of building trust based on the locality of communicating parties. We define the distance-bounding proof of knowledge scheme that combines a distance measurement technique and a cryptographic mechanism in order to verify the proximity of a party knowing a secret like a private key. This mechanism can be used when delivering a proof of interaction or a location stamp. Last we consider a possible architecture for establishing trust based on history. Our approach combines unlinkable credentials and distance-bounding proofs of knowledge. Thanks to this new scheme, we can show that trust among unknown parties can be built while preserving their privacy. The results of a preliminary implementation are discussed.