Patent ID: 8392708

Claim:
A computer implemented method for auditing integrity of stored data, comprising: determining by an auditor coupled to a processor, whether a data set stored at a first storage arrangement by a storage provider on behalf of a client 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, wherein the data set includes an encryption key and an encrypted version of the data set encrypted with the encryption key, wherein the determining by the auditor includes determining whether the encryption key is corrupt without exposing a value of the encryption key to the auditor, wherein the determining whether the encryption key is corrupt comprises: issuing a key challenge from the auditor to the storage provider having the encryption key, wherein the key challenge is a function of a pseudo-random value generated by the auditor; selecting by the storage provider having the encryption key, in response to the key challenge, a pseudo-random α for which the greatest common divisor of α and p−1 is equal to 1, wherein p is a prime number and α is an integer; generating by the storage provider having the encryption key, an actual key response as a function of the key challenge, the value of the encryption key, and α ; and providing the actual key response to the auditor, wherein the actual response does not reveal the value of the encryption key to the auditor to prevent exposure of information specified by the data set to the auditor while the auditor is determining whether the data set stored at the first storage arrangement is corrupt; and outputting, by the processor, data indicative of data corruption in response to determining that the data set stored at the first storage arrangement is corrupt.