Databases Reference
In-Depth Information
Table 1.
Notation used.
Symbol Description
r
A database record
A
B
+
-tree key
k
A
B
+
-tree pointer
p
h
A hash value
s
A signature
|
x
|
Size of object
x
N
D
Total number of database records
N
R
Total number of query results
P
Page size
f
x
Node fanout of structure
x
d
x
Height of structure
x
H
l
(
x
)
A hash operation on input
x
of length
l
S
l
(
x
)
A signing operation on input
x
of length
l
V
l
(
x
)
A verifying operation on input
x
of length
l
C
x
Cost of operation
x
VO
The verification object
3 Authenticated Index Structures for Selection Queries
Existing solutions for the query authentication problem work as follows. The
data owner creates a specialized authenticated data structure that captures
the original database and uploads it at the servers together with the database
itself. The structure is used by the servers to provide a verification object
VO
, along with every query answer, which clients can use for authenticating
the results. Verification usually occurs by means of using collision-resistant
hash functions and digital signature schemes. Note that in any solution, some
information that is known to be authentically published by the owner must be
made available to the client directly; otherwise, from the client's point of view,
the owner cannot be differentiated from any other potentially malicious entity.
For example, this information could be the owner's public key of any public
signature scheme. For any authentication method to be successful it must be
computationally infeasible for a malicious server to produce an incorrect query
answer along with a verification object that will be accepted by a client that
holds the correct authentication information of the owner.
Next, we illustrate three approaches for query correctness and complete-
ness for selection queries on a single attribute: a signature-based approach
similar to the ones described in [9, 24], a Merkle-tree-like approach based on
the ideas presented in [28], and an improved embedded tree approach [29]. We
present them for the
static scenario
where no data updates occur between the
owner and the servers on the outsourced database. We also present
analytical
cost models
for all techniques, given a variety of performance metrics.
