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.