Searching in Encrypted Data


Doumen, J.M. and Brinkman, R. and Jonker, W. (2004) Searching in Encrypted Data. In: Finite Fields: Theory and Applications, 5-11 Dec 2004, Oberwolfach, Germany (pp. p. 2951).

open access
Abstract: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.
Item Type:Conference or Workshop Item
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page