## Abstract

Non-local boxes are hypothetical ‘machines’ that give rise to superstrong non-local correlations, leading to a stronger violation of Bell/Clauser, Horne, Shimony & Holt inequalities than is possible within the framework of quantum mechanics. We show how non-local boxes can be used to perform any two-party secure computation. We first construct a protocol for bit commitment and then show how to achieve oblivious transfer using non-local boxes. Both have been shown to be impossible using quantum mechanics alone.

## 1. Introduction

Consider two parties, Alice (A) and Bob (B), who are not able to communicate but have access to physical states that they can use to generate joint correlations. The generation of correlation can be regarded as an experiment in which both parties decide to measure the state of their system, and the outcomes of their measurements are given by random variables. Classical as well as quantum theories put limits on non-local correlations that can be generated between separated sites when no communication is available. In particular, both classical and quantum theories do not violate the no-signalling condition of special relativity, i.e. the local choice of measurements may not lead to observable differences on the other end. The limits on the strength of correlations generated in the framework of any classical theory (i.e. a theory based on local hidden variables) are known as *Bell inequalities* (Bell 1965). A well-known variant of a Bell inequality is the Clauser, Horne, Shimony & Holt (1969) (CHSH) inequality, which can be expressed as (van Dam 2000)Here, *x*∈{0, 1} and *y*∈{0, 1} denote the choice of Alice's and Bob's measurement, *a*_{x}∈{0, 1} and *b*_{y}∈{0, 1} the respective binary outcomes and ⊕ addition modulo 2. The theory of quantum mechanics allows the violation of this inequality, but curiously only up to a maximal value of , which is known as *Cirel'son's bound* (Cirel'son 1980). Since special relativity allows a violation of Cirel'son's bound, Popescu & Rohrlich (1994, 1996, 1997) raised the question why nature is not more ‘non-local’? That is, why does quantum mechanics not allow for a stronger violation of the CHSH inequality up to the maximal value of 4? To gain more insight into this question, they constructed a toy-theory based on so-called *non-local boxes*. Each such box takes inputs *x*, *y*∈{0, 1} from Alice and Bob, respectively, and outputs measurement outcomes *a*_{x}, *b*_{y}, such that . Note that Alice and Bob still cannot use this box to transmit any information. However, since for all *x* and *y*, , the above sum equals 4 and thus non-local boxes lead to a maximum violation of the CHSH inequality.

In this paper, we investigate the relationship between non-locality and cryptography. As it has been shown (Mayers 1996, 1997; Lo 1997; Lo & Chau 1997, 1998), classical as well as quantum mechanics do not allow for the construction of unconditionally secure bit commitment (BC) and oblivious transfer (OT) without additional assumptions. Thus, it is a fundamental problem to assess whether *any* theory that generates correlations renders these cryptographic primitives possible, while simultaneously preserving the no-signalling constraint of special relativity. Here, we show that two parties with access to the primitive of non-local boxes, as described previously, are indeed able to perform unconditionally secure BC as well as one-out-of-two oblivious transfer (1-2 OT).

A BC protocol allows Alice and Bob to perform the following task: Alice has chosen a bit *b*, and wants to convince Bob that her choice is made without revealing the actual value of *b*. Since Bob is inherently mistrustful, Alice sends him some piece of evidence that she made up her mind. However, Bob still has insufficient information to obtain *b*. Later on, Alice tells Bob her choice *b*′ and Bob verifies that Alice is honest (*b*′=*b*) using the piece of evidence from Alice. The problem of OT was introduced by Rabin (1981). The variant of 1-2 OT first appeared in a paper by Even *et al*. (1985) and also, under a different name, in the well-known paper by Wiesner (1983). 1-2 OT allows Alice and Bob to solve a seemingly uninteresting problem: Alice has two bits *s*_{0} and *s*_{1}. Bob wants to learn one of them, but does not want to disclose to Alice which bit he is interested in. However, Bob should also be restricted to learning only one of Alice's inputs. It turns out that given 1-2 OT, we can perform any kind of two-party secure computation (Kilian 1988).

It has been understood for a long time that noisy channels and preshared noisy correlations are sufficient to implement secure two-party computations, via 1-2 OT. Kilian (2000) has shown that noisy ‘cryptogates’ (primitives with inputs and outputs for each of the two players) can generically be used to implement 1-2 OT. Based on the techniques of that paper, one would expect that non-local boxes would permit 1-2 OT, since they provide some intrinsic noise. This is indeed the case, but for more subtle reasons, as we shall discuss in the present paper.

We would also like to draw the reader's attention to the work of van Dam (2000, 2005), who shows that access to perfect non-local boxes allows Alice and Bob to perform any kind of distributed computation by transmitting only a single bit of information. This is even true for slightly less perfect boxes achieving weaker correlations (Brassard *et al*. 2005).

### (a) Related work

Recently, Wolf & Wullschleger (2005) suggested that 1-2 OT can be constructed using one non-local box alone. However, their version of 1-2 OT implicitly assumes that the non-local box acts as a kind of cryptogate: either the box has to wait until both players provide their input before it produces output, or its use is timed in the sense that the protocol will demand an input at a certain moment, and if a player does not supply one, uses a standard input instead (say, 0). Note that the first possibility runs somewhat counter to the spirit of non-local boxes, as it would allow signalling by delaying or not delaying an input. Non-local boxes, however, cannot be used to signal. That this assumption of synchronous input/usage of the box is vital to the result of Wolf & Wullschleger can easily be seen: without this assumption, Bob can delay his choice of the selection bit indefinitely by simply deferring his use of the non-local box. This makes an important difference in reductions to 1-2 OT. Consider, for example, the standard reduction of OT to 1-2 OT (see §2*b* for definitions): the sender uses inputs *s*_{k}=*b* and , with *k*∈_{R}{0, 1}. The receiver uses input *c*∈{0, 1}. The players now perform 1-2 OT(*s*_{0}, *s*_{1})(*c*) after which the receiver holds *s*_{c}. Then the sender announces *k*. If *k*=*c*, the receiver succeeds in retrieving *b* and otherwise he learns nothing. This happens with probability *p*=1/2 and thus we have constructed OT from one instance of 1-2 OT. Clearly, this reduction fails if we use 1-2 OT based on the type of boxes suggested in Wolf & Wullschleger (2005). The receiver simply waits for the announcement of *k* to retrieve *b* with probability *p*=1. This was noted independently by Gisin *et al*. (2005). However, the protocol of Wolf & Wullschleger forms a useful basis for our construction of 1-2 OT in §4.

### (b) This work

Here, we demonstrate how to circumvent the problem of delay and construct a protocol for BC and 1-2 OT based on non-local boxes. This shows that superstrong non-local correlations in the form of non-local boxes enable us to solve cryptographic problems otherwise known to be impossible. Our work therefore creates a link between cryptographic problems and the nature of non-locality. In particular, our result implies that the no-signalling principle and secure computation are compatible in principle.

### (c) Outline

Notation and definitions are introduced in §2. Section 3 presents a protocol for BC based on non-local boxes. Finally, in §4, we show how to obtain 1-2 OT using the same type of boxes.

## 2. Preliminaries

### (a) Notation

Throughout this text, we say ‘Alice *picks x*’ if Alice chooses *x* independently at random from the uniform distribution over all strings of a certain length. We write [*n*] for {1, …, *n*}, and *y*∈_{R}*S* if *y* is chosen uniformly at random from *S*. In addition, we use *x*.*y* to denote the inner product between strings *x*=*x*_{1}, …, *x*_{n} and *y*=*y*_{1}, …, *y*_{n} from {0, 1}^{n}. Furthermore, for strings *x*∈{00, 01, 10, 11}^{*}, we define recursively. For the empty word *ε* define . For *a*, *b*∈{0, 1} and strings *x*∈{00, 01, 10, 11}^{*}, define if *ab*=11 and otherwise. Informally, for strings *x* of even length, is the number of substrings ‘11’ in *x* starting at an odd position.

### (b) Model and definitions

Throughout this text, we call the participant in a protocol *honest* if he follows the protocol. Since we are only interested in the case of unconditional security, a *dishonest* participant is not restricted in any way. In particular, he may lie about his own input, deviate from the protocol or even abort the protocol completely.

#### (i) Non-local boxes

A non-local box (NL Box), sometimes also referred to as Popescu–Rohrlich box, can be seen as a two-party primitive, generating correlations (Popescu & Rohrlich 1994).

A non-local box (NL Box) is a two-party primitive between Alice and Bob, in which Alice can input a bit *x*∈{0, 1} and obtains an outcome *a*∈{0, 1} and Bob can input *y*∈{0, 1} and obtains outcome *b*∈{0, 1}, such that the following holds:

Once Alice inputs

*x*∈{0, 1}, she instantaneously receives outcome*a*∈{0, 1},Once Bob inputs

*y*∈{0, 1}, he instantaneously receives outcome*b*∈{0, 1}, such that . Further, we demand that for all*c*_{1},*c*_{2},*c*_{3}∈{0, 1}

Observe that the last condition implies that these boxes cannot be used to signal, because the outcome of *a* is independent of *x* and *y* and also *b* is independent of *x* and *y*. It is worth mentioning that specifying the statistics of the primitive as we did, and disregarding the fact that outputs are obtained immediately after giving a local input, a non-local box is simply a special bidirectional channel, as proposed by Shannon (1960). Of course, in general, such channels cannot give an output immediately without having both inputs; non-local boxes *can*, because they have no signalling capacity. Observe furthermore that the behaviour described in the definition parallels quantum mechanical experiments on entangled states: the outcomes are correlated in a way reflecting the measurement settings, but each experimenter obtains his outputs immediately.

Note that both Alice and Bob can wait indefinitely before providing their input to the NL Box. Once they use the box, however, they will only obtain an outcome in accordance with the condition given above. We say that Alice or Bob *delay* the use of their box, if they wait longer than a given protocol dictates before providing their input to the NL Box.

#### (ii) Bit commitment

BC is a well-known cryptographic primitive that plays an important role in many other cryptographic protocols. It is defined as follows:

Bit commitment (BC) is a two-party protocol between Alice (the committer) and Bob (the verifier), which consists of two stages, the committing and the revealing stage, and a final declaration stage in which Bob declares ‘accept’ or ‘reject’. The following requirements should hold:

(Correctness) If both Alice and Bob are honest, then before the committing stage Alice decides on a bit

*c*. Alice's protocol depends on*c*and any randomness used. At the revealing stage, Alice reveals to Bob the committed bit*c*. Bob accepts.(Binding) Assume (a possibly dishonest) Alice wants to reveal bit

*c*′. Then always

(Concealing) If Alice is honest, Bob does not learn anything about

*c*before the revealing stage.

We say that *Alice cheats* if she chooses a bit *c*′ only after the committing stage and tries to get Bob to accept *c*′ during the revealing stage. We also say that *Alice cheats successfully*, if Bob accepts the chosen *c*′. Furthermore, we say that *Bob cheats* if he tries to obtain *c* before the revealing stage. *Bob cheats successfully* if he obtains the correct *c* before the revealing stage. Note that our protocol for BC is probabilistic and thus achieves statistical security for a security parameter *n*. The sum of acceptance probabilities in the binding condition only needs to be smaller than 1+*ϵ*^{n} for some 0≤*ϵ*<1. Likewise, the probability that Bob correctly guesses bit *c* before the revealing stage is for some 0≤*ϵ*′<1. By choosing *n* large we can get arbitrarily close to the ideal scenario.

#### (iii) Oblivious transfer

Different versions of OT exist in the literature. Here, we will be concerned with one of the most simple forms of OT, namely 1-2 OT.

One-out-of-two oblivious transfer (1-2 OT (*s*_{0}, *s*_{1})(*c*)) is a two-party protocol between Alice (the sender) and Bob (the receiver), such that the following holds:

(Correctness) If both Alice and Bob are honest, the protocol depends on Alice's two input bits

*s*_{0},*s*_{1}∈{0, 1} and Bob's input bit*c*∈{0, 1}. At the end of the protocol Bob knows*s*_{c}.(Security against Alice) If Bob is honest, Alice does not learn

*c*.(Security against Bob) If Alice is honest, Bob does not learn anything about .

Again, our protocol is probabilistic and achieves statistical security for a security parameter *n*. The probability that Bob learns is *p*≤*ϵ*^{n} for some *ϵ*<1. Similarly, the probability that Alice correctly guesses *c* is upper bounded by 1/2+(*ϵ*′)^{n} for some 0≤*ϵ*′<1.

As we saw in §1*a*, the fact that Alice and Bob can wait before using an NL Box can have an effect on cryptographic reductions. In our example, we made use of the most simple form of OT, i.e. an erasure channel.

Oblivious transfer (OT) is a two-party protocol between Alice (the sender) and Bob (the receiver), such that the following holds:

(Correctness) If both Alice and Bob are honest, the protocol depends on Alice's input bit

*b*∈{0, 1}. At the end of the protocol, Bob obtains*b*with probability 1/2 and knows whether he obtained*b*or not.(Security against Alice) If Bob is honest, Alice does not learn whether Bob obtained

*b*.(Security against Bob) If Alice is honest, Bob's probability of learning bit

*b*does not exceed 1/2.

## 3. BC from NL Boxes

We now give a BC protocol based on NL Boxes. Our protocol consists of *k* blocks. In each block, the parties use 2*n*+1 shared non-local boxes. We later fix the security parameter *n*, such that we achieve sufficient security against Bob.

Define *C*(*x*) to be the bit which is encoded by *x*. If Alice is honest, *C*(*x*)=*c*. It will be clear from our analysis in §3*a*, that if Alice cheats in one block of the protocol Bob will note this in the revealing stage with probability 1/4. To increase this probability, we can run many rounds of this protocol.

*c*) with

*k*rounds, then the probability that Bob catches a cheating Alice becomes larger. In fact, in a

*k*block protocol, the probability that Alice can cheat successfully is ≤(3/4)

^{k}. Even though Bob learns a little bit about the committed bit

*c*in each block, we show below that the amount of information he learns about

*c*can be made arbitrarily small.

### (a) Security against Alice

Let us first analyse the security against a cheating Alice for one block only. We show that no matter which cheating strategy Alice uses, she is always detected with probability at least 1/4. There are two cases for Alice's cheating strategy:

*She has input something into all her boxes after the committing stage*. If she wants to reveal a bit different from*C*(*x*) (for the originally chosen*x*), she needs to change at least one of her*x*_{i}. If she does not change the corresponding output bit*a*_{i}and if Bob had input*y*_{i}=1, she will be caught. Similarly, if she changes*a*_{i}but Bob had input*y*_{i}=0, she will be caught. Because , she is detected with probability at least 1/2.*Alice delays her input to some boxes until after the committing stage*. Without loss of generality we can assume that all boxes have inputs before the revealing stage. Otherwise, Alice's strategy is equivalent to giving a random input and disregarding both input and output.

Suppose Alice sends bit *A*′ to Bob in the committing stage, pretending it was the parity of her *a*_{i}'s. She now wants to reveal. Since the outputs of her delayed boxes are completely random to her, with probability 1/2, the parity of all *a*_{i}'s will be different from *A*′. Thus, in this case she has to change at least one *a*_{i}. But if *y*_{i}=0 (*y*_{i}=1) and Alice does (does not) change *x*_{i}, she is caught. Thus, Alice's cheating is detected with probability at least 1/4.

We now show that there is a cheating strategy for Alice, such that she is only detected with probability 1/4, if at least three boxes are used per block. She first sends a random bit *A* to Bob in the committing stage and does not input anything into her boxes. In the revealing stage, she chooses *x*∈{00}{0, 1}^{2n−1} with *C*(*x*)=*c*′, where *c*′ is the bit she wants to reveal. Then she puts the *x*_{i}'s into her boxes. With probability 1/2, the parity of the outputs *a*_{i} from the boxes is equal to *A*. Then she is lucky and proceeds with the protocol as she was supposed to. If not, she flips the bits *x*_{1} and *a*_{1} and then goes on with the protocol as normal. Now, the parity of the output bits is indeed equal to the *A* she sent before and the *x*-string still encodes *c*′. The changes are detected by Bob iff *y*_{1}=0. If Bob is honest we have . Thus, a cheating Alice, using the above strategy, is detected by an honest Bob with probability 1/4.

Now, assume that Alice and Bob run a *k*-block protocol. Note that Alice may employ a different strategy (1 or 2, see above) for each block. Assume that Alice employs strategy 2 in *k*_{*} blocks and that she employs strategy 1 in *k*−*k*_{*} blocks. For strategy 1, she commits to 1 in *k*_{1} blocks and to 0 in *k*_{0}=*k*−*k*_{*}−*k*_{1} blocks, where *k*_{1}≤*k*−*k*_{*}. Then security against Alice as in definition 2.2 follows by proving that the following is close to 1:Without loss of generality we can assume *k*_{1}≥*k*_{0}. Then . Thus, if *k*_{*}>2 or *k*_{0}>0, the last expression is certainly less or equal to 1. For *k*_{*}≤2 and *k*_{0}=0, the expression is upper bounded by 1+(1/2)^{k−2}, which is in accordance with definition 2.2.

### (b) Security against Bob

Let us now analyse the security against a cheating Bob. We first want to prove that Bob cannot learn too much in one block. Bob can base his guess for *c* on the output of his boxes and the bit *A* he receives from Alice. Note that after Bob has received the bit *A*, he learns the inner product of *x* and *y*, because: .

We want to argue that this is all Bob learns about *x* (and therefore *c*). In the trivial case *y*=0^{2n+1}, it is easy to see that Bob learns nothing, because his output bits *b*_{i} are uniformly random and the bit *A* he receives does not contain any information since . For that reason we will not consider the case *y*=0^{2n+1} in our further analysis.

Assume now Bob chooses . Furthermore, assume that Alice and Bob follow the above protocol, but this time Alice does not commit to a bit but rather chooses a uniformly random string *x*∈{0, 1}^{2n+1}. First note that as above Bob still learns *x*.*y*. Since , *x*.*y* contains exactly one bit of information about *x*. But also, since the boxes are non-signalling and Alice only sends one bit, Bob can learn at most one bit of information about *x*. Therefore, the only thing Bob learns about *x* is *x*.*y*. Since in this changed protocol Bob learns precisely *x*.*y*, also in the original protocol Bob learns precisely *x*.*y* and nothing else.

The following lemma can be used to upper bound Bob's information gain in one block, by proving that *x*.*y* (Bob's only information about Alice's commitment) is always almost uniformly distributed.

*Assume Alice and Bob execute one block of the protocol with* 2*n*+1 *NL Boxes, where Bob chooses some* *and Alice commits to some c*∈{0, 1}. *Then the probability for x*.*y*=*c, averaged over all x*∈*C*^{−1}(*c*)*, obeys*

We write as a shorthand for . The proof is by induction on *n*. For *n*=0, the statement is easily seen to be true. Assume now *n*>0. Let *y*_{1}, *y*_{2} be the first two bits of *y* and *y*′ the rest, i.e. *y*=*y*_{1}*y*_{2}*y*′. To explain the argument, let us, for instance, look at the case *y*_{1}*y*_{2}=01. For any *x*′∈{0, 1}^{2n−1}, we have if *x*_{1}*x*_{2}∈{00, 10, 11} and we have if *x*_{1}*x*_{2}=01. This observation yieldswhere we used in the second equality for any and for . By the inductive assumption and thus . In the other cases for *y*_{1}*y*_{2}, we getfrom which the bound follows by the same argument as above. ▪

We now analyse a *k*-block protocol, where for simplicity *k* is even. We only consider the case where Alice commits to *c*=0 and *c*=1 each with probability 1/2.

*Assume Alice and Bob run a k-block protocol, in which in each block* 2*n*+1 *boxes are used*. *Then the probability that Bob can guess the committed bit correctly is upper bounded by* 1/2+*k*/2^{n+1}.

Let *r*_{i} be Bob's best guess for *c* using only *x*.*y* from the *i*th block. Set *ϵ*_{i}, such that . By lemma 3.1, 0≤*ϵ*≤1/2^{n+1}. Note that Bob's only information about *c* is *r*_{1}, …, *r*_{k}.

Let us think of the process of how *r*_{i} is obtained in a way which is easier to analyse but equivalent to the original. With probability 1−2*ϵ*_{i} (a) the bit *r*_{i} is chosen randomly from {0, 1} and with probability 2*ϵ*_{i} (b) *r*_{i} is set to *c*.

By the union bound the probability that at least once during the *k* blocks case (b) occurs is at most . Thus, with probability at least 1−*k*/2^{n} the bits *r*_{1}, …, *r*_{k} are completely random. Bob's probability of guessing correctly is upper bounded by . ▪

Note that the analysis in lemma 3.2 is not tight, but sufficient for our purposes.

## 4. 1-2 OT from NL Boxes

We now show how to construct 1-2 OT from NL Boxes. We thereby assume that Alice and Bob have access to a secure BC scheme as given in §3 for sufficiently large *k*. Our protocol extends the protocol suggested by Wolf & Wullschleger (2005) and uses an idea presented in the context of quantum oblivious transfer by Crépeau (1987, 1994) and Crépeau & Kilian (1988).

### (a) Protocol

Before presenting the actual protocol, we briefly discuss the intuition behind it. The rough idea is that using NL Boxes, we can approximate an erasure channel from Alice and Bob. Suppose Alice has input *v*∈{0, 1}. She picks *y*∈_{R}{0, 1}, sets *r*_{y}=*v* and picks . If Alice inputs and Bob inputs *y*′∈_{R}{0, 1} to an NL Box, they will obtain outputs *a* and *b*, with . If Alice now sends to Bob, Bob will obtain *r*_{y′} by computing . He cannot obtain more than one bit of information, as he receives only one bit of communication from Alice. Now Alice announces *y* to Bob. If *y*=*y*′, Bob received Alice's input bit *r*_{y′}=*v*. This happens with probability 1/2. The only trick we need is to make sure Bob actually did use the NL Box and made his choice of *y*′ before Alice's announcement. To achieve this, BC is used in step 2.

### (b) Correctness

We first need to show that if both parties are honest, Bob succeeds in retrieving *s*_{c} with high probability. Note that Bob can retrieve *s*_{c}, if he can construct a set , with , where , since only then and he can computeWe are thus interested in the probability of Bob constructing such a set successfully. Let *X*_{i} be the random variable, such that . Note that since Alice and Bob choose *y*_{i} and independently uniformly at random, the random variable is binomially distributed. From Hoeffding's inequality (Hoeffding 1963), we obtain(4.1)Then,where the last inequality comes from equation (4.1). Thus, the probability of Bob failing is exponentially small in *n*.

### (c) Security against Alice

Suppose that Bob is honest, but Alice tries to learn *c*. As outlined in §2, NL Boxes do not allow signalling and therefore Alice learns nothing during step 1 of the protocol. Due to the concealing properties of the BC scheme, Alice's information gain in step 2 is negligible for a sufficiently large security parameter *k*. Thus, the only time she receives information from Bob is during step 4. Note that Bob picks independently of *y*_{i}. Alice has no information on . This means that the elements of the sets *J*_{0} and *J*_{1} are independent of *c* from Alice's point of view: their composition depends only on whether for a given *i*. Alice thus learns nothing from observing the sets *J*_{0} and *J*_{1}.

Note that Alice gains nothing from trying to delay her own boxes. By delaying boxes in the commitment protocol employed in step 2, she will only remain more ignorant about Bob's commitment. Furthermore, each round *i* in step 1 corresponds to Alice using an erasure channel with input , because the following two conditions are satisfied: step 2 ensures us that Bob uses this channel, and since Alice sends *y*_{i} to Bob during step 3, Bob knows whether he obtained *v*_{i}. The situation where Alice delays using the boxes is equivalent to using the channel with a randomly chosen input and gives her no additional advantage. Since we can construct an erasure channel, we thus obtain an 1-2 OT via the above construction (Crépeau 1987).

### (d) Security against Bob

Now suppose that Alice is honest, but Bob tries to learn more than *s*_{c}. We now show that Bob can retrieve exactly one of the bits *s*_{0}, *s*_{1}. In particular, we show that he cannot compute any function *f* of *s*_{0} and *s*_{1} which depends on both input bits.1

Because Alice is honest, all *v*_{i} are independent. Furthermore, since the sets *J*_{0} and *J*_{1} are disjoint, it follows that and are independent. All Bob receives from Alice is and . Thus, in order to compute any function *f* of *s*_{0}, *s*_{1} which depends on both input bits, Bob needs to learn both *r* and *r*′. Bob will only obtain *r* and *r*′ and then also learn more than one of the bits *s*_{0}, *s*_{1}, if he succeeds in creating two sets *J*_{0}, *J*_{1}⊂[*n*], with and , such that . We are therefore interested in the probability that Bob can successfully construct two such sets.

In order to construct such sets, Bob may try to delay using some of the NL Boxes during step 1. This will enable him to wait for the announcement in step 3, to force *y*_{i}=*y*_{i}′ and obtain *v*_{yi} with certainty. By assumption, the BC scheme is binding for sufficiently large *k* and thus Bob cannot try to fool Alice by breaking the commitment itself. However, he can try to commit to random values and escape detection during step 2. In particular, he can choose to be honest in step 1 for exactly one NL Box in runs *i* and *n*+*i*. Without loss of generality, suppose he was honest in run *n*+*i* and delayed use of the box in run *i*, he then commits once to the outcome of the honest box, and once to and a random *b*_{i}∈_{R}{0, 1}. The probability that Alice challenges him on the box he has been honest with in step 1 is 1/2. Then he has succeeded to cheat on one of the bits, , and will obtain *v*_{yi} with certainty. However, with probability 1/2, Alice will challenge him on the other NL Box. In this case, he can escape detection with probability 1/2. He announces and *b*_{i} and hopes that this matches the input of Alice's box. He will have committed to the correct *b*_{i} with probability 1/2 and then he escapes detection. Thus, the total probability of cheating successfully on one of the bits is given by 1/2+(1/2)(1/2)=3/4. Let *C*⊆[*n*], with , 0≤*k*≤*n* denote the set of indices on which Bob tries to deceive Alice. He will remain undetected with probabilitySuppose now, that Bob successfully cheated on *k* bits. We are then interested in bounding the probability of constructing two valid sets if Bob already has *k* valid entries. Note that we now only consider the probability of achieving for indices *i*∉*C* and then . For *k*<*n*,If *k*=*n*, Bob will be caught with probability (3/4)^{n}. Thus, the probability of Bob deceiving Alice can be made arbitrarily small by choosing *n* large.

## 5. Conclusion

We have shown how to obtain protocols for BC and 1-2 OT given access to non-local boxes. This creates a link between cryptographic problems, which may appear very artificial, and non-local correlations. If such NL Boxes were available in nature, we could implement these cryptographic protocols securely, which is known to be impossible to achieve using quantum mechanics alone.

Interestingly, the quantum mechanical impossibility proofs for BC and coin tossing (Mayers 1996, 1997; Lo & Chau 1997, 1998; Lo 1997) via the so-called EPR-attack (Einstein–Podolsky–Rosen-attack) are the quantum version of delaying the input. One may want to go back to explore why we could circumvent this attack here, and the reason seems to be that the NL Box is more like a quantum mechanical entangled state *together with an encasing experimental setup*, which enforces that the particles can only be measured separately. In contrast, for the EPR-attack to work, Alice has to be able to perform arbitrary collective operations on her qubits.

## Acknowledgments

We thank the Newton Institute Cambridge for hosting the QIS workshop where a part of this paper originated. This project was supported by the EU under project RESQ (IST-2001-37559). M.C. and A.W. acknowledge furthermore support by the UK Engineering and Physical Sciences Research Council. M.C. acknowledges the support of a DAAD Doktorandenstipendium; H.B., F.U. and S.W. receive support from the NWO vici project 2004–2009. We would also like to thank Stefan Wolf and Jürg Wullschleger for discussions on their work (Wolf & Wullschleger 2005). Furthermore, we would like to thank Serge Fehr and Robbert de Haan for useful discussions about 1-2 OT.

## Footnotes

↵A function

*f*depends on the*j*th input argument if there is an input to*f*, such that changing the*j*th argument changes the value of*f*.- Received November 18, 2005.
- Accepted January 6, 2006.

- © 2006 The Royal Society