Databases Reference
In-Depth Information
is returned, in order for the client to be able to guarantee that no boundary
results have been dropped. Notice that since our completeness requirements
are less stringent than those of [9] (where they assume that database access
permissions restrict which tuples the database can expose to the user), for
fairness we have simplified the query algorithm substantially here.
There are two obvious and serious drawbacks associated with this ap-
proach. First, the extremely large
size that contains a linear number
of signatures w.r.t.
N
R
(the total number of query results), taking into ac-
count that signature sizes are very large. Second, the high verification cost
for the clients. Authentication requires
N
R
verification operations which, as
mentioned earlier, are very expensive. To solve this problem one can use the
aggregated signature scheme discussed in Section 2.3. Instead of sending one
signature per query result the server can send one
combined signature s
π
for all
results, and the client can use an aggregate verification instead of individual
verifications.
By using aggregated RSA signatures, the client can authenticate the results
by hashing consecutive pairs of tuples in the result-set, and calculating the
VO
product
m
π
=
∀q
h
q
(mod
n
) (where
n
is the RSA modulus from the public
key of the owner). It is important to notice that both
s
π
and
m
π
require a
linear number of modular multiplications (w.r.t.
N
R
). The cost models of the
aggregated signature scheme for the metrics considered are as follows:
Node fanout:
The node fanout of the
B
+
-tree structure is:
P
−|
p
|
f
a
=
+1
.
(1)
|
k
|
+
|
p
|
are the sizes of a
B
+
-tree key and
where
P
is the disk page size,
|
k
|
and
|
p
|
pointer respectively.
Storage cost:
The total size of the authenticated structure (excluding the database itself)
is equal to the size of the
B
+
-tree plus the size of the signatures. For a total
of
N
D
tuples the height of the tree is equal to
d
a
= log
f
a
N
D
, consisting of
N
I
=
(=
d
a
−
1
i
=0
f
d
a
−
1
f
a
−
1
f
a
) nodes in total. Hence, the total storage cost is
equal to:
f
d
a
a
−
1
a
s
C
=
P
·
+
N
D
·|
s
|
.
(2)
f
a
−
1
The storage cost also reflects the initial communication cost between the
owner and servers. Notice that the owner does not have to upload the B
+
-tree
to the servers, since the latter can rebuild it by themselves, which will reduce
the owner/server communication cost but increase the computation cost at
the servers. Nevertheless, the cost of sending the signatures cannot be avoided.
