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.