Information retrieval techniques hide the user's query, e.g., the data item searched for, but not the data being queried. To outsource valuable data to an insecure server, such techniques are clearly not appropriate. The authors consider a cloud computing setting in which similarity querying of metric data is outsourced to a service provider. The data is to be revealed only to trusted users, not to the service provider or anyone else. The paper presents techniques that transform the data prior to supplying it to the service provider for similarity queries on the transformed data. Their techniques provide interesting trade-offs between query cost and accuracy. They are then further extended to offer an intuitive privacy guarantee.