Roberto Tamassia, Brown University - November 2010

Authenticating keyword searches on outsourced documents appears to be an especially difficult type of problem in the design of authenticated data structures. The main challenge stems from the fact that the set of items returned in response to a search has size typically much smaller than set of items inspected during the execution of the search algorithm. Thus, solutions that authenticate the steps and intermediate results of the search algorithm would yield integrity proofs that are much larger than the query result. We are interested in developing efficient authentication methods where the proof size is comparable (allowing a small overhead) or smaller than the search result size. Also, we seek solutions that take into account the parallelism afforded by information retrieval computations in the cloud.