Peer-to-peer (P2P) systems, and client-server type storage and computation outsourcing constitute some of the major applications that the next generation cloud schemes will address. Since these applications are just emerging, it is the perfect time to design them with security and privacy in mind. Furthermore, considering the high-churn characteristics of such systems, the cryptographic protocols employed must be efficient and scalable. This thesis shows that cryptography can be used to efficiently and scalably provide security and privacy for the next generation cloud systems. We start by describing an efficient and scalable fair exchange protocol that can be used for exchanging files between participants of a P2P file sharing system. In this system, there are two central authorities that we introduce: the "arbiter" and the "bank." We then try distributing these entities to reduce trust assumptions and to improve performance. Our work on distributing the arbiter leads to impossibility results, whereas our work on distributing the bank leads to a more general cloud computation result showing how a boss can employ untrusted contractors, and fine or reward them. We then consider cloud storage scenario, where the client outsources storage of her files to an untrusted server. We show how the client can challenge the server to prove that her file is kept intact, even when the files are dynamic. Next, we provide an agreement protocol for a dynamic message, where two parties agree on the latest version of a message that changes over time. We then apply this agreement protocol to the cloud storage setting and show how a judge can arbitrate between the client and the server officially based on the agreed-upon message and the proof sent by the server. Lastly, we show that all our solutions are efficient and scalable by presenting results from the cryptographic library we implemented. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page: http://www.proquest.com/en-US/products/dissertations/individuals.shtml.]