<p>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 <a href="http://arxiv.org/abs/0902.3918">http://arxiv.org/abs/0902.3918</a></p>

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

CC BY-SA 3.0
2011-09-23T22:04:42.500Z
2011-09-23T22:04:42.500Z
Christian Schaffner
<p>No, commitment has strictly lower complexity than OT. I think an easy way to see this is the approach taken in <em>Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation</em> 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.</p>

<p>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.</p>

<p>Another way to see it is through <a href="http://www.springerlink.com/content/xdlq2t5kfnugqywy/">Impagliazzo-Rudich</a>. 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.</p>

CC BY-SA 2.5
2010-11-08T18:12:02.740Z
@Mikero: that's a really nice, and simple, proof.
Peter Shor 
CC BY-SA 2.5
2010-11-08T19:31:48.010Z
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
CC BY-SA 2.5
2010-11-08T21:47:11.210Z
@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 
CC BY-SA 2.5
2010-11-08T23:03:52.097Z
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
CC BY-SA 2.5
2010-11-09T00:41:54.373Z
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 
CC BY-SA 2.5
2010-11-11T22:33:47.973Z
@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 
CC BY-SA 2.5
2010-11-12T20:15:23.640Z
@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
CC BY-SA 2.5
2010-11-08T16:38:06.043Z
2010-11-08T19:38:53.353Z
2010-11-08T19:38:53.353Z
mikero
<p>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)? </p>

<p>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?</p>

<p>Finally, has anybody looked at the problem if the players are quantum?</p>

CC BY-SA 2.5
2010-11-08T17:34:17.487Z
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
CC BY-SA 2.5
2010-11-08T18:10:07.777Z
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 
CC BY-SA 2.5
2010-11-08T19:18:21.137Z
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 
CC BY-SA 2.5
2010-11-08T22:21:48.663Z
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 
CC BY-SA 2.5
2010-11-10T14:22:30.617Z
@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 
<reference-request><cr.crypto-security>
Does bit commitment yield oblivious transfer in the information-theoretic security model?
Peter Shor 
# Does bit commitment yield oblivious transfer in the information-theoretic security model?

(Asked by: username_0 on 2010-11-08)

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?

**Tags:** reference-request, cr.crypto-security

> **Comments:**
> **username_1**: 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 .  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_0**: @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.  

---

## 2 answers

### Answer by username_3 on 2010-11-08. Score: 14 | Accepted answer

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](http://www.springerlink.com/content/xdlq2t5kfnugqywy/). 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.

> **Comments:**
> **username_0**: @Mikero: that's a really nice, and simple, proof.  
> **username_3**: 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.  
> **username_0**: @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.  
> **username_3**: 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!  
> **username_0**: 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.  
> **username_0**: @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.  
> **username_3**: @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.  

---

### Answer by username_2 on 2011-09-23. Score: 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>


---

