Implications of superstrong non-locality for cryptography

Harry Buhrman, Matthias Christandl, Falk Unger, Stephanie Wehner, Andreas Winter

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.

Keywords:

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)Embedded ImageHere, x∈{0, 1} and y∈{0, 1} denote the choice of Alice's and Bob's measurement, ax∈{0, 1} and by∈{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 Embedded Image, 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 ax, by, such that Embedded Image. Note that Alice and Bob still cannot use this box to transmit any information. However, since for all x and y, Embedded Image, 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 s0 and s1. 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 §2b for definitions): the sender uses inputs sk=b and Embedded Image, with kR{0, 1}. The receiver uses input c∈{0, 1}. The players now perform 1-2 OT(s0, s1)(c) after which the receiver holds sc. 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 yRS if y is chosen uniformly at random from S. In addition, we use x.y to denote the inner product Embedded Image between strings x=x1, …, xn and y=y1, …, yn from {0, 1}n. Furthermore, for strings x∈{00, 01, 10, 11}*, we define Embedded Image recursively. For the empty word ε define Embedded Image. For a, b∈{0, 1} and strings x∈{00, 01, 10, 11}*, define Embedded Image if ab=11 and Embedded Image otherwise. Informally, for strings x of even length, Embedded Image 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:

  1. Once Alice inputs x∈{0, 1}, she instantaneously receives outcome a∈{0, 1},

  2. Once Bob inputs y∈{0, 1}, he instantaneously receives outcome b∈{0, 1}, such that Embedded Image. Further, we demand that for all c1, c2, c3∈{0, 1}

Embedded Image

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:

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

  2. (Binding) Assume (a possibly dishonest) Alice wants to reveal bit c′. Then always

Embedded Image

  1. (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 Embedded Image 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 (s0, s1)(c)) is a two-party protocol between Alice (the sender) and Bob (the receiver), such that the following holds:

  1. (Correctness) If both Alice and Bob are honest, the protocol depends on Alice's two input bits s0, s1∈{0, 1} and Bob's input bit c∈{0, 1}. At the end of the protocol Bob knows sc.

  2. (Security against Alice) If Bob is honest, Alice does not learn c.

  3. (Security against Bob) If Alice is honest, Bob does not learn anything about Embedded Image.

Again, our protocol is probabilistic and achieves statistical security for a security parameter n. The probability that Bob learns Embedded Image 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 §1a, 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:

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

  2. (Security against Alice) If Bob is honest, Alice does not learn whether Bob obtained b.

  3. (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 2n+1 shared non-local boxes. We later fix the security parameter n, such that we achieve sufficient security against Bob.

Embedded Image

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 §3a, 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.

Embedded Image

If Alice and Bob run the full protocol NLBC(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:

  1. 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 xi. If she does not change the corresponding output bit ai and if Bob had input yi=1, she will be caught. Similarly, if she changes ai but Bob had input yi=0, she will be caught. Because Embedded Image, she is detected with probability at least 1/2.

  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 ai'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 ai's will be different from A′. Thus, in this case she has to change at least one ai. But if yi=0 (yi=1) and Alice does (does not) change xi, 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 xi's into her boxes. With probability 1/2, the parity of the outputs ai 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 x1 and a1 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 y1=0. If Bob is honest we have Embedded Image. 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 kk* blocks. For strategy 1, she commits to 1 in k1 blocks and to 0 in k0=kk*k1 blocks, where k1kk*. Then security against Alice as in definition 2.2 follows by proving that the following is close to 1:Embedded ImageWithout loss of generality we can assume k1k0. Then Embedded Image. Thus, if k*>2 or k0>0, the last expression is certainly less or equal to 1. For k*≤2 and k0=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: Embedded Image.

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

Assume now Bob chooses Embedded Image. 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 Embedded Image, 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 2n+1 NL Boxes, where Bob chooses some Embedded Image and Alice commits to some c∈{0, 1}. Then the probability for x.y=c, averaged over all xC−1(c), obeysEmbedded Image

We write Embedded Image as a shorthand for Embedded Image. The proof is by induction on n. For n=0, the statement is easily seen to be true. Assume now n>0. Let y1, y2 be the first two bits of y and y′ the rest, i.e. y=y1y2y′. To explain the argument, let us, for instance, look at the case y1y2=01. For any x′∈{0, 1}2n−1, we have Embedded Image if x1x2∈{00, 10, 11} and we have Embedded Image if x1x2=01. This observation yieldsEmbedded Imagewhere we used in the second equality Embedded Image for any Embedded Image and Embedded Image for Embedded Image. By the inductive assumption Embedded Image and thus Embedded Image. In the other cases for y1y2, we getEmbedded Imagefrom 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 2n+1 boxes are used. Then the probability that Bob can guess the committed bit correctly is upper bounded by 1/2+k/2n+1.

Let ri be Bob's best guess for c using only x.y from the ith block. Set ϵi, such that Embedded Image. By lemma 3.1, 0≤ϵ≤1/2n+1. Note that Bob's only information about c is r1, …, rk.

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

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

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 yR{0, 1}, sets ry=v and picks Embedded Image. If Alice inputs Embedded Image and Bob inputs y′∈R{0, 1} to an NL Box, they will obtain outputs a and b, with Embedded Image. If Alice now sends Embedded Image to Bob, Bob will obtain ry by computing Embedded Image. 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 ry=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.

Embedded Image

(b) Correctness

We first need to show that if both parties are honest, Bob succeeds in retrieving sc with high probability. Note that Bob can retrieve sc, if he can construct a set Embedded Image, with Embedded Image, where Embedded Image, since only then Embedded Image and he can computeEmbedded ImageWe are thus interested in the probability of Bob constructing such a set successfully. Let Xi be the random variable, such that Embedded Image. Note that since Alice and Bob choose yi and Embedded Image independently uniformly at random, the random variable Embedded Image is binomially distributed. From Hoeffding's inequality (Hoeffding 1963), we obtainEmbedded Image(4.1)Then,Embedded Imagewhere 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 Embedded Image independently of yi. Alice has no information on Embedded Image. This means that the elements of the sets J0 and J1 are independent of c from Alice's point of view: their composition depends only on whether Embedded Image for a given i. Alice thus learns nothing from observing the sets J0 and J1.

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 Embedded Image, because the following two conditions are satisfied: step 2 ensures us that Bob uses this channel, and since Alice sends yi to Bob during step 3, Bob knows whether he obtained vi. 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 sc. We now show that Bob can retrieve exactly one of the bits s0, s1. In particular, we show that he cannot compute any function f of s0 and s1 which depends on both input bits.1

Because Alice is honest, all vi are independent. Furthermore, since the sets J0 and J1 are disjoint, it follows that Embedded Image and Embedded Image are independent. All Bob receives from Alice is Embedded Image and Embedded Image. Thus, in order to compute any function f of s0, s1 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 s0, s1, if he succeeds in creating two sets J0, J1⊂[n], with Embedded Image and Embedded Image, such that Embedded Image. 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 yi=yi′ and obtain vyi 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 Embedded Image and a random biR{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, Embedded Image, and will obtain vyi 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 Embedded Image and bi and hopes that this matches the input of Alice's box. He will have committed to the correct bi 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 Embedded Image, 0≤kn denote the set of indices on which Bob tries to deceive Alice. He will remain undetected with probabilityEmbedded ImageSuppose 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 Embedded Image for indices i∉C and then Embedded Image. For k<n,Embedded ImageIf 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 jth input argument if there is an input to f, such that changing the jth argument changes the value of f.

    • Received November 18, 2005.
    • Accepted January 6, 2006.

References

View Abstract