As a possible solution we can decouple data storage from data services. For data that doesn't need expensive computation, we can further decouple key owners f

As a possible solution we can decouple data storage from data services. For data that doesn't need expensive computation, we can further decouple key owners from data storage. Users always own their data, they can choose which data services, storage, or key manager to use and they should all interoperate. This is already a pretty common pattern in the cloud, just the same business entity owns all three. You basically need legislation that says business entities must interoperate with different data storage or key providers. So you can subscribe to gmail from google and they store your data in Amazon or maybe EFF's data storage provider. You can then get fine-grained audit trail of how and when your data is accessed. We can then come up with standard rules like maybe your data is only accessible without your end-user credential (i.e your computer+password) for law enforcement or limited operational activities described by the provider and approved by you(or your delegate).