Substantial advances in cloud technologies have made outsourcing data to the cloud highly beneficial today (e.g., costs savings, scalability, provisioning time). However, strong concerns from private companies and public institutions about the security of the outsourced data still hamper the adoption of cloud solutions. This reluctance is fed by frequent massive data breaches either caused by external attacks against cloud service providers or by negligent or opaque practices from the service provider itself. For broader adoption of cloud services, this dissertation addresses the data security and privacy concerns in the cloud setting. The goal is to ensure security and privacy of outsourced data while maintaining the ability to execute queries efficiently. Security/privacy comes at a cost of functionality/performance. Therefore, we seek for a proper balance in the space of security, privacy, functionality, and performance. This dissertation works the problems of range query execution over encrypted data, privacy preserving data mining in the context of environmental sustainability studies, and access privacy in the cloud. To enable efficient and secure range query processing over traditional databases, we introduce PINED-RQ, a highly efficient and differentially private range query execution framework that constructs a novel differentially private index over an outsourced database. Second, this dissertation presents a comprehensive study of the environmental sustainability metrics. Our contributions in this context are twofold: 1) to better evaluate the environmental impacts of the industrial processes privately, we formally define privacy preserving certification paradigm and develop a framework that enables untrusted third party to certify parties based on a well agreed upon set of criteria. 2) to explore the privacy concerns over publicizing the industrial activities in the form of life cycle assessment (LCA) computations, which is a standard way of evaluating an impact of a product and service. This dissertation initiates a study to explore privacy and security challenges that prevent organizations from making public disclosures about their activities. Finally, this dissertation explores access privacy in the cloud setting. We design and develop TaoStore, a highly efficient and practical cloud data store, which secures data confidentiality and hides access patterns from adversaries. Additionally, we propose a new ORAM security model, called aaob-security, which considers completely asynchronous network communication and concurrent processing of requests. This dissertation shows that it is possible to deliver practical and high-performance data services in the cloud without sacrificing security

and privacy if the requirements of each application are analyzed correctly and a correct balance is found in the space of security, privacy, functionality, and performance.