An apparatus comprises a storage system and a cryptographic module incorporated in or otherwise associated with the storage system. The cryptographic module is configured to obtain a plurality of data encryption keys used to encrypt respective ones of the data items for storage in the storage system and a plurality of tenant keys for respective ones of the tenants. A given one of the data items is encrypted using a particular one of the data encryption keys. The given data item as stored for a given one of the tenants has associated metadata that includes the particular data encryption key encrypted using the tenant key of the given tenant. Such an arrangement allows for efficient deduplication. For example, a single copy of the given data item can be stored for multiple ones of the tenants by appropriate configuration of the metadata associated with the given data item.