Efficient Tree Search in Encrypted Data

R. Brinkman; L. Feng; J. Doumen; P.H. Hartel; W. Jonker

doi:10.1201/1086/44530.13.3.20040701/83065.3

Efficient Tree Search in Encrypted Data

R. Brinkman, L. Feng, J. Doumen, P.H. Hartel, W. Jonker

Databases (Former)

Research output: Contribution to journal › Article › Academic › peer-review

167 Downloads (Pure)

Abstract

Sometimes there is a need to store sensitive data on an untrusted database server. Song Wagner and Perrig have introduced a way to search for the existence of a word in an encrypted textual document. The search speed is linear in the size of the document. It does not scale well for a large database. We have developed a tree search algorithm based on the linear search algorithm that is suitable for XML databases. It is more efficient since it exploits the structure of XML. We have built prototype implementations for both the linear and the tree search case. Experiments show a major improvement in search time.

Original language	English
Pages (from-to)	14-21
Number of pages	8
Journal	Information systems security
Volume	13
Issue number	3
DOIs	https://doi.org/10.1201/1086/44530.13.3.20040701/83065.3
Publication status	Published - Jul 2004

Keywords

SCS-Cybersecurity

Access to Document

10.1201/1086/44530.13.3.20040701/83065.3

Brinkman04efficientAccepted author version, 393 KB

1 Report
1 Paper

Efficient Tree Search in Encrypted Data
Brinkman, R., Feng, L., Doumen, J. M., Hartel, P. H. & Jonker, W., Apr 2004, p. 126-135. 10 p.
Research output: Contribution to conference › Paper › peer-review

Open Access
File
Efficient Tree Search in Encrypted Data
Brinkman, R., Feng, L., Doumen, J. M., Hartel, P. H. & Jonker, W., Mar 2004, Enschede: Centre for Telematics and Information Technology (CTIT). 10 p. (CTIT technical report series; no. TR-CTIT-04-15)
Research output: Book/Report › Report › Other research output

Open Access
File

Cite this

@article{3b1e3681247c47a0915be14488bb670a,

title = "Efficient Tree Search in Encrypted Data",

abstract = "Sometimes there is a need to store sensitive data on an untrusted database server. Song Wagner and Perrig have introduced a way to search for the existence of a word in an encrypted textual document. The search speed is linear in the size of the document. It does not scale well for a large database. We have developed a tree search algorithm based on the linear search algorithm that is suitable for XML databases. It is more efficient since it exploits the structure of XML. We have built prototype implementations for both the linear and the tree search case. Experiments show a major improvement in search time.",

keywords = "SCS-Cybersecurity",

author = "R. Brinkman and L. Feng and J. Doumen and P.H. Hartel and W. Jonker",

year = "2004",

month = jul,

doi = "10.1201/1086/44530.13.3.20040701/83065.3",

language = "English",

volume = "13",

pages = "14--21",

journal = "Information systems security",

issn = "1065-898X",

publisher = "Taylor & Francis",

number = "3",

}

TY - JOUR

T1 - Efficient Tree Search in Encrypted Data

AU - Brinkman, R.

AU - Feng, L.

AU - Doumen, J.

AU - Hartel, P.H.

AU - Jonker, W.

PY - 2004/7

Y1 - 2004/7

N2 - Sometimes there is a need to store sensitive data on an untrusted database server. Song Wagner and Perrig have introduced a way to search for the existence of a word in an encrypted textual document. The search speed is linear in the size of the document. It does not scale well for a large database. We have developed a tree search algorithm based on the linear search algorithm that is suitable for XML databases. It is more efficient since it exploits the structure of XML. We have built prototype implementations for both the linear and the tree search case. Experiments show a major improvement in search time.

AB - Sometimes there is a need to store sensitive data on an untrusted database server. Song Wagner and Perrig have introduced a way to search for the existence of a word in an encrypted textual document. The search speed is linear in the size of the document. It does not scale well for a large database. We have developed a tree search algorithm based on the linear search algorithm that is suitable for XML databases. It is more efficient since it exploits the structure of XML. We have built prototype implementations for both the linear and the tree search case. Experiments show a major improvement in search time.

KW - SCS-Cybersecurity

U2 - 10.1201/1086/44530.13.3.20040701/83065.3

DO - 10.1201/1086/44530.13.3.20040701/83065.3

M3 - Article

SN - 1065-898X

VL - 13

SP - 14

EP - 21

JO - Information systems security

JF - Information systems security

IS - 3

ER -

Efficient Tree Search in Encrypted Data

Abstract

Keywords

Access to Document

Fingerprint

Research output