Paper 2026/1109

SoK: Cryptographic Erasure on Public Ledgers: Application-Layer Architectures, Key-Lifecycle Adversaries, and GDPR Art. 17 Sufficiency

Abstract

Public permissionless ledgers are append-only by design, yet are increasingly asked to host data subject to statutory erasure obligations (GDPR Art. 17, EDPB Guidelines 02/2025). The prevailing cryptographic response, redacting the chain itself, needs either a different chaining hash or the cooperation of every node, neither of which a controller on Bitcoin or Ethereum mainnet commands. This SoK systematizes the orthogonal application-layer design space, in which the ledger is left untouched and erasure is achieved by destroying the key material required to read the on-chain bytes. We organise the literature along two axes, data locus (on-chain ciphertext, anchor-only, or hybrid), key custody (single-custodian or threshold), and access gate (none, time, or witness), into a twelve-cell grid with canonical constructions from 1996 to 2026. We extend standard IND-CCA security with a key-lifecycle adversary model parametrised by HSM side-channel leakage, coercion fraction over the custody committee, and algorithmic-break horizon, give the security experiment as pseudo-code with adaptive corruption, cumulative leakage across key rotations, a decryption oracle, and a stronger post-destruction adversary class, and prove that the resulting Destruction-IND-CCA notion suffices for a semantic-security formalisation of the EDPB "render unrecoverable" criterion. We state what is provable per custody model: a concrete bound for single-custodian AEAD, a bound for Shamir threshold custody that grows with the number of rotations, an impossibility result for delay-only designs, and a reduction showing witness-gated erasure needs extractable witness encryption. Evaluating seven reference architectures against eleven engineering, cryptographic, and regulatory criteria, including a production RegTech engine measured at 2.6 × 10^3 events/s single-threaded (10^4 projected with connection pooling), we find that the literature has concentrated on chain-rewriting while the application-layer branch lacks a common threat-model vocabulary. We close this gap and identify five open problems: post-quantum destruction security, the leakage threshold of a custody scheme, decentralised lifecycle audit (with a multi-custody extension covering encrypted mempools), composition with ZKP selective disclosure, and erasure under multi-regime retention conflict.

Note: v3 (November 2026). Adds the proof-carrying redaction line for Bitcoin and for permissioned smart-contract chains (Botta, Iovino and Visconti, IEEE TNSM 2022; Kiraz, Larraia and Vaughan, IEEE ICBC 2024; Avitabile, Botta, Friolo and Visconti, Blockchain: Research and Applications 2025) to Sections 1 and 2 and to the scope statement, and corrects the abstract's claim about redaction on Bitcoin accordingly; Section 7.6 states the restrictions of the formal results; three bibliography entries corrected after an online check of every reference. v2 (November 2026). Formal core rewritten after review at PoPETs 2027 Issue 2: the security experiment is given as pseudo-code (Destruction-IND-CCA) with adaptive custodian corruption, cumulative leakage across key rotations, a decryption oracle and a stronger post-destruction adversary class; the regulatory criterion is restated as semantic security of the post-destruction view and the former "equivalence" claim is replaced by a one-directional sufficiency theorem (title changed accordingly); results are stated per custody model (single custodian, Shamir threshold with refresh, time gates, witness gates); the taxonomy separates custody from access gates; the on-chain residue is analysed under the EDPB 02/2026 anonymisation tests; the description and limitations of the reference implementation are corrected; a limitations section is added. Also: the Shamir-custody theorem now has a full hybrid proof (Appendix C) and a counting bound valid for any leakage budget; the witness-gate result is stated as conditional on extractable witness encryption with unique witnesses; twenty-nine related works are added; the cryptographic costs of the threshold-committee and time-lock architectures are measured with public implementations (tlock, threshold_crypto) rather than estimated; the Bitcoin anchoring proofs of the reference implementation are upgraded and verified (24 blocks).