many Grid services deployments, the clients and servers reside in different administrative domains. Hence, there is a requirement both to discover each other?s authorization policy, in order to be able to present the right assertions that allow access, and to reveal as little as possible of the access policy details to unauthorized parties. This paper describes a mechanism where the client and servers are semantically annotated with policies that protect their resources. These annotations specify both constraints and capabilities that are used during a negotiation to reason about and communicate the need to see certain credentials from the other party and to determine whether requested credentials can be obtained and revealed. The result of the negotiation is a state where both parties have satisfied their policy constraints for a subsequent interaction or where such interaction is disallowed by either or both. Furthermore, we present an implementation of a prototype, based on the PEERTRUST policy language, and a reasoning engine that is integrated in the Web services runtime component of the Globus Toolkit. The negotiation process is facilitated through the implementation of WSRF-compliant service interfaces for protocol message exchanges.