Cryptography Reference

In-Depth Information

(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

property.

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.

←