In one embodiment, metadata of a data object to be stored in a storage system is received, where the metadata is in a hierarchical structure having multiple levels, each level having multiple nodes and each node being one of a root node, a leaf node and an intermediate node. Each leaf node represents a deduplicated segment associated with the data object. The hierarchical structure is traversed to encrypt each of the nodes in a bottom-up approach, starting from leaf nodes, using different keys. A child key for encrypting content of a child node is stored in a parent node that references the child node, and the child key is encrypted by a parent key associated with the parent node. The encrypted content of the nodes are then stored in one or more storage units of the storage system in a deduplicated manner.