FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

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

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

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

• 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 AOS 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 HIBS interprets HIBS.SK[I[1..n]] as an AOS 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 AOS = (AOS.

Setup, AOS.Append, AOS.Vfy) is aos-uf-cma secure, then the HIBS scheme HIBS 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 AOS scheme. B runs the HIBS-UF-CMA experiment against HIBS 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 AOS 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 AOS.

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 R i can check that the AS it receives an advertisement from was the last to be appended before R i 4 ).

In practice, the number of path advertisements received by any AS to a given source AS R 0 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 M n+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:

«Graduate Scholarship Committee Handbook A Manual of Policies and Procedures (Abridged Version) September 2015 Faculty of Graduate Studies and Research Killam Centre for Advanced Studies 2-29 Triffo Hall Revised: September 29, 2015 Contents GRADUATE SCHOLARSHIP COMMITTEE Authority Membership Responsibilities Responsibilities of the GSC Chair Responsibilities of the GSC Secretary POLICIES OF THE GRADUATE SCHOLARSHIP COMMITTEE Definitions Eligibility Concurrent Awards Employment While Holding an...»

«Brochure More information from http://www.researchandmarkets.com/reports/3132060/ Global and Chinese Pipemidic Acid Anhydrous Industry, 2010-2020 Market Research Report Description: The Global and Chinese Pipemidic Acid Anhydrous Industry, 2010-2020 Market Research Report is a professional and in-depth study on the current state of the global Pipemidic Acid Anhydrous industry with a focus on the Chinese market. The report provides key statistics on the market status of the Pipemidic Acid...»

«G7495 Notebook PC Benutzeranleitung für Windows 8® Urheberrechtinformationen Kein Teil dieses Handbuchs, einschließlich der darin beschriebenen Produkte und Software, darf ohne ausdrückliche schriftliche Genehmigung von ASUSTeK COMPUTER INC. (“ASUS”) mit jeglichen Mitteln in jeglicher Form reproduziert, übertragen, transkribiert, in Wiederaufrufsystemen gespeichert oder in jegliche Sprache übersetzt werden, abgesehen von vom Käufer als Sicherungskopie angelegter Dokumentation. ASUS...»

«Cronicas De Un Caballero Andante 1958 1999 In the achievements, Cronicas de Un Caballero Andante: 1958-1999 there are predetermined buzz SharpBrains when you reflect cut meetings for cut for asking clients and fixing to download for discounts make experienced despite the expense. Dramatically, are this fact after the payment for the condominiums for it can keep to have the offices after your today. Out, your research company enables a own construction and is the factors. The homebuyers are...»

«Case 2:05-cv-04201-ILRL-JCW Document 188 Filed 02/19/10 Page 1 of 20 UNITED STATES DISTRICT COURT EASTERN DISTRICT OF LOUISIANA U.S. ex rel GRAY CIVIL ACTION VERSUS NO: 05-4201 LOCKHEED MARTIN CORPORATION SECTION: B(2) ORDER AND REASONS Before the Court is Defendant’s Motion for Partial Summary Judgment as to all False Claims Act Qui Tam Causes of Action (Count I) asserted by Relator Jeffrey Gray (Rec. Doc. No. 126). The Motion is opposed. A reply brief has also been filed (Rec. Doc. No....»

«Martin-Ch05 7/20/07 2:28 PM Page 59 5 Statistical power Conor V. Dolan and Stèphanie M. van den Berg A primary concern in any study designed to detect and estimate genetic and environmental contributions to the variance of (complex) phenotypes is the probability of detecting a hypothesized effect, given that it is present. This probability is usually referred to as statistical power (e.g. Cohen, 1992; Kraemer, 1985). If this probability is low, one should be reticent to embark on the study....»

«Chamber of Mines News Briefs – November 17 18, 2015 [Note: News headlines are hyperlinked to their stories in this document.] Federal News Now for the hard part: The road ahead for eight cabinet ministers Nunavut News Nunavut Arctic College sees fewer grads in 2014, but high satisfaction, employability Exploration up 28 per cent Medevac companies unveil new look Resource Development and Energy News New Microdiamond data supports increased diamond content at CH-7 and the the potential to add...»

«WORKING PAPER The Changing Relationship between Education and Marriage in the United States, 1940–2000 BERNA M. TORR WR-530 October 2007 This product is part of the RAND Labor and Population working This paper series made possible by the NIA funded RAND Center for the Study paper series. RAND working papers of Aging (P30AG012815) and the NICHD funded RAND Population Research are intended to share researchers’ Center (R24HD050906). latest findings and to solicit informal peer review. They...»

«Modulhandbuch für den Bachelor-Studiengang Pflegeentwicklung und Management Stand: 18.08.2011 Mitarbeit: Prof. Dr. Susanne Busch, Prof. Dr. Knut Dahlgaard, Prof. Dr. Uta Gaidys, Prof. Dr. Martina Hasseler, Prof. Dr. Änne-Dörte Jahncke-Latteck, Vertr. Prof. Dr. Corinna Petersen-Ewert, Prof. Dr. Wolfgang Schütte, Prof. Dr. Peter Stratmeyer, Prof. Petra Weber, Dipl.-Pflegewirt Kay Winkler-Budwasch Redaktion: Dipl.-Pflegewirt Kay Winkler-Budwasch Inhaltsverzeichnis Das Studiengangskonzept im...»

«8, Khabarovskaya Str., Vladivostok Russia, 690002, Tel.: +7 (4232) 45-75-59 Fax.: +7 (4232) 44-60-13 E-mail: office@inmarlegal.com URL: www.inmarlegal.com LAY TIME By A. Deinega www.inmarlegal.com www.inmarlegal.com TABLE OF CONTENTS 1. Notion and regulation of lay time 2. Beginning of calculation of the lay time 3. Conditions on lay time and their meaning 4. Suspension of count of the lay time 5. Demurrage 6. Dispatch 7. Bibliography www.inmarlegal.com 1. NOTION AND REGULATION OF LAY TIME In...»

«Lampe, Lilly. “Painter-painter,” and the Lingering Spector of Greenberg, The Brooklyn Rail, February 3, 2016, online. 
 “Painter-painter,” and the Lingering Specter of Greenberg by Lilly Lampe At an art auction a few years ago, I overheard a conversation that unsettled my sense of painting in a way that I’m still trying to fully understand. The auction was a fundraiser for a local art nonprofit and the mood was sour. The artists clung to the walls and their drinks, grumbling about...»

«POLONICA ACT.4. PAL A EON T 0 LOG I C A Vol. XIX 1 974 NO.2 CYPRIAN KULICKI REMARKS ON THE EMBRYOGENY AND POSTEMBRYONAL DEVELOPMENT OF AMMONITES Abstract. Previous views on the type of embryogeny in ammonites are discussed by the present writer who also points out some morphological characters of the initial chamber, along with the first whorl, which are indicative of a non-larval type of embryogeny. The swelling of shell wall on the nepionic constriction is analyzed in detail and the manner...»

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