A method for data integrity protection includes receiving items of data for storage in a storage medium. The items are grouped into multiple groups, such that at least some of the groups include respective pluralities of the items. A respective group signature is computed over each of the groups, thereby generating multiple group signatures. An upper-level signature is computed over the group signatures. Groups of the items, the group signatures, and the upper-level signature are stored in respective locations in the storage medium.