CAREFUL: a Secure and Privacy-Preserving Deletion Notification Distribution Protocol

The right to deletion mandates that data controllers receiving deletion requests not only erase the specified data but also notify other controllers to do the same. Designing a secure and privacy-preserving protocol for distributing deletion notifications across involved data controllers, a topic not previously addressed in the literature, presents significant challenges. In this paper, we introduce CAREFUL, a secure and privacy-preserving deletion notification distribution protocol—the first to address these challenges. It operates within a centralized architecture consisting of regulatory and service planes. The fundamental principle of CAREFUL is that the regulatory plane creates a cryptographic access control structure, ensuring that data controllers in the service plane only identify the next-hop nodes for notification. With CAREFUL, the circulation history of data pending for deletion, which is a special user’s privacy, can be preserved. Moreover, CAREFUL protects the deletion notification distribution from various malicious attacks over untrusted underlay networks. Experimental results validate CAREFUL’s practicality and its efficiency in terms of resource overhead.