Efficient Tree Search in Encrypted Data

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

Research output: Contribution to conference › Paper

49 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 languageEnglish
Pages126-135
Number of pages10
Publication statusPublished - Apr 2004
Event2nd International Workshop on Security In Information Systems, WOSIS 2004 - Porto, Portugal
Duration: 14 Apr 2004 → 17 Apr 2004
Conference number: 2

Conference

Conference2nd International Workshop on Security In Information Systems, WOSIS 2004
Abbreviated titleWOSIS
CountryPortugal
CityPorto
Period14/04/04 → 17/04/04

Fingerprint

XML
Servers
Experiments

Keywords

  • IR-65546
  • SCS-Cybersecurity
  • DB-SDM: SECURE DATA MANAGEMENT
  • EWI-1734

Cite this

Brinkman, R., Feng, L., Doumen, J. M., Hartel, P. H., & Jonker, W. (2004). Efficient Tree Search in Encrypted Data. 126-135. Paper presented at 2nd International Workshop on Security In Information Systems, WOSIS 2004, Porto, Portugal.
Brinkman, R. ; Feng, L. ; Doumen, J.M. ; Hartel, P.H. ; Jonker, W. / Efficient Tree Search in Encrypted Data. Paper presented at 2nd International Workshop on Security In Information Systems, WOSIS 2004, Porto, Portugal.10 p.
@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 = "IR-65546, SCS-Cybersecurity, DB-SDM: SECURE DATA MANAGEMENT, EWI-1734",
author = "R. Brinkman and L. Feng and J.M. Doumen and P.H. Hartel and W. Jonker",
note = "Imported from EWI/DB PMS [db-utwente:inpr:0000003563]; 2nd International Workshop on Security In Information Systems, WOSIS 2004, WOSIS ; Conference date: 14-04-2004 Through 17-04-2004",
year = "2004",
month = "4",
language = "English",
pages = "126--135",

}

Brinkman, R, Feng, L, Doumen, JM, Hartel, PH & Jonker, W 2004, 'Efficient Tree Search in Encrypted Data' Paper presented at 2nd International Workshop on Security In Information Systems, WOSIS 2004, Porto, Portugal, 14/04/04 - 17/04/04, pp. 126-135.

Efficient Tree Search in Encrypted Data. / Brinkman, R.; Feng, L.; Doumen, J.M.; Hartel, P.H.; Jonker, W.

2004. 126-135 Paper presented at 2nd International Workshop on Security In Information Systems, WOSIS 2004, Porto, Portugal.

Research output: Contribution to conference › Paper

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 - Imported from EWI/DB PMS [db-utwente:inpr:0000003563]

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 - IR-65546

KW - SCS-Cybersecurity

KW - DB-SDM: SECURE DATA MANAGEMENT

KW - EWI-1734

M3 - Paper

SP - 126

EP - 135

ER -

Brinkman R, Feng L, Doumen JM, Hartel PH, Jonker W. Efficient Tree Search in Encrypted Data. 2004. Paper presented at 2nd International Workshop on Security In Information Systems, WOSIS 2004, Porto, Portugal.

Access to Document