KIT | KIT-Bibliothek | Impressum

On Secrecy and Performance Models for Query Processing on Outsourced Graph Data

Suntaxi, Gabriela; El Ghazi, Aboubakr Achraf; Böhm, Klemens

Database outsourcing is a challenging task concerning data secrecy. Even if an adversary, including the service provider, accesses the data, she should not be able to learn any information from the accessed data. In this paper we address this problem for graph-structured data. First, we define a secrecy notion for graph-structured data based on the concept of indistinguishability. The notion ensures that an adversary can learn the edges existing between the nodes only with negligible probability. To address this problem, we propose an approach based on bucketization. Next to bucketization, it makes use of obfuscated indexes and encryption. We show that finding an optimal bucketization tailored to graph-structured data is NP-hard; therefore we come up with a heuristic. We prove that the proposed bucketization approach fulfills our secrecy notion. In addition, we present a performance model which consists of (1) a number of buckets model that estimates the number of buckets obtained after applying our bucketization approach and (2) a query-cost model. Finally, we demonstrate with a set of experiments (1) the accuracy of our number of ... mehr

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht
Jahr 2017
Sprache Englisch
Identifikator DOI(KIT): 10.5445/IR/1000069204
ISSN: 2190-4782
URN: urn:nbn:de:swb:90-692041
KITopen ID: 1000069204
Verlag Karlsruhe
Umfang 14 S.
Serie Karlsruhe Reports in Informatics ; 2017,5
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page