FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

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

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

-- [ Page 1 ] --

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


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

–  –  –

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:

«Эверсманния. Энтомологические исследования Eversmannia в России и соседних регионах. Вып. 15-16. 5. XII. 2008: 17 43 No. 15-16. 2008 А.В. Соловьев г. Ульяновск, Ульяновский государственный педагогический университет Слизневидки (Lepidoptera: Limacodidae) России A.V. Solovyev. The limacodid moths (Lepidoptera: Limacodidae) of Russia. SUMMARY....»

«Arch. Tierz., Dummerstorf 44 (2001) 4, 435-440 Institute of Animal Breeding and Genetics, Juslus Liebig University, Giessen, Germany CHRISTINA WEIMANN, BIRGIT LEYHE-HORN, MATTHIAS GAULY and GEORG ERHARDT Suitability of microsatellites BM1329 and OarAElOl as markers for the introgression of the FecB locus into different sheep breeds Dedicated to Prof. Dr. Dr. h. c.mult. Horst Kräußlich on the occasion ofhis 75lh birthday Summary Litter size in sheep can be improved by introgression of the...»

«Spektro-Mikroskopie mit niederenergetischen Elektronen und Photoelektronen (LEEM / PEEM) Abstract / Zusammenfassung Mit einem “Low Energy Electron Microscope” (LEEM) bzw. “Photoemission Electron Microscope” (PEEM) lassen sich Oberflächen von Festkörpern mit sehr hoher Ortsauflösung (bis zu 2 nm) untersuchen. Insbesondere können kinetische Prozesse wie z.B. Schichtoder Kristallwachstum in situ während des Wachstumsprozesses in Echtzeit beobachtet werden. Es stehen verschiedene...»

«The Senate Community Affairs References Committee The Hidden Toll: Suicide in Australia June 2010 © Commonwealth of Australia 2010 ISBN 978-1-74229-209-0 Senate Community Affairs Committee Secretariat: Ms Naomi Bleeser (Secretary) Mr Hamish Hansford (Secretary) Mr Owen Griffiths (Principal Research Officer) Ms Leonie Peake (Research Officer) Ms Lauren Burke (Research Officer) Ms Sophia Fernandes (Executive Assistant) Ms Victoria Robinson-Conlon (Executive Assistant) The Senate Parliament House...»

«Survey of Conflicts & Resolution in India’s Northeast ? Ajai Sahni? India’s Northeast is the location of the earliest and longest lasting insurgency in the country, in Nagaland, where separatist violence commenced in 1952, as well as of a multiplicity of more recent conflicts that have proliferated, especially since the late 1970s. Every State in the region is currently affected by insurgent and terrorist violence, 1 and four of these – Assam, Manipur, Nagaland and Tripura – witness...»

«April 2016 Detailed guidance for employers Opting out: How to process ‘opt-outs’ from workers who want to leave a pension scheme Publications in the series 1 Employer duties and defining the workforce An introduction to the new employer duties Getting ready First steps to prepare for the new employer duties 3 Assessing the workforce How to identify the different categories of worker 3a Postponement 3b Transitional period for schemes with defined benefits 3c Having completed the assessment...»

«Technoparkstrasse 1 Tel.: 044 / 350 10 10 8005 Zürich Fax.: 044 / 350 10 19 INTERLIS Tools Benutzerhandbuch Zusammenfassung Diese Dokumentation beschreibt die Installation und Bedienung der Version 2014 der Produkte INTERLIS Tools, INTERLIS Tools Professional und INTERLIS Tools for SDE. Copyright © infoGrips GmbH, 2013 17.12.2013 INTERLIS Tools Benutzerhandbuch, 17.12.2013 Die Dokumentation darf nur mit Erlaubnis der infoGrips GmbH vervielfältigt werden. Seite 2 Copyright © infoGrips GmbH,...»

«Columbia College Online Campus Page |1 CISS 238 DEA Java Programming March Session 14-54 March 23 – May 16, 2015 Course Description An introduction to programming using Java. Topics include methods, classes, objects, advanced object concepts, input, selection, repetition, arrays and strings, applets, HTML, graphics, inheritance concepts, Abstract windows tool kit, file input and output. Prerequisites: CISS 170 and MATH 150 Proctored Exams: Final Textbooks Starting Out With Java: Early...»

«Evidence for necessity of data retention in the EU Table of Contents Introduction 1. Context 2. How communications data are used 3. Overview of types of cases in which data are important 4. Consequences of absence of data retention 5. Cross-border aspects of data retention 6. Statistics and quantitative data 7. Article 10 Available statistics Limitations of quantitative data Conceptual and methodological issues Qualitative data 8. Terrorism Murder and manslaughter Serious sexual offences and...»

«Global market review of automotive electric motors – forecasts to 2017 2010 edition Page i Global market review of automotive electric motors – forecasts to 2017 2010 edition By Matthew Beecham June 2010 Published by Aroq Limited Seneca House Buntsford Park Road Bromsgrove Worcestershire B60 3DX United Kingdom Tel: +44 (0)1527 573 600 Fax: +44 (0)1527 577 423 Web: www.just-auto.com Registered in England no: 4307068 © 2010 All content copyright Aroq Ltd. All rights reserved. Page ii...»

«GeoResearch Forum Vols. 1-2 (1996)pp. 221-234 O 1996 Transtec Publications, Swiizerland Upper Tithonian Ammonites and Floras from the Chicama Basin, Northern Peruvian Andes R. Enay', G. Barale2, J. Jacay3 and E. Jaillard4 ' Centre des Sciences de la Terre et URA no1, 27-43Boulevard du 11 Novembre 1918,F-69622Villeurbanne Cedex, France * Laboratoire de Paléobotanique du Mésozoique et URA no1 1, 27-43 Boulevard du 1 Novembre 1918, F-69622Villeurbanne Cedex, France Institut Francais d'Études...»

«Ernst Krenek Verzeichnis der Bühnenwerke Catalogue of Dramatic Works ernst krenek institut Ernst Krenek 1900 –1991 Verzeichnis der Bühnenwerke Catalogue of Dramatic Works ernst krenek institut Impressum Für den Inhalt verantwortlich (Hg.) Ernst Krenek Institut Privatstiftung Wissenschaftliche Betreuung Florian Schönwiese, Generalsekretär Lothar Knessl Donau-Universität Krems Dr.-Karl-Dorrek-Straße 30 Zusammenstellung und Redaktion A-3500 Krems an der Donau Marie-Therese Rudolph T +...»

<<  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.