A method comprising: encrypting, at a multitenant database system having first tenant data and second tenant data, one or more fragments of the first tenant data based on a first encryption key associated with the first tenant; encrypting, at the multitenant database system , cross-tenant data using a system (100, 200, 1200, 1200a-d) encryption key that is different from the first encryption key and a second encryption key associated with the second tenant, wherein the cross-tenant data is data for the first tenant and the second tenant; generating, at the multitenant database system , non-encrypted header information for each of the encrypted one or more fragments of the first tenant data , wherein the header information has metadata including a first tenant identifier; and storing, in an immutable storage of the multitenant database system, the encrypted one or more fragments of the first tenant data, the corresponding non-encrypted header information, and the encrypted cross-tenant data; wherein the encrypting the one or more fragments of the first tenant data further comprises: segregating, at a memory storage coupled to the multitenant database system , the first tenant data of the first tenant from at least second tenant data of the second tenant, based on the first tenant identifier; and retrieving, from a key cache memory based on the first tenant identifier, the first encryption key to encrypt one or more fragments of the first tenant data , wherein the first encryption key is different from the second encryption key. encrypting, at a multitenant database system having first tenant data and second tenant data, one or more fragments of the first tenant data based on a first encryption key associated with the first tenant; encrypting, at the multitenant database system , cross-tenant data using a system (100, 200, 1200, 1200a-d) encryption key that is different from the first encryption key and a second encryption key associated with the second tenant, wherein the cross-tenant data is data for the first tenant and the second tenant; generating, at the multitenant database system , non-encrypted header information for each of the encrypted one or more fragments of the first tenant data , wherein the header information has metadata including a first tenant identifier; and storing, in an immutable storage of the multitenant database system, the encrypted one or more fragments of the first tenant data, the corresponding non-encrypted header information, and the encrypted cross-tenant data; wherein the encrypting the one or more fragments of the first tenant data further comprises: segregating, at a memory storage coupled to the multitenant database system , the first tenant data of the first tenant from at least second tenant data of the second tenant, based on the first tenant identifier; and retrieving, from a key cache memory based on the first tenant identifier, the first encryption key to encrypt one or more fragments of the first tenant data , wherein the first encryption key is different from the second encryption key. segregating, at a memory storage coupled to the multitenant database system , the first tenant data of the first tenant from at least second tenant data of the second tenant, based on the first tenant identifier; and retrieving, from a key cache memory based on the first tenant identifier, the first encryption key to encrypt one or more fragments of the first tenant data , wherein the first encryption key is different from the second encryption key. <EOS>