Trust negotiation makes it possible for two parties to carry on secure transactions by first establishing trust through a bilateral, iterative process of requesting and disclosing digital credentials and policies. Credentials, exchanged during trust negotiations, often contain sensitive attributes that attest to the properties of the credential owner. Uncontrolled disclosure of such sensitive attributes may cause grave damage to the credential owner. Research has shown that disclosing non-sensitive attributes only can cause identity to be revealed as well. Consequently, we impose a stronger requirement: our negotiations should have the k-anonymity property -- the set of credentials submitted by a subject during a negotiation should be equal to k other such sets received by the counterpart during earlier negotiations. In this paper we propose a protocol that ensures k-anonymity. Our protocol has a number of important features. First, a credential submitter before submitting its set of credentials has the assurance that its set will be identical to k other sets already stored with the counterpart. Second, we provide a cryptographic protocol ensuring that the credentials submitted by the submitter during different negotiations cannot be linked to each other. Third, we ensure that the critical data exchanged during the protocol is valid. Fourth, the major part of the protocol involves the negotiating parties only; the protocol invokes the validator only only when some critical information needs to be validated.