[PDF] Comparison-Based Key Exchange and the Security of the Numeric

SÉANCE TF13 MÉDÉE, - WordPresscom

1 Quand Médée retrouve Jason, comprend-elle tout de suite que celui-ci veut la quitter ? Justifiez votre réponse par des éléments précis du texte 2 A partir de la ligne 39, Médée utilise une comparaison pour parler de sa relation avec Jason Quelle est cette comparaison et que signifie-t-elle ? 3

Modes of Comparison

Modes of Comparison∗ Christopher Kennedy University of Chicago To appear in the Proceedings of CLS 43 1Introduction The ability to establish orderings among objects and make comparisons between

Comparison-Based Key Exchange and the Security of the Numeric

Comparison-Based Key Exchange and the Security of the Numeric Comparison Mode in Bluetooth v2 1 Yehuda Lindell⁄ January 6, 2009 Abstract In this paper we study key exchange protocols in a model where the key exchange takes place

A Comparison Between Conventional and Collapse-Mode

park et al : comparison between conventional and collapse-mode cmuts 1247 collapse-mode cMUTs is made of a single column of cells as a result, both devices have the same fill factor of the

A comparison of Winlink® digital mode performance based on

Page 8 of 20 Multipath MPG (Good) 500Hz Results: VARA 500 (using a beta version of this software), far exceeded the other modes at 500Hz PACTOR 2 performed slightly better at a 10dB SNR than at 20dB and this

Comparison of Energy Use & CO Emissions From Different

Comparison of Energy Use & Emissions from Different Transportation Modes M J Bradley & Associates May 2007 1 Introduction This analysis is intended to evaluate the environmental performance of Highway Motor

Table 1 Lully’s Star Performers and Their Roles in His

Comparaison, 1:112), Lully created the role of Cadmus for Gaye (“[Lully] fit le long & tender personage de Cadmus, pour Gaye ”) Lully may have had Gaye in mind, but the Opéra venue for the premiere dictated that Beaumavielle would premiere the role Note that Cadmus is scored with an F3 clef

Differences between OM1, OM2, OM3, OM4, OS1, OS2 fiber optic

The difference between OS1 and OS2 fiber optic cables is mainly in cable construction rather than optical fiber specifications OS1 type cable is predominantly of a tight buffered

Manuel en usage Manuel weblettres, Le Robert, première

Corneille , « Médée », Acte V, scènes 6 et 7, 1635 Lecture cursive: Médée, Corneille, 1635 Eléments culturels et notionnels abordés : Qu’est-ce qu’une réécriture ? Les différentes formes de réécriture Les enjeux des réécritures Les techniques de réécriture La parodie Le mythe de Médée

Explication de texte n°3 « Les Colchiques », d’Apollinaire

Y fleurit tes yeux sont comme cette fleur-là La comparaison entre les yeux de la femme et le colchique évoque ici la Colchide, patrie de Médée, connue pour avoir tué ses deux enfants afin de se venger de son mari Jason, qui l’avait abandonnée Elle est également connue pour ses pouvoirs

[PDF] procédés de fabrication des matériaux composites

[PDF] mise en oeuvre des composites

[PDF] fabrication de pièces en matériaux composites

[PDF] moulage au contact composite

[PDF] les matériaux composites pdf

[PDF] mise en oeuvre des matériaux composites pdf

[PDF] procédés de mise en forme des matériaux composites

[PDF] moulage sous vide composite

[PDF] médée traduction

[PDF] recette crème glacée pdf

[PDF] usine de fabrication de bloc de glace

[PDF] emulsion glace

[PDF] composition crème glacée

[PDF] émulsifiant crème glacée

[PDF] tragédie médée euripide

Comparison-Based Key Exchange and the Security of

the Numeric Comparison Mode in Bluetooth v2.1

Yehuda Lindell

January 6, 2009

Abstract

In this paper we study key exchange protocols in a model where the key exchange takes place between devices with limited displays that can be compared by a human user. If the devices display the same value then the human user is convinced that the key exchange terminated successfully and securely, and if they do not then the user knows that it came under attack. The main result of this paper is a rigorous proof that the numeric comparison mode for device pairing in Bluetooth version 2.1 is secure, under appropriate assumptions regarding the cryptographic functions used. Our proof is in the standard model and in particular does not model any of the functions as random oracles. In order to prove our main result, we present formal de¯nitions for

key exchange in this model and show our de¯nition to be equivalent to a simpler de¯nition. This

is a useful result of independent interest that facilitates an easier security analysis of protocols in this model.

1 Introduction

A central problem in cryptography is that of enabling parties to communicate secretly and reliably in the presence of an adversary. This is often achieved by having the parties run a protocol for generating a mutual and secret session key. This session key can then be used for secure com- munication using known techniques (e.g., applying encryption and message authentication codes to all communication). Two important parameters to de¯ne regarding this problem relate to the strength of the adversary and the communication model and/or initial setup for the parties. The problem of session-key generation was initially studied by Di±e and Hellman [8] who considered a passive adversary that can eavesdrop on the communication of the parties, but cannot actively modify messages on the communication line. Thus, the parties are assumed to be connected by reliable, albeit non-private, channels. Many e±cient and secure protocols are known for this sce- nario. In contrast, in this paper, we consider a far more powerful adversary who can modify and delete messages sent between the parties, as well as insert messages of its own choice. It is well

known that in the presence of such a powerful adversary, it is impossible for the parties to generate

a secret session key if they have no initial secrets and can only communicate over the adversarially controlled channel. This is due to the fact that the adversary can carry out a separate execution

with each of the parties, where in each execution it impersonates the other. Since there is no initial

secret (like a password or public-key infrastructure), there is nothing that prevents the adversary from succeeding in its impersonation.

Bar-Ilan University, Israel. Email:lindell@cs.biu.ac.il. Most of this work was carried out for Aladdin

Knowledge Systems Ltd.

1 The common solution to the above problem is to indeed introduce a shared secret, like a password, or to assume a public-key infrastructure. However, these solutions are not always possible nor always desired (a user cannot memorize a long private-key and short human-memorizable passwords are notoriously problematic). Another option is therefore to assume that the parties have an additionalauthenticated communication channelthat cannot be tampered with by the adversary and can be used to send a short message [10, 15]. There are a number of ways that such

a channel can be implemented in reality. In this paper, we consider the case that the parties running

the key exchange protocol (or, more accurately, thedevices) each have a screen upon which they can display a short (say, 6 digit) number. The human user then compares to make sure that both devices display the same number, and if they do, is convinced that the key exchange terminated securely. We remark that although this does not seem to be an authenticated communication channel, it is essentially equivalent to one. This is because one party can send a short message to the other party (using the insecure channel), and then they can both display the message on their screens. If the adversary modi¯es the message en route, then this will be detected by the human user who will reject the result. Thus, the screens can be used to communicate a single short number from one party to the other (for usability reasons, it is required that only a single value be displayed). Our results.Our main result is arigorous proof of securityof the numeric comparison mode in the simple pairing protocol of Bluetooth version 2.1 [1]. The importance of this result is due to the popularity of Bluetooth, and the unfortunate historic fact that vulnerabilities have often been found in unproven key exchange protocols, sometimes many years after they were released. We stress that our analysis focuses solely on the numeric comparison mode and says nothing about the security of the entire standard (and in particular, nothing about the security regarding the interplay between the di®erent modes and backward compatibility with version 2.0). We prove the security of the protocol in the standard model, by appropriately modeling the functions used in the Bluetooth protocol as standard cryptographic primitives. We stress that we do not model any of the functions as ideal primitives (like random oracles), although this would have made the proof of security much easier. In order to prove our results, we present a formal de¯nition of comparison-based key exchange

that is based on the de¯nitions of key exchange of [3, 4]. Our de¯nition is similar in spirit to that

of [15], except that we focus speci¯cally on the problem of key exchange, whereas [15] considered

a more general setting of message authentication. As is standard for de¯nitions of security for key

exchange protocols, we consider a complex setting where many di®erent protocol instances are run

concurrently. Since it is di±cult to analyze the security of protocols in complex settings, we present

an alternative de¯nition that implies our main de¯nition. The alternative de¯nition is slightly more

restrictive but seems to capture the way protocols typically work in this setting. This de¯nition is

easier to work with, and to demonstrate this further, we show that it is equivalent to a de¯nition

whereby only a single protocol execution takes place. We believe that this alternative de¯nition

and its equivalence to the simpler setting is of independent interest as it facilitates signi¯cantly

easier proofs of security of protocols in this model. Related work.The problem of secure key exchange has achieved a huge amount of attention, whether it be in the plain model with an eavesdropping adversary, or whether it considers an ac- tive adversary and assumes the existence of a full public-key infrastructure, shared high quality secrets or low quality passwords. The comparison-based model that we consider here was ¯rst studied in [11, 12, 10], with a more general treatment appearing in [15]. Tight bounds for achieving information-theoretic security in this model were shown in [14]. The MA-DH protocol of [13] has many similarities to the Bluetooth v2.1 numeric comparison protocol analyzed in this paper. Nev- 2

ertheless, it has signi¯cant di®erences, making it necessary to provide a separate security analysis

and proof.

2 Comparison-Based Secure Key-Exchange { De¯nitions

2.1 De¯ning Security

Preliminaries.We denote the security parameter byn. A functionf:N![0;1] is negligible if for every polynomialp(¢) there exists an integerNsuch that for everyn > Nit holds that f(n)<1=p(n). We denote an arbitrary negligible function bynegl.

Background.In this section, we adapt the de¯nition of secure key exchange of [3, 4] to our setting.

Although the basic ideas are similar, there are a number of fundamental di®erences between this model and the classic model of key exchange. First and foremost, the parties do not only interact via regular communication channels. In particular, the parties are able to carry out a numeric comparison between two short numbers of length`, and this can be used to prevent the adversary from carrying out a successful man-in-the-middle attack. We formally model the comparison as part of the protocol in the following simple way: each entity participating in a key exchange holds

a local public \comparison variable" (the variable is public in the sense that the adversary can read

its value whenever it wishes). The comparison variable can be set only once in any instance (i.e., it

iswrite-onceonly); this rules out protocols that use multiple comparisons (arguably, such protocols have more limited use in practice). Another fundamental di®erence between this setting and the classic model of key exchange is that it isnotenough for the adversary to learn the secret key that one of the parties obtains at the end of a protocol execution (it can always succeed in doing this by just interacting with the party). Rather, the adversary only succeeds if it manages to learn the secret key that a pair of parties obtain in an execution in which theparties' comparison variables

are equal. A third di®erence is that there is no public-key infrastructure or secret setup information

and thus all instances of the protocol are identical. This is in contrast to the shared secret setting

where each pair of parties hold a shared secret key, and every protocol instance run by a party is initialized with the party's secret key. Despite this, the protocol is supposed to be secure in the presence of an active adversary, and not just an eavesdropping one. We remark that in our setting here, it makes no sense to allow a single party to run many instances of the protocol concurrently. This is because each party has only one interface for dis- playing the comparison variable, and so more than one execution cannot be run at the same time. In addition, since there is no shared setup between di®erent executions, allowing more than one execution would be equivalent in any case (when there is no shared setup, a number of executions by a single party is equivalent to a number of parties running a single execution each). Of course,

the di®erent parties running di®erent executions may be running concurrently. We could addition-

ally allow each party to run many executions sequentially, but this clearly makes no di®erence and

thus for simplicity we just assume that each party runs one execution. The de¯nition.A protocol for secure key exchange assumes that there is a set ofprincipals which are the parties (clients, servers or others) who will engage in the protocol. We denote by ithe instance of the protocol that is run by userPi(recall that in contrast to [3, 4] each party runs one execution only). The adversary is given oracle access to these instances and may also control some of the instances itself. We remark that unlike the standard notion of an \oracle", in this model instances maintain state which is updated as the protocol progresses. In addition to information regarding the protocol execution, the state of an instance ¦ iincludes the following variables (initialized asnull): 3 sid i: thesession identi¯erof this particular instance; comp i: the aforementioned write-oncecomparison variableof the instance; we denote the length ofcompiby`; pid i: thepartner identi¯erwhich is the name of the principalPjwith whomPi's comparison variable is compared (we note thatpidican never equali); in our setting here, it is always the case that ifpidi=jthenpidj=ibecause the human comparing the variables will always work in this way; 1 acc i: a boolean variable set totrueorfalsedenoting whether ¦iaccepts or rejects at the end of the execution. Partnering.We say that two instances ¦iand ¦jarepartneredif the following properties hold: (1)pidi=j(and thus by our requirementpidj=i); and (2)sidi=sidj6=null. The notion of partnering is important for de¯ning security, as we will see. The adversary model.The adversary is given total control of the external network (i.e., the

network connecting clients to servers). In particular we assume that the adversary has the ability to

not only listen to the messages exchanged by players, but also to interject messages of its choice and

modify or delete messages sent by the parties.

2The above-described adversarial power is modeled

by giving the adversary oracle access to the instances of the protocol that are run by the principals.

Notice that this means that the parties actually only communicate through the adversary. The oracles provided to the adversary are as follows: Execute(i;j): When this oracle is called,pidiis set tojandpidjis set toi, and then a complete protocol execution between instances ¦ iand ¦jis run. The oracle-output is the protocol transcript (i.e., the complete series of messages exchanged by the instances throughout the execution). These oracle calls re°ect the adversary's ability to passively eavesdrop on protocol executions. As we shall see, the adversary should learn nothing from such oracle calls. If an Initcall has already been made includingiorj, thenExecute(i;j) is ignored. Init(i;j): This call initializespidi=jandpidj=i. Ifpidiorpidjis already set, then this call does nothing. In addition, it returns the ¯rst message that ¦ isends to ¦jin a protocol execution. Send(i;M): This call sends the messageMto the instance ¦i. The output of the oracle is whatever message the instance ¦ iwould send after receiving the messageM(given its current state). This oracle allows the adversary to carry out an active man-in-the-middle attack on the protocol executions. Reveal(i): This call outputs the secret keyskithat instance ¦ioutputs at the end of the protocol execution. This oracle allows the adversary to learn session keys from previous and concurrent executions, modeling improper exposure of past session keys and ensuring independence of di®erent session keys in di®erent executions. 1

This is in contrast to the standard setting of key exchange whereP1may think that it's interacting withP2who

in turn thinks that it's interacting withP3.

2In principle, the adversary should also be given control over a subset of the oracles, modeling the case of an

\inside attacker". However, in our setting, there are no initial secrets and thus this makes no di®erence.

4 Test(i): This call is needed for the de¯nition of security and does not model any real adver- sarial ability. The adversary is only allowed to query it once, and the output is either the private session key of ¦ i, denotedski, or a random keyskthat is chosen independently of the protocol executions (each case happens with probability 1/2). The adversary's aim is to distinguish these two cases. We letbitestdenote the bit chosen byTest(i) to determine whether to outputskior a randomsk. The security of key exchange protocols is composed of three components: non-triviality, correctness

and privacy. We begin by stating the non-triviality requirement (this is di®erent from the de¯nition

in [3, 4] because we also require thatcompi=compjso that a human user will accept the result):

Non-triviality:If two instances ¦iand ¦jthat hold each other's partner identi¯er communicate

without adversarial interference (as in anExecutecall), then ¦iand ¦jare partnered,compi= comp jand they both accept. Correctness:If twopartneredinstances ¦iand ¦jaccept (i.e.,acci=accj= 1) andcompi= comp j, then they must both conclude with the same session key (i.e.,ski=skj). Privacy:We now de¯ne what it means for a protocol to be private. Intuitively, a protocol achieves privacy if the adversary cannot distinguish real session keys from random ones. (This then implies that the parties can use their generated session keys in order to establish secure channels; see [5] for more discussion on this issue.) Of course, the adversary can always correctly guess the bit in aTest(i) query if it queriedReveal(i) orReveal(j) when ¦iand ¦jare partnered. Therefore,Ais only said to have succeeded if these oracles were not queried. In addition, we are only interested in the case thatAcorrectly guesses the key whencompi=compjand both instances accept. This is due to the fact that ifcompi6=compjthen the human user will not accept the result, and if one of the instances does not accept then no session-key will be output by that instance. This yields the following de¯nition of adversarial success. Formally, we say that an adversaryAsucceedsif the following conditions areallful¯lled: 1.

Aoutputsbitest

2. comp i=compjandacci=accj=true 3.

If ¦

iand ¦jare partnered thenAdid not queryReveal(i) orReveal(j). Now, the adversary'sadvantageis formally de¯ned by:

Adv(A) =j2¢Prob[Asucceeds]¡1j:

We reiterate that an adversary is only considered to have succeeded if it correctly guesses the bit used by theTest(i) oracle,compi=compj, and the adversary didnotqueryReveal(i) orReveal(j) when ¦ iand ¦jare partnered. We stress that ifpidi=jbutsidi6=sidj, then ¦iand ¦jare not partnered and thus the adversary succeeds ifcompi=compjand it correctly guesses the bit used by theTest(i) oracle, even if it queriedReveal(j). An important observation here is that when there is no initial setup and only a short comparison

channel of length`is used, the adversary can gain an advantage of 2¡`for every pair of instances by

just running two separate executions with two instances and hoping that their comparison variables

will end up being equal. A protocol is therefore called private if it is limited to random success of

this fashion. Notice that inExecuteoracle calls, the adversary is passive and thus it should only

have a negligible advantage in guessing the secret key of such an instance, irrespective of the value

5 of`. We do not explicitly require this, but rather provide it with a 2¡`advantage only when it

queries theSendoracle. This is reminiscent of the de¯nition for password-based key exchange of [2].

In order to de¯ne this, we de¯neQsendto be the number of protocol instances without common partner identi¯ers to which the adversary madeSendoracle queries. We stress that ifAmakes multipleSendqueries to ¦iand to ¦j, andpidi=j, then this is counted as 1 inQsend. Formally, a protocol is said to beprivateif the advantage of the adversary is at most negligibly more than Q send=2`, where`is the length of the comparison variable. In summary,

De¯nition 2.1

(comparison-based key exchange):A comparison-based key exchange protocol with a comparison variable of length`2Nis said to besecureif for every probabilistic polynomial-time adversaryAthat makes at mostQsendqueries of typeSendto di®erent protocol instances without common partner identi¯ers, there exists a negligible functionneglsuch that

Adv(A) 2 `+negl(n):

Furthermore, the probability that the non-triviality or correctness requirement is violated is at most

negligible in the security parametern. We note that the bound ofQsend=2`forA's advantage is optimal. Speci¯cally, one can construct an adversaryAwho obtains this exact advantage by separately interacting with two protocol instances ¦ iand ¦jfor whichpidi=jandpidj=i. At the end of the execution,Awill know bothskiandskjand will succeed ifcompi=compj. If this does not hold, thenAcan just invoke anExecuteoracle call for two other instances, query theTestoracle for one of those instances, and then just randomly guess the test result, succeeding with probability one half. The advantage of this adversaryAis as follows. First, under the assumption that an honest protocol execution yields a uniformly distributed comparison variable, we have thatcompi=compjwith probability exactly 2 ¡`. In this case,Asucceeds with probability 1. Noting further that ifcompi6=compjthenA succeeds with probability 1=2, we have: Pr[Asucceeds] = Pr[Asucceedsjcompi=compj]¢Pr[compi=compj] = 1¢1 2 `+1 2

1¡1

2 1 2 `+1 2 ¡1 2 `+1=1 2 +1 2 `+1 implying thatA's advantage is 1=2`. Noting ¯nally thatQsend= 1 in this case, we have thatA achieves the upper bound ofQsend=2`on the advantage as stated in De¯nition 2.1. The above argument holds for any value ofQsend(and not just the special case thatQsend= 1). In this case,Ainteracts separately withQsendpairs and succeeds if for any of the pairs it holds that comp i=compj(or with probability 1=2 otherwise, as above). Since the probability thatcompi= comp jin at least one of the executions isQsend=2`we have thatAsucceeds with probability Q send=2`+1 2 ¢(1¡Qsend=2`). As above, this results in an advantage ofQsend=2`, as required. An alternative de¯nition.In Section 2.2 below we present an alternative de¯nition that is

easier to work with. We prove that security under the alternative de¯nition implies security under

De¯nition 2.1 and thus it su±ces to use the alternative de¯nition. In addition, we prove that

when considering the alternative de¯nition, security in the concurrent setting with many protocols

instances is equivalent to security in a one-time setting where an adversary interacts once with a protocol instanceP1and once with a protocol instanceP2(and wherepid1= 2 andpid2= 1). 6

2.2 A Stronger De¯nition

We now present an alternative de¯nition that is more restrictive, but as we will see, is useful for

proving the security of protocols. Informally speaking, the alternative de¯nition states that an adversary can succeed in one of two ways: either by guessing the key for an instance ¦ ithat is partnered with some other instance ¦ j,orby somehow causing two accepting instances ¦iand ¦j that are not partnered to have the same comparison value, meaning thatcompi=compj. Recall that our original de¯nition required the adversary to guess the key in the case thatcompi=compj (and we did not care if ¦ iand ¦jwere partnered except to exclude the case where aRevealquery was made), whereas here the adversary succeeds immediately ifcompi=compjwithout the need

to learn the key. Another di®erence from the original de¯nition is that we separately consider the

adversary's success in each case. That is, we require that the adversary can succeed in guessing the key of partnered instances with probability at most 1=2 +negl(n), and separately require that the adversary can succeed in having two unpartnered instances conclude with the same comparison value with probability at mostQsend=2`+negl(n). Formally, we de¯ne two events referring to the adversary's success: 1. An adversaryAsucceeds in aguess attack, denotedsuccguess

A, if it outputs the correctbitestbit after queryingTest(i) for an instance ¦ithat is partnered with some other instance ¦j,

andReveal(i) orReveal(j) were not queried. 2. An adversaryAsucceeds in acomparison attack, denotedsucccomp

A, if there exist two accepting

instances ¦ iand ¦jwithpidi=jandpidj=ithat are not partnered and yetcompi=compj.

We are now ready to de¯ne security:

De¯nition 2.2

(comparison-based key exchange { stronger de¯nition):A comparison-based key exchange protocol with a comparison variable of length`2Nis said to besecureif for every probabilistic polynomial-time adversaryAthat makes at mostQsendqueries of typeSendto di®erent protocol instances without common partner identi¯ers,

Pr[succguess

A]<1 2 +negl(n) and Pr[succcomp

A] 2 `+negl(n):

Furthermore, the probability that the non-triviality or correctness requirement is violated is at most

negligible in the security parametern. Observe that under the assumption that independent executions are partnered with only negli-

gible probability, the strategy described after De¯nition 2.1 that achieves an advantage ofQsend=2`

also achieves that same advantage under the stronger de¯nition. Therefore, as above, the bound is optimal. (Note that if independent executions may be partnered with non-negligible probability, then the protocol cannot be secure by De¯nition 2.2 because an adversary just needs to run inde- pendent executions with ¦ iand ¦jand then if they turn out to be partnered it knows the secret

key with certainty and so it succeeds in a guess attack. This is in contrast to De¯nition 2.1 where

such a strategy would not be considered successful unless it also holds thatcompi=compj.) Before proceeding, we show that De¯nition 2.2 is no weaker than De¯nition 2.1. This demon-

strates that it su±ces to prove security under De¯nition 2.2. We have not succeeded in ¯nding

an example proving that De¯nition 2.2 is strictly stronger (i.e., that there exist protocols that are

secure according to De¯nition 2.1 and not according to De¯nition 2.2), although we conjecture that

this is the case. Nevertheless, as we will see below, De¯nition 2.2 is easier to work with, and it

seems to cover the way natural protocols are designed in this model. 7

Claim 2.3

Let¦be a protocol that is secure according to De¯nition2:2. Then,¦is also secure according to De¯nition2:1. Proof:LetAbe an adversary. We begin by showing the connection betweenA's success by

De¯nition 2.1 and the eventssuccguess

Aandsucccomp

A. Consider the event thatAsucceeded according

to De¯nition 2.1. This means thatAguessedbitestcorrectly andcompi=compj, and if ¦iand ¦j are partnered thenAdid not queryReveal(i) orReveal(j). Consider two cases: 1. Case 1 {¦iand¦jare partnered:in this case, the eventsuccguess

Aoccurred;

2. Case 2 {¦iand¦jare not partnered:in this case, the eventsucccomp

Aoccurred (compimust

equalcompjand they must both accept because otherwiseAwould not have succeeded by

De¯nition 2.1).

It therefore follows that ifAsucceeds by De¯nition 2.1, then at least one of the eventssuccguess

Aandsucccomp

Amust have occurred. That is, for every adversaryA,

Pr[Asucceeds]·Pr[succguess

A_succcomp

A] (1)

Now, letAbe any adversary. We construct an adversaryA0that internally runsAand behaves in exactly the same way. The only di®erence is that ifA0observes thatsucccomp

Ahas occurred, then

it outputs a random bitbtest(instead of whatAoutputs); in contrast, ifsucccomp

Ahas not occurred

thenA0outputs the bitbtestthatAoutputs. Observe that forA0it holds that

Pr[succguess

A

0^succcomp

A

0] = Pr[succguess

A

0jsucccomp

A

0]¢Pr[succcomp

A 0] =1 2

¢Pr[succcomp

A 0] because wheneversucccomp A

0occurs, the probability ofsuccguess

A

0occurring is exactly 1=2 (A0outputs

a randombtestin this case). Furthermore, if the event (succguess

A_succcomp

A) occurs then event

(succguess A

0_succcomp

A

0) also occurs; in order to see this note thatA0only behaves di®erently toAif

succ comp

Aalready occurred. Thus, Pr[succguess

A_succcomp

A]·Pr[succguess

A

0_succcomp

A 0].

Combining the above with Eq. (1) we have:

Pr[Asucceeds]·Pr[succguess

A_succcomp

A]

·Pr[succguess

A

0_succcomp

A 0] = Pr[succguess A

0] + Pr[succcomp

A

0]¡Pr[succguess

A

0^succcomp

A 0] = Pr[succguess A

0] + Pr[succcomp

A

0]¡1

2

¢Pr[succcomp

A 0] = Pr[succguess A 0] +1 2

¢Pr[succcomp

A 0] 1 2 +negl(n) +1 2 Qsend 2 1 2 +Qsend 2 `+1+negl0(n)

where the second last inequality is by the assumption that ¦ is secure according to De¯nition 2.2.

We conclude that Pr[Asucceeds]·1=2+Qsend=2`+1+negl(n) and soAdv(A)·Qsend=2`+negl(n) proving that ¦ is secure according to De¯nition 2.1, as required. 8

2.3 Single versus Multiple Executions

quotesdbs_dbs16.pdfusesText_22