Patent ID: 8904171

Claim:
A method for performing a search on a set of documents, the method comprising: encrypting nodes of a search tree, at a server, with a first private encryption key to produce an encrypted search tree; sending the encrypted search tree to a client; receiving an encrypted, permuted search tree from the client at the server, wherein nodes of the encrypted search tree have been permuted and encrypted by the client, the encrypted, permuted search tree having been encrypted with a second private encryption key, wherein the second private encryption key is different than the first private encryption key; decrypting the encrypted, permuted search tree using a first decryption key, corresponding to the first private encryption key, to produce a tree with nodes encrypted with the second private encryption key based on a commutative property of homomorphic encryption; receiving, at the server, a query from the client, the query comprising a set of keywords, wherein each query term is encrypted with the second private encryption key; performing a search using the query, including performing an oblivious matching keyword test in which an evaluation occurs at each node of the decrypted encrypted, permuted search tree to determine if one or more matches exist; and returning results to the client based on a match of keywords for each document, the results including one or more encrypted leaf nodes of the tree, the encrypted leaf nodes encrypted with the second private encryption key.