According to the Census Bureau of the U.S. Department of Commerce, Electronic Commerce in the United States generated sales of approximately 100 billion USD in the year 2006. Today, there is a large number of corporations that use electronic commerce as their primary means of conducting business. As the number of customers using the Internet for acquiring services increases, the demand for providing fast, reliable and secure transactions increases accordingly --- most of the times beyond the capacity of individual businesses to provide the level of service required, given the overwhelming data management and information processing costs involved. Increased demand has fueled a trend towards outsourcing data management and information processing applications to third-party service providers in order to mitigate the in-house cost of furnishing online services. In this model the third-party service provider is responsible for offering the necessary resources and mechanisms for efficiently managing and accessing the outsourced data, by data owners and customers respectively. Clearly, data outsourcing intrinsically raises issues related with trust. Service providers cannot always be trusted (they might have malicious intend), might be compromised (by other parties with malicious intend) or run faulty software (unintentional errors). Hence, this model raises very interesting research issues on how to guarantee quality of service in untrusted database management environments, which translates into providing verification proofs to both data owners and clients that the information they process is correct. In this talk I will give an overview of the applications of database outsourcing, formally introduce trust related information security problems, give a brief introduction of the necessary cryptographic tools that are commonly used for alleviating the impact of such problems and, finally, motivate two specific verification problems along with their solutions.