A distributed database encrypts a table using a table encryption key protected by a client master encryption key. The encrypted table is replicated among a plurality of nodes of the distributed database. The table encryption key is replicated among the plurality of nodes, and is stored on each node in a respective secure memory. In the event of node failure, a copy of the stored key held by another member of the replication group is used to restore a node to operation. The replication group may continue operation in the event of a revocation of authorization to access the client master encryption key.