# «Append-Only Signatures Eike Kiltz∗ Anton Mityagin† Saurabh Panjwani‡ Barath Raghavan§ May 6, 2005 Abstract We present a new ...»

A preliminary version of this paper appeared in the 32nd International Colloquium on Automata, Languages and Programming, ICALP 2005, Lecture Notes in Computer Science Vol.

???, Giuseppe F. Italiano, Catuscia Palamidessi and Moti Yung eds, Springer Verlag, 2005. This

is the full version.

Append-Only Signatures

Eike Kiltz∗ Anton Mityagin† Saurabh Panjwani‡ Barath Raghavan§

May 6, 2005

Abstract

We present a new primitive—Append-only Signatures (AOS)—with the property that any party given an AOS signature Sig[M1 ] on message M1 can compute Sig[M1 M2 ] for any message M2, where M1 M2 is the concatenation of M1 and M2. We deﬁne the security of AOS, present concrete AOS schemes, and prove their security under standard assumptions.

In addition, we ﬁnd that despite its simple deﬁnition, AOS is equivalent to Hierarchical Identity-based Signatures (HIBS) through eﬃcient and security-preserving reductions. Finally, we show direct applications of AOS to problems in network security. Our investigations indicate that AOS is both useful in practical applications and worthy of further study as a cryptographic primitive.

Keywords: Algebraic Signatures, Append-only Signatures, Hierarchical Identity-based Signatures ∗ Department of Computer Science and Engineering, University of California, San Diego, San Diego, USA.

Email: ekiltz@cs.ucsd.edu. URL: http://www.kiltz.net/. Research supported by a DAAD postdoc fellowship.

† Department of Computer Science and Engineering, University of California, San Diego, San Diego, USA.

Email: amityagin@cs.ucsd.edu. Research supported in part by NSF grants ANR-0129617 and CCR-0208842.

‡ Department of Computer Science and Engineering, University of California, San Diego, San Diego, USA.

Email: panjwani@cs.ucsd.edu. URL: http://www.cse.ucsd.edu/users/spanjwan/. Research supported in part by NSF grant 0313241. Any opinions, ﬁndings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reﬂect the views of the National Science Foundation.

§ Department of Computer Science and Engineering, University of California, San Diego, San Diego, USA.

Email: barath@cs.ucsd.edu. Research supported by a NSF Graduate Research Fellowship.

Contents 1 Introduction 1 2 Append-only Signatures 3 3 Eﬃcient AOS Constructions

D AOS with short key size 28 1 Introduction In many real-world applications, users and programs alike require notions of delegation to model the ﬂow of information. It is often required that delegation from one party to another enables the delegatee to “append” to the information it received but to do nothing more. For example, in wide-area Internet routing, each network passes a routing path advertisement to its neighboring networks, which then append to it information about themselves and forward the updated advertisement to their neighbors. For security, the route advertisements must be authenticated;

intermediate networks must be incapable of modifying routes except according to the protocol (that is, by appending their names to already-received advertisements). Likewise, in the context of secure resource delegation for distributed systems, users need to delegate their share of resources to other users, who may then re-delegate to other users by including their own resources in the pool. In many of these applications, it is desirable that delegation is possible without parties having to share any cryptographic keys and that the authenticity of any information received through a series of delegations is veriﬁable based only on the identity of the ﬁrst party in the chain.

To directly address the needs of these applications, we present a new cryptographic primitive called Append-Only Signatures (AOS). Informally, an AOS scheme enables the extension of signed messages and update of the corresponding signatures, without requiring possession of the signing key. That is, any party given an AOS signature Sig[M1 ] on message M1 can compute Sig[M1 M2 ] for any message M2, where M1 M2 is the concatenation of M1 and M2. The veriﬁer of the ﬁnal signature needs the initial signer’s public key but does not need to know the public keys or any other information from intermediate signers except the message data appended. Clearly, such a scheme cannot be secure according to the standard notion of security for signatures. Instead, we deﬁne an AOS scheme to be secure if it is infeasible to forge signatures of messages that are not obtained by extending already-signed messages. We deﬁne the security of AOS more formally in Section 2.

We present several provably secure AOS schemes, oﬀering diﬀerent tradeoﬀs of ﬂexibility and eﬃciency. Our ﬁrst construction shows a generic approach to building AOS schemes from any standard digital signature scheme SIG using certiﬁcate chains. The construction works as follows: The secret and public keys for the AOS scheme are obtained by running the key generator for SIG. For any message M = M1 M2 · · · Mn, each Mi being a symbol in some predetermined message space, the AOS signature of M is deﬁned as a sequence of n public keys pk1, pk2, · · ·, pkn (generated using the key generator for SIG) and a sequence of n certiﬁcates binding the message symbols to these public keys. The ith certiﬁcate in the chain binds the message symbol Mi to the corresponding public key pki and is signed using the secret key, ski−1, corresponding to pki−1. The secret key, sk0, of the AOS scheme signs the ﬁrst certiﬁcate in the chain while the secret key skn (corresponding to the last public key), is revealed as part of the AOS signature and is used for appending new symbols to M. We observe that if the message space is small enough, we can make use of “weaker”, and more eﬃcient, signature schemes without compromising the security of the resulting AOS scheme. Furthermore, using aggregation techniques[BGLS03, LMRS04], the size of the certiﬁcate chain can be made a constant, that is, independent of the number of message symbols appended, which leads to shorter AOS signatures than those in the basic scheme. (See Section 3 for more details on this scheme.) Since signature schemes exist given the existence of one-way functions [Rom90], the above construction implies the existence of AOS under the same assumption. We also present a more eﬃcient construction of AOS for applications in which the message space is constant size and the total number of append operations performed is also constant. This construction is based on a stronger assumption and makes use of pseudorandom generators and collision-resistant hash functions (CRHFs). We remark that both these schemes—one using CRHFs and one based on certiﬁcate chains—are in the standard model; neither of them makes use of random oracles.

Relation to Hierarchical Identity-Based Signatures. Identity-Based Signature (IBS) schemes, due to Shamir [Sha85], are signature schemes in which the identity of the signer (for example, her email address) plays the role of his public key. Such schemes assume the existence of a trusted authority that holds a master public-private key pair that is used to assign secret keys to users based on their identities. Anyone can verify signatures on messages signed by a user knowing only the master public key and the identity of that user. Hierarchical IBS (HIBS) schemes, proposed by Gentry and Silverberg [GS02], are a natural generalization of this concept to a setting in which users are arranged in a hierarchy and a user at any level in this hierarchy can delegate secret keys to her descendants based on their identities and her own secret key. To verify the signature created by any user, one needs to know the identity of the user (and her position in the hierarchy) and the public key of the root user.

HIBS can be implemented using certiﬁcate chains (as suggested in [GS02]) and the resulting construction bears a strong resemblance to the certiﬁcate-based construction of AOS we give in this paper. Upon closer examination, we ﬁnd that the similarity between the two constructions is not accidental: it is an artifact of the close relationship between the two primitives themselves—AOS and HIBS are, in fact, tightly equivalent. This means that (a) there exist generic transformations from any HIBS scheme into a corresponding AOS scheme and, likewise, from any AOS scheme into a corresponding HIBS scheme; and (b) these transformations are extremely eﬃcient (the derived scheme is as eﬃcient as the scheme being derived from) and highly security-preserving (an adversary attacking the derived scheme can be transformed into an adversary attacking the original one, losing only a constant factor in eﬃciency and query complexity).

A beneﬁt of this equivalence is that it considerably simpliﬁes the notion of HIBS and makes security analysis for HIBS schemes less onerous: AOS is simpler than HIBS, and, for any HIBS scheme, it is typically easy to ﬁnd an equivalent AOS scheme whose security properties carry over to the corresponding HIBS scheme. For example, our security proof for certiﬁcate-based AOS translates to a security proof for certiﬁcate-based HIBS (originally proposed in [GS02]).

Although this construction of HIBS was known prior to our work, it was never analyzed in the literature, and, to the best of our knowledge, we give the ﬁrst proof of security for it. Furthermore, our construction of AOS based on pseudorandom generators and CRHFs yields a novel approach to designing HIBS and can be useful for some restricted scenarios (for example, in a constant-depth hierarchy wherein each user signs messages from a constant-size message space).

We remark that both these constructions yield HIBS schemes in the standard model and neither involves the use of computationally intensive bilinear maps (this is in contrast with some recent results on HIBS [CHYC04]). Finally, we believe that AOS is a more intuitive primitive to study because it clearly reﬂects the requirements of our problem domains (such as secure routing) and is better suited for analyzing the problems that motivate our work.

Related Work. Append-only signatures belong to a general class of primitives called algebraic signatures. Informally, an algebraic signature scheme allows the creation of signatures on a new message M using the signatures on some known messages, M1, M2,..., Mn, and the public key, provided the new message can be obtained from the known messages using some prespeciﬁed set of (n-ary) operations, say O = {f1, f2, · · ·, fm }. That is, given the signatures, sig[M1 ],..., sig[Mn ] and the public key, it is easy to compute sig[fi (M1,..., Mn )] for any fi ∈ O. In our setting, each fi has arity 1 and appends some ﬁxed message symbol Mi to an input message M. Security for algebraic signatures is deﬁned in a manner similar to our approach to security of AOS (that is, it should be hard to forge signatures of messages that cannot be obtained by applying the operations in O to already-signed messages). Examples of algebraic signatures studied in the literature include transitive signatures by Micali and Rivest [MR02], homomorphic signatures by Johnson, Molnar, Song and Wagner [JMSW02], and graph-based algebraic signatures by Hevia and Micciancio [HM02].

Although no obvious relation exists between our primitive and any of the previously studied algebraic signature primitives, we do note that some of the techniques we use in our constructions parallel prior techniques. For example, our construction of AOS schemes using CRHFs can be viewed as a special instance of graph-based algebraic signature schemes studied in [HM02] (although the set of update operations considered there are diﬀerent from the append operation that we consider). Also, [JMSW02] introduces the notion of redactable signatures—signatures that allow “deletion” of message symbols without access to the secret key—and one of the constructions for this primitive given in their paper is also an example of graph-based algebraic signatures.

A concept closely related to AOS (and algebraic signatures, in general) is that of incremental signatures, proposed by Bellare, Goldreich, and Goldwasser [BGG94, BGG95]. Given an incremental signature on a message M, it is possible to compute the signature on a slightly updated version of M in time proportional to the “amount” of change made to M (rather than on the length of the entire message). The update operation, however, requires access to the initial signer’s secret key whereas, in the case of AOS, a message can be updated by any party. Moreover, the update operations considered in [BGG94, BGG95] are replace, insert and delete whereas we are interested in performing append operations on messages.

Application to Secure Routing. In our discussion of applications of AOS, which we expand upon in Section 5, our main focus is on the problem of wide-area Internet routing security. We argue that the existence of secure AOS schemes is a suﬃcient condition for guaranteeing an important security property of routing protocols, namely, authenticity of route announcements.

Though routing is an important component of modern communication networks, its security has received little attention from the cryptography community (although a rich literature exists in the computer networks community [KLS00, SRS+ 04, HPS04, WKvO05]). Most cryptographic protocols assume that the network is an untrusted black box possibly under full control of the adversary; while this is useful when modeling the security of end-to-end protocols, it fails to capture the security of the underlying routing protocols. We are motivated by this apparent gap, as routing is not just an application in which cryptography is required, but a necessary component of the networks used by most cryptographic protocols.