ZFS does that with snapshots already. (ZFS is not encrypted, but the principle is the same)

I believe immutable trees would be the correct algorithm here.

The algorithm relies on a tree structure, where the leaves are the files. Every time a new snapshot is written, every leaf node changed writes a new path to the root node, while leaving the rest of the tree intact.

When a snapshot needs to be deleted, you just remove all the old root nodes and have a garbage-collection like-process delete all the old files.

EDIT: Look at example here: https://en.wikipedia.org/wiki/Persistent_data_structure#Tree... . When xs is deleted, nodes a,c,f can also be deleted.

EDIT2: I feel like I can never make posts like these while keeping it short and sweet, and adding enough details. ZFS can be encrypted, but accessing any files is right at its fingertips, not over a slow network connection. And there are caveats about how to encrypt the metadata, but you do not need to decrypt the whole backup to figure out what to do delete.