Software services offer many opportunities like reduced cost for IT infrastructure. They also introduce new risks, for example the clients lose control over their data. While data can be secured against external threats using standard techniques, the service providers themselves have to be trusted to ensure privacy. In this paper, we examine methods that can increase the level of privacy a service offers without the need to fully trust the service provider.