A system, method and programmed article of manufacture to perform efficient encryption key updates in encrypted database-as-a-service (DAS) environments using a key registry and key locks. A database as a service environment allows organizations to send their data management infrastructures to a database service provider. The service provider employs data encryption techniques to ensure the privacy of hosted data. The security of encryption techniques relies on the confidentiality of the encryption keys. The dynamic nature of the encrypted database in the DAS model adds complexity and raises specific requirements on key management techniques. The solution is provided by the key registry and by the key update lock, key management process and log management process to allow data update access to data concurrently with encryption key update for the same data.