Application service providers (ASPs) and web services are becoming increasingly popular despite adverse IT market conditions. New languages and protocols like XML, SOAP, and UDDI provide the technical underpinnings for a global infrastructure where anybody with a networked computer has access to a large number of digital services. Not every potential customer, however, may feel comfortable about entrusting sensitive personal or corporate data to a ser- vice provider in an unprotected manner. Even if there is a high level of trust be- tween customer and provider, there may be legal requirements that require a higher level of privacy. Customers may also want to be prepared for an unfore- seen change of control on the provider’s side. something that is not an uncom- mon occurrence especially among start-up companies. This paper reviews sev- eral solutions how customers can use a provider’s services without giving it ac- cess to any sensitive data. After discussing the relative merits of trust vs. tech- nology, we focus on privacy homomorphisms, an encryption technique origi- nally proposed by Rivest et al. that maintains the structure of the input data while obscuring the actual content. We conclude with several proposals how to integrate privacy homomorphisms into existing service architectures.