Advances in networking technologies and the continued growth of the Internet have triggered a new trend towards outsourcing data management and information technology needs to external service providers. As a recent manifestation of this trend, there has been growing interest in outsourcing database services in both the commercial world and the research community. Although the outsourced database service model is emerging as an efficient replacement solution for traditional in-house database management systems, its clients, however, have to store their private data at an external service provider, who is typically not fully trusted, and so it introduces numerous security research challenges. To ensure data confidentiality, the outsourced data is usually encrypted and querying is then carried out with the support of trusted client front-ends or secure coprocessors. Despite a large number of research activities done for securing outsourced databases and removing unencrypted data from exposure to the external server and other intruders, no work has been able to radically secure outsourced databases with associated indexes during the query execution. By exploiting such indexes and with relevant available knowledge, attackers can infer confidential information from the outsourced encrypted data. This article discusses potential attacks in such situations and introduces two security protocols for outsourcing database services. The main contributions focus on solutions to the problem of data privacy/confidentiality and user privacy. The theoretical analyses show that the proposed protocols can effectively protect outsourced data and its associated indexes as well as the clients against various sophisticated attacks.