Cloud services offer reduced costs, elasticity and a promised unlimited managed storage space that attract many end-users. File sharing, collaborative platforms, email platforms, back-up servers and file storage are some of the services that set the cloud as an essential tool for everyday use. Currently, most operating systems offer built-in outsourced cloud storage applications, by design, such as One Drive and iCloud, as natural substitutes succeeding to the local storage. However, many users, even those willing to use the aforementioned cloud services, remain reluctant towards fully adopting cloud outsourced storage and services. Concerns related to data confidentiality rise uncertainty for users maintaining sensitive information. There are many, recurrent, worldwide data breaches that led to the disclosure of users sensitive information. To name a few: a breach of Yahoo late 2014 and publicly announced in September 2016, known as the largest data breach of Internet history, led to the disclosure of more than 500 million user accounts; a breach of health insurers, Anthem in February 2015 and Premera BlueCross BlueShield in March 2015, that led to the disclosure of credit card information, bank account information, social security numbers, data income and more information for more than millions of customers and users. A traditional countermeasure for such devastating attacks consists of encrypting users data so that even if a security breach occurs, the attackers cannot get any information from the data. Unfortunately, this solution impedes most of cloud services, and in particular, searching on outsourced data. Researchers therefore got interested in the following question: "how to search on outsourced encrypted data while preserving efficient communication, computation and storage overhead?" This question had several solutions, mostly based on cryptographic primitives, offering numerous security and efficiency guarantees. While this problem has been explicitly identified for more than a decade, many research dimensions remain unsolved. The main goal of this thesis is to come up with practical constructions that are (1) suitable for real life deployments verifying necessary efficiency requirements, but also, (2) providing good security insurances. Throughout our research investigation, we identified symmetric searchable encryption (SSE) and oblivious RAM (ORAM) as the two potential and main cryptographic primitives candidate for real life settings. We have recognized several challenges and issues inherent to these constructions and provided a number of contributions that improve upon the state of the art. First, we contributed to make SSE schemes more expressive by enabling Boolean, semantic, and substring queries. Practitioners, however, need to be very careful about the provided balance between the security leakage and the degree of desired expressiveness. Second, we improve ORAM's bandwidth by introducing a novel recursive data structure and a new eviction procedure for the tree-based class of ORAM constructions, but also, we introduce the concept of resizability in ORAM which is a required feature for cloud storage elasticity.