FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

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

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

-- [ 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 (M 1,..., 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 (M 1,..., Mn ) it should be infeasible to forge an AOS signature on any message not having (M 1,..., 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 M n 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 SGN = (SGN.G, SGN.S, SGN.V) be any standard digital signature scheme. Construct an append-only signature scheme using SGN 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 SGN = (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 SGN 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 SGN, 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 SGN 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 SGN 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 SGN 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 SGN signatures, n SGN public keys, 1 SGN 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, ASGN = (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 ASGN, n public keys of ASGN, and one secret key of ASGN.

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] [1, 1] [0, 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:

«Medienkulturwissenschaft Kommentiertes Vorlesungsverzeichnis Veranstaltungen des Moduls „Ausgewählte Aspekte der Kulturwissenschaft“ Wintersemester 2012/2013 Inhaltsverzeichnis Vorbemerkung Modul „Ausgewählte Aspekte der Kulturwissenschaft“ Philologische Fakultät Seminar für klassische Philologie Die klassische Antike in der europäischen Literatur von 1945 bis heute Sprache und Kultur der Antiken Welt Romanisches Seminar PanoRomania – Die romanischen Sprachen im Überblick...»

«DRAFT CHAPTER 5 – WELLINGTON STREET AREA Municipal and educational buildings have shaped the character of the area covered in this chapter. From early nineteenth-century origins on Calderwood (originally William) Street, civic purposes spread to Wellington Street and Thomas Street, and then, in the 1970s, as far south as Grand Depot Road. A pair of houses of the 1760s still stands on Thomas Street, facing General Gordon Square, but concerted development of the area did not begin until soon...»

«THE SIGNIFICANCE OF RESPONSES OF THE GENOME TO CHALLENGE Nobel lecture, 8 December, 1983 by BARBARA McCLINTOCK Carnegie Institution of Washington Cold Spring Harbor Laboratory Cold Spring Harbor, New York, U.S.A. I. Introduction An experiment conducted in the mid-nineteen forties prepared me to expect unusual responses of a genome to challenges for which the genome is unprepared to meet in an orderly, programmed manner. In most known instances of this kind, the types of response were not...»

«Tutorials: Animation Autodesk® 3ds® Max 2010 Software © 2009 Autodesk, Inc. All rights reserved. Except as otherwise permitted by Autodesk, Inc., this publication, or parts thereof, may not be reproduced in any form, by any method, for any purpose. Certain materials included in this publication are reprinted with the permission of the copyright holder. The following are registered trademarks or trademarks of Autodesk, Inc., in the USA and other countries: 3DEC (design/logo), 3December,...»

«UNIVERSIDADE DA BEIRA INTERIOR Engenharia Discovery of Noun Semantic Relations based on Sentential Context Analysis Rumen Valentinov Moraliyski Tese para a obtenção do Grau de Doutor em Engenharia Informática (3º ciclo de estudos) Orientador: Prof. Doutor Gaël Harry Dias Covilhã, Fevereiro de 2013 ii The work on this dissertation was supported by the Programa Operacional Potencial Humano of the Quadro de Referência Estratégico Nacional, by the PhD grant SFRH/BD/19909/2004 of the...»

«SUUNTO AMBIT2 R 2.0 BENUTZERHANDBUCH 1 SICHERHEIT 2 Display-Unterteilung und -Symbole 3 Tastenfunktionen 3.1 Hintergrundbeleuchtung und Tastensperre verwenden 4 Erste Schritte 5 Anpassen Ihrer Suunto Ambit2 R 5.1 Mit Movescount verbinden 5.2 Aktualisierung Ihrer Suunto Ambit2 R 5.3 Benutzerdefinierte Sportmodi 5.4 Suunto Apps 5.5 Display umkehren 5.6 Display-Kontrast anpassen 6 Zeitmodus verwenden 6.1 Zeiteinstellungen ändern 6.2 GPS timekeeping verwenden 7 Timer-Funktionen 7.1 Stoppuhr...»

«Hans H. Bauer/Gregor Stokburger/Maik Hammerschmidt Marketing Performance Hans H. Bauer/Gregor Stokburger/ Maik Hammerschmidt Marketing Performance Messen – Analysieren – Optimieren Bibliografische Information Der Deutschen Bibliothek Die Deutsche Bibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.ddb.de abrufbar. Dieser Ausgabe liegt ein Post-it® Beileger der Firma 3M Deutschland GmbH bei....»

«Online versus Offline Booking: A comparative Investigation of the Trustworthiness of Tourism Distribution Channels for Flights and Holiday Packages Diplomarbeit zur Erlangung des Grades eines Diplom-Ökonomen der Wirtschaftswissenschaftlichen Fakultät der Leibniz Universität Hannover vorgelegt von Thomas Rose geboren am 04.10.1981 in Großburgwedel Erstprüfer: Prof. Dr. Michael H. Breitner Wedemark, den 06.07.2009 Contents List of Figures List of Abbreviations 1. Introduction 1.1. Motivation...»

«TWO WAYS OF MODULARIZATION STRATEGY IN JAPAN TOYOTA HONDA VS. NISSAN MAZDA Masayoshi IKEDA Yoichiro NAKAGAWA Today, as the end of the 20th century draws closer, European and US auto industries are several years ahead of Japanese counterpart in their effort for modularization. However, of all European and US automakers, the modularization effort made by the Big Three in the US is not so conspicuous, because of obstructions such as opposition from UAW. Meanwhile, German automakers are mainly...»

«http://zelot.org ©Перевод Е. Кузьмишина, 2003 http://zelot.org 2 ALBERT PIKE Wemyrm)u rpas ‫ספר הדברי‬ THE BOOK OF THE WORDS CHARLESTON А. М. 5792 ©Перевод Е. Кузьмишина, 2003 http://zelot.org 3 АЛЬБЕРТ ПАЙК КНИГА СЛОВ (СЕФЕР ХА-ДВАРИМ) ЧАРЛЬСТОН ©Перевод с английского, вступительная статья и примечания в тексте Е.Л. Кузьмишина, 2003...»

«Sicherheitsdatenblatt gemäß EU-Verordnung 1907/2006 Seite 1 von 5 Ausstellungsdatum : 16.03.2011 Ersatz für das Datenblatt vom : 04.02.2010 * Änderungen gegenüber Vorläufer, n.a. = nicht anwendbar, n.v. = nicht verfügbar 1 BEZEICHNUNG DES STOFFES BZW. DER ZUBEREITUNG UND DES UNTERNEHMENS 1.1 Bezeichnung des Stoffes oder der Zubereitung Handelsname : OTTO-O.A.S.E. organic.agro.superabsorbent.ecogranules Artikel Nr. : n.v. Rezeptur Nr. : n.v. Registriernummer : n.v. 1.2 Verwendung des...»

«1 The Antecedents and Consequences of Market Orientation in Australia by Sue Pulendran † Richard Speed † Robert E. Widing II § Abstract: The subject of market orientation has been of interest to both researchers and practitioners for several years. The work of Jaworski and Kohli (1993) inspired a substantial body of literature that empirically examined the antecedents and consequences of a market orientation. This article contributes to that body of literature by investigating the...»

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