Trust negotiation is a process that establishes mutual trust by the exchange of digital credentials and/or guiding policies among entities who may have no pre-existing knowledge about each other. Motivated by the desire to disclose as little sensitive information as possible in practice, this paper investigates the problem of minimizing the "cost" of the credentials exchanged by a trust-negotiation protocol. A credential or a policy is assigned a weighted cost, referred to as its sensitivity cost. We formalize an optimization problem, namely the minimum sensitivity cost problem, whose objective is to minimize the total sensitivity costs of the credentials and policies disclosed during trust negotiation. We study the complexity of the minimal sensitivity cost problem and propose algorithms to solve the problem efficiently, for the cases that policies are cost-sensitive and cost-insensitive. A simple finite state machine model of trust-negotiation protocols is presented to model various trust-negotiation protocols, and to provide a quantitative evaluation of the number of exchange rounds needed to achieve a successful negotiation, and the probability of achieving a successful negotiation under various credential disclosure strategies.