Today's Internet offers people a vast selection of data centric services, such as online query services, the cloud, and location-based services, etc. These internet services bring people a lot of convenience, but at the same time raise privacy concerns, e.g., sensitive information revealed by the queries, sensitive data being stored and processed in the cloud, and fine-grained location information disclosed to location-based applications. Privacy protection is desired to improve user satisfaction as well as to allow broader adoption of these internet services. However, there is usually a conflict between service functionality, performance and privacy protection. Privacy-preserving cryptographic protocols provide strong privacy, but have limited functionality and impractically expensive performance. Real internet services and applications seldom consider and incorporate privacy protection. A good balance between service functionality, performance and privacy protection is needed, so that adequate privacy can be preserved while minimally affecting functionality and performance.

This dissertation shows that using cryptographic techniques alone could be difficult to deliver a practical privacy-preserving system. With selective use of cryptographic techniques and other privacy-preserving techniques and design choices, it is possible to provide reasonably strong data security and privacy while adequately supporting practical functionalities and performance for privacy-preserving data centric services. We propose practical privacy-preserving protocols, algorithms and systems in various internet service settings. Our proposals advance the state-of-the-art of privacy-preserving systems by achieving balanced privacy, performance and functionality together. To provide practical query privacy protection for using online query services, we propose protocols that obfuscate database queries and that process obfuscated queries. Our protocols apply the expensive cryptographic operations selectively on the service data, thus significantly improving performance without linearly degrading privacy. To provide secure management and query processing on relational data in the cloud, we encrypt and disperse the data in the cloud, but build a secure index to allow the processing of various database queries on the encrypted and dispersed data, thus achieving strong data confidentiality and close to real time performance. To provide practical location privacy protection in location-based social applications, we apply user-specific, distance-preserving transformations to location coordinates, and break the association between locations and the corresponding location data, thus protecting sensitive locations and still enabling neighborhood queries and efficient retrieval of location data.