System and method for secure deletion of data
First Claim
Patent Images
1. A system, comprising:
- a plurality of networked storage devices of a cloud-based storage service that implement a data store configured to store encrypted data, wherein the plurality of networked storage devices is connected via a storage service network;
a separate index for each of at least two levels of a storage hierarchy for the data store, wherein each index is configured to store a plurality of metadata entries for the encrypted data stored across the plurality of networked storage devices, wherein each metadata entry is for a different data item in the data store, and wherein each metadata entry comprises an identifier, location information and a random encryption key; and
a hierarchical storage manager connected to the networked storage devices via the storage service network and configured to receive, via a web services interface and over an intermediate network, a storage request to store a data item, wherein in response to the storage request, the storage manager is configured to;
generate a random key for the data item at a first level of the storage hierarchy;
encrypt the data item, wherein the random key is usable to decrypt the encrypted data item at the first level of the storage hierarchy;
generate one or more different random keys for one or more portions of the data item at a second level of the storage hierarchy;
encrypt the respective one or more portions of the encrypted data item, wherein the one or more different random keys are usable to decrypt the respective one or more encrypted portions of the encrypted data item at the second level of the storage hierarchy;
store the respective one or more encrypted portions of the encrypted data item over the storage service network to one or more of the networked storage devices of the data store; and
store the random key in a metadata entry in an index for the first level of the storage hierarchy and store the one or more different random keys in respective metadata entries of an index for the second level of the storage hierarchy;
wherein the storage manager is further configured to receive a delete request over the intermediate network to delete, at a specified level of the storage hierarchy, one or more of a plurality of data items stored in the data store, wherein in response to the delete request, the hierarchical storage manager is configured to;
access the corresponding metadata entry in the index for the specified level of the storage hierarchy to remove at least the random key from the corresponding metadata entry in the index for each of the data items to be deleted at the specified level of the storage hierarchy, wherein after the delete request is complete;
the encrypted data for the one or more data items requested to be deleted remains on the networked storage devices that implement the data store, andone or more random keys, corresponding to the one or more data items requested to be deleted, in an index for another level of the storage hierarchy not specified in the delete request remain in respective metadata entries.
1 Assignment
0 Petitions
Accused Products
Abstract
Systems and methods for secure deletion of data items in a storage system may support the deletion of stored data item. In response to a storage request, a storage manager may generate a key corresponding to the data item to be stored and encrypt the data item before storing the data item in a data store. The key may be stored in an index comprising metadata corresponding to the data item. In response to a delete request, the storage system may determine the corresponding metadata entry in the index and remove the key corresponding to the data item without accessing the data item.
49 Citations
27 Claims
-
1. A system, comprising:
-
a plurality of networked storage devices of a cloud-based storage service that implement a data store configured to store encrypted data, wherein the plurality of networked storage devices is connected via a storage service network; a separate index for each of at least two levels of a storage hierarchy for the data store, wherein each index is configured to store a plurality of metadata entries for the encrypted data stored across the plurality of networked storage devices, wherein each metadata entry is for a different data item in the data store, and wherein each metadata entry comprises an identifier, location information and a random encryption key; and a hierarchical storage manager connected to the networked storage devices via the storage service network and configured to receive, via a web services interface and over an intermediate network, a storage request to store a data item, wherein in response to the storage request, the storage manager is configured to; generate a random key for the data item at a first level of the storage hierarchy; encrypt the data item, wherein the random key is usable to decrypt the encrypted data item at the first level of the storage hierarchy; generate one or more different random keys for one or more portions of the data item at a second level of the storage hierarchy; encrypt the respective one or more portions of the encrypted data item, wherein the one or more different random keys are usable to decrypt the respective one or more encrypted portions of the encrypted data item at the second level of the storage hierarchy; store the respective one or more encrypted portions of the encrypted data item over the storage service network to one or more of the networked storage devices of the data store; and store the random key in a metadata entry in an index for the first level of the storage hierarchy and store the one or more different random keys in respective metadata entries of an index for the second level of the storage hierarchy; wherein the storage manager is further configured to receive a delete request over the intermediate network to delete, at a specified level of the storage hierarchy, one or more of a plurality of data items stored in the data store, wherein in response to the delete request, the hierarchical storage manager is configured to; access the corresponding metadata entry in the index for the specified level of the storage hierarchy to remove at least the random key from the corresponding metadata entry in the index for each of the data items to be deleted at the specified level of the storage hierarchy, wherein after the delete request is complete; the encrypted data for the one or more data items requested to be deleted remains on the networked storage devices that implement the data store, and one or more random keys, corresponding to the one or more data items requested to be deleted, in an index for another level of the storage hierarchy not specified in the delete request remain in respective metadata entries. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A system, comprising:
-
one or more processors; and a memory coupled to the one or more processors and storing program instructions that when executed by the one or more processors implement a storage manager configured to; receive, by a cloud-based storage service over an intermediate network, a storage request to store a data item in a data store having a storage hierarchy, the data store implemented by one or more networked storage devices of the cloud-based storage service, wherein the one or more networked storage devices are connected via a storage service network; generate, by the cloud-based storage service, a random key for the data item at a first level of the storage hierarchy; encrypt, by the cloud-based storage service, the data item, wherein the random key is usable to decrypt the encrypted data item at the first level of the storage hierarchy; generate one or more different random keys for one or more portions of the data item at a second level of the storage hierarchy; encrypt the respective one or more portions of the encrypted data item, wherein the one or more different random keys are usable to decrypt the respective one or more encrypted portions of the encrypted data item at the second level of the storage hierarchy; store, by the cloud-based storage service, the respective one or more encrypted portions of the encrypted data item over the storage service network to the one or more networked storage devices of the data store; store the random key in a metadata entry of an index for the first level of the storage hierarchy and store the one or more random keys in respective metadata entries of an index for the second level of the storage hierarchy, wherein the indexes are configured to store a plurality of metadata entries for the encrypted data stored in the one or more networked storage devices; and in response to receipt of a delete request over the intermediate network to delete, at a specified level of the storage hierarchy, one or more of a plurality of data items stored in the data store; access the corresponding metadata entry in the index for the specified level of the storage hierarchy to both modify the corresponding metadata entry, and remove the random key from the corresponding metadata entry in the index for each of the data items to be deleted at the specified level of the storage hierarchy, wherein after the delete request is complete; the encrypted data for the one or more data items requested to be deleted remains on the networked storage devices that implement the data store and one or more random keys, corresponding to the one or more data items requested to be deleted, in an index for another level of the storage hierarchy not specified in the delete request remain in respective metadata entries. - View Dependent Claims (8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A method, comprising:
performing, by one or more computers; receiving, over an intermediate network by a cloud-based storage service, a storage request to store a data item in a data store having a storage hierarchy, the data store implemented by a plurality of networked storage devices of the cloud-based storage service, wherein the plurality of networked storage devices is connected via a storage service network; and in response to said receiving; generating a random key for the data item at a first level of the storage hierarchy; encrypting the data item, wherein the random key is useable to decrypt the encrypted data item at the first level of the storage hierarchy; generate one or more different random keys for one or more portions of the data item at a second level of the storage hierarchy; encrypt the respective one or more portions of the encrypted data item, wherein the one or more different random keys are usable to decrypt the respective one or more encrypted portions of the encrypted data item at the second level of the storage hierarchy; storing the respective one or more encrypted portions of the encrypted data item over the storage service network to one or more of the plurality of networked storage devices of the data store; accessing an index for the first level of the storage hierarchy to store the random key in a corresponding metadata entry in the first level index, and store the one or more random keys in respective metadata entries of an index for the second level of the storage hierarchy, the indexes configured to store a plurality of metadata entries for the encrypted data stored in the plurality of networked storage devices, wherein the metadata entries in the indexes comprise an identifier, location information and the random key for the data item; receiving a delete request over the intermediate network to delete, at a specified level of the storage hierarchy, one or more of a plurality of data items stored in the data store, wherein the plurality of data items is stored in an encrypted form in the data store; and subsequent to said receiving; determining a metadata entry for each of the one or more of a plurality of encrypted data items from the index for the specified level of the storage hierarchy; removing at least the random key from the metadata entry in the index for each of the data items to be deleted for the specified level of the storage hierarchy, wherein after the delete request is complete; the encrypted data for the one or more data items requested to be deleted remains on the networked storage devices that implement the data store and one or more random keys, corresponding to the one or more data items requested to be deleted, in an index for another level of the storage hierarchy not specified in the delete request remain in respective metadata entries. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23)
-
24. A non-transitory, computer-readable storage medium storing program instructions computer executable to implement a storage manager configured to:
-
receive a storage request over an intermediate network by a cloud-based storage service to store a data item in a data store having a storage hierarchy, the data store implemented by a plurality of networked storage devices of the cloud-based storage service that are connected via a storage service network; and in response to said receive the storage request; generate a random key for the data item at a first level of the storage hierarchy; encrypt the data item, wherein the random key is usable to decrypt the encrypted data item at the first level of the storage hierarchy; generate one or more different random keys for one or more portions of data item at a second level of the storage hierarchy; encrypt the respective one or more portions of the encrypted data item, wherein the one or more different random keys are usable to decrypt the respective one or more encrypted portions of the encrypted data item at the second level of the storage hierarchy; store the respective one or more encrypted portions of the encrypted data item over the storage service network to one or more of the networked storage devices of the data store; access an index for the first level of the storage hierarchy to store the random key in a corresponding metadata entry in the first level index, and store the one or more random keys in respective metadata entries of an index for the second level of the storage hierarchy the indexes configured to store a plurality of metadata entries for the encrypted data stored in the plurality of networked storage devices; receive a delete request over the intermediate network to delete, at a specified level of the storage hierarchy, one or more of a plurality of data items stored in a data store; subsequent to said receive the delete request; determine a metadata entry for each of the one or more of a plurality of encrypted data items from the index for the specified level of the storage hierarchy, wherein the metadata entry in the index comprises an identifier and a random encryption key for the data item; and remove at least the encryption key from the index for each of the data items to be deleted for the specified level of the storage hierarchy, wherein after the delete request is complete; the encrypted data for the one or more data items requested to be deleted remains on the networked storage devices that implement data store, and one or more random keys, corresponding to the one or more data items requested to be deleted, in an index for another level of the storage hierarchy not specified in the delete request remain in respective metadata entries. - View Dependent Claims (25, 26, 27)
-
Specification