WWW.ABSTRACT.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Abstract, dissertation, book
 
<< HOME
CONTACTS



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 5 ] --

In Tatsuaki Okamoto, editor, Advances in Cryptology – ASIACRYPT 2000, volume 1976 of Lecture Notes in Computer Science, pages 116–129, Kyoto, Japan, December 3–7, 2000. Springer-Verlag, Berlin, Germany.

[BB04] Dan Boneh and Xavier Boyen. Efficient selective-id secure identity based encryption without random oracles. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology – EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 223–238, Interlaken, Switzerland, May 2–6, 2004. Springer-Verlag, Berlin, Germany.

[BBG05] D. Boneh, X. Boyen, and E.-J. Goh. Hierarchical identity based encryption with constant size ciphertext. In Ronald Cramer, editor, Advances in Cryptology – EUROCRYPT 2005, Lecture Notes in Computer Science, page ???? Springer-Verlag, Berlin, Germany, May 22–26, 2005.

[BF03] Dan Boneh and Matthew K. Franklin. Identity based encryption from the Weil pairing. SIAM Journal on Computing, 32(3):586–615, 2003.

[BGG94] Mihir Bellare, Oded Goldreich, and Shafi Goldwasser. Incremental cryptography the case of hashing and signing. In Yvo Desmedt, editor, Advances in Cryptology – CRYPTO’94, pages 57–66. Springer-Verlag, Berlin, Germany, August 21–25, 1994.

[BGG95] Mihir Bellare, Oded Goldreich, and Shafi Goldwasser. Incremental cryptography and application to virus protection. In 27th Annual ACM Symposium on Theory of Computing, pages 57–66, Las Vegas, Nevada, USA, May 29 – June 1, 1995. ACM Press.

[BGLS03] Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In Eli Biham, editor, Advances in Cryptology – EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages 416–432, Warsaw, Poland, May 4–8, 2003. Springer-Verlag, Berlin, Germany.

[BM96] Daniel Bleichenbacher and Ueli M. Maurer. Optimal tree-based one-time digital signature schemes. In STACS ’96: Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, pages 363–374. Springer-Verlag, 1996.

[BM99] Mihir Bellare and Sara Miner. A forward-secure digital signature scheme. In Michael J. Wiener, editor, Advances in Cryptology – CRYPTO’99, volume 1666 of Lecture Notes in Computer Science, pages 431–448, Santa Barbara, CA, USA, August 15–19, 1999. Springer-Verlag, Berlin, Germany.

[CHK03] Ran Canetti, Shai Halevi, and Jonathan Katz. A forward-secure public-key encryption scheme. In Eli Biham, editor, Advances in Cryptology – EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages 255–271, Warsaw, Poland, May 4–8, 2003. Springer-Verlag, Berlin, Germany.

[CHYC04] S. S. M. Chow, L. C. K. Hui, S. M. Yiu, and K. P. Chow. Secure hierarchical identity based signature and its application. In Proceedings of ICICS 2004, pages 480–494, 2004.

[FCC+ 03] Yun Fu, Jeffrey Chase, Brent Chun, Stephen Schwab, and Amin Vahdat. SHARP: an architecture for secure resource peering. In Proceedings of the 19th ACM Symposium on Operating System Principles (SOSP), Bolton Landing, NY, October 2003.

[Gol01] Oded Goldreich. Foundations of Cryptography: Basic Tools, volume 1. Cambridge University Press, Cambridge, UK, 2001.

[Gol04] Oded Goldreich. Foundations of Cryptography: Basic Applications, volume 2. Cambridge University Press, Cambridge, UK, 2004.

[GS02] C. Gentry and A. Silverberg. Hierarchical id-based cryptography. In Yuliang Zheng, editor, Advances in Cryptology – ASIACRYPT 2002, volume 2501 of Lecture Notes in Computer Science, pages 548–566, Queenstown, New Zealand, December 1–5,

2002. Springer-Verlag, Berlin, Germany.

[HM02] A. Hevia and D. Micciancio. The provable security of graph-based one-time signatures and extensions to algebraic signature schemes. In Yuliang Zheng, editor, Advances in Cryptology – ASIACRYPT 2002, volume 2501 of Lecture Notes in Computer Science, pages 379 – 396, Queenstown, New Zealand, December 1–5, 2002.

Springer-Verlag, Berlin, Germany.

[HPS04] Yih-Chun Hu, Adrian Perrig, and Marvin Sirbu. SPV: secure path vector routing for securing BGP. In Proceedings of the ACM SIGCOMM Conference, pages 179–192, 2004.

[JMSW02] Robert Johnson, David Molnar, Dawn Xiaodong Song, and David Wagner. Homomorphic signature schemes. In Bart Preneel, editor, Topics in Cryptology – CTRSA 2002, volume 2271 of Lecture Notes in Computer Science, pages 244–262, San Jose, CA, USA, February 18–22, 2002. Springer-Verlag, Berlin, Germany.

[KLS00] Stephen Kent, Charles Lynn, and Karen Seo. Secure border gateway protocol (SBGP). IEEE Journal on Selected Areas in Communications, 18(4):582–592, 2000.

[LMRS04] Anna Lysyanskaya, Silvio Micali, Leonid Reyzin, and Hovav Shacham. Sequential aggregate signatures from trapdoor permutations. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology – EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 74–90, Interlaken, Switzerland, May 2–6,

2004. Springer-Verlag, Berlin, Germany.

[Mer88] Ralph C. Merkle. A digital signature based on a conventional encryption function.

In Carl Pomerance, editor, Advances in Cryptology – CRYPTO’87, volume 293 of Lecture Notes in Computer Science, pages 369–378, Santa Barbara, CA, USA, August 16–20, 1988. Springer-Verlag, Berlin, Germany.

[MOR01] Silvio Micali, Kazuo Ohta, and Leonid Reyzin. Accountable-subgroup multisignatures. In ACM CCS 01: 8th Conference on Computer and Communications Security, pages 245–254, Philadelphia, PA, USA, November 5–8, 2001. ACM Press.





[MR02] Silvio Micali and Ronald L. Rivest. Transitive signature schemes. In Bart Preneel, editor, Topics in Cryptology – CT-RSA 2002, volume 2271 of Lecture Notes in Computer Science, pages 236–243, San Jose, CA, USA, February 18–22, 2002.

Springer-Verlag, Berlin, Germany.

[Rom90] John Rompel. One-way functions are necessary and sufficient for secure signatures.

In 22nd Annual ACM Symposium on Theory of Computing, pages 387–394, Baltimore, Maryland, USA, May 14–16, 1990. ACM Press.

[RR02] Leonid Reyzin and Natan Reyzin. Better than biba: Short one-time signatures with fast signing and verifying. In Proceedings of 7th Australasian Conference ACSIP, 2002.

[Sha85] Adi Shamir. Identity-based cryptosystems and signature schemes. In G. R. Blakley and David Chaum, editors, Advances in Cryptology – CRYPTO’84, volume 196 of Lecture Notes in Computer Science, pages 47–53, Santa Barbara, CA, USA, August 19–23, 1985. Springer-Verlag, Berlin, Germany.

[SRS+ 04] Lakshminarayanan Subramanian, Volker Roth, Ion Stoica, Scott Shenker, and Randy Katz. Listen and whisper: Security mechanisms for bgp. In Proceedings of USENIX/ACM NSDI, 2004.

[WKvO05] Tao Wan, Evangelos Kranakis, and P.C. van Oorschot. Pretty secure BGP (psBGP).

In Proceedings of ISOC NDSS, 2005.

A Public Key Signature Schemes

A public key signature scheme SGN = (SGN.G, SGN.S, SGN.V) is a collection of three algorithms:

a key generation algorithm SGN.G, a signing algorithm SGN.S, and a verification algorithm SGN.V. These algorithms must be polynomial time in the security parameter and should have

the following input/output specification:

• SGN.G takes as input the security parameter 1k and outputs a secret key/public key pair (sk, pk ). The public key also includes some system parameters like the description of the message space SGN.MSpace.

• SGN.S takes as input a message M ∈ SGN.MSpace and produces a string sig which is called a signature of a message M.

• SGN.V takes as input a public key pk, a message M and a signature sig and returns either true or false.

The verification algorithm must accept all signatures produced by the signing algorithm, namely the following should hold for every (sk, pk ) produced by SGN.G(k ), every message M ∈ SGN.MSpace

and every choice of random coins:

–  –  –

Next we define unforgeability under chosen message attacks (sig-uf-cma) for a signature scheme.

Definition A.1 [SIG-UF-CMA] Let SGN be a signature scheme, let k be a security parameter,

and let A be an adversary. We consider the following experiment:

–  –  –

Signature scheme SGN is said to be unforgeable under chosen message attacks (sig-uf-cma) if the above advantage is negligible function in k for all polynomial-time adversaries A.

B Proof of Theorem 3.1 We show that for any adversary A against AOS1, there exists an adversary B against SGN running in about the same time as A such that Advaos-uf-cma (k ) ≤ s · Advsig-uf-cma (k ).

AOS1,A SGN,B The reduction factor s is the upper bound on the number of messages M for which Sig[M ] is defined by the Extract(·) oracle in the experiment Expforge-cma (k ). This bound should be AOS1,A known by B before she runs the simulation of A and the bound should hold for any choice of the public key, for any random coins of A and for any oracle responses. The number s could be also upper bounded by qe · d, where qe is the maximal number of AOSSign(·) queries made by A and d is the maximal length of the queries.

Now we proceed to the construction of adversary B who attacks the unforgeability of the public key signature scheme SGN. In the sig-uf-cma experiment the challenger runs a key generation algorithm SGN.G(1k ) to get a pair of keys (sk, pk ) and gives pk as input to B as well as an access to the SGN.Ssk (·) oracle.

During its execution B will construct a set T that at each moment of time will contain all the messages M for which Sig[M ] is already defined by Extract(·). This set plays the same role as in the original aos-uf-cma experiment. The only difference is that now, for each message M [1..n] ∈ T, we will keep not only a signature Sig[M [1..n]] but also a pair of elements (sk M [1..n], pk M [1..n] ). The latter will correspond to the secret key/public key pair for SGN generated by Extract(·) oracle when computing the signature for M [1..n]. The pseudocode

for the adversary B is given below:

–  –  –

At a high level, the adversary B works as follows. Before running A, it randomly selects an $ integer guess ← [1..s] which corresponds to an index of some message that will be queried to the Extract(·) oracle. Note that all messages are selected by A, so B does not know in advance the actual message M + [1..n+ ]. (It is defined only at the time when guess-th new message is queried to Extract(·).) Next, B runs A and simulates the AOSSign(·) oracle. B follows the protocol of the original oracle to compute signatures of all the messages that do not contain the guessed one as a prefix. For the guessed message M + [1..n+ ], the adversary B sets pk M + [1..n+ ] to be equal to the input public key pk and sk M + [1..n+ ] ← false. Therefore, if A queries the guessed message to the AOSSign oracle, B declares Failure since she does not know the secret key sk which corresponds to pk. However, B still can correctly answer all the AOSSign queries that contain M + [1..n+ ] as a prefix by using the SGN.Ssk (·) oracle that is given by the Expsig-uf-cma experiment. Also, since Extract(·) is recursive, any message is added to T only after all its prefixes are already in T.

Let A terminate and output a forgery of a message M ∗ [1..n]. B assumes that the forgery is valid and that her guessed message M + [1..n+ ] is equal to the prefix M ∗ [1..n∗ ] of the forged message. M ∗ [1..n∗ ] is the longest prefix of M ∗ [1..n] such that all the public keys pk ∗,... pk ∗ + 1 n from the signature Sig∗ match the stored public keys pk M ∗ [1],... pk M ∗ [1..n+ ]. In this case, B can easily make a forgery for SGN : if n+ n∗ then sign+ +1 is a forgery for SGN, otherwise (if ∗ + = n∗ ) the secret key sk ∗ should match the unknown secret key sk.

n n Next we bound the advantage of B. There are several events in the experiment we must consider.

FAIL : B does output Failure.

Without loss of generality, we can assume that if B does not fail then A always outputs a forgery Sig∗ for some message M ∗ [1..n] and that no prefix of M ∗ [1..n] was queried to AOSSign(·) (if this does not hold, A automatically loses). The second event is defined as

–  –  –

that is, AOS.Vfy(AOS.pk, Sig∗, M ∗ [1..n]) = 1. This event is defined only if B does not fail.

Finally, we consider random variables M + [1..n+ ] and M ∗ [1..n∗ ]. The former random variable, M + [1..n+ ], corresponds to a message, whose signature was defined at the time when B sets guess = ctr. If no such query was made, we set M + [1..n+ ] ← ⊥. The latter random variable, M ∗ [1..n∗ ], corresponds to the “good” prefix of the forgery M ∗ [1..n] returned by A. It is defined only if B does not fail. We define GUESS to be the event that B guesses the message A outputs

a forgery on:

GUESS : M + [1..n+ ] = M ∗ [1..n∗ ].

We observe that if B does not fail, A wins and the guess is correct; B then outputs a valid forgery of the signature scheme SGN. Therefore

–  –  –

The analysis is based on the following two claims. The first claim establishes that if B guessed the right value for M + [1..n+ ] and B does not output failure then the simulation of A is perfect and we have

–  –  –

It is left to show (3): that if B does not return Failure then the input of A is identically distributed to the original aos-uf-cma experiment.

First, from the construction of B we see that the claim is true for messages that do not contain the guessed message M + [1..n+ ] as a prefix. In this case, the Extract oracle uses the AOS.Append algorithm of AOS1 to append the signatures and therefore all signatures are distributed identically to the ones constructed by the Extract oracle in the original aos-uf-cma experiment.

In the case when A queries M [1..n] = M + [1..n+ ] to the AOSSign(·) oracle, the AOSSign(·) oracle calls Extract(M + [1..n+ ]) to get Sig[M + [1..n+ ]]. The signature Sig[M + [1..n+ ]] returned by the Extract oracle to has a form {pk 1, sig 1,..., pk n+, sig n+, sk n+ }, where sk n+ = false and B declares Failure on such a query.



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


Similar works:

«“Alan Turing Centenary Year India Celebrations” 3-Day Faculty Development Program on “Alan M. Turing – Simplification in Intelligent Computing Theory and Algorithms” Organized by Foundation for Advancement of Education and Research In association with Computer Society of India Division II [Software] NASSCOM, IFIP TC 1 & TC -2, ACM India Council Co-sponsored by P.E.S Institute of Technology Venue PES Institute of Technology, Hoskerehalli, Bangalore Date : 18 20 December 2012 Compiled...»

«Stichproben. Wiener Zeitschrift für kritische Afrikastudien. Nr. 7/2004, 4. Jg.Roots, Rights and Responsibilities: Place-making and Repatriation among Somalis in Denmark and Somaliland Mette Fink-Nielsen, Peter Hansen & Nauja Kleist Abstract How do Somalis residing in Denmark and repatriated Somalis in Somaliland understand the questions of repatriation, home and belonging? Which livelihood strategies and strategies of mobility do they deploy? How are the places of exile and homeland...»

«    The Use of the Anecdote in the Critical Study of Aboriginal Literature A Project submitted to the College of Graduate Studies and Research in Partial Fulfillment of the Requirements for the Degree of Masters of Arts in the Department of English University of Saskatchewan Saskatoon By Robyn Moore Copyright, Robyn Moore, November 2009. All Rights Reserved.     PERMISSION TO USE In presenting this thesis/dissertation in partial fulfillment of the requirements for a Postgraduate degree from...»

«Blood On Both Sides Flights Of Fantasy You comes offered on the Atlanta prep growth may have 5 Security cosmetics of the distribution that 566, a setting in actually 19 approval of a location estate of 60. Pay the home invitation pdf of every topic as the financial cargo. Free consolidation into the use should, very is the candidate to that the financial end must add entitled. A spouse may be pdf over from the Ovens renewal. Questions need other to learn it not also at a high possible talent as...»

«Playful Performers April 9–December 12, 2004 Playful Performers celebrates the ingenuity of African children as they explore, through playful activity, the world of masquerade performance. The aesthetic power and mystery of masquerade inspire children as young as five years of age to imitate adult masked dancers or to create their own masks, costumes and dances that they perform to the delight of youngsters and adults alike. This exhibition highlights the rich diversity of childhood...»

«EUROPEAN COMMISSION Brussels, XXX SANCO/2012/11820 [.](2012) XXX draft Proposal for a REGULATION OF THE EUROPEAN PARLIAMENT AND OF THE COUNCIL on the marketing and production, with a view to marketing, of plant reproductive material, and repealing Council Directives 66/401/EEC, 66/402/EEC, 68/193/EC, 1998/56/EC, 1999/105/EC, 2002/53/EC, 2002/54/EC, 2002/55/EC, 2002/56/EC, 2002/57/EC, 2008/72/EC and 2008/90/EC (Text with EEA relevance) EN EN EXPLANATORY MEMORANDUM 1. CONTEXT OF THE PROPOSAL...»

«RETRIEVERS (LABRADOR) SWEEPSTAKES Judge: Mr. Greg Lynch PUPPY SWEEPSTAKES RETRIEVERS, (LABRADOR). Sweepstakes, 6 to 9 Months Dogs. _ 1st (112) Sunchase Ania's Octave. Owner: Anna Hausmann & Yoshi Tanaka 2nd (102) Huckleberry's Dolla Dolla. Owner: Tina & Paul Jewett 3rd (111) Devanley's James P. Sullivan. Owner: Judy & Mark Segedi 4th (104) Black Rock Sho-N-Tail Spitting Image. Owner: Susan K. Burton RETRIEVERS, (LABRADOR). Sweepstakes, 9 to 12 Months Dogs. _ 1st (119) Belledin's Moose Tracks....»

«INTERNATIONAL ASSOCIATION FOR LADAKH STUDIES LADAKH STUDIES _ 15, August 2001 CONTENTS Editorial News from the Association: From the Hon. Sec.News from Ladakh: Special reports: Skushok Bakula Receives Important Mongolian Award, by Tashi Morup Another Dry Winter, by Seb Mankelow The End of the Chaddar? by Seb Mankelow Pant Finds Near-Unanimous Support for UT, by Tashi Morup 20 Killed in Leh Road Mishap Shelling Resumes in Kargil Articles: Dry Winters, Dry Summers: Water Shortages in Zangskar...»

«Научный журнал КубГАУ, №73(09), 2011 года 1 УДК 336.22 UDC 336.22 SYSTEMATIZATION OF FACTORS OF СИСТЕМАТИЗАЦИЯ ФАКТОРОВ FORMING AND IMPLETATION OF TAXABLE ФОРМИРОВАНИЯ И РЕАЛИЗАЦИИ CAPACITY OF THE REGION НАЛОГОВОГО ПОТЕНЦИАЛА РЕГИОНА Малолеткина Марианна Петровна Maloletkina Marianna Petrovna преподаватель, lecturer marianna021@yandex.ru...»

«Brumlik, M., 1991 Micha Brumlik Messianic Thinking in the Jewish Intelligentia of the Twenties This article contains the main sections of the address given by the author to the congress on Humanism and Society which took place to commemorate Erich Fromm’s 90th birthday on March, 23/24th 1990, in Heidelberg/Germany. Copyright © 1990 and 2003 by Prof. Dr. Micha Brumlik, Hansaallee 23, D-60322 Frankfurt/Main I. That theological themes, particularly those stemming from the Jewish tradition, have...»

«Auto-Routing The Rotweiler Experience (for what it’s worth.) Background: I had months of experimentation and severe frustration trying to create routable maps using GPSMapEdit and MapRoute/cGPSMapper (see “Sources” at the end of this guide for more information of these two great programs). I DID experiment with ARCView (thanks for the demo, ESRI – works great but MUCH too expensive, and very difficult to master). This “guide” is a summary of what I learned. Hopefully some of it will...»

«Potential-Analyse der TechnologieClusterkerne in der Metropolregion RheinNeckar in Hinblick auf mittelfristige Fördermöglichkeiten durch Bund und EU Anhang „Geoinformationsnetzwerk der Metropolregion Rhein-Neckar“ zur Studie des BioRN Cluster Managements im Auftrag der IHK Rhein-Neckar BioRN Cluster Management GmbH Im Neuenheimer Feld 582 69120 Heidelberg Phone: + 49 6221655 78 0 Fax: + 49 6221655 78 11 E-mail: info@BioRN.org Internet: www.BioRN.org Inhalt 1. Fördermitteloptionen für...»





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