FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |

«Eike Kiltz∗ Anton Mityagin† Saurabh Panjwani‡ Barath Raghavan§ April 30, 2005 Abstract We present a new primitive—Append-only Signatures ...»

-- [ Page 1 ] --

Append-Only Signatures

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

April 30, 2005


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 define the security of

AOS, present concrete AOS schemes, and prove their security under standard assumptions.

In addition, we find that despite its simple definition, AOS is equivalent to Hierarchical Identity-based Signatures (HIBS) through efficient 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, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect 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 Efficient AOS Constructions 5

3.1 Certificate-Based Append-Only Signatures...................... 5

3.2 Shorter Signatures via Aggregation..........

–  –  –

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 flow 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 verifiable based only on the identity of the first 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 verifier of the final 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 define 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 define the security of AOS more formally in Section 2.

We present several provably secure AOS schemes, offering different tradeoffs of flexibility and efficiency. Our first construction shows a generic approach to building AOS schemes from any standard digital signature scheme SIG using certificate 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 defined as a sequence of n public keys pk1, pk2, · · ·, pkn (generated using the key generator for SIG) and a sequence of n certificates binding the message symbols to these public keys. The ith certificate 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 first certificate 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 efficient, signature schemes without compromising the security of the resulting AOS scheme. Furthermore, using aggregation techniques[BGLS03, LMRS04], the size of the certificate 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 efficient 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 certificate 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 certificate chains (as suggested in [GS02]) and the resulting construction bears a strong resemblance to the certificate-based construction of AOS we give in this paper. Upon closer examination, we find 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 efficient (the derived scheme is as efficient 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 efficiency and query complexity).

A benefit of this equivalence is that it considerably simplifies 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 find an equivalent AOS scheme whose security properties carry over to the corresponding HIBS scheme. For example, our security proof for certificate-based AOS translates to a security proof for certificate-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 first 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 reflects 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 prespecified 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 fixed message symbol Mi to an input message M. Security for algebraic signatures is defined 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 different 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 sufficient 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.

Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |

Similar works:

«16/01/2012 Allgemeine Einkaufsbedingungen NMC sa 1. Geltung Für sämtliche Bestellungen für Ware und/oder Ausführung von Dienstleistungen gelten nur die vorliegenden allgemeinen Einkaufsbedingungen, insofern nicht ausdrücklich etwas anderes schriftlich vereinbart ist. Inhaltlich abweichende Verkaufsbedingungen des Lieferanten werden auch dann nicht Vertragsgrundlage, wenn NMC diesen im Einzelfall nicht ausdrücklich widerspricht. Nimmt NMC die Lieferung/Leistung ohne ausdrücklichen...»

«Published February 1, 2003. Distribution restricted to Sponsors until May 1, 2003. Auto-ID on the Line: The Value of Auto-ID Technology in Manufacturing Gavin Chappell, Lyle Ginsburg, Paul Schmidt, Jeff Smith, Joseph Tobolski auto-id center massachusetts institute of technology, 77 massachusetts avenue, bldg 3-449, cambridge, ma 02139-4307, usa Auto-ID Technologies Bring Sweet Success to Candy Maker potentially contaminated and that the Little did Choc-o-lot realize what a CHICAGO – What...»

«Dossier zur Nutzenbewertung – Modul 3A Stand: 16.09.2011 Vergleichstherapie, Patienten mit therap. bedeutsamem Zusatznutzen, Kosten, qualitätsgesicherte Anwendung Dokumentvorlage, Version vom 20.01.2011 Dossier zur Nutzenbewertung gemäß § 35a SGB V Cabazitaxel (Jevtana®) Sanofi-Aventis Modul 3 A mHR Prostatakarzinom Zweckmäßige Vergleichstherapie, Anzahl der Patienten mit therapeutisch bedeutsamem Zusatznutzen, Kosten der Therapie für die GKV, Anforderungen an eine...»

«Lations СПРАВОЧНИК Микротезаурусы подокументирова нию нарушенийправч еловека Judith Dueck Manuel Guzman Bert Verstappen ВЫРАЖЕНИЕ БЛАГОДАРНОСТИ Опубликовано и распространяется: HURIDOCS Advice and Support Unit/Secretariat 48 chemin du Grand-Montfleury CH-1290 Versoix Switzerland Tel. 41.22.755 5252, fax 41.22.755 5260 E-mail: huridocs@comlink.org Website: http://www.huridocs.org/...»

«PROTOCOL OF AMENDMENT TO THE INTERNATIONAL CONVENTION ON THE SIMPLIFICATION AND HARMONIZATION OF CUSTOMS PROCEDURES OF 18 MAY 1973 (Brussels, 26 June 1999) The Contracting Parties to the International Convention on the Simplification and Harmonization of Customs Procedures (done at Kyoto on 18 May 1973 and entered into force on 25 September 1974), hereinafter the Convention, established under the auspices of the Customs Co-operation Council, hereinafter the Council, CONSIDERING that to achieve...»

«Current Science and Ellen White: 12 Controversial Statements1 Jerry Moon, 2007 Certain statements by Ellen White seem to conflict with current understandings in the natural sciences. It is well known that some of her statements contradicted scientific thinking at the time she wrote, but have since received broad scientific support, such as her denunciation of tobacco as a poison (4SG 128 [1864]), and her recommendation of a balanced, varied vegetarian diet as preferable to a diet including...»

«MLA Examples MLA EXAMPLES The examples below will help you properly format your citations for the Works Cited page of your paper. MLA requires that you include certain fields of information for each type of source that you cited in your research paper. Click here to see an example of a research paper with a works cited list. Click on the type of source you are trying to cite. Abstracts, Indexes Films and Video Recordings Oral Presentations Annuals, Almanacs, Foreword Pamphlets Yearbooks...»

«Masaryk University Faculty of Arts Department of English and American Studies English Language and Literature Bc. Katarína Urbančíková Breaking Convention: Gaskell’s Unruly Heroines Master’s Diploma Thesis Supervisor: Bonita Rhoads I declare that I have worked on this thesis independently, using only the primary and secondary sources listed in the bibliography... Author’s signature I would like to thank my supervisor Bonita Rhoads for guiding me through the process of writing this...»

«SPECIAL DISCOUNT OFFERS FOR TRAVEL AGENTS NOVEMBER 1, 2013 – JANUARY 31, 2014 Aliante Casino + Hotel + Spa Offer/ Rate: $45 midweek/ $85 weekend (+$9.99 daily resort fee) Reservations: By phone: Call (877) 477-7627 and mention code: TRAVEL By internet: www.aliantegaming.com enter code: TRAVEL Agents must provide IATA # at time of booking. Inclusions: In-Room High Speed Internet, Local & Domestic Long Distance Calls, Coffee & Tea Service in the Hotel Lobby from 6am-10am, Daily Newspaper,...»

«Claudio Magris Das Alphabet der Welt Von Büchern und Menschen Übersetzt aus dem Italienischen von Ragni Maria Gschwend ISBN: 978-3-446-23759-9 Weitere Informationen oder Bestellungen unter http://www.hanser-literaturverlage.de/978-3-446-23759-9 sowie im Buchhandel. © Carl Hanser Verlag, München Bücher meines Lebens Für die Griechen wurde die Welt von einem Strom umflossen, dem Ozean. Für mich ist dieser Strom, der die Erde umschließt, der Ganges, mit dessen gewaltigem Fließen Die...»

«ISWS CR Loan Copy Illinois State Water Survey Division GROUND-WATER SECTION SWS Contract Report 473 REGIONAL ASSESSMENT OF NORTHERN ILLINOIS GROUND-WATER RESOURCES by John S. Nealon, James R. Kirk, and Adrian P. Visocky Prepared for the Illinois Department of Energy and Natural Resources Champaign, Illinois October 1989 Illinois Department of Energy and Natural Resources ISWS Nealon, J. S. CR REGIONAL ASSESSMENT OF 473 NORTHERN ILLINOIS Loan Copy GROUND-WATER RESOURCES w473 DEMCO REGIONAL...»

«Code of Conduct for the Protection of Children from Sexual Exploitation in Travel and Tourism Background and Implementation Examples Steering Committee on the Code of Conduct World Tourism Organization, ECPAT International, Interpol, International Hotel and Restaurants Association, Tourism Authority of Thailand, EMBRATUR, Tour Operators’ Initiative for Sustainable Tourism Development, Federation of International Youth Travel Organizations, Japan Committee for UNICEF Produced by the Steering...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.