A service discovery protocol may allow clients in a distributed computing environment to search for services. Service providers (or a listener agent) may respond to search requests by publishing or providing corresponding service advertisements or URIs to corresponding service advertisements. When a service provider responds to a discovery search request (either directly or through a listener agent), the provider may choose to publish a protected or an un-protected (complete) advertisement. A protected advertisement may include the set of information necessary to obtain a complete advertisement. Publishing a protected advertisement may force the client to obtain a valid credential from an authentication service before receiving the complete un-protected advertisement from the service provider. A complete un-protected advertisement is needed to create a message endpoint for accessing the service. Forcing clients to obtain a valid credential before receiving an advertisement may provide an additional level of security for the service provider. The security credential that may need to be obtained to receive the complete advertisement may also be used to construct a message gate to communicate with the service where the gate embeds the security credential in each message to the service.