Secure search and retrieval

An apparatus for performing a search on a set of documents, the apparatus comprising:

• a memory for storing an encrypted, permuted search tree with nodes that have been permuted and encrypted, the encrypted permuted search tree having been encrypted with a first private encryption key;
• a communication interface to receive a query from a client, the query comprising a set of keywords, wherein each query term is encrypted with the first private encryption key;
• and
• a processor coupled to the memory and the communication interface to
• perform a search using the query, including performing an oblivious matching keyword test in which an evaluation occurs at each node of the tree to determine if one or more matches exist, and
• return, via the communication interface, results 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 first private encryption key.

An article of manufacture comprising one or more computer readable storage media having instruction stored thereon which when executed by a system cause the system to perform a method for searching a set of documents, the method comprising:

• receiving an encrypted, permuted search tree with nodes that have been permuted and encrypted, the encrypted permuted search tree having been encrypted with a first private encryption key;
• receiving, at a communication interface of the system, a query from a client, the query comprising a set of keywords, wherein each query term is encrypted with the first private encryption key;
• performing, using a processor of the system a search based on the query, including performing an oblivious matching keyword test in which an evaluation occurs at each node of the tree to determine if one or more matches exist;
• and
• returning results 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 first private encryption key.