Provable Co-Owned Data Deletion with Zero-Residuals and Verifiability in Multi-Cloud Environment

The rapid expansion of multi-cloud environments and the growing prevalence of collaborative data ownership present significant challenges in ensuring the verifiable deletion of co-owned data. Current approaches predominantly address individual ownership and often rely on simplistic one-bit result protocols where a deletion command merely outputs success or failure, turning the deletion into a black box without proper verification. This paper tackles the problem of secure processing and verifiable deletion of shared outsourced data in multi-cloud environments. We design a framework that enables a data owner to outsource encrypted data to multiple co-owners, who perform computations directly within their respective cloud providers---ensuring that sensitive data never leaves the cloud. Our system leverages readily available cloud Hardware Security Modules (HSMs) to manage cryptographic keys from generation to controlled destruction---ensuring data remains inaccessible beyond its intended use. Secure Enclaves enforce on-cloud data computation, eliminating local copies and preventing unauthorized exposure. Encrypted data is structured within a fixed storage model, ensuring controlled allocation and strict storage constraints. When data expires or must be deleted to meet regulatory requirements, our framework triggers zero-residual permuted overwriting to remove the data traces irreversibly. Verifiability is achieved at two levels: Bounded Merkle Hash Tree (BMHT) ensures bounded storage and verifiable deletion within each cloud provider. In contrast, Global Merkle Forest (GMF) aggregates BMHT roots across providers, enabling consistent global verification. The data owner maintains a log of these BMHT roots, allowing independent verification of secure deletion across the multi-cloud environment.