Encryption with 2 symmetric keys and decryption with one key
One solution I was thinking of is to encrypt the data with 2 keys (key1 AND key2) and decrypt it with any of the keys (key1 OR key2). Is is possible?


The immediately obvious way is, when you want to encrypt a record $M$, you select a random key $r$, and generate $Encr_{key1}(r), Encr_{key2}(r), Encr_r(M)$

The decryption process is obvious, using the $key_i$ you have, you recover $r$, and then use that key to decrypt the actual record.

Is there any reason this scheme doesn't solve your problem?