International Association for Cryptologic Research

International Association
for Cryptologic Research


Sara K. Miner


Composition and Efficiency Tradeoffs for Forward-Secure Digital Signatures
Forward-secure digital signatures, initially proposed by Anderson in CCS 97 and formalized by Bellare and Miner in Crypto 99, are signature schemes which enjoy the additional guarantee that a compromise of the secret key at some point in time does not help forge signatures allegedly signed in an earlier time period. Consequently, if the secret key is lost, then the key can be safely revoked without invalidating previously-issued signatures. Since the introduction of the concept, several forward-secure signature schemes have been proposed, with varying performance both in terms of space and time. Which scheme is most useful in practice typically depends on the requirements of the specific application. In this paper we propose and study some general composition operations that can be used to combine existing signature schemes (whether forward-secure or not) into new forward-secure signature schemes. Our schemes offer interesting trade-offs between the various efficiency parameters, achieving a greater flexibility in accommodating the requirements of different applications. As an extension of our techniques, we also construct the first efficient forward-secure signature scheme where the total number of time periods for which the public key is used does not have to be fixed in advance. The scheme can be used for practically unbounded time, and the performance depends (minimally) only on the time elapsed so far. Our scheme achieves excellent performance overall, is very competitive with previous schemes with respect to all parameters, and outperforms each of the previous schemes in at least one parameter. Moreover, the scheme can be based on any underlying digital signature scheme, and does not rely on specific assumptions. Its forward security is proven in the standard model, without using a random oracle.
Concrete Security Characterizations of PRFs and PRPs: Reductions and Applications
Anand Desai Sara Miner
We investigate, in a concrete security setting, several alternate characterizations of pseudorandom functions (PRFs) and pseudorandom permutations (PRPs). By analyzing the concrete complexity of the reductions between the standard notions and the alternate ones, we show that the latter, while equivalent under polynomial-time reductions, are weaker in the concrete security sense. With these alternate notions, we argue that it is possible to get better concrete security bounds for certain PRF/PRP-based schemes. As an example, we show how using an alternate characterization of a PRF could result in tighter security bounds for a certain class of message authentication codes. We also apply these techniques to give a simple concrete security analysis of the counter mode of encryption. In addition, our results provide some insight into how injectivity impacts pseudorandomness.
Forward Security in Threshold Signature Schemes
We consider the usage of forward security with threshold signature schemes. This means that even if more than the threshold number of players are compromised, some security remains: it is not possible to forge signatures relating to the past. In this paper, we describe the first forward-secure threshold signature schemes whose parameters (other than signing or verifying time) do not vary in length with the number of time periods in the scheme. Both are threshold versions of the Bellare-Miner forward-secure signature scheme, which is Fiat-Shamir-based. One scheme uses multiplicative secret sharing, and tolerates mobile eavesdropping adversaries. The second scheme is based on polynomial secret sharing, and we prove it forward-secure based on the security of the Bellare-Miner scheme. We then sketch modifications which would allow this scheme to tolerate malicious adversaries. Finally, we give several general constructions which add forward security to any existing threshold scheme.
Graph-Based Authentication of Digital Streams
Sara Miner Jessica Staddon
We consider the authentication of digital streams over a lossy network. The overall approach taken is graph-based, as this yields simple methods for controlling overhead, delay, and the ability to authenticate, while serving to unify many previously known hash- and MAC-based techniques. The loss pattern of the network is defined probabilistically, allowing both bursty and random packet loss to be modeled. Our authentication schemes are customizable by the sender of the stream; that is, within reasonable constraints on the input parameters, we provide schemes that achieve the desired authentication probability while meeting the input upper bound on the overhead per packet. In addition, we demonstrate that some of the shortcomings of previously known schemes correspond to easily identifiable properties of a graph, and hence, may be more easily avoided by taking a graph-based approach to designing authentication schemes.
A forward-secure digital signature scheme
Mihir Bellare Sara Miner
We describe a digital signature scheme in which the public key is fixed but the secret signing key is updated at regular intervals so as to provide a <i>forward security</i> property: compromise of the current secret key does not enable an adversary to forge signatures pertaining to the past. This can be useful to mitigate the damage caused by key exposure without requiring distribution of keys. Our construction uses ideas from the Fiat-Shamir and Ong-Schnorr identification and signature schemes, and is proven to be forward secure based on the hardness of factoring, in the random oracle model. The construction is also quite efficient.