Cryptography Reference
In-Depth Information
Authentication trees.
The security benefits of the refreshing
paradigm are increased when combining it with the use of
authen-
tication trees
, as introduced in (98). The idea is to use the pub-
lic verification-key in order to authenticate several (e.g., two) fresh
instances of the signature scheme, use each of these instances to authen-
ticate several additional fresh instances, and so on. We obtain a tree of
fresh instances of the basic signature scheme, where each internal node
authenticates its children. We can now use the leaves of this tree in order
to sign actual documents, where each leaf is used at most once. Thus,
a signature to an actual document consists of (1) a signature to this
document authenticated with respect to the verification-key associated
with some leaf, and (2) a sequence of verification-keys associated with
the nodes along the path from the root to this leaf, where each such
verification-key is authenticated with respect to the verification-key of
its parent. We stress that (by suitable implementation to be discussed
below) each instance of the signature scheme is used to sign at most one
string (i.e., a single sequence of verification-keys if the instance resides
in an internal node, and an actual document if the instance resides in a
leaf). Thus, it suces to use a signature scheme that is secure as long
as it is used to legitimately sign a single string. Such signature schemes,
called
one-time signature schemes
and introduced in (108), are easier to
construct than standard signature schemes, especially if one only wishes
to sign strings that are significantly shorter than the signing-key (resp.,
than the verification-key). For example, using a one-way function
f
,we
may let the signing-key consist of a sequence of
n
pairs of strings, let the
corresponding verification-key consist of the corresponding sequence of
images of
f
, and sign an
n
-bit long message by revealing the adequate
pre-images.
1
The hashing paradigm.
Note, however, that in the aforementioned
authentication-tree, the instances of the signature scheme (associated
with internal nodes) are used to sign a pair of verification-keys. Thus,
2
n
2
,thecor-
responding verification-key is (
f
(
s
1
)
,f
(
s
1
))
, ...,
(
f
(
s
n
)
,f
(
s
n
))), and the signature of the
message
σ
1
···σ
n
is (
s
σ
1
, ..., s
σ
n
).
1
That is, the signing-key consist of a sequence ((
s
1
,s
1
)
, ...,
(
s
n
,s
n
))
∈{
0
,
1
}
