A method, system and program are provided for enabling access to encrypted data in a storage cartridge by wrapping the data key used to encrypt the data with one or more encryption keys (e.g., a public key from a public/private key pair) to form one or more encryption encapsulated data keys (EEDKs) and then storing the EEDK(s) on the storage cartridge along with the encrypted data. The encrypted data may be decoded by retrieving the EEDK from the storage cartridge, decrypting the EEDK with a decryption key (e.g., the private key from the public/private key pair) to extract the underlying data key, and then using the extracted data key to decrypt the encrypted data.