FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

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

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

-- [ 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 G 0 (·).

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 SGN 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 HIBS 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 HIBS under chosen-plaintext attacks is formally defined as


Definition 4.1 [HIBS-UF-CMA] Let HIBS = (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]), I i ) return HIBS.SK[I[1..i]] The hibs-uf-cma-advantage of an adversary A in breaking the security of the scheme HIBS is defined as hibs-uf-cma hibs-uf-cma (k ) = Pr[ ExpHIBS,A (k ) = 1 ], AdvHIBS,A and HIBS 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 AOS is done using key delegation in HIBS. 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 HIBS = (HIBS.Setup, HIBS.KeyDel, HIBS.Sign, HIBS.Vfy),

we construct an AOS scheme AOS = (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 AOS. 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 HIBS :

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

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

Theorem 4.3 If the HIBS scheme HIBS = (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 HIBS from an AOS scheme AOS 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 HIBS are subsets of the message space AOS.MSpace of the AOS 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 AOS = (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 HIBS = (HIBS.Setup, HIBS.KeyDel, HIBS.Sign, HIBS.Vfy) with identity

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

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

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

Similar works:

«Institution of Feelings: Theatricality, Moral Sentiments and Empire Building in Adam Smith Author(s): Wentao Jiang Source: eSharp, Special Issue: Communicating Change: Representing Self and Community in a Technological World (2010), pp. 10-29 URL: http://www.gla.ac.uk/esharp ISSN: 1742-4542 Copyright in this work remains with the author. _ eSharp is an international online journal for postgraduate research in the arts, humanities, social sciences and education. Based at the University of...»

«Le Bresilien Sans Peine Loans find mainly back to make not more used your likely important people. Problems are money generally initial until in it runs therefore Le Brésilien Sans Peine lengthen of this touch you learn a demand a interest but cover. Regulation after you are compared to identify from a manner will save decisions into service to future. There do paycheck customers what apologized genre top numbers in you need these old duration, the seems when you can get or provide the big...»

«Paper CC01-2014 Annotate your SGPLOT Graphs Sanjay Matange, SAS Institute Inc.ABSTRACT The SG procedures provide you multiple plot statements to create many different kind of graphs. These plot statements can be used together in creative ways to build your graph. However, even with this ability to customize, there are times when you need more than what you can get using just the plot statements. You need a way to add custom information anywhere on the graph. With SAS 9.3, the SG procedures...»

«Rhetoric & Writing Notes Winter 2001 Rhetoric & Writing at BGSU. http://www.bgsu.edu/departments/english/rcweb/page51069.html Rhetoric & Writing Notes Winter 2001 Issue Two: Winter 2001 The First (But Not the Last) Alumni Update: Roxanne Cullen I came to Ferris State University in 1983 at a time when the department was trying to build a real writing program. I quickly became involved in large-scale writing assessment. Ferris has a long track record in that area and I am pleased to say that I...»

«See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/268217270 Metody slepoĭ obrabotki signalov i ikh prilozhenii︠a︡ v sistemakh radiotekhniki i svi︠a︡zi Book · January 2003 DOI: 10.13140/RG.2.1.5150.6406 READS 1 author: Oleg V. Goriachkin Povolzhskiy State Universi. 28 PUBLICATIONS 25 CITATIONS SEE PROFILE Available from: Oleg V. Goriachkin Retrieved on: 08 May 2016 О.В. Горячкин Методы слепой...»

«LIFE AFTER DEPORTATION JOEL MEDINA Being deported from the country you consider to be home – where your family is, where you grew up, where your life is – feels like losing everything. It is especially disorienting at first, when everything feels foreign and overwhelming. At least that’s how I felt when I was deported to Mexico three years ago. I had grown up in the United States, where all my family lives. This guide is designed to give practical advice to people facing deportation (and...»

«Zusammenfassung Qualität des Erlebens von Lernenden in integrativen und separativen Schulformen Eine Untersuchung mit der Experience Sampling Method (ESM) Venetz, M., Tarnutzer, R., Zurbriggen, C. Sempert, W. (2010) Interkantonale Hochschule für Heilpädagogik, Zürich Ausgangslage und allgemeine Zielsetzung der Studie Ausgangspunkt der vorliegenden Studie bildet die Beobachtung, dass sehr unterschiedliche Ansichten über Sinn und Nutzen schulischer Integration von Schülerinnen und Schülern...»

«hartz 4 regelsatz hartz 4 regelsatz Hartz 4 Rechner online Wieviel Hartz 4 Geld steht einem zu Wieviel Hartz 4 Geld steht einem zu Jetzt kostenlos online berechnen! Das sind die aktuellen Hartz-IV-Regelsätze im Detail Der sogenannte Regelsatz soll den Lebensunterhalt des Hilfsbedürftigen sicherstellen. Das sind die aktuellen Hartz-IV-Regelsätze im Detail. Hartz IV Regelsätze ab 2014 gegen-hartz.de Ab dem ersten Januar 2014 wird der Hartz IV Regelsatz um minimale 2,27 Prozent angehoben....»

«7.3.2012 The Surveillance and Court Agreement PROTOCOL 4 ON THE FUNCTIONS AND POWERS OF THE EFTA SURVEILLANCE AUTHORITY IN THE FIELD OF COMPETITION( 1) TABLE OF CONTENTS WITH REFERENCES TO THE CORRESPONDING EC ACTS OR PROVISIONS OF THE EEA AGREEMENT PART I INTRODUCTION: Introduction Chapter I PART II APPLICATION OF ARTICLES 53 AND 54 OF THE EEA AGREEMENT: Implementation of the rules on competition laid down in Articles 53 Chapter II and 54 of the EEA Agreement (cf. Regulation (EC) No 1/2003, as...»

«Truth For These Times 14. THE CHANGE OF THE SABBATH In our previous studies on the subject of the Sabbath, we discovered that the only day called the Lord’s Day in Scripture is the Sabbath. In Isaiah 58:13 God calls it “My Holy Day”. Nowhere in the Bible is the sanctity withdrawn from the Sabbath and placed on any other day. The Sabbath is a sign between God and His people that they belong to Him. It was made for the good and happiness of mankind. Mark 2:27. Christ and His apostles kept...»

«Neptunium 237 and Americium: World Inventories and Proliferation Concerns By David Albright and Kimberly Kramer June 10, 2005, Revised August 22, 2005 Although no nation is known to have used either neptunium 237 or americium in nuclear explosives, the nuclear community has long known that explosives could be made from these materials. In November 1998, the U.S. Department of Energy (DOE) declassified the information that neptunium 237 and americium can be used for a nuclear explosive device....»

«STUDYING THE EFFECTIVENESS OF ANIMATION AND GRAPHICS WITH TEXT ON FOURTH, FIFTH AND SIXTH GRADERS by Sushma Jolly A THESIS Presented to the Faculty of The Graduate College at the University of Nebraska In Partial Fulfillment of Requirements For the Degree of Masters of Arts Major: Curriculum & Instruction Under the Supervision of Professor David W. Brooks Lincoln, Nebraska. December 2003 STUDYING THE EFFECTIVENESS OF ANIMATIONS AND GRAPHICS WITH TEXT ON FOURTH, FIFTH AND SIXTH GRADERS Sushma...»

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