Databases Reference
In-Depth Information
Construction cost:
The cost incurred by the owner for constructing the structure has three com-
ponents: the signature computation cost, bulk-loading the
B
+
-tree, and the
I/O cost for storing the structure. Since the signing operation is very expen-
sive, it dominates the overall cost. Bulk-loading the
B
+
-tree in main memory
is much less expensive and its cost can be omitted. Hence:
s
P
·C
IO
.
C
S
2
|h|
)+
C
c
=
N
D
C
·
(
C
H
|r|
+
(3)
VO
construction cost:
The cost of constructing the
for a range query depends on the total disk
I/O for traversing the
B
+
-tree and retrieving all necessary record/signature
pairs, as well as on the computation cost of
s
π
. Assuming that the total
number of leaf pages accessed is
N
Q
=
N
R
VO
f
a
,the
VO
construction cost is:
1+
N
R
·|
r
|
+
N
R
·|
s
|
q
=(
N
Q
+
d
a
−
C
)
·C
IO
+
C
s
π
,
(4)
P
P
where the last term is the modular multiplication cost for computing the
aggregated signature, which is linear to
N
R
. The I/O overhead for retrieving
the signatures is also large.
Authentication cost:
The size of the
VO
is equal to the result-set size plus the size of one signature:
a
=
N
R
·|
|VO|
r
|
+
|
s
|
.
(5)
The cost of verifying the query results is dominated by the hash function
computations and modular multiplications at the client:
a
v
C
=
N
R
·C
H
|r|
+
C
m
π
+
C
V
|n|
,
(6)
where the modular multiplication cost for computing the aggregated hash
value is linear to the result-set size
N
R
, and the size of the final product has
length in the order of
(the RSA modulus). The final term is the cost of
verifying the product using
s
π
and the owner's public key.
It becomes obvious now that one advantage of the aggregated signature
scheme is that it features small
|
n
|
sizes and hence small client/server com-
munication cost. On the other hand it has the following serious drawbacks: 1.
Large storage overhead on the servers, dominated by the large signature sizes,
2. Large communication overhead between the owners and the servers that
cannot be reduced, 3. A very high initial construction cost, dominated by the
cost of computing the signatures, 4. Added I/O cost for retrieving signatures,
linear to
N
R
, 5. An added modular multiplication cost, linear to the result-set
VO
