Databases Reference
In-Depth Information
In particular, we provide models for the
storage
,
construction
,
query
,
and
authentication
cost of each technique, taking into account the overhead
of hashing, signing, verifying data, and performing expensive computations
(like modular multiplications of large numbers). The analysis considers range
queries on a specific database attribute
A
indexed by a
B
+
-tree [30]. The size
of the structure is important first for quantifying the storage overhead on the
servers, and second for possibly quantifying the owner/server communication
cost. The construction cost is useful for quantifying the overhead incurred
by the database owner for outsourcing the data. The query cost quantifies
the incurred server cost for answering client queries, and hence the potential
query throughput. The authentication cost quantifies the server/client com-
munication cost and, in addition, the client side incurred cost for verifying
the query results. The notation used is summarized in Table 1. In the rest,
for ease of exposition, it is assumed that all structures are bulk-loaded in a
bottom-up fashion and that all index nodes are completely full. Extensions
for supporting multiple selection attributes are discussed in Section 6.
Aggregated Signatures with B
+
-trees
The first authenticated data structure for static environments is a direct ex-
tension of aggregated signatures and ideas that appeared in [24, 9]. To guar-
antee correctness and completeness the following technique can be used: First,
the owner individually hashes and signs all consecutive pairs of tuples in the
database, assuming some sorted order on a given attribute
A
. For example,
given two consecutive tuples
r
i
,r
j
the owner transmits to the servers the pair
(
r
i
,s
i
), where
s
i
=
' denotes some canonical pairing of strings that
can be uniquely parsed back into its two components; e.g., simple string con-
catenation if the lengths are fixed). The first and last tuples can be paired with
special marker records. Chaining tuples in this way will enable the clients to
verify that no in-between tuples have been dropped from the results or mod-
ified in any way. An example of this scheme is shown in Figure 2.
S
(
r
i
|
r
j
)('
|
B
+
-tree
r
1
r
2
r
3
r
n
r
x
...
S
(
r
1
|
r
2
)
S
(
r
2
|
r
)
S
(
r
3
|
r
)
S
(
r
n
|
r
)
3
4
x
Fig. 2.
The signature-based approach.
In order to speed up query execution on the server side a
B
+
-tree is con-
structed on top of attribute
A
. To answer a query the server constructs a
VO
that contains one pair
r
q
|
s
q
per query result. In addition, one tuple to the left
of the lower-bound of the query results and one to the right of the upper-bound
