A method comprising: encrypting, at a multitenant database system (100, 200) 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 (100, 200), 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 (100, 200), 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 (108, 118) 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 (100, 200), 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 (100, 200) 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 (100, 200), 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 (100, 200), 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 (108, 118) 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 (100, 200), 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 (100, 200), 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.