Databases Reference
In-Depth Information
5
Authenticated Index Structures for
Outsourced Databases
Feifei Li
1
, Marios Hadjileftheriou
2
, George Kollios
3
, and Leonid Reyzin
3
1
Department of Computer Science
Florida State University
lifeifei@cs.fsu.edu
2
AT&T Labs Inc.
marioh@research.att.com
3
Computer Science Department
Boston University
gkollios@cs.bu.edu,reyzin@cs.bu.edu
Summary.
In an outsourced database (ODB) system the database owner publishes
data through a number of remote servers, with the goal of enabling clients at the
edge of the network to access and query the data more eciently. As servers might be
untrusted or can be compromised,
query authentication
becomes an essential com-
ponent of ODB systems. In this chapter we present three techniques to authenticate
selection range queries and we analyze their performance over different cost metrics.
In addition, we discuss extensions to other query types.
1 Introduction
Today, there is a large number of corporations that use electronic commerce
as their primary means of conducting business. As the number of customers
using the Internet for acquiring services increases, the demand for providing
fast, reliable and secure transactions increases accordingly — most of the
times beyond the capacity of individual businesses to provide the level of
service required, given the overwhelming data management and information
processing costs involved.
Increased demand has fueled a trend towards outsourcing data manage-
ment and information processing needs to third-party service providers in
order to mitigate the in-house cost of furnishing online services [1]. In this
model the third-party service provider is responsible for offering the neces-
sary resources and mechanisms for eciently managing and accessing the
outsourced data, by data owners and customers respectively. Clearly, data out-
sourcing intrinsically raises issues related with trust. Service providers cannot
always be trusted (they might have malicious intend), might be compromised
(by other parties with malicious intend) or run faulty software (unintentional
