(1) One-way functions exist.
(2) Secure signature schemes exist.
(3) Secure message authentication schemes exist.
We stress that, unlike in the case of public-key encryption schemes,
the construction of signature schemes (which may be viewed as a
public-key analogue of message authentication) does not use a trapdoor
How to construct secure signature schemes
Three central paradigms used in the construction of secure signature
schemes are the “refreshing” of the “effective” signing-key, the usage
of an “authentication tree”, and the “hashing paradigm” (all to be
discussed in the sequel). In addition to being used in the proof of
Theorem 6.2, all three paradigms are also of independent interest.
The refreshing paradigm. Introduced in (82), the refreshing
paradigm is aimed at limiting the potential dangers of chosen message
attacks. This is achieved by signing the actual document using a newly
(randomly) generated instance of the signature scheme, and authenti-
cating (the verification-key of) this random instance with respect to the
fixed public-key. That is, consider a basic signature scheme ( G, S, V )
used as follows. Suppose that the user U has generated a key-pair,
( s, v )
G (1 n ), and has placed the verification-key v on a public-file.
When a party asks U to sign some document α , the user U generates
a new (“fresh”) key-pair, ( s ,v )
G (1 n ), signs v using the origi-
nal signing-key s ,signs α using the new signing-key s , and presents
( S s ( v ) ,v ,S s ( α )) as a signature to α . An alleged signature, ( β 1 ,v ,β 2 ),
is verified by checking whether both V v ( v ,β 1 )=1and V v ( α, β 2 )=1
hold. Intuitively, the gain in terms of security is that a full-fledged cho-
sen message attack cannot be launched on a fixed instance of ( G, S, V )
(i.e., on the fixed verification-key that resides in the public-file and is
known to the attacker). All that an attacker may obtain (via a chosen
message attack on the new scheme) is signatures, relative to the origi-
nal signing-key s of ( G, S, V ), to random strings (distributed according
to G (1 n )) as well as additional signatures that are each relative to a
random and independently distributed signing-key.