A method performed by a processing system includes identifying a first node in a metadata tree of a patient that corresponds to an encrypted electronic health record in an encrypted data store and preventing a portion of the first node from being decrypted with a node key of a first healthcare participant in response to a second node of the metadata tree including key rotation information that indicates that the node key has been revoked by a second healthcare participant.