Many operators of cellphone networks now offer location-based services to their customers, whereby an operator often outsources service provisioning to a third-party provider. Since a person's location could reveal sensitive information about the person, the operator must ensure that the service provider processes location information about the operator's customers in a privacy-preserving way. So far, this assurance has been based on a legal contract between the operator and the provider. However, there has been no technical mechanism that lets the operator verify whether the provider adheres to the privacy policy outlined in the contract. We propose an architecture for location-based services based on Trusted Computing and Secure Logging that provides such a technical mechanism. Trusted Computing lets an operator query the configuration of a location-based service. The operator will hand over location information to the service only if the service is configured such that the service provider cannot get access to location information using software-based attacks. This includes passive attacks, where the provider monitors information flowing into and out of its service, and active attacks, where the provider modifies or injects customer queries to the service. We introduce several requirements that must be satisfied by a location-based service to defend against passive attacks. Furthermore, we present Secure Logging, an auditing mechanism to defend against active attacks.