  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.
