The increasing availability of information about people's context makes it possible to deploy context-sensitive services, where access to resources provided or managed by a service is limited depending on a person's context. For example, a location-based service can require Alice to be at a particular location in order to let her use a printer or learn her friends' location. However, constraining access to a resource based on confidential information about a person's context can result in privacy violations. For instance, if access is constrained based on Bob's location, granting or rejecting access will provide information about Bob's location and can violate Bob's privacy. We introduce an access-control algorithm that avoids privacy violations caused by context-sensitive services. Our algorithm exploits the concept of access-rights graphs, which represent all the information that needs to be collected in order to make a context-sensitive access decision. Moreover, we introduce hidden constraints, which keep some of this information secret and thus allow for more flexible access control. We present a distributed, certificate-based access-control architecture for context-sensitive services that avoids privacy violations, two sample implementations, and a performance evaluation.