Crypto-Erasure in Hash-Linked Audit Logs: Guarantees and Their Limits

#Abstract

An append-only hash-linked audit log and a statutory right to erasure are incompatible in their naive forms. This report describes resolving the conflict by encrypting personal data under per-subject keys held outside the log, so that destroying a key renders the plaintext unrecoverable while the chain continues to verify. The resulting guarantee is bounded by three conditions, each of which is stated, and one of which cannot be enforced by the library at all. No formal adversary model is given.

#Why the log is chained

An audit log an administrator can modify is not evidence. Where the credentials that perform an action can also remove its record, the log answers no question of interest.

Linking each entry to its predecessor by a cryptographic hash makes modification detectable. The technique originates in digital timestamping [1] and in hash tree constructions [2], and secure audit log designs have addressed a compromising adversary directly [3].

The property obtained is detection rather than prevention. Nothing prevents a party with storage access from writing to storage. What changes is that concealment requires rewriting every subsequent entry and any externally published chain head.

#The conflict

The right to erasure entitles a data subject to have personal data concerning them removed [4]. The log's design property is that nothing is removed. These cannot both hold over the same bytes.

#Construction

Personal data within an entry is encrypted under a key associated with that data subject. The entry stored in the log is ciphertext, and the key is held in separate storage with its own access control.

Because the hash covers the ciphertext rather than the plaintext, destroying the key leaves every hash unchanged and the chain verifiable end to end, while the plaintext becomes unrecoverable by any party including the operator.

The key is deleted, not the record. The trail retains its integrity and the data subject obtains an outcome that is, in practice, indistinguishable from deletion.

#Three bounding conditions

Key destruction must be complete. The entire guarantee rests on the key being irrecoverable everywhere it existed, including backups of the key store, which is precisely where keys survive unnoticed. Sanitisation guidance exists because deleted and unrecoverable are distinct states [5]. A library can guarantee its own behaviour and cannot guarantee that an operator's key management system lacks a soft-delete window, which makes this the weakest link and one outside the system's control.

Metadata remains in the clear. Timestamps, actor identifiers, resource types and action names must remain readable, because a log that cannot be queried serves no purpose. The fact that a subject performed an action at a time therefore survives erasure. Whether that residue is itself personal data depends on the data and is a legal determination rather than a technical one.

Hash algorithms have finite lifetimes. A chain constructed today may require verification decades hence. The format carries an algorithm identifier permitting a successor chain, and the earlier segment remains verifiable only under its original algorithm.

#Design constraint that makes reporting possible

Entries have a fixed shape: actor, action, resource, outcome, scope and timestamp. Every subsequent request to add a free-form field has been declined. Economy of mechanism is the relevant principle [6], and the practical consequence is that a compliance report is a query rather than a text-mining exercise.

#An unanticipated effect

Once engineers trusted that the log could not have been silently modified, they began consulting it during incidents rather than reconstructing sequences from application logs. The log's value in ordinary operation exceeded its value at audit, which was not the reason it was built.

#Limitations

No formal adversary model is given. The construction assumes the key store and the log store are not under unified adversarial control, and does not analyse the case where they are.

Per-subject keys imply a key per subject, and the operational cost of that at scale, including rotation and the enumeration required to erase, is not evaluated here. Systems with very large subject populations may find the key management cost dominant, and no measurement is offered either way.