Various approaches for extracting client's data from a storage provider are presented. In one approach, an auditor is initialized with a verification data set that confirms that an initial version of a data set stored by the storage provider is intact. The auditor extracts a second version of the data set from the storage provider; the second version hides information specified by the data set from the auditor. The auditor determines whether the second version matches the initial version. The second version is returned to the client if the initial version matches the second version. The auditor is prevented from recovering the information specified by the data set using the state information, and the client need not store any state information related to the initial and second versions needed to recover the information specified by the data set. If the initial version does not match the second version, the auditor outputs data indicative of data corruption.