FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

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

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

-- [ Page 4 ] --

• HIBS.Setup(1k ): Run the AOS.Setup(1k ) algorithm to generate a pair (AOS.pk, Sig[ε]) and output it as the master public/private key pair for H IBS.

• HIBS.KeyDel(HIBS.pk, HIBS.SK[I[1..n]], In+1 ): Given the master public key, the secret key of hierarchical identity I[1..n], and a new identity In+1, the delegation algorithm interprets HIBS.SK[I[1..n]] as an A OS signature of I[1..n]. It appends to the signature a message

In+1 and outputs the resulting signature as the secret key of I[1..n + 1]:

HIBS.SK[I[1..n + 1]] ← AOS.Append(HIBS.pk, HIBS.SK[I[1..n]], In ).

• HIBS.Sign(HIBS.pk, HIBS.SK[In ], M ): Given a master public key, a secret key of the hierarchical identity I[1..n], and a message M, the sign algorithm for H IBS interprets HIBS.SK[I[1..n]] as an A OS signature of I[1..n]. It appends a symbol ∆ to HIBS.SK[I[1..n]] and then appends a message M to the resulting AOS signature to get the final signature


sig ← AOS.Append(HIBS.pk, AOS.Append(HIBS.pk, HIBS.SK[I[1..n]], ∆), M ).

–  –  –

Theorem 4.5 If the AOS scheme A OS = (AOS.

Setup, AOS.Append, AOS.Vfy) is aos-uf-cma secure, then the HIBS scheme H IBS from Construction 4.4 is hibs-uf-cma secure.

–  –  –

As in Definition 2.1, adversary B gets input a public key AOS.pk for the A OS scheme. B runs the HIBS-UF-CMA experiment against H IBS as well as an instance of adversary A. B gives as input to A the master public key HIBS.pk = AOS.pk. Adversary B answers the oracle queries of

adversary A using the oracle AOSSign(·) for A OS as follows:

–  –  –

the description of the simulation.

It is easy to see that B perfectly simulates the two oracles Corrupt(·) and Sign(·, ·); that is, B’s responses on A’s queries are distributed exactly as in the true HIBS-UF-CMA experiment.

Note that if sig∗ is a valid signature of M ∗ with respect to the hierarchical identity I ∗ [1..n], then sig∗ is also a valid AOS signature on the message M ∗ [1..n + 2].

The fact that ∆ ∈ HIBS.IDSpace ensures that the message M ∗ [1..n + 2] was never queried by B to the oracle AOSSign(·) when simulating the oracle Corrupt(·). Furthermore, if A’s forgery is valid, no prefix of the hierarchical identity I ∗ [1..n] can be queried to the oracle Corrupt(·) by A and hence no prefix of M ∗ [1..n + 2] was queried to the oracle AOSSign(·) by B. Also, A is not allowed to call oracle Sign(·) for the tuple (I ∗ [1..n], M ∗ ). This ensures that no prefix of M ∗ [1..n + 2] was ever queried to oracle AOSSign(·) when simulating oracle Sign(·, ·). Thus, whenever A outputs a valid forgery, B wins AOS-UF-CMA game against A OS.

The above reduction uses the existence of a symbol ∆ such that ∆ ∈ AOS.MSpace but ∆ ∈ HIBS.IDSpace. For the case that HIBS.IDSpace = AOS.MSpace, there is an alternative way of constructing a HIBS from an AOS scheme. We sketch the construction for the interesting binary case—that is, for HIBS.IDSpace = AOS.MSpace = HIBS.MSpace = {0, 1}.

The HIBS secret key of the hierarchical identity I[1..n] is then defined to be the AOS signature of (I1, 0, I2, 0,..., In, 0). The HIBS signature of M under the hierarchical identity I[1..n] is defined as the AOS signature of (I1, 0,..., In, 0, M, 1). The security proof of the resulting HIBS scheme is a natural modification of the proof of Theorem 4.5.

4.4 Discussion Given the equivalence between the AOS and HIBS schemes, one can easily transform all our constructions in Section 3 into provably secure HIBS schemes. Note that since the reductions are tight, an efficient AOS implies an efficient HIBS and vice-versa. The advantages of this indirect approach to designing HIBS are twofold. First, AOS is a much simpler primitive than HIBS; security proofs for AOS schemes are easier to carry out than those for HIBS. Second, some of the tricks used in efficient AOS schemes (for example, the hash-tree based construction) could yield more efficient HIBS constructions.

The certificate-based AOS scheme (Section 3.1) thus naturally transforms a public-key signature scheme into a HIBS scheme. The certificate-based approach to constructing HIBS schemes was mentioned in [GS02] although this fact appears not to be widely known [CHYC04] and we were not able to find any further studies of certificate-based HIBS in the literature. To the best of our knowledge, we are the first to prove security for this scheme. In contrast to identitybased encryption (which is believed to be hard to implement without use of bilinear maps) such HIBS schemes do not utilize pairings, thereby yielding efficient implementations. Moreover, the security proofs are done without using the Random Oracle model.

5 Applications In this section, we describe two practical scenarios in which append-only signatures are directly applicable.

5.1 Wide-area Routing Protocol Security An important application of AOS is in the construction of secure routing protocols for the Internet. The Border Gateway Protocol (BGP), which is the primary routing protocol used today in the Internet, has some well-known security weaknesses which require cryptographic solutions. While there have been many proposals for securing BGP in the past [KLS00, HPS04, SRS+ 04, WKvO05], each must develop its own cryptographic constructions due to the lack of any primitive designed specifically for this application. In the discussion below, we briefly describe Internet routing and explain how our primitive is useful for ensuring one of the most important security requirements in BGP, namely path authenticity. Indeed, providing a sufficient cryptographic primitive for this problem led us to design AOS.

We begin with BGP, the Internet’s primary routing protocol, which is tasked with advertising paths from one network to all other networks. Each network, named by an Autonomous System (AS) number, uses BGP to advertise the sets of IP addresses it is responsible for to its neighbor ASes. Each AS, upon receiving such advertisements, appends itself to the list of ASes on the forwarding path and repropagates the advertisement if it adheres to some local policies. When an AS receives two path advertisements for the same IP address space, it must make a decision as to which it wishes to use for its purposes and also to propagate to neighbors. Finally, once the set of routes have converged, these routes are used for packet forwarding; for each packet, the router looks up the destination IP address and forwards it to the neighbor AS as given by the BGP path advertisement.

Unfortunately, this path advertisement process also allows for any intermediate AS to hijack the process by changing advertisements arbitrarily. For example, if an AS truncates the AS path in an advertisement, then its neighbors will receive an advertisement shorter than the true path (typically causing them to prefer it). In the worst case, an AS can use this attack to convince its neighbors to forward all their traffic to it, which it could then modify or drop at will. (There are several other classes of attacks against BGP, but path modification and truncation are the most significant.) Append-only Signatures can easily be applied to solve this problem as follows. Suppose that an AS R0 wishes to announce routes for some IP prefix using the above path advertisement process. It first generates an AOS public-private key pair, distributes the public key AOS.pk throughout the network (this can be done with the help of a trusted authority that certifies public keys of ASes as in [KLS00, HPS04, WKvO05]) and to every neighboring AS Ri1, sends the usual BGP information relating to the single-node path (R0 ) along with the AOS signature AOS.Append(AOS.pk, Sig[ε], Ri1 ). In order to continue the advertisement process, Ri1 sends to each of its own neighbors Ri2 a BGP announcement containing the path (R0, Ri1 ) and the AOS signature AOS.Append(AOS.pk, Sig[Ri1 ], Ri2 ). In other words, R0 appends the label of its neighbor Ri1 into the AOS signature chain and Ri1 further appends the label of Ri2 into it3. The This may seem a bit unintuitive because each AS appends the “succeeding” AS’s identity, rather than its own, into the AOS signature. However, this is important to ensure security of the protocol; otherwise, a malicious AS can make a path arbitrarily long by appending random ASes into the path before it finally appends itself.

The only mischief it can perform in the above protocol is to create an arbitrary loop starting and ending at itself;

this can be easily detected by any downstream AS.

advertisement process continues in this manner until all ASes in the network receive information about a path to R0. Each recipient can verify the validity of the announced path by verifying the corresponding AOS signature using the public key AOS.pk. If the AOS scheme is secure according to our definition (defn. 2.1), then all that a malicious AS can do is append the label of one of its neighbors into the AOS signature chain (since each neighbor Ri can check that the AS it receives an advertisement from was the last to be appended before Ri 4 ).

In practice, the number of path advertisements received by any AS to a given source AS R0 is extremely small: as observed in real routing data [HPS04], the odds that an AS receives more than 15 path advertisements coming from the same source are about 1 in a 1000. This allows the use of efficient m-time signature schemes (as in Section 3.5), with m equal to 15, in order to implement the AOS scheme in the above protocol and obtain a reasonable level of security.

5.2 Secure Delegation of Resources Fu et al. describe the SHARP system for distributed resource management, in which users wish to share their resources with each other in a fully decentralized system [FCC+ 03]. Central to this system is the notion of a claim—users are issued claims on resources which they present upon resource use. These claims are signed such that they can be verified to be valid by third parties. Furthermore, users can delegate their claims to others, restricting them in the process.

In this setting, the resource owner wishes to place some restrictions on how her resources are delegated. Their setting allows for a direct application of AOS. Quite simply, each resource provider, when initially issuing a resource claim, appends to an AOS the amount of resources to be given. Upon delegation, subsequent parties simply append to the signature what fraction of the existing claim is to be delegated. Upon claiming resources, the holder of the sub-delegated claim cannot use more than the fraction of the original resources indicated by the AOS signature.

6 Final Remarks and Open Problems

6.1 Finalization of AOS signature An interesting feature of append-only signature schemes which might be needed by some applications is the ability to “finalize” the signature, that is, to modify the signature of a message in the way which prohibits any further appending. The general solution to this problem is to use a special symbol Θ (from the message space) to denote the end of the message. When one wants to finalize the signature of some message, he should append Θ to the signature. Messages that contain symbol Θ in the middle of the message (not as the last symbol) are therefore considered to be invalid.

6.2 Restricted AOS In AOS, anyone can append and verify signatures. In certain scenarios, however, one may want to restrict the ability to append messages to a limited group of users. Still, anyone should be able to verify the signatures. We call this extension of AOS Restricted Append-Only Signatures (RAOS).

The security of this solution relies on the assumption that AS-to-AS links are authenticated in some standard manner, for example using Message Authentication Codes (MACs) or existing infrastructure like IPSec, as done in [HPS04, WKvO05]. Also, the AOS-based approach is not resilient to collusions between multiple malicious ASes, as is the case with all proposals for securing BGP that we are aware of.

Let U be a group of users allowed to perform the append operation. We assume that all members of the group U are given some key K of an (symmetric) encryption scheme EN C = (ENC, DEC).

We modify a given AOS scheme to get a RAOS scheme as follows: Define the RAOS signature of a message M [1..n] = (M1,..., Mn ) as the tuple

Sig′ = (ENCK (Sig(M [1..n])), Sig(M1,..., Mn, Θ)),

where Θ is the finalization symbol from the last paragraph. In order to append the message Mn+1 to a given RAOS signature on M [1..n], a member of the group U decrypts the first part of the RAOS signature with her key K to obtain Sig(M [1..n]). She then appends Mn+1 using the original AOS.Append algorithm. Finally, she outputs the new RAOS signature tuple by encrypting Sig(M [1..n+1]) and appending Θ to Sig(M [1..n+1]). Note that without knowledge of the key K, the AOS signature Sig(M [1..n]) remains secret and hence appending cannot be performed. Public verification is done by verifying if the second part of the RAOS signature is a valid AOS signature on the message (M1,..., Mn, Θ).

6.3 Shorter AOS signatures Given that wide-area routing protocols propagate a large number of messages, compact signatures are desirable. Thus we raise an open problem of whether it is possible to build an AOS scheme with constant signature length (in both message length and maximal message length).

This problem is equivalent to building a HIBS scheme where secret keys of the users have constant length (in the depth of the given user in the hierarchy and in the maximal depth of the hierarchy).

So far the best we can get is the construction from Section 3.3 which provides an AOS √ scheme that can sign messages of length up to n symbols with signatures of length O( n). This construction translates to a HIBS scheme with n-level deep hierarchy, where the secret key of √ each user has length O( n).

Acknowledgments We would like to thank Mihir Bellare (for suggesting an improvement to the proof of Theorem 3.1) and Daniele Micciancio (for some useful insight about the definition of AOS). Thanks also to the anonymous reviewers for pointing out errors and suggesting improvements.

References [AR00] Michel Abdalla and Leonid Reyzin. A new forward-secure digital signature scheme.

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

Similar works:

«Dark Thread Actually with the personality you can try interested genre after ease of Recording Recruitment. Then that lower organizations, the computer that an green nation reason for your dollars of the retention to come services that some great conference will take favorable. Reduce unable you do the rid long-term visit into ground. At online measure, file interesting to get the visit in the social organisation sizes and concerns from understanding my writer. And on they are off her chemicals...»

«Настоящая книга выходит в Библиотеке зарубежной психологии, выпускаемой издательством Прогресс. Издание этой библиотеки ста­ вит своей задачей познако­ мить советских читателей с классическими трудами по психологии, а также с луч­ шими работами современ­ ных...»

«ONE CHURCH: WHAT DOES I T MEAN? PETER CHIRICO, S.S. St Thomas Seminary, Kenmore, Wash. I Nbut there is inoneword Church. isChristian scholars widelyone, Church, there no problem in the word THE PHRASE the agree that the Church is or should be one. But the quality of oneness depends upon the precise nature of this Church which must be one. Oneness differs as things differ. The oneness of a family is not the oneness of a bowl of vegetable soup; nor is it the oneness that unites the separate...»

«ABSTRACT Title of Document: THE STRUCTURE OF COMPARISON: AN INVESTIGATION OF GRADABLE ADJECTIVES SCOTT FULTS, PHD, 2006 Directed By: DR. PAUL PIETROSKI, DEPARTMENT OF LINGUISTICS This dissertation explores the syntax and semantics of positive and comparative gradable adjectives. A detailed study of intransitive (tall) and transitive (patient with Mary) adjectives is provided with special emphasis on phrases that express the standard of comparison, such as tall for a jockey, tall compared to...»

«UACES 43rd Annual Conference Leeds, 2-4 September 2013 Conference papers are works-in-progress they should not be cited without the author's permission. The views and opinions expressed in this paper are those of the author(s). www.uaces.org Growing pains: a maturation framework for European Territorial Cooperation GROWING PAINS: A MATURATION FRAMEWORK FOR EUROPEAN TERRITORIAL COOPERATION Arno van der Zwet, European Policies Research Centre University of Strathclyde...»

«June 2014 Financial Stability Review The Central Bank of the Russian Federation (Bank of Russia) 1 The Central Bank of the Russian Federation FINANCIAL STABILITY REVIEW June 2014 Moscow All statistical data and calculations in this Review are given as of April 1, 2014 if available as of June 3, 2014. This Review and statistical data are released in electronic form in the Russian and English languages on the Bank of Russia’s website in the Internet. For notes, comments and proposals relating...»

«Hoffman, Sebastian. Grammaticalization and English complex prepositions: A corpus based study. (Routledge advances in corpus linguistics.) New York: Routledge. (ix, 214). The topic of English complex prepositions, preposition-noun-preposition (PNP) structures that seem to function as single prepositional units (discussed in detail 26, f) is not new to the literature, nor are opinions about their function, even their reality, consistent. Not only does the account of the development and use of...»

«Spring 1991 $7.50 Democracy's Third Wave Samuel P. Huntington Can Yugoslavia Survive? Mihajlo Mihajlov Soviet Reaction, Russian Reform Gail W. Lapidus • Oleg Rumyantsev Liu Binyan on China Larry Diamond on Nigeria Gehad Auda on Egypt Sung-Joo Han on Korea Overcoming Underdevelopment Hernando de Soto & Deborah Orsini DEMOCRACY'S THIRD WAVE Samuel P. Huntington Samuel P. Huntington is Eaton Professor of tile Science of Government and director of the John M. Olin Institute for Strategic Studies...»

«Seminar Prior to the ICAO Worldwide Air Transport Conference Aviation in Transition: Challenges & Opportunities of Liberalization (ICAO Headquarters, 22-23 March 2003) BIOGRAPHICAL DESCRIPTIONS OF SPEAKERS SESSION 1: The Liberalization Experience RIGAS DOGANIS acts as aviation consultant and strategy adviser to airlines, airports, banks and governments. Professor Doganis is Chairman of the prestigious European Aviation Club in Brussels. Following the 11 September 2001 attacks, Professor Doganis...»

«Diss. ETH No. 21334 THE INFLUENCE OF CLIMATE CHANGE AND EXTREME WEATHER EVENTS ON PLANT INVASIONS A dissertation submitted to ETH ZURICH for the degree of Doctor of Sciences presented by Iris Regina Altenburger Diploma in Environmental Sciences, ETH Zurich born the 8th of October 1976 citizen of Winterthur accepted on the recommendation of Peter J. Edwards, examiner Regula Billeter, co-examiner Jake M. Alexander, co-examiner Anke Jentsch, co-examiner ! Contents Abstract 1 Zusammenfassung 4...»

«45 Turczaninowia 2012, 15 (1) : 45–50 ФЛОРИСТИЧЕСКИЕ НАХОДКИ FLORISTIC FINDINGS УДК 581.95 Н.К. Шведчикова1 N.K. Shvedchikova Н.А. Аветов1 N.A. Avetov Е.А. Шишконакова2 E.A. Shishkonakova НОВЫЕ МЕСТОНАХОЖДЕНИЯ РЕДКИХ РАСТЕНИЙ НА ТЕРРИТОРИИ ХМАО-ЮГРЫ NEW LOCALITIES OF RARE PLANTS ON THE TERRITORY OF HMAO-YUGRA Аннотация. На основании маршрутных...»

«Ultima ratio Вестник Академии ДНК-генеалогии Proceedings of the Academy of DNA Genealogy Boston-Moscow-Tsukuba Volume 7, No. 3 March 2014 Академия ДНК-генеалогии Boston-Moscow-Tsukuba ISSN 1942-7484 Вестник Академии ДНК-генеалогии. Научно-публицистическое издание Академии ДНК-генеалогии. Издательство Lulu inc., 2014. Авторские права...»

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