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.

Leakage-abuse attacks using access pattern leakage from range queries have been shown to reconstruct encrypted databases. However, prior work is either restricted to one-dimensional databases or requires access to all possible responses in two-dimensions. In this paper, we explore what an adversary can achieve with minimal leakage, focusing on denser databases, and present a leakage abuse attack from access pattern of range queries in multiple dimensions. Our attack employs a novel technique to systematically amplify access pattern leakage, inferring a large number of new query responses that have not been requested by the user. Letm be the size of the database domain. Our attack works on d-dimensional databases and achieves approximate reconstruction. For dense databases and a parameter 0 < ? < 1, our attack fully reconstructs an inner portion of size ?m of the database (referred to as the ?-core) after observing O(m logm) queries, uniformly at random. These are significant improvements over previous attacks that require the full set of responses, which has size O(m²). We are the first to leverage graph drawing techniques for database reconstruction attacks. We implement our attack and evaluate it with experiments on real-world databases, achieving accurate reconstructions after observing a small percentage of the responses.