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

Implications of superstrong non-locality for cryptography. (English) Zbl 1149.94305

Proc. R. Soc. Lond., Ser. A, Math. Phys. Eng. Sci. 462, No. 2071, 1919-1932 (2006).
Summary: 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.

Cited in 13 Documents

MSC:

94A60 Cryptography

Keywords:

non-locality; non-local boxes; cryptography
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Bell, J.S. 1965 On the Einstein–Podolsky–Rosen paradox. <i>Physics</i>&nbsp;<b>1</b>, 195–200.
[2] Brassard, G. Buhrman, H. Linden, N. Methot, A. Tapp, A. & Unger, F. 2005 A limit on non-locality in any world in which communication complexity is not trivial. See http://arxiv.org/abs/quant-ph/0508042. · Zbl 1228.81055
[3] Cirel’son, B. 1980 Quantum generalizations of Bell’s inequality. <i>Lett. Math. Phys.</i>&nbsp;<b>4</b>, 93–100, (doi:10.1007/BF00417500).
[4] Clauser, J., Horne, M., Shimony, A. & Holt, R. 1969 Proposed experiment to test local hidden-variable theories. <i>Phys. Rev. Lett.</i>&nbsp;<b>23</b>, 880–884, (doi:10.1103/PhysRevLett.23.880). · Zbl 1371.81014
[5] Crépeau, C. 1987 Equivalence between two flavours of oblivious transfers. <i>Proc. CRYPTO–advances in cryptology</i>. pp. 350–354.
[6] Crépeau, C. 1994 Quantum oblivious transfer. <i>J. Mod. Opt.</i>&nbsp;<b>41</b>, 2455–2466.
[7] Crépeau, C. & Kilian, J. 1988 Achieving oblivious transfer using weakened security assumptions. <i>Proc. 29th IEEE FOCS</i>. pp. 42–52.
[8] Even, S., Goldreich, O. & Lempel, A. 1985 A randomized protocol for signing contracts. <i>Commun. ACM</i>&nbsp;<b>28</b>, 637–647, (doi:10.1145/3812.3818).
[9] Gisin, N. Popescu, S. & Short, T. 2005 The physics of no-bit-commitment: generalized quantum non-locality versus oblivious transfer. See http://arxiv.org/abs/quant-ph/0504134. · Zbl 1103.68561
[10] Hoeffding, W. 1963 Probability inequalities for sums of bounded random variables. <i>J. Am. Stat. Assoc.</i>&nbsp;<b>58</b>, 13–30. · Zbl 0127.10602
[11] Kilian, J. 1988 Founding cryptography on oblivious transfer. Proc. 20th ACM STOCpp. 20–31.
[12] Kilian, J. 2000 More general completeness theorems for secure two-party computation. <i>Proc. 32nd ACM STOC</i>. pp. 316–324. · Zbl 1296.94123
[13] Lo, H.-K. 1997 Insecurity of quantum secure computations. <i>Phys. Rev. A</i>&nbsp;<b>56</b>, 1154. (doi:10.1103/PhysRevA.56.1154).
[14] Lo, H.-K. & Chau, H.F. 1997 Is quantum bit commitment really possible?. <i>Phys. Rev. Lett.</i>&nbsp;<b>78</b>, 3410. (doi:10.1103/PhysRevLett.78.3410).
[15] Lo, H.-K. & Chau, H. 1998 Why quantum bit commitment and ideal quantum coin tossing are impossible. <i>Proc. PhysComp98</i>. pp. 177–187. · Zbl 1040.81509
[16] Mayers, D. 1996 The trouble with quantum bit commitment. See http://arxiv.org/abs/quant-ph/9603015.
[17] Mayers, D. 1997 Unconditionally secure quantum bit commitment is impossible. <i>Phys. Rev. Lett.</i>&nbsp;<b>78</b>, 3414–3417, (doi:10.1103/PhysRevLett.78.3414).
[18] Popescu, S. & Rohrlich, D. 1994 Quantum nonlocality as an axiom. <i>Found. Phys.</i>&nbsp;<b>24</b>, 379–385, (doi:10.1007/BF02058098).
[19] Popescu, S. & Rohrlich, D. 1996 Nonlocality as an axiom for quantum theory. <i>ch. 16. Annals of the Israel Physical Society</i><i>The dilemma of Einstein, Podolsky and Rosen, 60 years later: Int. Symp. in honour of Nathan Rosen</i> (eds. Mann, A. & Revzen, M.), vol. 12. Haifa: Israel Physical Society
[20] Popescu, S. & Rohrlich, D. 1997 Causality and nonlocality as axioms for quantum mechanics. In <i>Proc. Symp. of Causality and Locality in Modern Physics and Astronomy: open questions and possible solutions, York University, Toronto, 25–29 August 1997</i>.
[21] Rabin, M. 1981 <i>How to exchange secrets by oblivious transfer</i>. Technical report, Aiken Computer Laboratory, Harvard University, Technical report TR-81.
[22] Shannon, C. 1960 Two-way communication channels. <i>Proc. 4th Berkeley Symp. on Probability and Statistics</i>. pp. 611–644.
[23] van Dam, W. 2000 Nonlocality & communication complexity. Ph.D. thesis, University of Oxford, Department of Physics.
[24] van Dam, W. 2005 Impossible consequences of superstrong nonlocality. See http://arxiv.org/abs/quant-ph/0501159. · Zbl 1336.81021
[25] Wiesner, S. 1983 Conjugate coding. <i>Sigact News</i>&nbsp;<b>15</b>, 78–88, (doi:10.1145/1008908.1008920).
[26] Wolf, S. & Wullschleger, J. 2005 Oblivious transfer and quantum non-locality. In <i>Proc. Int. Symp. on Information Theory (ISIT)</i>, pp. 1745–1748.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.