Various approaches are described for auditing integrity of stored data. In one approach, a data set is provided from a client to a storage provider, and the data set is stored at a first storage arrangement by the storage provider. An auditor determines whether the data set stored at the first storage arrangement is corrupt without reliance on any part of the data set and any derivative of any part of the data set stored by the client. While the auditor is determining whether the data set stored at the first storage arrangement is corrupt, the auditor is prevented from being exposed to information specified by the data set. The auditor outputs data indicative of data corruption in response to determining that the data set stored at the first storage arrangement is corrupt.