A cloud provider that can technically determine tenants’ operations may be compelled to disclose such activities by law enforcement agencies (LEAs). The situation gets even more complex when multiple LEAs across different jurisdictions are involved, e.g., because of the distributed locations of cloud servers and data storage. Yet cloud providers typically do not need or want to know about their tenants’ activities, other than measuring how such activities incur expenses for using cloud resources. Thus mechanisms should be developed for cloud providers to have sufficient plausible deniability with regards to the processing being carried out by tenants on their platform, in jurisdictions that permit cloud providers to avoid liabilities in this way. Symmetrically, such mechanisms could protect tenants from legal over-reach, for example, when the country in which the cloud provider is incorporated could force disclosure of the processing carried out by cloud tenants. But to what extent can cloud providers acquire plausible deniability? Current discussions regarding risk have focused on data confidentiality and integrity. We argue that processing operations can equally reveal sensitive information—such as trade secrets and business processes—and that for some classes of application both data protection and algorithm protection are necessary. In this paper, we examine the legal and technical motivations for achieving plausible deniability in cloud interactions. We demonstrate the likely performance overhead of using containers secured with technologies such as Intel SGX. Further, we examine the current limitations of our proposed plausible deniability mechanisms, and outline a potential approach for enabling lawful access to enclaves subject to appropriate judicial oversight.