Facilitated by the rapid growth of the Internet, electronic commerce is growing exponentially. As a result, millions of players participate in electronic trade, yet many of these players are strangers to each other. This implies mistrust, which may bring about manipulative and malicious trade behaviors among the parties. This problem intensifies in electronic environments where agents act on behalf of humans. There, self-interested, utility-maximizing agents, have a strong motivation, and no moral means against, malicious action. Attempts to prevent such misbehavior usually concentrate on designing non-manipulable mechanisms. Yet, these tend to be either computationally intractable or sub-optimal. We suggest a new approach: a mechanism that allows agents in an open system to establish trust among themselves and to dynamically update this trust. Although we rely on certificates for our solution, we do not require (in contrast to previous solutions) any centralized certificate authority system, nor do we require some well known, trusted parties. Our solution is fully distributed, it is computationally feasible, and can be easily added to any agent architecture.