Method and apparatus for non-redundant encrypted storage

Abstract

For secure non-redundant storage of data, to store a data blocklet (sub-block), one takes a hash of each blocklet. The hash value is used as a key to encrypt the blocklet data. The key is then hashed to encrypt it and the hashed key used in the blocklet index to identify the blocklet. The blocklet index entry also conventionally includes the address of that encrypted blocklet. Unless one has a file representation which is a vector of the hash values, one cannot obtain direct information about the original blocklet from the blocklet index or the blocklet storage. To retrieve data, each original blocklet hash is hashed again to generate the index entry.

I claim: 
     
       1. A method, comprising:
 computing a first hash by applying a first hash function to a sub-block produced by a data de-duplication system, computing a second different hash by applying a second, different hash function to the first hash; and upon determining that the second hash is not located in an index associated with the data de-duplication system, where the index stores second hash values computed by applying the second, different hash function to sub-blocks processed by the data de-duplication system: producing an encrypted sub-block by applying an encryption function to the sub-block, where the encryption function uses the first hash as an encryption key; storing the encrypted sub-block in a data store maintained by the data de-duplication system; storing, in the index, the second hash value and a location in the data store where the encrypted sub-block is stored; accessing a sub-block stored in the data store by: computing a candidate hash value by applying the second hash function to a received hash value; and upon determining that the candidate hash value appears in the index: retrieving an encrypted sub-block associated with the candidate hash value; and producing a decrypted sub-block by applying a decryption function to the encrypted sub-block, where the decryption function employs a value, other than the received hash value, as a decryption key. 
 
     
     
       2. The method of  claim 1 , where the data store is a hard disk drive or magnetic tape drive or solid state memory. 
     
     
       3. The method of  claim 1 , where the index is stored in random access memory.