FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 || 3 | 4 |   ...   | 6 |

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

-- [ Page 2 ] --

2 Append-only Signatures Informally, append-only signatures (AOS) are signatures that enable the public extension of existing signatures. That is, any party given an AOS signature Sig on a message (M1,..., Mn ) can compute an AOS signature on any message (M1,..., Mn, Mn+1 ). (As in the introduction, one could represent the message (M1,..., Mn ) as the string M1 ||... ||Mn which better captures the idea of appending. However, since we want to differentiate between a message of the form “A” “B” and that of the form “AB” (“A”,“B” and “AB” being three different message symbols), we prefer to think of messages as n-tuples). Besides the append operation, AOS is the same as ordinary signatures. That is, given only an AOS signature on the message (M1,..., Mn ) it should be infeasible to forge an AOS signature on any message not having (M1,..., Mn ) as a prefix. In terms of conventional signatures, AOS may seem strange, as it allows the “forgery” of signatures on messages not previously obtained. In particular, given a signature on the empty message ε, a signature on any message (M1,..., Mn ) can be computed. In the context of AOS, we view this as a feature, and, as we will show, this is useful in several applications.

We now formally define AOS and the corresponding notion of security. Let AOS.MSpace be any set of symbols (for example, {0, 1} or {0, 1}∗ ). For an integer n ≥ 0, a message of length n is an n tuple of symbols written as M [1..n] = (M1, M2,..., Mn ) with Mi ∈ AOS.MSpace.

The special case of n = 0 is the empty message, denoted as ε, also written as M [1..0]. We use the symbol ⊑ to denote the prefix relation over the messages: for a given message M [1..n] = (M1, M2,..., Mn ), any message from the set {M [1..i], 0 ≤ i ≤ n} is a prefix. Note that ε is a prefix of any other message.

An append-only signature (AOS) scheme with respect to the message space AOS.MSpace is a collection of three algorithms: a setup algorithm (AOS.Setup), an append algorithm (AOS.Append),

and a verify algorithm (AOS.Vfy), defined as follows:

• AOS.Setup (the key generation algorithm) takes the security parameter as input and outputs a pair of keys: the public key AOS.pk and the secret key Sig[ε], which is the signature on the empty message ε.

• AOS.Append (the append algorithm) takes the public key AOS.pk, a signature on a message M [1..n − 1] = (M1,... Mn−1 ), of length n − 1, and a symbol Mn ∈ AOS.MSpace and produces a signature on the message M [1..n] = (M1,..., Mn ).

• AOS.Vfy (the verification algorithm) takes the public key AOS.pk, a message M [1..n], and a signature sig, and returns either true or false.

All algorithms can be randomized and all of them must be polynomial-time in the security parameter. Additionally, the scheme should have the property that for any pair (AOS.pk, Sig[ε]) generated by AOS.Setup(1k ) and any message M [1..n] = (M1, M2,..., Mn ) (where n is polynomially bounded in the security parameter), the signature on M [1..n] given by sig = AOS.Append(AOS.pk, M [1..n − 1], AOS.Append(AOS.pk, M [1..n − 2],...

..., AOS.Append(AOS.pk, Sig[ε], M1 ), · · ·, Mn−1 ), Mn ) (1) should be accepted by a verification algorithm. That is, AOS.Vfy(AOS.pk, M [1..n], sig) must return true.

The way an AOS signature is defined in Eq. (1) implies that the only way of appending a sequence of symbols to a given AOS signature is to append the symbols one-by-one.

This means that the distribution of an AOS signature created by appending a symbol Mn to a message (M1, · · ·, Mn−1 ) is the same as the distribution of the signature on the message (M1, · · ·, Mn−1, Mn ) when generated from scratch (using the secret key Sig[ε]). This fact ensures history independence of AOS: that is, no party, given an AOS signature, can tell whether the signature was created by the owner of the secret key or whether it passed through multiple parties that appended symbols at every step1. History independence is a useful property to have The above definition precludes trivial schemes of the following form: Let SG N = (SGN.G, SGN.S, SGN.V) be any standard digital signature scheme. Construct an append-only signature scheme using SG N in which the signature of any message M [1..n] = (M1, · · ·, Mn ) is (SGN.S(M [1..n]), n) and the program AOS.Append takes a in most applications (as already highlighted in previous work on algebraic signatures [JMSW02] and incremental signatures [BGG95]).

–  –  –

Note that in our definition of security, adversary A is given access to the oracle AOSSign(·), not to the oracle Extract(·). (The latter is used internally by AOSSign(·) to create intermediate signatures.) The history independence property of AOS ensures that the adversary can get no advantage when given the power to decide “how” the signature on any message is to be created by AOSSign(·) (for example, whether it asks for a message (M1, M2 ) to be signed from scratch or by first signing M1 and then appending M2, it would get the same reply in return).

3 Efficient AOS Constructions

3.1 Certificate-Based Append-Only Signatures We present an efficient construction of a provably-secure AOS scheme based on a public-key signature scheme. Let SG N = (SGN.G, SGN.S, SGN.V) be a signature scheme with a space of public keys SGN.PKSpace and message space SGN.MSpace = AOS.MSpace × SGN.PKSpace. (A formal definition of a public-key signature scheme including a security definition is given in Appendix A.) That is, messages to be signed by SG N are tuples of the form (M, pk), where M ∈ AOS.MSpace and pk ∈ SGN.PKSpace. Intuitively, an AOS signature Sig of a message

M [1..n] consists of the following elements:

{pk1, sig 1,..., pkn, sig n, skn }, message M [1..n], its signature (σ, n) and a new symbol M [n + 1] and simply outputs (σ, n). Verification of a signature (σ, n) on message M [1..N ] (N ≥ n) is carried out by testing if σ is the signature, according to SG N, on M [1..n]. Although this scheme allows appending to already signed messages in an arbitrary manner, one can easily distinguish between signatures created by such append operations and those created from scratch.

where for 1 ≤ i ≤ n, (pk i, sk i ) are random public/secret key pairs of the public-key signature scheme SG N and sig i is a signature on the tuple (Mi, pk i ) under the secret key ski−1. Note that the secret key sk i used to sign sig i is entangled with sig i+1 by signing its corresponding public key pk i, thereby certifying its validity. For this reason, this construction is sometimes referred to as a certificate chain. The signature sig 0 needs to be signed with the secret key sk 0, which we define to be the master secret key.

More formally, we construct the AOS scheme AOS1 with the message space AOS.MSpace

as specified below:

• AOS.Setup(1k ) (the setup algorithm):

Run SGN.G(1k ) to generate a pair (sk0, pk0 ). Set AOS.pk ← pk0 and Sig[ε] ← {sk0 }.

Return (AOS.pk, Sig[ε]).

• AOS.Append(AOS.pk, Sig[M [1..n]], Mn+1 ) (the append algorithm):

Parse Sig as {pk1, sig 1,..., pkn, sig n, skn }. If n = 0, then Sig[ε] consists of a single secret key sk0. Run SGN.G(1k ) to generate a pair (skn+1, pkn+1 ). Compute sig n+1 ← SGN.Sskn (Mn+1, pkn+1 ). Return {pk1, sig 1,..., pkn, sig n, pkn+1, sig n+1, skn+1 }.

• AOS.Vfy(AOS.pk, M [1..n], Sig) (the verification algorithm):

Parse Sig as {pk1, sig 1,..., pkn, sig n, skn }. If n = 0, then Sig = {sk0 }. Set pk0 to be the master public key AOS.pk. For i = 1..n−1 verify that SGN.V(pki−1, sig i, (Mi, pki )) = true.

If any of the verifications fail, return false. If all the verifications succeed, verify that (skn, pkn ) is a valid secret key/public key pair: pick any message M ∈ SGN.MSpace and $ compute sig ← SGN.S(skn, M ). Return true if SGN.V(pkn, sig, M ) = true and false otherwise.

The length of a signature of AOS1 grows linearly with the number of symbols in a message.

The efficiency of AOS1 is summarized in Table 1. We prove aos-uf-cma security of AOS1 provided that the original public-key signature scheme SG N is sig-uf-cma secure (as defined in Appendix A).

Theorem 3.1 The AOS scheme AOS1 is aos-uf-cma secure assuming that the public-key signature scheme SG N is sig-uf-cma secure.

The full proof of Theorem 3.1 is in Appendix B. Here we sketch the main ideas of why this construction works. Intuitively, in order to break the aos-uf-cma security of AOS1, an adversary has two choices between which we must distinguish. First, she could try to forge a signature on a prefix of a message she already knows the signature of. Since a valid AOS1 signature of this prefix (say, of length n′ ) has to contain the secret key sk n′ in cleartext, this would imply a full break of the security of the signature scheme. Second, the adversary could try to forge an AOS signature on a message that is different from all those with known signatures. To do so, the adversary could use existing public/secret key pairs, meaning she has to produce (for some i) a new signature on a tuple (Mi, pk i ) under an unknown secret key and a different message Mi.

Otherwise, the adversary breaks the certificate chain. That is, at some position i, the adversary creates a fresh secret-public key pair (sk i, pk i ) and uses sk i to create sigi. However, sigi−1 is a signature on the public key pk i and the symbol Mi−1 under the secret key sk i−1. In order to use a new secret key sk i to create sigi, the adversary has to forge a signature under the unknown secret key sk i−1. This clearly contradicts the uf-cma security of the signature scheme.

Metric Certificate-based AOS n SG N signatures, n SG N public keys, 1 SG N secret key Signature length 1 × SGN.G(·) Setup time 1 × SGN.G(·), 1 × SGN.S(·) Append time (n + 1) × SGN.V(·), 1 × SGN.S(·) Verify time Table 1: Efficiency of certificate-based AOS. Data is given for messages of length n.

3.2 Shorter Signatures via Aggregation An aggregate signature scheme, A SG N = (ASGN.G, ASGN.S, ASGN.AGG, ASGN.V), allows the aggregation of n signatures on n distinct messages from n distinct users into a single signature.

Its verification algorithm, ASGN.V(n, ·), takes an aggregated signature, n messages, and n public keys and verifies that the n users signed the n messages. A sequential signature aggregation algorithm assumes to receive the signatures sequentially: given an aggregated signature of n − 1 messages and a signature on an nth message, it outputs an aggregated signature for all n messages.

When using the certificate-based construction of AOS from Section 3.1, we can use sequential signature aggregation to shrink the size of the signature (without significantly decreasing security or efficiency). To be more precise, the length of an AOS signature of a message of length n can be condensed to one signature of A SG N, n public keys of A SG N, and one secret key of A SG N.

We summarize the efficiency of this approach in Table 2. We note that there are two known signature aggregation techniques. The first scheme, given in [BGLS03], is based on bilinear maps. The second scheme (only supporting sequential aggregation) is from [MOR01] and can be based on homomorphic trapdoor permutations (such as RSA). We note that both aggregation schemes are in the random oracle model.

–  –  –

Table 2: Efficiency of AOS with signature aggregation. Data is given for messages of length n.

3.3 Compact Signatures via the Boneh-Goh-Boyen HIBE

–  –  –

Table 3: Efficiency of AOS2. d represents the maximum message length. e(·, ·) is a pairing operation on elements of the group G1 as used by the HIBE scheme.

–  –  –

0, 1 0, 1 0, 0 1, 1 1, 0 [0, 1] [0, 0] [0,[1, 1] 0] [1, 0] [0] [1] [1]

–  –  –

Figure 1: Structure of the hash-tree construction for d = 2. The diagram on the left depicts the hash tree. The diagram on the right highlights the node u = 0, 1 (shown in black) and the set of its complements, Comp(u) (shown in gray).

3.4 AOS via Hash Trees If the number of symbols in the alphabet AOS.MSpace is small, AOS can be efficiently implemented using hash trees [Mer88]. This approach suffers from dramatic complexity blowup as the size of the message space increases, but uses only secret-key primitives and provides good security guarantees. We believe that this construction is useful in computationally constrained applications.

Next we construct an AOS scheme AOS3 with fixed message space AOS.MSpace = {0, 1};

the messages of AOS3 are limited to length at most d. The construction uses a pseudorandom generator and a collision-resistant hash function (for a formal definition of the two primitives we refer the reader to the textbook of Goldreich [Gol01]). Let G : {0, 1}k → {0, 1}2k be a pseudorandom generator. Denote Gi : {0, 1}k → {0, 1}k to be the i-th k -bit component of G for i ∈ {0, 1}. Let H : {0, 1}2k → {0, 1}k be a collision-resistant hash function.

Consider the left graph T depicted in Figure 1. T consists of the upper tree U T and lower tree LT. The top node ε is called the source and the bottom node ε is called the destination.

˜ Let v1,..., vj denote the node at level j below ε (in the upper tree) such that each vi ∈ {0, 1} is an index of a node taken at the i-th level on the path from ε to v1,..., vj. A mirror image of this node in the lower tree is denoted as [v1,..., vj ].

Let u = v1,..., vj be any node in the upper tree of the graph. We define the complement of u, denoted Comp(u), to be the minimal set of nodes in LT − {˜} such that every path from ε ε to ε passes through exactly one node from {u} ∪ Comp(u). An example of a complement ˜ set is given in Figure 1 (the right graph). Let ¬ denote the not operator. Then Comp(u) = {[v1,..., vi−1, ¬vi ] | i = 1,..., j}.

Pages:     | 1 || 3 | 4 |   ...   | 6 |

Similar works:

«8. Meßtechnik und Prüfung von Quarzoszillatoren Die gebräuchlichsten Methoden zur Prüfung und Messung von Quarzoszillatoren ist in der Norm DIN IEC 679-1 ausführlich beschrieben. Zusätzliche Meßmethoden sind in der Fachgrundspezifikation DIN EN 169000 (CECC 69000) enthalten, die zur Zeit in die Neufassung der DIN IEC 679-1 eingearbeitet wird. Messungen und Prüfungen, die in diesen Normen nicht oder nicht detailliert genug beschrieben sind, werden in Anlehnung an den MIL-Standard für...»

«Computational Analysis of Protein-Protein Interactions Dissertation zur Erlangung des Grades des Doktors der Naturwissenschaften der Naturwissenschaftlich-Technischen Fakultät III Chemie, Pharmazie, Biound Werkstoffwissenschaften der Universität des Saarlandes von Diplom-Biologe Sam Ansari Saarbrücken 2007 Tag des Kolloquiums: 13. Juni 2007 Dekan: Prof. Dr. Uli Müller Vorsitzender: Prof. Dr. Jörn Walter Berichterstatter: Prof. Dr. Volkhard Helms Prof. Dr. Hans-Peter Lenhof Beisitzender:...»

«(http://www.cheapflights.com/news/) BEACH & NATURE (HTTP://WWW.CHEAPFLIGHTS.COM/NEWS/CATEGORY/BEACH-NATURE-EN-US/) Beach porn: 40 photos to wash the winter chill away (https://www.facebook.com/sharer/sharer.php? (http://twitter.com/share? (https://plus.google.com/share? (http://www.pinterest.com/pin/create/button/? (http://www.stumbleupon.com/badge/? 59 shares...»

«65 In: U. Graf & E. Moser Opitz (Hrsg.) (2007), Diagnostik am Schulanfang. (= Entwicklungslinien der Grundschulpädagogik. Band 3), S. 67-86. Baltmannsweiler: Schneider Hohengehren. II: Bereichsspezifische Diagnostik (1) Sprachund Schriftspracherwerb Petra Schulz Erstspracherwerb Deutsch: Sprachliche Fähigkeiten von Eins bis Zehn* „Das ist so ein Luftkissen, das rauskommt an der Seite, wenn man ein’ Unfall hat, dass man sich nicht weh tut.“ Das Kind, das hier den Begriff ‚Airbag’...»

«Peregram Fall 2009 Velma Morrison Interpretive Center News Nick Dunlop Clara of San Jose—See article on Nick Dunlop photography exhibit. Falling Leaves & Flying Falcons! Daily flight demonstrations commencing in October—Trish Nixon, Raptor Specialist A s the long days of summer wane, brisk breezes and the golden hues of autumn bring a change to our hilltop here in Boise. We begin to prepare our birds for outdoor flights; one of the highlights of our education program. Our Gyrfalcons perk...»

«Slightly expanded version of paper in Proceedings AISB Conference, Warwick University 1985 published as: A.G. Cohn and J.R. Thomas (eds) Artificial Intelligence and Its Applications, John Wiley and Sons 1986. DID SEARLE ATTACK STRONG STRONG OR WEAK STRONG AI? Aaron Sloman School of Cognitive and Computin Sciences University of Sussex Brighton BN1 9QH ABSTRACT John Searle’s attack on the Strong AI thesis, and the published replies, are all based on a failure to distinguish two interpretations...»

«Journey to the End of the Night Louis-Ferdinand Céline Translated by Ralph Manheim Preface by André Derval ONEWORLD CLASSICS oneworld classics ltd London House 243-253 Lower Mortlake Road Richmond Surrey TW9 2LL United Kingdom www.oneworldclassics.com Journey to the End of the Night first published in French as Voyage au bout de la nuit in 1932 This translation first published in Great Britain by John Calder (Publishers) Ltd in 1988 This revised edition of Journey to the End of the Night...»

«Disney's Women: Changes in Depictions of Femininity In Walt Disney's Animated Feature Films, 1937-1999 by Amy Michele Davis Thesis Submitted for Ph.D. degree University College London L •, '' V. Thesis Abstract The animated films of Walt Disney have played an important role in American culture. Most Americans, either during childhood or adulthood, have been exposed to at least some of them. The films themselves have, in some respects, reflected American society and culture. They may also, at...»

«Angelica Zambrano 3rd Experience in Heaven & Hell Angelica, an Ecuadorian girl, shares the revelation she received from God of Heaven and Hell after a time of Prayer and Fasting. At this time I invite my loyal friend, the Holy Spirit, may He be the One who speaks through me and may it be Him who testifies about the experience He gave me. To be honest with you, I don’t want to speak about it. Do you want to know why I don’t want to speak about it? The reason is because within the church is...»

«SPRACHERWERB 03.11.2006 BEATE LINGNAU (UNIVERSITÄT-BIELEFELD) Spracherwerb Erwerbsreihenfolge  Säuglingsalter  Erwerbsreihenfolge ab dem ersten Lebensjahr – Lexikon/Semantik – Grammatik – Pragmatik Theorien zum Spracherwerb Cracking the speech code is childs „ play for human infants but an unsolved problem for adult theorists and our machines“ Kuhl 2004 Altersbezeichnungen  Schwangerschaft(vor der Geburt)  Säuglingsalter (bis ein Jahr)  Kleinkindalter (bis drei...»

«PORTLAND HARBOR RI/FS REMEDIAL INVESTIGATION REPORT DRAFT FINAL DO NOT QUOTE OR CITE This document is currently under review by US EPA and its federal, state, and tribal partners, and is subject to change in whole or in part. August 29, 2011 Prepared for The Lower Willamette Group Prepared by Integral Consulting Inc. Windward Environmental LLC Kennedy/Jenks Consultants Anchor QEA, LLC IC11-0001 RECOMMENDED FOR INCLUSION IN ADMINISTRATIVE RECORD LWG Portland Harbor RI/FS Draft Final Remedial...»

«International Conference on Contemporary Issues in Education 17 19 may 2015 / Dubai United Arab Emirates     Multicultural education for positive social change in Nigeria: the decision making and social action approach in the classroom Grace O. Abamba College of Education, Agbor; Delta State, Nigeria. mrsabambagrace@gmail.com. Abstract Nigeria is a multicultural society with over 250 ethnic groups and cultures with variations in socio-economic backgrounds, abilities and unequal opportunities....»

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