DelRightGuard: A secure yet lightweight data deletion notification distribution protocol for safeguarding right to deletion

In recent years, the right to deletion of individual has been recognized by many privacy protection laws and regulations. It stipulates that the data controller receiving individual data deletion request shall not only erase the required data, but also take reasonable steps to inform other data controllers to delete the same data. Prior to irrecoverable data erasure, it is of paramount importance to design a distribution and acknowledgement process of deletion notifications across involved data controllers. The design of such a mechanism is faced with the following challenges: 1) completeness: Ensuring that all relevant data controllers, who possess the data slated for erasure, are duly informed; 2) robustness: Immune from malicious attacks when deletion notifications traverse through untrusted networks; 3) lightweight: Reduce the right to deletion compliance cost and accommodate more deletion requests for data controllers. To this end, this article proposes DelRightGuard, which is the first attempt to tackle with the aforementioned challenges. DelRightGuard is built on a cross-plane cooperation architecture between regulatory and service planes. Within regulatory plane, DelRightGuard proposes a cuckoo filters based on data circulation recording algorithm to efficiently ensure the completeness of deletion notifications. Within service plane, DelRightGuard devises a secure yet lightweight deletion notification distribution protocol that runs on a network function hosted by each data controller. This protocol employs HMAC based hop-by-hop forward traversal verification, recursive backward acknowledgement and probabilistic sampling verification, so that it ensure the robustness and lightweight of deletion notification distribution process. We implement a prototype for DelRightGuard. The experimental result confirms that it is practical with acceptable performance.