Users data are stored and utilized in the cloud for various purposes. How to best utilize these data while at the same time preserving the privacy of their owners is a challenging problem. In this dissertation, we focus on three important cloud applications, and propose solutions to enhance the privacy-utility tradeoffs of the existing ones.The first application is the federated SQL processing, where multiple mutually-untrusted data owners hold valuable data of their own, and want to execute joint SQL queries on these data without leaking information about individual records in their own shares. The second one is the cloud data collection and analysis, where services collect their users data, with proper privacy guarantees, and want to enable expressive and accurate analysis on the collected data. The last one is the end-to-end encrypted data retrieval, where a single data owner outsources her end-to-end encrypted data to the cloud, and, later, wants to retrieve some of them that are most relevant to the keyword queries requests. After comprehensive literature review of the existing solutions, we realize that the privacy- utility tradeoffs of state of the art can be substantially improved. For federated SQL processing, existing solutions leverage trusted hardware for efficient and secure computations in the cloud, while subsequent work demonstrate the devastating side-channel vulnerability of these solutions. We mitigate such vulnerability to improve the existing solutions. For data collection and analysis, existing solutions do not support joint analysis across data collected by separate services, and the supported analytics is limited, i.e., counting frequency of certain value. We propose new mechanisms and estimation algorithms to achieve better utility on the collected data. For end-to-end encrypted data retrieval, existing solutions are vulnerable to the powerful yet practical file-injection attacks, and we propose new constructions that can defend against such attacks, with practical performance. We thoroughly analyze the privacy and utility of the proposed solutions, when necessary. We also implement prototypes for all the solutions, and conduct extensive evaluations to show the performance of our proposed solutions.