We show here that the recent work of Wolf and Wullschleger (quant-ph/0502030) on oblivious transfer apparently opens the possibility that non-local correlations which are stronger than those in quantum mechanics could be used for bit-commitment. This is surprising, because it is the very existence of non-local correlations which in quantum mechanics prevents bit-commitment. We resolve this apparent paradox by stressing the difference between non-local correlations and oblivious transfer, based on the time-ordering of their inputs and outputs, which prevents bit-commitment.
Oblivious transfer, a central functionality in modern cryptography, allows a party to send two one-bit messages to another who can choose one of them to read, remaining ignorant about the other, whereas the sender does not learn the receiver's choice. Oblivious transfer the security of which is information-theoretic for both parties is known impossible to achieve from scratch. The joint behavior of certain bi-partite quantum states is non-local, i.e., cannot be explained by shared classical information. In order to better understand such behavior, which is classically explainable only by communication, but does not allow for it, Popescu and Rohrlich have described a "non-locality machine": Two parties both input a bit, and both get a random output bit the XOR of which is the AND of the input bits. We show a close connection, in a cryptographic sense, between OT and the "PR primitive." More specifically, unconditional OT can be achieved from a single realization of PR, and vice versa. Our reductions, which are single-copy, information-theoretic, and perfect, also lead to a simple and optimal protocol allowing for inverting the direction of OT
Correlated oblivious transfer (COT) is a crucial building block for secure multi-party computation (MPC) and can be generated efficiently via OT extension. Recent works based on the pseudorandom correlation generator (PCG) paradigm presented a new way to generate random COT correlations using only communication sublinear to the output length. However, due to their high computational complexity, these protocols are only faster than the classical IKNP-style OT extension under restricted network bandwidth. In this paper, we propose new COT protocols in the PCG paradigm that achieve unprecedented performance. \em With
50 Mbps network bandwidth, our maliciously secure protocol can produce one COT correlation in
22 nanoseconds. More specifically, our results are summarized as follows: \beginenumerate \item We propose a semi-honest COT protocol with sublinear communication and linear computation. This protocol assumes primal-LPN and is built upon a recent VOLE protocol with semi-honest security by Schoppmann et al. (CCS 2019). We are able to apply various optimizations to reduce its communication cost by roughly
15×, not counting a one-time setup cost that diminishes as we generate more COT correlations. \item We strengthen our COT protocol to malicious security with no loss of efficiency. Among all optimizations, our new protocol features a new checking technique that ensures correctness and consistency essentially for free. In particular, our maliciously secure protocol is only \em
1−3 nanoseconds slower for each COT. \item We implemented our protocols, and the code will be publicly available at EMP toolkit. We observe at least
9× improvement in running time compared to the state-of-the-art protocol by Boyle et al. (CCS 2019) in both semi-honest and malicious settings under any network faster than
50 Mbps. \endenumerate With this new record of efficiency for generating COT correlations, we anticipate new protocol designs and optimizations will flourish on top of our protocol.