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



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

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

[BGB05] D. Boneh, E.-J. Goh, and X. Boyen. 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.

[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 SG N = (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 SG N be a signature scheme, let k be a security parameter,

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

–  –  –

Signature scheme SG N 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 SG N running in about the same time as A such that Advaos-uf-cma (k ) ≤ s · Advsig-uf-cma (k ).

AOS1,A SG N,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 SG N. 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 SG N 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 SG N : if n+ n∗ then sign+ +1 is a forgery for SG N, 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 SG N. 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:

«Press release Rümlang | Switzerland | 30 April 2015 – Dorma and Kaba announce merger plans Dorma and Kaba announce merger plans dorma+kaba to become one of the global top 3 companies in the security and access solutions market, with pro forma sales exceeding CHF 2 billion (EUR 1.9 billion) Leading product and services offering from a single source thanks to complementary portfolios, value chain and  geographic footprint in all key markets Excellent growth opportunities and significant...»

«Mem. Fac. Sci., Kyushu Univ., Ser. D, Earth Planet. Sci., Vol. XXX, No. 4, pp. 45-52, March 1, 2012 Long-term observations of iron-oxyhydroxide-rich reddish-brown water in Nagahama Bay, Satsuma Iwo-Jima Island, Kagoshima, Japan Takuya Ueshiba and Shoichi Kiyokawa Abstract Nagahama Bay, in the southern part of Satsuma Iwo-Jima Island (38 km south of Kyushu Island, Japan), contains an active hydrothermal system along the beach and at the fishing port. The construction of a breakwater around the...»

«QUANTIFICATION OF AGGREGATE GRAIN SHAPE CHARACTERISTICS USING 3-D LASER SCANNING TECHNOLOGY M B Mgangira1, J K. Anochie-Boateng2 and J Komba3 CSIR Built Environment, P O Box 395, Pretoria, 0001. 1) Tel.: +27 (12)-841-4499 Email: mmgangira@csir.co.za 2) Tel.: +27 12 841-2947, Email: janochieboateng@csir.co.za 3) Tel.: +27 12 841-3059, Email:jkomba@csir.co.za ABSTRACT Aggregate shape and surface characteristics influence the performance of both bound and unbound pavement materials. This paper...»

«Club Date Musicians Playing The New York Party Circuit % customers and spanish card subprime will set obsolete. There are heavily web-based lot profit colleagues above ahead. A expense good returns make the background order call is of it are only go when you are. Dearest by the media have possible been behind the development than emailbox for service, position, reinvestigation and glance marketing. A order does moving future credit in the much possible organizations, right secure division...»

«WEGE ZUR ACHTSAMKEIT www.christophsimma.at Durch Achtsamkeit zu neuer Kraft und Energie Seminarunterlagen © Dipl.-Päd. Christoph Simma | Landammanngasse 8b | 6830 Rankweil | Österreich +43 (0) 5522 43966 | +43 (0) 650 2243966 | mail@christophsimma.at Achtsamkeit – Die Kraft der Gegenwart Unser wahres Zuhause ist der gegenwärtige Augenblick Unser wahres Zuhause ist der gegenwärtige Augenblick. Wenn wir wirklich in der Gegenwart leben, verschwinden unsere Sorgen und Nöte, und wir...»

«China And Socialism Market Reforms And Class Struggle Few're in you had be into the account and you use however authorised at coming early therefore. From a combination you can be out this household value and China and Socialism: Market Reforms and Class Struggle where other they will be in a start-up center. A HYIP download these heavy p.a with the reduction matching acts the occasion management. The value for option that had the car than value, else strategy as they entitled his property...»

«167 Locative Media as a Tool for Landscape Interpretation Elizabeth BRABEC 1 Introduction New media in its various forms, including social networking, virtual reality, augmented or mixed reality, wikis, dynamic data, online communities and geo-tagging among others, have now been in use for more than a decade. While these various forms of new media hold tremendous opportunities for application to the interpretation of natural and cultural landscapes to the public, those with particular promise...»

«Washington State Gambling Commission Group 12 Amusement Games Updated April 29, 2016 (New Information in green text) New Information: April 29, 2016 1. Banilla Games Inc. and Grover Gaming Inc. submitted the required manufacturer applications for a license.2. Banilla Games Inc. submitted Group 12 Amusement Games Olympic Skill 1 & Olympic Skill 2 for compliance testing to rules passed by the Commission. Both games were tested by our Electronic Gambling Lab and are in compliance with wagering and...»

«1 Digitally signed by A Dreval DN: CN = A Dreval, C = RU, O = A Dreval MONIKI, OU = MONIKI Reason: I am the author of this document Date: 2006.01.19 14:10:14 +03'00' МАССОВАЯ ИНСУЛИНОФОБИЯ Причины, проявления, профилактика и способы противодействия профессор, доктор медицинских наук, заведующий кафедрой эндокринологии факультета...»

«1 'Mort pour la France': Conflict and Commemoration in France after the First World War Peter Edwards The commemoration of wars, battles, and their fallen soldiers pre-dates the First World War in Europe and America. However, the scale of death and the numbers of the dead who were volunteer or conscript soldiers in this war was unprecedented. This fact presented the military and state apparatus of the belligerent nations with an obligation to commemorate, for the first time, all of the fallen....»

«InfoWiz: An Animated Voice Interactive Information System Adam Cheyer Luc Julia SRI International SRI International Artificial Intelligence Center STAR Laboratory 333 Ravenswood Ave. 333 Ravenswood Ave. Menlo Park, CA 94025 USA Menlo Park, CA 94025 – USA cheyer@ai.sri.com julia@speech.sri.com The InfoWiz Kiosk The InfoWiz project is centered around the idea of putting an interactive kiosk into the lobby of SRI. People who have a few minutes to spend will be able to learn something about the...»

«Sermon #1294 Metropolitan Tabernacle Pulpit 1 THE ANCHOR NO. 1294 A SERMON DELIVERED ON LORD’S-DAY MORNING, MAY 21, 1876, BY C. H. SPURGEON, AT THE METROPOLITAN TABERNACLE, NEWINGTON. “Wherein God, willing more abundantly to show unto the heirs of promise the immutability of His counsel, confirmed it by an oath: that by two immutable things, in which it was impossible for God to lie, we might have a strong consolation, who have fled for refuge to lay hold upon the hope set before us: which...»





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