Cloud computing provides users with ample computing resources, storage, and bandwidth to meet their computing needs, often at minimal cost. As such services become popular and available to a larger body of users, security mechanisms become an integral part of them. Conventional means for protecting data privacy, such as encryption, can protect communication and stored data from unauthorized access including the service provider itself. Such tools, however, are not sufficient against powerful adversaries who can force users into opening their encrypted content. In this work we introduce the concept of deniable cloud storage that guarantees privacy of data even when one’s communication and storage can be opened by an adversary. We show that existing techniques and systems do not adequately solve this problem. We design the first sender-and-receiver deniable public-key encryption scheme that is both practical and is built from standard tools. Furthermore, we treat practical aspects of user collaboration and provide an implementation of a deniable shared file system, DenFS.