I think we'd need a jointly-held key generator for auto-minted keys along with a service that can tell a store if a non-auto-minted key is already in use. Or at least, that would be the brain-dead way to to do it. Maybe we can sophistimacate the structure of the key to orthogonalize the key sets?

Or maybe there's something like the Akubra ID mapping blobstore?