16

Suppose you have two arbitrarily powerful participants who don't trust each other. They have access to bit commitment (e.g., sealed envelopes containing data that one player can hand to the other but that can't be opened until the first player gives the second a key). Can you use this to build an oblivious transfer protocol. Is this true even if the players agree to open all the envelopes at the end to detect cheating (e.g., after the poker hand is played, everybody agrees to reveal their cards)?

I assume that you can't get oblivious transfer out of bit commitment, because oblivious transfer is cryptographically universal, and I can't find any references that say bit commitment is, but is there a proof somewhere that you can't do it?

Finally, has anybody looked at the problem if the players are quantum?

Peter Shor
  • 24,763
  • 4
  • 93
  • 133
  • 2
    In a comment on a question on mathoverflow, it is stated that quantum Oblivious Transfer is equivalent to quantum Bit Commitment (with references) : http://mathoverflow.net/questions/32801/is-there-a-two-party-multiplicative-and-additive-secret-sharing-scheme/33884#33884 . – Mohammad Alaggan Nov 08 '10 at 17:34
  • 4
    These two papers show that unconditionally secure quantum bit commitment is impossible. If you could do quantum oblivious transfer, that would imply you could do quantum bit commitment, so they also show unconditionally secure quantum oblivious transfer is also impossible. What I'm wondering about is if you are given (as a black box) bit commitment that works for quantum protocols, could you also do oblivious transfer for quantum protocols. – Peter Shor Nov 08 '10 at 18:10
  • 3
    Maybe a little more background is necessary. I think I have a rather simple scheme which, given bit commitment, uses it to achieve oblivious transfer in a quantum protocol. I wanted (1) to know what the classical proofs were that oblivious transfer is strictly more powerful, to make sure that they don't apply to the quantum case, and (2) to know whether anybody has observed this before. The literature for quantum oblivious transfer and bit commitment is difficult to search because several proofs of security fell apart when Mayers and Lo and Chau proved their no-go theorem. – Peter Shor Nov 08 '10 at 19:18
  • 4
    Searching the literature a little more, there is a bit-commitment ==> oblivious transfer proof in the quantum regime in a 1991 paper of Bennett, Brassard, Crépeau and Skubiszewska (http://www.springerlink.com/content/k6nye3kay7cm7yyx/), so this is known. – Peter Shor Nov 08 '10 at 22:21
  • 2
    @M. Alaggan: Let me apologize for dismissing your comment above so abruptly. The author of the MathOverflow comment you referred to probably did know they were equivalent, and in fact that comment did put me on the bibliographical trail which led to the reference proof I found in my above comment. So, many thanks. – Peter Shor Nov 10 '10 at 14:22

2 Answers2

14

No, commitment has strictly lower complexity than OT. I think an easy way to see this is the approach taken in Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation by Maji, Prabhakaran, Rosulek in TCC 2009 (disclaimer: self promotion!). In that paper we have a result characterizing what you can do given access to ideal commitment in the UC model with statistical security.

Suppose there were a statistically secure protocol (against malicious adversaries) $\pi$ for OT using access to ideal black-box bit commitment. Then $\pi$ must be secure against honest-but-curious adversaries as well (not as trivial as it probably sounds, but not very difficult to show either). But you could compose $\pi$ with the trivial honest-but-curious protocol for commitment, and have an honest-but-curious OT protocol that is statistically secure with no setups. But this is known to be impossible.

Another way to see it is through Impagliazzo-Rudich. If you have computationally unbounded parties and a random oracle, you can do commitment (since all you need are one-way functions) but you cannot do things like key agreement, and thus not OT.

Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152
mikero
  • 2,799
  • 22
  • 23
  • 1
    @Mikero: that's a really nice, and simple, proof. – Peter Shor Nov 08 '10 at 18:12
  • For OT of classical bits (i.e., classical ideal world) the argument will go through for quantum protocols/adversaries. If the OT manipulates qbits then there may be complications. The step that is "not as trivial as it sounds but not difficult" involves saying that WLOG the simulator always uses the input supplied by the environment. This is a property of OT that must be shown (if the simulator didn't send what was given, the outputs would be incorrect with noticeable probability, thus the simulation unsound), and would have to be re-argued if the environment can give/receive qbits from OT. – mikero Nov 08 '10 at 19:31
  • 1
    @Mikero: I don't understand your previous comment. What does it mean for the OT not to manipulate qubits? Do you mean that the two parties just communicate with classical bits, but may have quantum processors? This would follow from the fact that no information-theoretic secure protocol for OT exists, even with bit commitment. – Peter Shor Nov 08 '10 at 21:47
  • I'm considering whether a "quantum OT protocol" means classical OT (OT functionality only know about bits) with a possibly quantum protocol, or an OT in which the environment knows about qubits and the OT sends/receives qubits. In the former case, I think the same argument goes through unmodified. Presumably you mean the latter case. Then if there really is a counterexample in the quantum world it would mean that OT of qubits does not have the property that WLOG the simulation maps honest-but-curious real-world adversaries to honest-but-curious ideal adversaries. Interesting! – mikero Nov 08 '10 at 23:03
  • 1
    If I understand your question correctly, both the Bennett et al. paper and my proof are for classical OT, with quantum messages between the participants to implement the OT. – Peter Shor Nov 09 '10 at 00:41
  • @Mikero: I think there is an honest-but-curious quantum protocol for 1-out-of-2 oblivious transfer. Alice sends Bob two qubits, one with the bit encoded in basis X, and the other encoded in a complementary basis Y. Bob measures both in some basis. Alice then tells Bob which qubit was encoded in which basis. Bob learns the qubit encoded in that basis, but nothing about the one encoded in the other basis. In fact, this protocol (with bit commitment added cleverly so the participants can't cheat) shows that bit commitment -> oblivious transfer. – Peter Shor Nov 11 '10 at 22:33
  • @Peter Shor: OK, yes, that sounds right for honest-but-curious quantum adversaries. Good to know where exactly the "commitment $\not\Rightarrow$ OT" argument breaks down for quantum protocols. – mikero Nov 12 '10 at 20:15
7

In the quantum case, the first protocol to build (classical) oblivious transfer based on (classical) bit commitment using a quantum protocol was proposed in 1991 by Bennett, Brassard, Crépeau and Skubiszewska (http://www.springerlink.com/content/k6nye3kay7cm7yyx/), but a complete proof of security was given only recently by Damgaard, Fehr, Lunemann, Salvail and Schaffner in http://arxiv.org/abs/0902.3918

For an extension to multi-party computation and a proof in the universal compasability framework, see the work by Unruh: http://arxiv.org/abs/0910.2912

Christian Schaffner
  • 71
  • 1
  • 1