Looking at this again, I went digging a bit to see if there was new stuff around.
this is actually old, but bluray has "broadcast encryption" which in some ways has similar properties to what we are working with:

https://en.wikipedia.org/wiki/Advanced_Access_Content_System

it's pretty simple: there is a "title key" a symmetric key that encrypts the content. Then each model of player shares a decryption key. this makes region locking possible, and also for content producers to make new content that is not playable on machines that have been cracked.

To view the movie, the player must first decrypt the content on the disc. The decryption process is somewhat convoluted. The disc contains 4 items—the Media Key Block (MKB), the Volume ID, the Encrypted Title Keys, and the Encrypted Content. The MKB is encrypted in a subset difference tree approach. Essentially, a set of keys are arranged in a tree such that any given key can be used to find every other key except its parent keys. This way, to revoke a given device key, the MKB needs only be encrypted with that device key's parent key.

Once the MKB is decrypted, it provides the Media Key, or the km. The km is combined with the Volume ID (which the program can only get by presenting a cryptographic certificate to the drive, as described above) in a one-way encryption scheme (AES-G) to produce the Volume Unique Key (Kvu). The Kvu is used to decrypt the encrypted title keys, and that is used to decrypt the encrypted content.

sounds like it's mainly concerned with encrypting the key to hundreds of keys, and making that look up efficient. There is no metadata to protect.