FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

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

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

-- [ 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 G 0, 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 View 0 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 + + are perfectly random. Let Exp1 [i] be the experiment when run under adversary C1 [i] and let View1 [i] be the random variable describing the view of adversary A when run in experiment Exp1 [i]. Then, for each 1 ≤ i ≤ n − 1, A cannot distinguish between View 1 [i] and View1 [i + 1] any better than with probability Adv prg (k ) for some adversary D who runs in the time needed G,D to run A.

+ + Next, consider a new adversary C0 which is defined as C0, just key( M1,..., Mn ) is replaced by a random string from {0, 1}k. Analogously define Exp0 and View0. Since G(·) is a pseudorandom generator, A cannot distinguish between the View 0 and View0 any better than with probability Advprg (k ).

G,D Analogous to the first sequence of hybrid adversaries, consider a sequence of adversaries C 0 [1],..., C0 [n]. Here C0 [1] = C0 and the i-th adversary C0 [i] is identical to C1 [i], except the value + + key( M1,..., Mn ) is replaced by a truly random string. Again define Exp0 [i] and View0 [i] as above. A similar argument shows that A cannot distinguish between View 0 [i] and View0 [i + 1] any better than with probability Advprg (k ). Finally, the experiments Exp0 [n] and Exp1 [n] are G,D identical so are View0 [n] and View1 [n]. This establishes a sequence of hybrids from View 0 to

View1 :

View0 ≈ View0 ≡ View0 [1] ≈... ≈ View0 [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 Adv prg (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, Boyen and Goh (see Section 4 of [BBG05]) (BBG − HIBE ) 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 BBG − HIBE. 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 G 1 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 [BBG05] for an exact definition.) Theorem D.1 Suppose the computational l + 1-BHDE assumptions holds in the group G 1.

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 [BBG05] for more details.

The proof of the theorem follows that of the BBG − HIBE scheme from [BBG05] 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 BBG − HIBE scheme).

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

Similar works:

«Online Interaction in Higher Education: Is There Evidence of Diminishing Returns? ) in OnlineCourses Jonatan Castaño-Muñoz, Teresa Sancho-Vinuesa, and Josep M. Duart Universitat Oberta de Catalunya (UOC), Spain Abstract Online interaction is considered to be a key aspect of effective e-learning and improved academic achievement. However, few studies have examined how effectiveness varies with the degree of interaction intensity. Using data for 17,090 students from three Catalan universities,...»

«Double-Resonance Studies on Compact, High-performance Rubidium Cell Frequency Standards Thejesh N. Bandi This thesis presents experimental studies on continuous-wave (CW) laser-microwave double-resonance (DR) spectroscopy and metrology in rubidium (87Rb) vapor cells in view of new high-performance, compact Rb-cell atomic clocks. Two different approaches were studied in this work; the wall-coated cell approach and the enlarged cell buffer gas cell approach. New magnetron-type cavity microwave...»

«Biscuit S Earth Day Celebration Biscuit S Holiday Celebrations The better mailing where owners are propelled to make says if us find your owner to sell what likes major to you. For just delegating start, they will make your pdf venture dream to sell whenever you is most unsecured of you to like now. A 24-hour cat over images, these Vimta OEM Handling Spanish cleantech Saudi job has the simple or prices through rich by amortization. The gps-enabled services can as work more, finding yourself...»

«2013 Herbal Extract Catalogue Lab Chemical Trading Company Herbal Extracts All the world's attention nowadays is focused on natural substances to help cure diseases instead of chemicals. Lab Chemicals Trading Company offers a wide variety of Chinese, Indian, and local Egyptian Herbal Extracts. If you didn't find the herbal extract you want, just inquire here ABCDEFGHIJKLMNOPQRSTUVWXYZ A Acacia Gum or Gum Arabic Acai Berry Extract Acerola Extract Aescin Aloe vera L. Extract Amygdalin...»

«ANIMATION The Phrasing of Action and Dialogue in an animated film By Eric Larson 1 Animation The Phrasing of Action and Dialogue PDF provided by www.animationmeat.com DRAWINGS THAT LIVE Acting is a recreation of emotions, and animation is acting! We must recognize both the validity of tradition and the necessity of exploration and discovery. We need a knowledge of the past and a basic and realistic understanding of the present, so that our creative energies can be fully geared towards our...»

«Anleitung Manual No 3034 HOT Hammer 2 1/10 XL SCALE READY TO RUN ELECTRIC POWERED RACE TRUGGY (BRUSHLESS VERSION) WATERPROOF mit 2,4 GHz 2-Kanal Fernsteueranlage with 2.4 GHZ 2-channel RC-transmitter mit 2,4 GHz 2-Kanal Fernsteueranlage with 2.4 GHZ 2-channel RC-transmitter www.maliracing.com INHALTSVERZEICHNIS 1. Einleitung 4 2. Hinweise zur Sicherheit 5 3. Produktbeschreibung 8 4. Das Modell startklar machen 9 5. Fahrbetrieb 12 6. SetUp 12 7. Wartung und Pflege 16 8. Entsorgungshinweise 18 9....»

«Why The Vasa Sank: 10 Lessons Learned Introduction Around 4:00 PM on August 10th, 1628 the warship Vasa set sail in Stockholm harbor on its maiden voyage as the newest ship in the Royal Swedish Navy. After sailing about 1300 meters, a light gust of wind caused the Vasa to heel over on its side. Water poured in through the gun portals and the ship sank with a loss of 53 lives. The Vasa lay in shallow waters of Stockholm harbor (at 32 meters depth) and after initial attempts to salvage it failed,...»

«Ministry of Education and Science of the Russian Federation Ural Federal University named after the first President of Russia B. N. Yeltsin The Institute of Public Administration and Entrepreneurship Russian society of sociologists Garold E. Zborovsky RUSSIAN SOCIOLOGY: ON THE WAY TO CIVIL SOCIETY Scientific monograph Ekaterinburg 2014 Министерство образования и науки Российской Федерации Уральский федеральный...»

«Abstract. Beszterda Ingeborga, Aspetti e tenderize riscontrabili nel repertorio linguistico italiano contemporaneo [Aspects and tendencies typical of the linguistic repertory in the modern Italian language]. Studia Romanica Posnaniensia, Adam Mickiewicz University Press, Poznań, vol. XXXIV: 2007, pp. 3-15. ISBN 978-83-232174-7-3, ISSN 0137-2475. The aim of this article is to discuss the fundamental features and the main avenues of the development of the modern Italian language. A great many...»

«RAM MANOHAR BASNET Biochemical correlates of synaptic plasticity in exercise Master’s thesis in Neuroscience August 2012 Preface This Master’s thesis was carried out at laboratory of synaptic plasticity, Centre for Molecular Biology and neuroscience, Department of Anatomy, IMB, University of Oslo. I am extremely grateful to Norwegian University of Science and Technology (NTNU) for providing me with the opportunity to study in Norway under quota scheme. Thanks to my principal supervisor...»

«MASSACHUSETTS MILITARY BASES Clean Energy Assessment and Strategic Plan for Massachusetts Military Installations MA Department of Energy Resources / MassDevelopment Date: December 17, 2014 Sponsored by: Project name: Massachusetts Military Bases DNV GL [Business Area] Report title: Clean Energy Assessment and Strategic Plan for [Unit/Division/Descriptor] Massachusetts Military Installations [Office Post 1] Customer: MA Department of Energy Resources / [Office Post 2] MassDevelopment [Address]...»

«ALM International Journal, Volume 1(1), pp. 36-56 Mathematical Autobiography Among College Learners in the United States Shandy Hauk Assistant Professor, Mathematics School of Mathematical Sciences University of Northern Colorado hauk@unco.edu Abstract This study examines the K-12 mathematical experiences of U.S. university students via an expressive writing assignment: a mathematical autobiography essay. The essays of 67 college students, out of over 300 enrolled in 16 sections of a college...»

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