Efficient Tree Search in Encrypted Data

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

Efficient Tree Search in Encrypted Data

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

Databases (Former)

Research output: Contribution to conference › Paper › peer-review

222 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	126-135
Number of pages	10
Publication status	Published - Apr 2004
Event	2nd International Workshop on Security In Information Systems, WOSIS 2004 - Porto, Portugal Duration: 14 Apr 2004 → 17 Apr 2004 Conference number: 2

Conference

Conference	2nd International Workshop on Security In Information Systems, WOSIS 2004
Abbreviated title	WOSIS
Country/Territory	Portugal
City	Porto
Period	14/04/04 → 17/04/04

Keywords

SCS-Cybersecurity
DB-SDM: SECURE DATA MANAGEMENT

Access to Document

Brinkman2004efficientAccepted author version, 169 KB

1 Report
1 Article

Efficient Tree Search in Encrypted Data
Brinkman, R., Feng, L., Doumen, J., Hartel, P. H. & Jonker, W., Jul 2004, In: Information Systems Security. 13, 3, p. 14-21 8 p.
Research output: Contribution to journal › Article › Academic › peer-review

Open Access
File
203 Downloads (Pure)
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

@conference{034f8423f9df40f38393d89f3f226d65,

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, DB-SDM: SECURE DATA MANAGEMENT",

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

year = "2004",

month = apr,

language = "English",

pages = "126--135",

note = "2nd International Workshop on Security In Information Systems, WOSIS 2004, WOSIS ; Conference date: 14-04-2004 Through 17-04-2004",

}

TY - CONF

T1 - Efficient Tree Search in Encrypted Data

AU - Brinkman, R.

AU - Feng, L.

AU - Doumen, J.M.

AU - Hartel, P.H.

AU - Jonker, W.

N1 - Conference code: 2

PY - 2004/4

Y1 - 2004/4

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

KW - DB-SDM: SECURE DATA MANAGEMENT

M3 - Paper

SP - 126

EP - 135

T2 - 2nd International Workshop on Security In Information Systems, WOSIS 2004

Y2 - 14 April 2004 through 17 April 2004

ER -

Efficient Tree Search in Encrypted Data

Abstract

Conference

Keywords

Access to Document

Fingerprint

Research output