Untraceable secret credentials: trust establishment with privacy

There is generally no a priori trust relationship among entities interacting in pervasive computing environments which makes it necessary to establish trust from scratch. This task becomes extremely challenging when it is simultaneously necessary to protect the privacy of the actors involved. This paper shows how trust can be based on previous interactions yet remain unlinkable to any previous event or any specific entity. A solution based on group blind signatures is proposed that relies on credentials both secret, meaning that they contain an encrypted description of previous interactions, and untraceable, meaning that they cannot be recognized when presented to their issuer. can prove that he was previously certified as a reliable partner by the entity he is interacting with again. After any interaction, a credential is provided in order to subsequently assert what happened in a previous relationship. When two entities interact, they can exchange one or more credentials that enable trust establishment. To ensure that a credential holder will show negative as well as positive statements, we propose to encrypt credentials so that only the issuer and some trusted relatives can open it.