Databases Reference
In-Depth Information
2.1 Collision-resistant hash functions.
For our purposes, a hash function
is an eciently computable function
that takes a variable-length input
x
to a fixed-length output
y
=
H
(
x
).
Colli-
sion resistance
states that it is computationally infeasible to find two inputs
x
1
H
(
x
2
). Collision-resistant hash functions can be
built provably based on various cryptographic assumptions, such as hardness
of discrete logarithms [16]. However, we concentrate on using heuristic hash
functions that have the advantage of being very fast to evaluate. Specifically
we focus on SHA-1 [17], which takes variable-length inputs to 160-bit (20-
byte) outputs. SHA-1 is currently considered collision-resistant in practice,
despite some recent successful attacks [18, 19]. We also note that any even-
tual replacement to SHA-1 developed by the cryptographic community can
be used instead of SHA-1.
=
x
2
such that
H
(
x
1
)=
H
2.2 Public-key digital signature schemes.
A public-key digital signature scheme, formally defined in [20], is a tool for
authenticating the integrity and ownership of the signed message. In such a
scheme, the signer generates a pair of keys (
SK , PK
), keeps the secret key
SK
secret, and publishes the public key
PK
associated with her identity.
Subsequently, for any message
m
that she sends, a signature
s
m
is produced by
s
m
=
(
PK ,m,s
m
)
that outputs “valid” or “invalid.” A valid signature on a message assures
the recipient that the owner of the secret key intended to authenticate the
message, and that the message has not been changed. The most commonly
used public digital signature scheme is RSA [21]. Existing solutions [9, 22, 23,
24] for the query authentication problem chose to use this scheme, hence we
adopt the common 1024-bit (128-byte) RSA here. Its signing and verification
cost is one hash computation and one modular exponentiation with 1024-bit
modulus and exponent.
S
(
SK ,m
). The recipient of
s
m
and
m
can verify
s
m
via
V
2.3 A Signature Aggregation Scheme.
In the case when
t
signatures
s
1
,...,s
t
on
t
messages
m
1
,...,m
t
signed by
the same signer need to be verified all at once, certain signature schemes allow
for more ecient communication and verification than
t
individual signatures.
Namely, for RSA it is possible to combine the
t
signatures into a single ag-
gregated signature
s
1
,t
that has the same size as an individual signature and
that can be verified (almost) as fast as an individual signature. This tech-
nique is called Condensed-RSA [25]. The combining operation can be done
by anyone, as it does not require knowledge of
SK
; moreover, the security of
the combined signature is the same as the security of individual signatures.
In particular, aggregation of
t
RSA signatures can be done at the cost of
t
−
1
modular multiplications, and verification can be performed at the cost of
t
−
1
