The amount of data an average person has, is becoming so huge that in the near future this cannot be stored locally anymore, and an external server will have to be used. When this server is not (entirely) trusted, the data should be encrypted. However, the data should still be accessible as a database - it should be possible to query the data. When using thin clients or low-bandwidth networks it is best to perform most of the work at the server. In  we present a method, inspired by secure multi-party computation, to efficiently search in encrypted data. We represent the data as an XML document, and translate XML elements to polynomials which contain information about themselves and their descendants in the XML tree. These polynomials are split (using secret sharing) into two parts: a random polynomial for the client and the difference between the original polynomial and the client polynomial for the server. The client polynomials are generated by a pseudorandom sequence generator, and thus only the seed has to be stored on the client. In a combined effort of both the server and the client a query can be evaluated without traversing the whole tree and without the server learning too much about the data or the query.
|Number of pages||1|
|Publication status||Published - 2004|