FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 |   ...   | 4 | 5 ||

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

-- [ Page 6 ] --

We are left to show what happens when the AOSSign query M [1..n] contains M + [1..n+ ] as a prefix and n+ n. We know that signatures of all the prefixes of length smaller that n+ are correctly distributed. The recursive Extract oracle constructs Sig[M [1..n+ ]] and appends it using the SGN.Ssk (·) oracle. The signature Sig[M [1..n+ ]] has the form {pk 1, sig 1,..., pk n+, sig n+, sk n+ }, where pk n+ = pk and sk n+ = false. The input public key pk was generated by SGN.G(1k ) and thus pk n+ is correctly distributed. To append Sig[M [1..n+ ]] with Mn+ +1, Extract(·) computes (sk n+ +1, pk n+ +1 ) ← SGN.G(1k ), queries sig sk (Mn+ +1, pk n+ +1 ) and sets Sig[M [1..n+ + 1]] ← {pk 1, sig 1,..., pk n+ +1, sig n+ +1, sk n+ +1 }. This signature is correctly distributed and all the following signatures are constructed by appending this one using AOS.Append.

Proof of of Claim B.2: Let A terminate and output a forgery for M ∗ [1..n]. Without loss of generality we can assume that no prefix of M ∗ [1..n] is contained in MSGSet. Thus the target message M ∗ [1..n∗ ] must be different from all the AOSSign queries made by A. The previous claim established that A’s AOSSign queries are totally independent from the choice of M + [1..n+ ].

The index of the guessed message was uniformly chosen from [1..s]. If there exists an AOSSign query equal to M + [1..n+ ], then B declares Failure; otherwise A outputs message M ∗ [1..n∗ ] which must be different from all the AOSSign queries. Therefore the probability that B does not fail and that M ∗ [1..n∗ ] = M + [1..n+ ] is exactly 1/s.

–  –  –

Here Advxxx (k ) denotes the advantage of a (polynomially bounded) adversary B attacking the S,B xxx security of the primitive S, where xxx can be cr (collision resistance), 1-way (one-wayness), or prg (pseudorandomness). For a formal definition we refer the reader to the textbooks of Goldreich [Gol01, Gol04]).

We denote the original aos-uf-cma experiment played by A as Exp. Consider an arbitrary adversary A that is run in Exp. At the key-generation stage the challenger picks a random secret key key(ε), computes the values of key(·) on all the nodes in the graph T, and gives a public key key(˜) to A. The adversary outputs a forgery (M ∗ [1..t], Sig∗ ) and with probabilε ity Advaos-uf-cma (k ), A’s forgery is valid. Let u∗ = M1,..., Mt∗ and parse Sig∗ as the set ∗ AOS3,A {key∗ (x) | x ∈ {u∗ } ∪ Comp(u∗ )}. Let Desc(u∗ ) be the set {u∗ } ∪ Comp(u∗ ) including all their (lower) descendants in the graph T. Then the signature on u∗ defines key∗ (·) on the set Desc(u∗ ).

We define the event

–  –  –

i.e. key∗ (˜) = key(˜). We define KEYS as the event that key∗ (x) = key(x) on all x ∈ Desc(u∗ ) ε ε in experiment Exp. Then we have

–  –  –

Intuitively, we are going to show that in the first case there is an efficient attack on the pseudorandomness of G or the one-wayness of G0 or G1 and in the second case one can break collision-resistance of H, G0 or G1.

We will bound p1 and p2 in turn. First we bound p2. Note that ¬E means that there exists some x ∈ Desc(u∗ ) such that key∗ (x) = key(x). Hence FORGE ∧ ¬KEYS means that among the possible descendants x ∈ Desc(u∗ ) satisfying key∗ (x) = key(x), there must exist some x together with one of its children y, such that key∗ (x) = key(x) but key∗ (y) = key(y) (since we require key∗ (˜) = key(˜)).

ε ε Consider the following adversary B (attacking the collision resistance of G0, G1 or H) that runs the aos-uf-cma experiment for A. B picks a random secret key key(ε), recursively computes key(x) for all nodes x in the graph T, and returns the public key key(˜) to A. The input of ε A is distributed identically to the experiment Expaos-uf-cma (k ). Thus with probability p2, A AOS3,A outputs a valid forgery {key∗ (x) | x ∈ {u∗ } ∪ Comp(u∗ )} for some node u∗ ∈ U T such that there exists a node x ∈ T (x is some descendant x of {u∗ } ∪ Comp(u∗ )) and its child y such that key∗ (x) = key(x) but key∗ (y) = key(y). Such an x can be identified by B in the same time as verifying a signature. If x ∈ U T then {key∗ (x), key(x)} is a collision either for G0 or G1 (Gi (key∗ (x)) = Gi (key(x)) for some i ∈ {0, 1}). Otherwise let x′ be another parent of y, then H(key∗ (x), key∗ (x′ )) = H(key(x), key(x′ )) and {(key∗ (x), key∗ (x′ )), (key(x), key(x′ ))} is a collision for H(·, ·). Therefore p2 ≤ Advcr (k ) + Advcr0,B (k ) + Advcr1,B (k ).

H,B G G We now proceed to bound p1. First consider a single adversary C0 participating in the oneway experiments for both G0 and G1 simultaneously. The adversary C0 will run A and in the case A successfully forges AOS3, she will win in either one of the experiments (that is, finding a preimage for G0 or G1 of a given input value C). Second, consider an adversary C1 participating in the same oneway experiment and that only slightly differs from the description of adversary C0. The adversary C1 will be used to bound probability p1.

Finally, using a hybrid argument, we will connect the two adversaries by showing that the views of adversary A when run by C0 and C1 in the execution of the experiment are computational indistinguishable assuming G is a pseudorandom generator.

We describe the two adversaries C0 and C1 as follows:

Adversary Ci (1k, c):

$ key(ε) ← {0, 1}k and define key(·) recursively on all the descendants.

+$ + Pick a random node u+ = M1,..., Mn ← U T \ {ε} ∪ {d-th level of LT }.

+ ) ← c else do nothing if i = 0 then redefine key(u

Run A(1k, key(˜)) and answer all the Sign(M [1..t]) queries made by A as follows:

ε if (M [1..t] = M + [1..t]) and (t n) then return abort.

else set u = M1,..., Mt ; return Sig = {key(x) | x ∈ {u} ∪ Comp(u)}.

Eventually A terminates and outputs a forgery Sig∗ for some message M ∗ [1..t].

Denote M1,..., Mt∗ as u∗ ; parse Sig∗ as {key∗ (x) | x ∈ u∗ ∪ Comp(u∗ )}.

∗ if M ∗ [1..t] = M + [1..n − 1] then return key∗ (u∗ ) else return abort.

For i ∈ {0, 1} denote by Expi the simultaneous oneway experiment when run under adversary Ci. We define the two events ABORTCi :Adversary Ci aborts in experiment Expi KEYSCi :key∗ (x) = key(x) for all x ∈ Desc(u∗ ) in experiment Expi Furthermore, we define the two probabilities

–  –  –

in experiment Expi. Intuitively, in the remainder of the proof we will show that the value q0 is related to the onewayness of G0 and G1, that q1 can be lower bounded using p1, and that |q0 − q1 | is small.

Consider the experiment Exp0. Assuming C0 does not abort, u+ is a child of u∗ and hence we have GMn (key∗ (u∗ )) = key(u+ ) = c if the event KEYSC0 happens. Hence adversary C0 outputs +

–  –  –

in experiment Exp0. We will now lower bound probability q1 in experiment Exp1.

Claim C.1 q1 ≥ p1 /(3 · 2d ).

We rewrite q1 as q1 = Pr [ KEYSC1 | ¬ABORTC1 ] · Pr[ ¬ABORTC1 ].

The event ¬ABORTC1 in Exp1 happens if and only if the right value for u+ was guessed by C1, i.e. if u+ is a child of u∗. Hence, assuming C1 does not abort, the view of A in experiment Exp1 is identically distributed to the view of A the experiment Exp. Hence with probability at least p1, A outputs a valid forgery (u∗, Sig∗ ) such that key∗ (x) = key(x) on all descendants

x ∈ Desc(u∗ ) in Exp1 :

–  –  –

Since the choice of u+ in the experiment Exp1 is totally independent from the inputs of A (and u+ is chosen randomly from the set of 3 · 2d − 2 nodes), we have

–  –  –

This completes the proof of the claim.

For i ∈ {0, 1} define Viewi to be the view of adversary A in experiment Expi. The following lemma establishes that the views of A in the experiments Exp0 and Exp1 are computationally indistinguishable.

Lemma C.2 A cannot distinguish between the two distributions View0 and View1 better than with probability 2d · Advprg (k ) for some adversary D running in about the same time as A.

G,D We will prove the lemma later. As an implication of Lemma C.2 we get that |q0 − q1 | ≤ 2d · Advprg (k ). Thus G,D

–  –  –

In Exp1, key(ε) is chosen at random and the keys on the rest of R is generated by iterating G(·).

On the other hand, in Exp0 the values of key(·) on R are defined in the same way except for + + key( M1,..., Mn ), which is replaced by the challenge string for the onewayness experiment.

Our goal is to show that from adversary A’s view, these two experiments are computational indistinguishable.

We define a sequence of n hybrid adversaries C1 [1],..., C1 [n] as follows: Let C1 [1] = C1 and the i-th adversary C1 [i] behaves like C1 except that it assigns random keys key(·) on the nodes + + + + + { M1,..., Mj, M1,..., Mj−1, ¬Mj | j = 1,..., i} and uses G(·) to compute key(·) on the rest of the nodes. The only difference between adversaries C1 [i] and C1 [i + 1] is that in the first case key( M1,..., Mi+ ), key( M1,..., ¬Mi+ ) are pseudorandom and in the second case they + +

–  –  –

View0 ≈ View′ ≡ View′ [1] ≈... ≈ View′ [n] ≡ View1 [n] ≈... ≈ View1 [1] ≡ View1, where ≈ means that the distributions of the two random variables are computational indistinguishable and ≡ means they are identical. A cannot distinguish between any consecutive pair of the views any better than with probability Advprg (k ), therefore total probability that A will G,D distinguish between View0 and View1 is no more than 2n · Advprg (k ) ≤ 2d · Advprg (k ).

G,D G,D D AOS with short key size In this section we review the hybrid HIBE scheme from Boneh, Goh and Boyen (see Section 4 of [BGB05]) (B G B − H IBE ) achieving short private keys. By the results from Section 4 we know that a HIBE scheme implies an AOS scheme. Motivated by this reduction, we present a concrete AOS scheme (called AOS2 ) based on BG B − H IBE. In presenting the concrete scheme, we are able to make some (straightforward) efficiency improvements over the generic reduction by making the AOS verification algorithm deterministic (instead of probabilistic).

The main intention of this section is to demonstrate that AOS (and hence also HIBS) can be carried out with secret key size of order “square root of the length of the signed message”.

We briefly review the necessary facts about bilinear maps and bilinear groups. Let G1 and G2 be groups with the following properties.

• G1 is an additive groups of prime order q.

–  –  –

We have stipulated that our groups should have a bilinear map e : G1 × G1 → G2. This should satisfy the conditions below.

Bilinear: For all U, V ∈ G1, a, b ∈ Z, e(aU, bV ) = e(U, V )ab Non-degenerate: e(P, P ) = 1G2

–  –  –

We denote the induced index mapping as π : {1,..., d} → {1,..., l} × {1,..., l} with π(n) = (n1, n2 ). Here n1 is called the row index and n2 the column index.

We may now describe AOS2 = (AOS.Setup, AOS.Append, AOS.Vfy) giving its constituting algorithms.

• AOS.Setup(1k ): Pick two random generators P, Q ∈ G1 and a random element α ∈ Zq.

Next, pick random elements G1,..., Gl and H1,..., Hl ∈ G1. The public key consists of

–  –  –

In this case we have π(n) = (n1, 1) and to generate a signature for the message M [1..n] chose a random r ∈ Zq and compute Sig[M [1..n]] as

–  –  –

The length of the signature of AOS2 grows linearly with the square root of the length of the message. Security is proved with respect to the l + 1-Bilinear Diffie-Hellman Exponent (BDHE) assumption. (See [BGB05] for an exact definition.) Theorem D.1 Suppose the computational l + 1-BHDE assumptions holds in the group G1.

Then the AOS2 scheme is selective message aos-uf-cma secure.

Here selective message aos-uf-cma security is defined similar to Definition 2.1. The difference is that in the security experiment, the adversary has to commit to the message she is going to forge the signature for before the public/secret keys are issued and the public key is given to her. In the random oracle model, the scheme can be modified to get a full unforgeable AOS scheme. However, the security reduction is not tight and only allows for signatures on messages of constant length. Again, we refer the reader to [BGB05] for more details.

The proof of the theorem follows that of the BG B − H IBE scheme from [BGB05] and is omitted here. We note that since we are dealing with signatures instead of encryption, we can prove security of our scheme with respect to a computational assumption (rather than a decisional assumption as the original BG B − H IBE scheme).

Pages:     | 1 |   ...   | 4 | 5 ||

Similar works:

«CAHKT -TIETEPEyprCKlIII1 rOCYJlA PCTB EHHbII1 YHlII B EPClIITET Ha npaeQX pYKonucu lI\EPlAK HlIIIa leJIlII(COBH3 AHAJIM3 CTPYKTYPHO-CEMAHTfflIECKOfr MOJ(EJIM Cl1TYAU,l1l1 C JIOKATl1ll0M HOME (Ha MaTCpnaJJC aHrJlOH3hPIHhIX TCKCTOB) 10.02.04. Clleql1aJlhHOCTb: fepMaHCII1e }l3bIKH llaYI.JuLIM PYKOBO)l,MTCJIL: )l,OKTOP q-mJIOJIOrHI.JCCKHX uaYK, E. llpocpeccop XOM}\KOHa f. CalIKT-lIcTcp6ypr Содержание Введение.. 4 Глава 1. Локатив home в русле...»

«The magazine for members of the 1100 Club www.the1100club.com Idle Chatter November December 2010 YOUR CLUB Your Committee HONORARY PRESIDENT Allan Webb Committee Officials CHAIRMAN GENERAL SECRETARY MEMBERSHIP SECRETARY Chris Bryant David Wilkins Koren Maddison 145 Penmere Drive 61 Ambleside Road,Lightwater 29 Grafton Way, West Molesey Newquay Cornwall TR7 1NS Surrey GU18 5UH Surrey. KT8 2NW chairman@the1100club.com membership@the1100club.com general-secretary@the1100club.com CLUB HISTORIAN...»

«Deutscher Bundestag 17/956 Drucksache 17. Wahlperiode 05. 03. 2010 Kleine Anfrage der Abgeordneten Sevim Dag˘ delen, Dr. Diether Dehm, Jan van Aken, Annette Groth, Inge Höger, Andrej Hunko, Harald Koch, Niema Movassat und der Fraktion DIE LINKE. Deutsche Positionen zur Ausgestaltung des Europäischen Auswärtigen Dienstes Der Vertrag von Lissabon, der nach Angaben der Bundesregierung die Europäische Union (EU) „handlungsfähiger, transparenter und demokratischer“ machen sollte, trat am...»

«1 Limnogeology Division Newsletter Volume 11, Number 1 October 2013 Limnogeology Division Officers and Management Board Amy Myrbo Chair LacCore / Limnological Research Center, Department of Geology and Geophysics, University of Minnesota, 500 Pillsbury Dr SE, Minneapolis, MN 55455 (612) 626-7889 (direct) (612) 626-7750 (fax) amyrbo@umn.edu Johan C. Varecamp Vice-Chair Dept. of Earth & Environmental Sciences, Wesleyan University 45 Wyllys Avenue, Middletown, CT 06459 (860) 685-2248 (direct)...»

«gold unze preis gold unze preis Gold Verkauf Preis Sie suchen ein Gold verkauf preis Sie suchen ein Gold verkauf preis Sparen Sie Geld auf GigaGünstig. 1 Unze Gold Kaufen Such 1 Unze Gold Kaufen. Such 1 Unze Gold Kaufen. Ergebnisse von 6 Suchmaschinen! 1 Unze Philharmoniker Schneller sicherer Versand. Schneller sicherer Versand. Auch per Barzahlung und Nachnahme. In Gold Investieren | GMX.net Top-Infos: In Gold Investieren sofort alles herausfinden! Goldpreis Rechner | Berechnen Sie den...»

«Ancient Sunrise® Henna for Hair, Chapter 5, Plants that Dye Hair Copyright © 2015 Catherine Cartwright-Jones Cover Graphic by Alex Morgan Published by TapDancing Lizard® LLC 339 Tallmadge Rd. Kent, Ohio, 44240 Terms of Service: Creative Commons: Attribution-NonCommercial-NoDerivs 3.0 Unported You are free to Share, to copy and redistribute this material in any medium or format under the following terms. The licensor cannot revoke these freedoms as long as you follow the license terms....»

«MASARYK-UNIVERSITÄT PÄDAGOGISCHE FAKULTÄT Lehrstuhl für deutsche Sprache und Literatur Kirsten Boie und ihr kinderund jugendliterarisches Werk Diplomarbeit Brünn 2008 Betreuerin: PhDr. Jana Baroková, Ph.D. Verfasserin: Gabriela Pichaničová Erklärung Hiermit erkläre ich, dass ich die vorliegende Diplomarbeit selbständig verfasst habe und nur die angegebenen Quellen und Hilfsmittel benutzt habe. Ich bin damit einverstanden, dass meine Diplomarbeit in der Bibliothek der Pädagogischen...»

«Flavia Adani’s Curriculum Vitæ Prof. Dr. Flavia ADANI Curriculum Vitæ January, 2016 CONTACT INFORMATION Address: University of Potsdam Excellent Center for Cognitive Science Linguistic Department Karl-Liebknecht-Straße 24-25 14476 Potsdam Phone: +49 331 977 2639 E-mail: Flavia DOT adani AT uni MINUS potsdam DOT de Web-site: www.uni-potsdam.de/aladdin PERSONAL Born on 13.05.1978 in Modena (Italy), married, two children. EMPLOYEMENT 2010-to date Department of Linguistics, University of...»

«ASPCA Guide To Pet Care I are new name by why to guarantee their accident and be the foreign place night ASPCA Guide to Pet Care today of Hong. Of a income energy unlocks to have for your passionate asset if lack, phase fees will try colored. Likely see up the consumption of your nothing things. Mean out a great great loan during your payment event can keep. Without he make the call and house, apply a most you can lessen. This markets of that price urbanization over an annual assets that the...»

«INOR 1 Investigating the oxidation of olefins using derivatives of the non-heme iron catalyst [Fe(BPMEN)](OTf)2] Claire A. Lidston1, Claire.A.Lidston@williams.edu, Matthew R. Davies1, Robert D. Pike2, Christopher Goh1, cgoh@williams.edu. (1) Dept of Chemistry, Williams College, Williamstown, Massachusetts, United States (2) Colg of William Mary, Williamsburg, Virginia, United States The complex [Fe(BPMEN)](OTf)2 (N,N‘-bis(2-pyridylmethyl)-1,2-diaminoethane) has been established as a highly...»

«Unit Support Notes — Travel and Tourism: Scotland (National 5) This document may be reproduced in whole or in part for educational purposes provided that no profit is derived from reproduction and that, if reproduced in part, the source is acknowledged. Additional copies of these Unit Support Notes can be downloaded from SQA’s website: www.sqa.org.uk. Please refer to the note of changes at the end of this document for details of changes from previous version (where applicable). © Scottish...»

«® Parallels Panel Copyright-Vermerk Parallels Holdings, Ltd. c/o Parallels International GmbH Vordergasse 59 CH-Schaffhausen Schweiz Tel.: +41-526320-411 Fax: +41-52672-2010 Copyright © 1999-2011 Parallels Holdings, Ltd. und Tochterunternehmen. Alle Rechte vorbehalten. Dieses Produkt ist durch US-amerikanische und internationale Urheberrechtsgesetze geschützt. Die dem Produkt zugrunde liegenden Technologien, Patente und Warenzeichen werden unter folgendem Link aufgelistet:...»

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