Cryptography Reference
In-Depth Information
verification key). The idea is to use the initial signing key (i.e., the one corresponding
to the public verification key) in order to sign/authenticate two new/random verifi-
cation keys. The two corresponding signing keys are used to sign/authenticate four
new/random verification keys (two per each signing key), and so on. Stopping after
such steps, this process forms a binary tree with 2
leaves, where each leaf corresponds to
an instance of the one-time signature scheme. The signing keys at the leaves can be used
to sign the actual messages, and the corresponding verification keys can be authenticated
using the path from the root. That is, to sign a new message, we proceed as follows:
1.
Allocate a new leaf in the tree. This requires either keeping a counter of the number
of messages signed thus far or selecting a leaf at random (assuming that the number of
leaves is much larger than the square of the number of messages to be signed).
2.
Generate or retrieve from storage the pairs of signing/verification keys corresponding
to each vertex on the path from the root to the selected leaf, along with the key pairs
of the siblings of the vertices on the path. That is, let
v
0
,v
1
,...,v
denote the vertices
along the path from the root
v
0
to the selected leaf
v
, and let
u
i
be the sibling of
v
i
=
,...,
v
i
and each
u
i
, for
(for
i
1
). Then we generate/retrieve the key pairs of each
.
It is important to use the same key pair when encountering the same vertex in the
process of signing two different messages.
3.
Sign the message using the signing key associated with the selected leaf
i
=
1
,...,
v
. Sign each
pair of verification keys associated with the children of each internal vertex, along the
foregoing path, using the signing key associated with the parent vertex. That is, for
i
v
i
and
u
i
(placed in some canonical order)
using the signing key associated with vertex
=
1
,...,
, sign the verification keys of
v
i
−
1
.
The signature is obtained by concatenating all these signatures (along with the cor-
responding verification keys). Recall that the key pair associated with the root is the
actual key pair of the signature scheme; that is, the verification component is placed in
the public file, and the signature of the verification keys of the root's children (relative
to the root's signing key) is part of all signatures.
Pseudorandom functions can be used to eliminate the need to store the values of vertices
used in previous signatures [89].
Employing this paradigm, and assuming that the RSA function is infeasible to in-
vert, one obtains a secure signature scheme [125, 89] (with a counter of the number
of messages signed) in which the
i
th message is signed/verified in time 2 log
2
i
slower
than plain RSA. Using a tree of large fan-in (and assuming again that RSA is infea-
sible to invert), one can obtain a secure signature scheme [67, 56] that for reasonable
parameters is only five times slower than plain RSA.
8
We stress that plain RSA is
not a secure signature scheme, whereas the security of its randomized version (men-
tioned earlier) is not known to be reducible to the assumption that RSA is hard to
invert.
8
This figure refers to signing up to 1,000,000,000 messages. The scheme in [67] requires a universal set
of system parameters consisting of 1000-2000 integers of the size of the moduli. In the scheme of [56], that
requirement is removed.
