Many useful internet-based services, such as email, back-up storage, electronic medical records, etc., are hosted in the Cloud in large, expensive data centers run by major companies. Private outsourcing of services and computation to the Cloud is an important issue for sensitive data. Many services currently rely on trusting the Cloud provider to maintain confidentiality of private data and to assure integrity of data and computation. Privacy loss can occur through either explicit mining of personal data, or inadvertent leakage, or compromising anonymity in databases. We will discuss solutions based on emerging tools from cryptography to prevent and mitigate these problems.