Service Discovery as an essential element in pervasive computing environments is widely accepted. Much active research on service discovery has been conducted, but privacy has been ignored and may be sacrificed. While it is essential that legitimate users should be able to discover services of which they have credentials, it is also necessary that services be hidden from illegitimate users. Since service information, service provider's information, service requests, and credentials to access services via service discovery protocols may be sensitive, we may want to keep them private. Existing service discovery protocols do not solve these problems. We present a user-centric model, called PrudentExposure, as the first approach designed for exposing minimal information privately, securely, and automatically for both service providers and users of service discovery protocols. We analyze the mathematical properties of our model and formally verify our security protocol.