FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

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

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

-- [ Page 3 ] --

In AOS3, we associate every node of the graph T with a secret key. Keys are assigned in a top-down manner, starting with a random key for the root ε of U T. Furthermore, for nodes in U T everybody can compute key( v1,..., vj, 0 ) and key( v1,..., vj, 1 ) from key( v1,..., vj, 0 ) (using the pseudo random generators G0 (·), G1 (·)) and for nodes in LT everybody can compute key([v1,..., vj ]) from key([v1,..., vj, 0]) and key([v1,..., vj, 1]) (using the hash function H(·, ·)).

The nodes between LT and U T are “connected” through the pseudorandom generator G0 (·).

The secret key is key(ε), the public key is key(˜). The AOS of a node v1,..., vn (representing ε n, n ≤ d) is given by the set of keys {key(x) | x ∈ the message M [1..n] = (M1,..., Mn ) ∈ {0, 1} { v1,..., vn }∪Comp( v1,..., vn )}. Verification of a given AOS is done by computing top-down the corresponding keys in LT and checking if the last key matches the public key key(˜). The ε

algorithms constituting AOS3 are defined as follows:

–  –  –

We give the efficiency of this scheme in Table 4. We prove aos-uf-cma security of the AOS3

scheme assuming the security of the underlying functions G(·) and H(·, ·):

Theorem 3.2 If G(·) is a secure pseudorandom generator, G0 (·), G1 (·), are secure one-way functions and H(·, ·), G0 (·), and G1 (·) are all collision-resistant hash functions, then AOS3 is aos-uf-cma secure.

–  –  –

Table 4: Efficiency of the hash-tree based scheme AOS3. d represents the maximum message length, n represents the length of a given message, and k is the security parameter.

3.5 AOS via One-time Signatures We observe that we can combine the ideas of certificate-based AOS (Section 3.1) and hash-tree AOS (Section 3.4) to gain a more efficient append-only signature scheme when the message space is small. Assume the message space AOS.MSpace consists of m elements. Then we can use our certificate-based construction AOS1 instantiated with a m-time signature scheme. mtime signatures can be efficiently constructed using hash-trees (see [BM96], [HM02], [Mer88], and [RR02] for the definition and efficient constructions of m-time signatures). In addition, the security proof of AOS1 guarantees unforgeability if SG N is at least an |AOS.MSpace|-time signature scheme. Note that in contrast to AOS3, the length of the AOS messages in this construction is unbounded2.

4 Relations between HIBS and AOS In this section, we show that the concepts of AOS and Hierarchical Identity-based Signatures (HIBS) are in fact equivalent. Before we present the poly-time reductions between the AOS and HIBS, we first review related concepts and relationships.

In Identity-based Signature (IBS) schemes, the identity of a sender (for example, an email address) is used as a public key for verification of the signature. This approach assumes the existence of a trusted party (the certificate authority), which assigns secret keys to all users.

The certificate authority has a pair of keys: a master public key and a master secret key; the master secret key is used to delegate keys to the users and the master public key is used for signature verification. Anyone can verify signatures on messages signed by any user, knowing only the master public key and the identity of that user.

Hierarchical Identity-based Signature (HIBS) schemes are a natural generalization of IBS to the setting with a hierarchical organization of users. Assume that the users are structured in a tree with a root being the certificate authority. Descendants of a user are the usernames that contain this user’s name as a prefix; the canonical example involves domain names. In HIBS, each individual user can play the role of a certificate authority and can delegate secret keys to his descendants. As in IBS, a secret key allows a user to sign arbitrary messages such that anyone is able to verify the signature knowing only the identity of the sender and the master public key (announced by the certificate authority, who can be viewed as the root user). A formal description of HIBS follows.

Hierarchical Identity-based Encryption (HIBE) assumes the same hierarchy of users as HIBS and provides encryption/decryption mechanisms rather than signatures. In HIBE, anyone can Similar ideas were used by Abdalla and Reyzin [AR00] who who suggested how to improve the efficiency of binary certification method for constructing forward-secure signatures (see also Bellare and Miner [BM99]).

encrypt data to any user in the hierarchy knowing only the user’s identity and the master public key; the ciphertext can only be decrypted using the user’s secret key.

As noted by Naor (see Section 6 of [BF03]), any IBE scheme can readily be converted into a public key signature scheme (by interpreting user identities of IBE as messages for a regular signature scheme and defining the signature of a message to be the secret key associated with the corresponding identity). Similarly, any HIBE scheme can be transformed into a HIBS scheme.

This was sketched by Gentry and Silverberg [GS02], giving the construction for a HIBS scheme.

We note that the converse (transforming HIBS into HIBE) is not known to be possible. Related to these are Forward-secure Signature (FSS) schemes, which modify a secret key over time (while the public key remains the same) such that exposure of the secret key at a certain time period does not allow forgery of signatures from previous time periods. (See [BM99] for an exact definition of FSS.) In [CHK03] it is proved that HIBE implies Forward-secure Encryption (FSE) (which is defined as FSS with signing replaced by encryption). Using the same construction it is easy to show that HIBS implies FSS (as explicitly noted in [CHYC04]). More precisely, a HIBS scheme of depth d can be used to construct a forward-secure scheme providing security for 2d time steps (using a tree-based construction). The converse (transforming FSS into HIBS) is not known to be possible. Thus, relating HIBE, HIBS, AOS, and FSS, we obtain the following


HIBE ⇒ HIBS ⇔ AOS ⇒ FSS In particular, given a secure HIBE scheme, we can construct a secure AOS scheme and given a secure AOS scheme, it is easy to obtain a secure FSS scheme.

4.1 Definition of HIBS We recall the syntax of Hierarchical Identity-based Signature (HIBS) schemes and the appropriate notions of unforgeability. Let HIBS.IDSpace be any set of identities (typically {0, 1}∗ ). For an integer n ≥ 0, a username at the level n in the tree (called hierarchical identity of depth n) is an (ordered) n-tuple of identities written as I[1..n] = (I1, I2,..., In ) with each Ii ∈ HIBS.IDSpace.

The special case of n = 0 is the root identity, denoted as I[1..0] or ε. Further on, we will

refer to strings from HIBS.IDSpace as identities and to n-tuples of them as hierarchical identities. We use the symbol ⊑ to denote the prefix relation over the set of hierarchical identities:

for a given hierarchical identity I[1..n] = (I1, I2,..., In ), any hierarchical identity from the set {I[1..i], 0 ≤ i ≤ n} is its prefix. Note that the root identity ε is a prefix of any other hierarchical identity.

A HIBS scheme H IBS with respect to the message space HIBS.MSpace and the identity space HIBS.IDSpace is made up of four algorithms: a setup algorithm HIBS.Setup, a key delegation algorithm HIBS.KeyDel, a signature algorithm HIBS.Sign, and a verification algorithm HIBS.Vfy.

• HIBS.Setup (the setup algorithm) takes as input a security parameter and generates the master public key HIBS.pk of the scheme and the secret key of the root identity HIBS.SK[ε] (the master secret key).

• HIBS.KeyDel (the key delegation algorithm) takes as input a hierarchical identity I[1..n] = (I1,..., In ), its associated secret key HIBS.SK[I[1..n]], and an identity In+1 ∈ HIBS.IDSpace of its child. It returns a secret key HIBS.SK[I[1..n+1]] associated with the new hierarchical identity I[1..n + 1] = (I1,..., In, In+1 ).

• HIBS.Sign (the signing algorithm) takes a hierarchical identity I[1..n], the associated secret key HIBS.SK[I[1..n]], and a message M ∈ HIBS.MSpace. It computes a signature on this message M with respect to this identity.

• HIBS.Vfy (the verification algorithm) takes the master public key HIBS.pk, a hierarchical identity I[1..n], a message M, and a signature sig. It outputs true or false depending on whether sig is a valid signature of M signed by hierarchical identity I[1..n].

All these algorithms can be randomized. All of them must be polynomial-time in the security parameter. Moreover, it is required that for all pairs (HIBS.pk, HIBS.SK[ε]) of master public and secret keys output by HIBS.Setup, and for all messages M ∈ HIBS.MSpace, hierarchical identities I[1..n] and associated secret keys HIBS.SK[I[1..n]] (recursively generated from the secret key HIBS.SK[ε] using the HIBS.KeyDel algorithm),

HIBS.Vfy(HIBS.pk, I[1..n], HIBS.Sign(HIBS.SK[I[1..n]], I[1..n]), M ), M ) = true.

Unforgeability of the HIBS scheme H IBS under chosen-plaintext attacks is formally defined as


Definition 4.1 [HIBS-UF-CMA] Let H IBS = (HIBS.Setup, HIBS.KeyDel, HIBS.Sign, HIBS.Vfy) be a hierarchical identity-based signature scheme, let k be the security parameter, and let A be

an adversary. We consider the experiment:

–  –  –

Oracle Extract(I[1..i]) // defined recursively if i = 0 return HIBS.SK[ε] else if HIBS.SK[I[1..i]] = defined then return HIBS.SK[I[1..i]] else HIBS.SK[I[1..i]] ← HIBS.KeyDel(HIBS.pk, I[1..i − 1], Extract(I[1..i − 1]), Ii ) return HIBS.SK[I[1..i]] The hibs-uf-cma-advantage of an adversary A in breaking the security of the scheme H IBS is defined as Advhibs-uf-cma (k ) = Pr[ Exphibs-uf-cma (k ) = 1 ], H IBS,A H IBS,A and H IBS is said to be existentially unforgeable under chosen message attacks (hibs-uf-cmasecure) if the above advantage is a negligible function in k for all polynomial-time adversaries A. Note that the adversary is given access to the two oracles Corrupt(·) and Sign(·, ·), not to the oracle Extract(·). The latter one is only used internally by the experiment.

4.2 Constructing AOS from HIBS The idea of the reduction is as follows. We set AOS.MSpace = HIBS.IDSpace and associate an AOS message (M1,..., Mn ) of length n with the hierarchical identity I[1..n] = (M1,..., Mn ) of depth n. We then define the signature of this message as the secret key HIBS.SK[I[1..n]] of the hierarchical identity I[1..n].

Given the above analogy between signatures of messages and secret keys of hierarchical identities, we construct an AOS scheme given a HIBS scheme as follows. Appending to a given signature in A OS is done using key delegation in H IBS. The verification of an AOS signature HIBS.SK[I[1..n]] is done by signing a random message M ∈ HIBS.MSpace under the secret key HIBS.SK[I[1..n]] and verifying that the resulting signature is valid.

Construction 4.2 Given a HIBS scheme H IBS = (HIBS.Setup, HIBS.KeyDel, HIBS.Sign, HIBS.Vfy),

we construct an AOS scheme A OS = (AOS.Setup, AOS.Append, AOS.Vfy) as follows:

• AOS.Setup: Run the HIBS.Setup algorithm to generate a pair (HIBS.pk, HIBS.SK[ε]) and output (HIBS.pk, HIBS.SK[ε]) as the key pair for A OS. HIBS.SK[ε] is the signature of an empty message ε.

• AOS.Append: Given the public key AOS.pk, signature Sig[M [1..n]] of the message M [1..n], and the message Mn to append, the AOS signature on Sig[M [1..n + 1]] is returned as Sig[M [1..n + 1]] ← HIBS.KeyDel(HIBS.pk, Sig[M [1..n]], Mn+1 ).

• AOS.Vfy: Given a public key AOS.pk, a message M [1..n], and a signature Sig[I[1..n]], the verification algorithm first signs a random message M ∈ HIBS.MSpace under hierarchical

identity M [1..n] using Sig[I[1..n]] as a secret key of M [1..n] in H IBS :

sig ← HIBS.Sign(I[1..n], Sig[I[1..n]], M ).

Then it outputs the result of the H IBS verification HIBS.Vfy(HIBS.pk, I[1..n], M, sig).

Theorem 4.3 If the HIBS scheme H IBS = (HIBS.

Setup, HIBS.KeyDel, HIBS.Sign, HIBS.Vfy) is hibs-uf-cma secure, then the AOS scheme from Construction 4.2 is aos-uf-cma secure.

We omit the proof of Theorem 4.3.

4.3 Constructing HIBS from AOS A naive approach to building a HIBS scheme H IBS from an AOS scheme A OS is to first append all the identities and then to append a message to be signed. That is, both the identity space HIBS.IDSpace and the message space HIBS.MSpace of H IBS are subsets of the message space AOS.MSpace of the A OS scheme. The secret key of a hierarchical identity I[1..n] in this HIBS scheme is exactly the AOS signature of I[1..n] viewed as the AOS message. Delegation in HIBS is equivalent to appending in AOS. Signing a message M with respect to a hierarchical identity I[1..n] is defined by appending M to the AOS signature of I[1..n].

This naive construction is secure only if HIBS.IDSpace and HIBS.MSpace are disjoint subsets of AOS.MSpace. If there is some identity J which itself is a valid message, the security of the HIBS scheme can be broken even if its corresponding AOS is secure. An adversary could query the HIBS signing oracle with a message J and some hierarchical identity I[1..n]. The resulting signature equals the secret key for the hierarchical identity (I1,..., In, J), which violates the security of the HIBS scheme.

Our idea to overcome this problem is to insert a unique identifier between identities and messages. Let A OS = (AOS.Setup, AOS.Append, AOS.Vfy) be a secure AOS scheme with message space AOS.MSpace. Let HIBS.IDSpace and HIBS.MSpace be arbitrary subsets of AOS.MSpace such that there is some symbol ∆ from the AOS message space which is not a valid identity for the HIBS scheme (∆ can still be in the HIBS message space). Then we can construct a secure HIBS scheme H IBS = (HIBS.Setup, HIBS.KeyDel, HIBS.Sign, HIBS.Vfy) with identity

space HIBS.IDSpace and message space HIBS.MSpace as follows:

Construction 4.4 H IBS = (HIBS.Setup, HIBS.KeyDel, HIBS.Sign, HIBS.Vfy):

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

Similar works:

«THE STATISTICAL CONSULTANT Section on Statistical Consulting American Statistical Association Karen Copeland, Editor; Christopher Holloman, Assistant Editor Spring 2006; Volume 23, No. 1 IN THIS ISSUE 2005 Annual Report for the ASA Statistical Consulting Section   e-Directory Launch Update   Going Rates for Statistical Consulting: Results from the Statistical Consulting Section Rates   Survey Results Academic Consulting Profile: Wright State University   Consulting After Academics   SAS...»

«451 PRESTRESSED SOIL ANCHORS. (REV 8-14-12) (FA 8-27-12) (1-13) SECTION 451 (Pages 500-516) is deleted and the following substituted: SECTION 451 PRESTRESSED SOIL ANCHORS 451-1 Description. Construct prestressed soil anchors consisting of a high strength steel tendon anchored to the retaining wall on one end and to the soil on the other end through a bulb of pressure injected portland cement concrete grout. Test each anchor by prestressing to the load indicated in the Contract Documents before...»

«Anticipated and unanticipated effects of crude oil prices and gasoline inventory changes on gasoline prices Stanislav Radchenko∗ University of North Carolina at Charlotte revised April, 2005 Abstract This paper examines the effect of anticipated and unanticipated changes in oil prices and gasoline inventory on US gasoline prices. I show that gasoline price adjustments are faster and stronger for anticipated changes in oil prices and inventory levels than for unanticipated changes. In all...»

«Universität Lund Sprachenund Literaturzentrum TYSK01: Examensaufsatz Frühjahrsemester 2015 Erich Kästners politische Dichtung Gesellschaftskritik und Visionen eines Gebrauchslyrikers Betreuer: Alexander Bareis Verfasser: Sverker Kock Inhaltsverzeichnis 1.Einleitung, Fragestellung und Methode 1.1 Einleitung 1.2 Fragestellung 1.3 Methode und Material 2. Theoretische Ausgangspunkte 2.1 Sven Hanuschek 2.2 Renate Benson 2.3 Klaus Doderer 3. Kennst Du das Land, wo die Kanonen blühen? 4. Die...»

«*FM 2-19.4 Brigade Combat Team Intelligence Operations 25 NOVEMBER 2008 DISTRIBUTION RESTRICTION: Distribution authorized to U.S. Government agencies only because it requires protection in accordance with AR 380-5 or as specified by DCS G-3 Message DTG 091913ZMAR04. This determination was made on 9 September 2005. Contractor and other requests must be referred to ATTN: ATZS-CDI-D, U.S. Army Intelligence Center, Fort Huachuca, AZ 85613-7017, or via email at ATZS-FDC-D@conus.army.mil DESTRUCTION...»

«89 7. Insects as animal feed 7.1 OVeRVIeW In 2011, combined world feed production was estimated at 870 million tonnes, with revenue from global commercial feed manufacturing generating approximately US$350 billion globally. FAO estimates that production will have to increase by 70 percent to be able to feed the world in 2050, with meat outputs (poultry, pork and beef) expected to double (IFIF, 2012). Despite this, little has been said about the opportunities insects offer as feed sources (Box...»

«SERIES IZA DP No. 8379 PAPER The Math Gender Gap: The Role of Culture Natalia Nollenberger DISCUSSION Núria Rodríguez-Planas Almudena Sevilla August 2014 Forschungsinstitut zur Zukunft der Arbeit Institute for the Study of Labor The Math Gender Gap: The Role of Culture Natalia Nollenberger Queen Mary University of London Núria Rodríguez-Planas Queens College CUNY and IZA Almudena Sevilla Queen Mary University of London and IZA Discussion Paper No. 8379 August 2014 IZA P.O. Box 7240 53072...»

«Form DT/Company Double Taxation treaty relief APPLICATION for relief at source from United Kingdom income tax and CLAIM to repayment of United Kingdom income tax For use by a COMPANY or OTHER CONCERN resident in a country with which the United Kingdom has a double taxation treaty that provides for relief from UK income tax on interest or royalties arising in the UK. (Specific forms are available for companies resident in certain countries please see www.hmrc.gov.uk/cnr) Please · use the...»

«Use of ozonides in the treatment of malignant disease – basic principles and clinical results Dr.rer.nat. Gerhard Steidl Status as at 1.8.2002 CONTENTS Page Preface 1 I Basic principles 2 II. Information sheet 6 III Strengthening Para-Rizol formula for malignant disease: Para-Spezial 9 IV Clinical results 14 V Para-Spezial-N: latest development 20 VI Summary 20 Preface This publication follows on from the description of current uses of ozonide formulae begun in September 2000 with the article...»

«Anil's Ghost by Michael Ondaatje Michael Ondaatje learn by way of Alan Cumming7 CDs, eight hoursFrom the writer of The English Patient and winner of the Booker Prize, the Canada Australia Prize, and the Canada Governor General's Award, comes a brand new novel of electrical artistry and impression confirming Michael Ondaatje's popularity as one of many world's leading writers. The time is our personal time. where Sri Lanka, the island state off the southern tip of India, a rustic previously...»

«Österreichische Zeitschrift für Volkskunde \/. Herausgegeben vom Verein für Volkskunde U nter ständiger M itarbeit von Hanns Koren (Graz), Franz Lipp (Linz), Oskar Moser (Klagenfurt Graz) geleitet von Klaus Beitl und Franz Grieshofer Neue Serie Band XXXIX Gesamtserie Band 88 WIEN 1985 IM SELBSTVERLAG DES VEREINES FÜR VOLKSKUNDE Gedruckt mit Unterstützung des Bundesministeriums für Wissenschaft und Forschung der Burgenländischen Landesregierung der Kärntner Landesregierung der...»

«Jerusalem Center for Public Affairs )‫המרכז הירושלמי לענייני ציבור ומדינה (ער‬ Libel Tourism: International Forum Shopping for Defamation Claims Avi Bell1 » 1 © 2008 Jerusalem Center for Public Affairs 13 Tel Hai Street, Jerusalem, Israel Tel. 972-2-561-9281 Fax. 972-2-561-9112 Email: jcpa@netvision.net.il www.jcpa.org | www.globallawforum.org ISBN 978-965-218-070-4 Production Manager: Edna Weinstock-Gabay Graphic Design: www.ramijaki.co.il Rami & Jacky /...»

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