Auditor Assisted Extraction And Verification Of Client Data Returned From A Storage Provided While Hiding Client Data From The Auditor

• US 20100083001A1
• Filed: 10/01/2008
• Published: 04/01/2010
• Est. Priority Date: 04/09/2008
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: SHAH, Mehul A., Swaminathan, Ram
• Granted Patent: US 8,281,151 B2
• Time in Patent Office: Days
• US Class Current: 713/187
• CPC Class Codes: H04L 9/0822 using key encryption key
• CPC Class Codes: H04L 9/0825 using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3221 interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

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.

Claims

1. A processor-implemented method, comprising:

initializing an auditor with a verification data set that confirms that an initial version of a data set stored by a storage provider on behalf of a client is intact;

extracting and receiving a second version of the data set by the auditor from the storage provider, wherein the second version hides information specified by the data set from the auditor;

determining by the auditor whether the second version matches the initial version by applying a checking function on the second version and the verification data set;

returning the second version to the client in response to the initial version matching the second version, wherein the auditor is prevented from recovering the information specified by the data set, and the client is relieved from having to store any state related to the initial and second versions needed to recover the information specified by the data set; and

in response to the initial version not matching the second version, outputting data indicative of data corruption.

2. The method of claim 1, further comprising:

wherein the initial version of the data set includes an encryption key and an encrypted version of the data set as encrypted with the encryption key;

wherein the determining by the auditor includes,

determining whether the encrypted version of the data set is corrupt without exposing unencrypted values of the data set to the auditor; and

determining by the auditor, whether the encryption key is corrupt without exposing a value of the encryption key to the auditor.

3. The method of claim 2, further comprising:

recovering the encryption key from the second version by the client; and

decrypting data in the second version using the recovered encryption key by the client.

4. The method of claim 2, wherein the determining whether the encryption key is corrupt includes:

receiving from the storage provider and the client respective key-check values derived from the encryption key;

determining from the received key-check values and the verification data set, whether the storage provider failed to return an initial version of the encryption key intact or the client is obstructing the auditor with an invalid key-check value;

in response to determining that-the storage provider failed, outputting data indicative of storage provider failure; and

in response to determining that the client provided an invalid key-check value, outputting data indicative of client obstruction.

5. The method of claim 2, wherein a first value in the verification data set is generated from a cryptographically secure hash function of the encrypted version of the data set, and the applying of the checking function includes generating a second data value from the hash function of the second version of the data set and comparing the first data value to the second data value.

6. The method of claim 2, wherein the determining whether the encryption key is corrupt includes:

inputting a key commitment value to the auditor, wherein the key commitment value binds the storage provider to a value of the encryption key without revealing the encryption key to the auditor, and the key commitment value is a function of a generator for a cyclic group and the encryption key;

inputting a secret commitment value to the auditor, wherein the secret commitment value is a function of the generator and a shared secret value between the client and the storage provider, and the shared secret value is unknown to the auditor;

inputting a blinded encryption key to the auditor, wherein the blinded encryption key is based on the shared secret value;

determining by the auditor a key verification value as a function of the generator and the blind encryption key is equal to a product of the key commitment value and the secret commitment value;

outputting data indicative of the storage provider having provided a invalid encryption key in response to the key verification value being not equal to the product of the key commitment value and the secret commitment value; and

outputting the blinded encryption key to the client in response to the key verification value being equal to the product of the key commitment value and the secret commitment value.

7. The method of claim 2, wherein the determining whether the encryption key is corrupt includes:

inputting a first key commitment value to the auditor, wherein the first key commitment value binds the storage provider to a value of the encryption key without revealing the encryption key to the auditor, and the key commitment value is a function of a generator for a cyclic group and the encryption key;

inputting to the auditor a first data set having a signature provided by the storage provider, wherein the first data set includes a second key commitment value and the encryption key encrypted with a public key of the client;

determining by the auditor whether the signature on the first data set is that of the storage provider and whether the second key commitment value equals the first key commitment value;

outputting data indicative of one of the storage provider having signed the data set with an invalid signature or the second key commitment value being invalid in response to determining that the signature on the first data set is not that of the storage provider or the second key commitment value does not equal the first key commitment value.

8. The method of claim 7, further comprising outputting the first data set from the auditor to the client in response to the auditor determining that the signature on the first data set is that of the storage provider and the second key commitment value is equal to the first key commitment value.

9. The method of claim 8, further comprising:

decrypting by the client, the encrypted encryption key in the first data set into a decrypted key value using a private key of the client;

determining a key verification value as a function of the generator and the decrypted key value;

comparing key verification value to the key commitment value by the client;

decrypting data in the second version using the decrypted key value by the client in response to the key verification value being equal to the key commitment value.

10. The method of claim 9 further comprising:

in response to the key verification value being not equal to the key commitment value, transmitting an error code and the decrypted key value from the client to the auditor;

determining by the auditor from the decrypted key value and the encrypted encryption key from the first data set as encrypted with the public key of the client, one of the client or storage provider having provided faulty data; and

outputting data indicative of the client having provided faulty data in response to determining that the client provided faulty data; and

outputting data indicative of the storage provider client having provided faulty data in response to determining that the storage provider provided faulty data.

11. The method of claim 2, further comprising:

inputting a first key commitment value to the auditor, wherein the key commitment value binds the storage provider to a value of the encryption key without revealing the encryption key to the auditor, and the key commitment value is a function of a generator for a cyclic group and the encryption key;

receiving by the auditor from the storage provider, an encrypted version of the encryption key, wherein the encrypted version is the discrete log of the key commitment value as generated using verifiable encryption;

determining by the auditor using a verification function of the verifiable encryption on the encrypted version of the encryption key, whether the encrypted version of the encryption key is corrupt; and

outputting data indicative of the encrypted version of the encryption key being corrupt in response to determining that the encrypted version of the encryption key is corrupt.

12. The method of claim 11, further comprising outputting the encrypted version of the encryption key by the auditor to the client in response to determining that the encrypted version of the encryption key is not corrupt.

13. The method of claim 1, further comprising:

prior to receiving the second version of the data set from the storage provider by the auditor, performing the steps including,

determining by the auditor using the verification data set, whether a third version of the data set provided by the storage provider to the client has been corrupted from the initial version;

preventing exposure of information specified by the data set to the auditor while the auditor is determining whether the third version of the data set is corrupt; and

wherein the receiving of the second version, determining a match of the second version to the initial version and the returning of the second version are bypassed in response to determining that the third version is in tact.

14. An apparatus, comprising:

means for initializing an auditor with a verification data set that confirms that an initial version of a data set stored by a storage provider on behalf of a client is intact;

means for receiving a second version of the data set by the auditor from the storage provider, wherein the second version hides information specified by the data set from the auditor;

means for determining by the auditor whether the second version matches the initial version by applying a checking function on the second version and the verification data set;

means for returning the second version to the client in response to the initial version matching the second version, wherein the auditor is prevented from recovering the information specified by the data set, and the client is relieved from having to store any state related to the initial and second versions needed to recover the information specified by the data set; and

means, responsive to the initial version not matching the second version, for outputting data indicative of data corruption.

15. An article of manufacture, comprising:

a processor-readable program storage medium configured with instructions for extracting data stored by a storage provider on behalf of a client, wherein execution of the instructions by one or more processors causes the one or more processors to perform operations including,

initializing an auditor with a verification data set that confirms that an initial version of a data set stored by the storage provider on behalf of the client is intact;

extracting and receiving a second version of the data set by the auditor from the storage provider, wherein the second version hides information specified by the data set from the auditor;

determining by the auditor whether the second version matches the initial version by applying a checking function on the second version and the verification data set;

returning the second version to the client in response to the initial version matching the second version, wherein the auditor is prevented from recovering the information specified by the data set, and the client is relieved from having to store any state related to the initial and second versions needed to recover the information specified by the data set; and

in response to the initial version not matching the second version, outputting data indicative of data corruption.

16. The article of manufacture of claim 15, the operations further comprising:

wherein the initial version of the data set includes an encryption key and an encrypted version of the data set as encrypted with the encryption key;

wherein the determining by the auditor includes,

determining whether the encrypted version of the data set is corrupt without exposing unencrypted values of the data set to the auditor; and

determining by the auditor, whether the encryption key is corrupt without exposing a value of the encryption key to the auditor.

17. The article of manufacture of claim 16, the operations further comprising:

recovering the encryption key from the second version by the client; and

decrypting data in the second version using the recovered encryption key by the client.

18. The article of manufacture of claim 16, wherein the determining whether the encryption key is corrupt includes:

receiving from the storage provider and the client respective key-check values derived from the encryption key;

determining from the received key-check values and the verification data set, whether the storage provider failed to return an initial version of the encryption key intact or the client is obstructing the auditor with an invalid key-check value;

in response to determining that the storage provider failed, outputting data indicative of storage provider failure; and

in response to determining that the client provided an invalid key-check value, outputting data indicative of client obstruction.

19. The article of manufacture of claim 16, wherein a first value in the verification data set is generated from a cryptographically secure hash function of the encrypted version of the data set, and the applying of the checking function includes generating a second data value from the hash function of the second version of the data set and comparing the first data value to the second data value.

20. The article of manufacture of claim 15, the operations further comprising:

prior to receiving the second version of the data set from the storage provider by the auditor, performing the steps including,

determining by the auditor using the verification data set, whether a third version of the data set provided by the storage provider to the client has been corrupted from the initial version;

preventing exposure of information specified by the data set to the auditor while the auditor is determining whether the third version of the data set is corrupt; and

wherein the receiving of the second version, determining a match of the second version to the initial version and the returning of the second version are bypassed in response to determining that the third version is in tact.