Searching in Encrypted Data

J.M. Doumen, Richard Brinkman, Willem Jonker

Research output: Contribution to conferencePaper

64 Downloads (Pure)


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 [1] 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.
Original languageUndefined
Number of pages1
Publication statusPublished - 2004
EventFinite Fields: Theory and Applications - Oberwolfach, Germany
Duration: 5 Dec 200411 Dec 2004


WorkshopFinite Fields: Theory and Applications
Other5-11 Dec 2004


  • SCS-Cybersecurity
  • IR-64368
  • EWI-11118

Cite this