An apparatus comprises a storage system and a key manager incorporated in or otherwise associated with the storage system. The storage system is configured to store data items across a plurality of dimensions with each such dimension comprising a plurality of classes. The key manager is configured to assign class keys to respective ones of the classes of each of the dimensions. A given one of the data items associated with at least one of the classes in each of two or more of the dimensions is encrypted for storage in the storage system using a multidimensional key determined as a function of the class keys corresponding to respective ones of the classes with which that data item is associated. Such an arrangement allows all of the data items associated with a given one of the classes to be deleted by deleting the class key assigned to the given class.