Cryptographic primitives are essential for constructing privacy-preserving communication mechanisms. There are situations in which two parties that do not know each other need to exchange sensitive information on the Internet. Trust management mechanisms make use of digital credentials and certificates in order to establish trust among these strangers. We address the problem of choosing which credentials are exchanged. During this process, each party should learn no information about the preferences of the other party other than strictly required for trust establishment. We present a method to reach an agreement on the credentials to be exchanged that preserves the privacy of the parties. Our method is based on secure two-party computation protocols for set intersection. Namely, it is constructed from private matching schemes.