Secure and privacy preserving outsourcing of tree structured data

With the increasing use of web services, many new challenges concerning data security are becoming critical. Data or applications can now be outsourced to powerful remote servers, which are able to provide services on behalf of the owners. Unfortunately, such hosts may not always be trustworthy. In [1,2], we presented a one-server computationally private tree traversal technique, which allows clients to outsource tree-structured data. In this paper, we extend this protocol to prevent a polynomial time server with large memory to use correlations in client queries and in data structures to learn private information about queries and data. We show that, when the proposed techniques are used, computational privacy is achieved even for non-uniformly distributed node accesses that are common in real databases.