03-05-2012, 02:33 PM
A New Forward-Secure Digital Signature Scheme
A New Forward-Secure Digital Signature Scheme.pdf (Size: 263.46 KB / Downloads: 57)
1 Introduction
1.1 The problem
Many cryptographic techniques today, whether only available in the literature or actually used in
practice, are believed to be quite secure. Several, in fact, can be proven secure (with appropriate
denitions) under very reasonable assumptions. In a vast majority of solutions, however, security
guarantees last only as long as secrets remain unrevealed. If a secret is revealed (either accidentally
or via an attack), security is often compromised not only for subsequent uses of the secret, but also
for prior ones. For example, if a secret signing key becomes known to an adversary, one cannot
trust any signature produced with that key, regardless of when; if a secret decryption key becomes
known to an adversary, then any encrypted message, even if sent long before, is not guaranteed to
remain private.
To address this problem, several dierent approaches have been suggested. Many attempt to
lower the chance of exposure of secrets by distributing them across several systems, usually via
secret sharing. As pointed out in [2], this method is usually quite costly, and may, in fact, be too
expensive to be implemented by a typical individual user. Moreover, since each of the systems may
be susceptible to the same attack, the actual risk may not decrease.
A complementary approach is to reduce the potential damage in case secrets are exposed. In
what is often called forward security, the main idea is to ensure that secrets are used only for
short time periods, and that compromise of a secret does not aect anything based on secrets from
prior time periods. One of the challenges in designing such a system is to be able to change secret
information without the inconvenience of changing public information, such as the public key.
This approach has been known in the context of key agreement as forward secrecy [13, 7]. In
the context of digital signatures, it was rst proposed, together with a few simple solutions, by
Anderson in [1]. Bellare and Miner formalized Anderson's approach and provided more solutions
in [2]
The specic problem addressed in this paper is that of designing a forward-secure signature
scheme.
1.2 Forward-Secure Signature Schemes
Informally, a key-evolving signature scheme is one whose operation is divided into time periods,
with a dierent secret key for each time period. Each secret key is used to sign messages only
during a particular time-period, and to compute a new secret key at the end of that time period.
It is then erased. As in ordinary signature schemes, however, there is only one public key, which
remains the same through all the time periods. The verication algorithm checks not only that a
signature is valid, but also that it was generated during a specic time period.
Such a scheme is forward-secure if it is infeasible for an adaptive chosen-message adversary to
forge signatures for past time periods, even if it discovers the secret key for the current time period.
Note that, in particular, this implies that past secret keys cannot be recovered from the current
one. In a forward-secure signature scheme, even if the current secret key is compromised, signatures
from past time periods can still be trusted.
Anderson [1] proposed a construction of forward-secure signature schemes in which the size
of secret key (but not the public key) grows linearly with the number of time periods. The rst
forward-secure signature schemes in which key sizes do not grow linearly were proposed by Bellare
and Miner in [2]. Their most ecient scheme, forward-secure in the random oracle model of [3]
(assuming factoring is hard), uses ideas from the Fiat-Shamir [9] and Ong-Schnorr [15] identication
and signature schemes.
3
As mentioned in [2], although still practical, their scheme requires very large keys, mainly
because the original Fiat-Shamir scheme required very large keys (in fact, the forward-secure scheme
of [2] does not add much to the already large key).
1.3 Our Contributions
Main result. We propose a new forward-secure digital signature scheme, with much shorter keys
than those in the scheme of [2]. In fact, our keys are comparable in size to those used in similar
ordinary signature schemes.
Similarly to the scheme of [2], our scheme is based on signature schemes that are derived from
three-round identication protocols. Specically, the scheme is based on a generalized version of
Micali's signature scheme [16], which is in many ways similar to the schemes of Ong-Schnorr [15],
Guillou-Quisquater [12] and Ohta-Okamoto [18]. It is quite simple and ecient, although the
computational eciency of some components is less than that of the scheme of [2]. Our scheme
can also be proven forward secure in the random oracle model, assuming factoring is hard.
Other contributions. While [2] use reduction to identication schemes to prove security, we
use a direct proof technique. This enables us to provide a tighter exact security analysis for our
scheme than the indirect technique of [2]. In fact, our technique can also be applied to the scheme
of [2] to obtain a tighter security analysis for that scheme (which we present in Section 3.5).
We also present methods of achieving forward security in signature schemes without relying
on random oracles. In general, they are less ecient than our main construction, and are not
practical. However, they are still of interest, and can be viewed as an improvement on the treebased
construction of [2].
1.4 Outline
We start by giving in Section 2 precise denitions of key-evolving signature schemes and their
forward-security. We then proceed in Section 3 with the description of our main scheme, its security
analysis, and its comparison to the scheme of Bellare and Miner. We conclude in Section 4 by
discussing alternate methods for achieving forward security in signature schemes, which do not rely
on random oracles.
2 Denitions
In this section, we rst describe how a forward secure digital signature scheme operates and dene
its formal notion of security, both inside and outside the random oracle model. All denitions
provided here are based on those given in [2], which in turn are based on those given in [11] and [4].
Since our scheme is based on the hardness of factoring Blum integers, we also present a formal
denition for the security of this problem.
2.1 Forward-secure digital signature schemes
A forward-secure digital signature scheme is, rst of all, a key-evolving digital signature scheme. A
key-evolving signature scheme is very similar to a standard one. Like a standard signature scheme,
it contains a key generation algorithm, a signing algorithm, and a verication algorithm. The public
key is left unchanged throughout the lifetime of the scheme, making the verication algorithm very
similar to that of a standard signature scheme. Unlike a standard signature scheme, a key-evolving
signature scheme has its operation divided into time periods, each of which uses a dierent (but
4
related) secret key to sign a message. The way these keys are updated is given by a public update
algorithm, which computes the secret key for the new time period based on that for the previous
one. The forward security comes, in part, from the fact that this update function is one-way and,
given the secret key for the current period, it is hard to compute any of the previously used secret
keys. It is important, of course, for the signer to delete the old secret key as soon as the new
one is generated, since otherwise an adversary breaking the system could easily get hold of these
undeleted keys and forge messages for time periods preceding that of the break-in. Let us now
dene more formally what a key-evolving digital signature scheme is and then dene what it means
for it to be forward-secure.
Denition 2.1 [Key-evolving signature scheme] A key-evolving digital signature scheme is a
quadruple of algorithms, FSIG = (FSIG:key; FSIG:update; FSIGign; FSIG:vf), where:
FSIG:key, the key generation algorithm, is a probabilistic algorithm which takes as input a
security parameter k 2 N (given in unary as 1k) and the total number of periods T and returns
a pair (SK0;PK), the initial secret key and the public key;
FSIGign, the (possibly probabilistic) signing algorithm, takes as input the secret key SKj
for the current time period and the message M to be signed and returns a pair hj; signi, the
signature of M for time period j;
FSIG:update, the (possibly probabilistic) secret key update algorithm, takes as input the secret
key for the current period SKj and returns the new secret key SKj+1 for the next period.
FSIG:vf, the (deterministic) verication algorithm, takes as input the public key PK, a message
M, and a candidate signature hj; signi, and returns 1 if hj; signi is a valid signature of M or
0, otherwise. It is required that FSIG:vfPK (M; FSIGignSKj (M)) = 1 for every message M and
time period j.
We also assume that the secret key SKj for time period j T always contains both the value j
itself and the value T of the total number of periods. Finally, we adopt the convention that SKT+1
is the empty string and that FSIG:updateSKT returns SKT+1.
When we work in the random oracle model, all the above-mentioned algorithms would additionally
have oracle access to a public hash function H, which is assumed to be random in the security
analysis.
Security in the standard model. Informally, we want it to be computationally infeasible for
any adversary to forge a signature with respect to any of the previously used secret keys even in
the event of exposure of the current secret key. Of course, since the update algorithm is public,
nothing can be done with respect to future secret keys, except for revoking the public key and
considering invalid any signature for the time period of the break-in and thereafter. To dene this
notion of security formally, we again use the security model introduced by Bellare and Miner [2],
which extends that of Goldwasser, Micali and Rivest [11] to take into account the ability of the
adversary to obtain a key by means of a break-in.
In this new model, besides knowing the user's public key PK, the adversary also gets to know
the total number of time periods and the current time period. The adversary runs in three phases.
In the rst phase, the chosen message attack phase (cma), the adversary has access to a signing
oracle, which it can query to obtain signatures of messages of its choice with respect to the current
secret key. At the end of each time period, the adversary can choose whether to stay in the same
phase or switch to the break-in phase (breakin). In the break-in phase, which models the possibility
of a key exposure, we give the adversary the secret key SKj for the specic time period j it decided
5
to break in. In the last phase, the forgery phase (forge), the adversary outputs a pair signaturemessage,
that is, a forgery. The adversary is considered to be successful if it forges a signature of
some new message (that is, not previously queried to the signing oracle) for some time period prior
to j.
In order to capture the notion of forward security of a key-evolving signature scheme FSIG =
(FSIG:key; FSIG:update; FSIGign; FSIG:vf) more formally, let F be an adversary for this scheme. To
assess the success probability of F breaking the forward security of FSIG, consider the following
experiment.