Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Oblivious transfer from non-local correlations

Adrian Rabenseifner

Published Jan 1, 2009• 0 citations
Publisher
DOI
10.3929/ethz-a-005772961

Related papers

Efficient Oblivious Transfer Protocols Achieving a Non-zero Rate from Any Non-trivial Noisy Correlation

Hideki Imai, Kirill Morozov, Anderson C. A. Nascimento

Lecture notes in computer science•Jan 1, 2009•5 citations

Oblivious Transfer from Correlated Randomness

Himanshu Tyagi, Shun Watanabe

Cambridge University Press eBooks•Mar 23, 2023•0 citations

Oblivious transfer and quantum non-locality

Stefan Wolf, Jürg Wullschleger

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

arXiv:quant-ph/0502030•IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•55 citations

Ferret: Fast Extension for Correlated OT with Small Communication

Kang Yang, Chenkai Weng, Xiao Lan +2 more

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\times$, 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\times$ 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.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 30, 2020•155 citations

Randomness From Non-Local Correlations

Viktor Galliard

•Jan 1, 2012•0 citations

On (Im)possibility of Oblivious Transfer via Noisy Multiple Access Channels and Non-Signaling Correlations

Hadi Aghaee, Christian Deppe, Holger Boche

We investigate the feasibility of oblivious transfer over discrete memoryless multiple-access channels assisted by tripartite non-signaling correlations among honest-but-curious parties. Modeling the shared resource as an arbitrary non-signaling box provides a unified framework encompassing both channel behavior and induced correlations, including quantum and super-quantum resources. Our main result establishes an impossibility: oblivious transfer cannot be achieved, as any nontrivial non-signaling correlation used as resources inevitably causes receiver’s observation to depend on both senders’ inputs, violating sender-privacy. Consequently, no tripartite non-signaling assistance, including entanglement or PR-box–type correlations, can enable or enhance network oblivious transfer over noisy multiple-access channels.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 citations
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 505050 Mbps network bandwidth, our maliciously secure protocol can produce one COT correlation in 222222 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×15\times15×, 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−31-31−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×9\times9× 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 505050 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.
We investigate the feasibility of oblivious transfer over discrete memoryless multiple-access channels assisted by tripartite non-signaling correlations among honest-but-curious parties. Modeling the shared resource as an arbitrary non-signaling box provides a unified framework encompassing both channel behavior and induced correlations, including quantum and super-quantum resources. Our main result establishes an impossibility: oblivious transfer cannot be achieved, as any nontrivial non-signaling correlation used as resources inevitably causes receiver’s observation to depend on both senders’ inputs, violating sender-privacy. Consequently, no tripartite non-signaling assistance, including entanglement or PR-box–type correlations, can enable or enhance network oblivious transfer over noisy multiple-access channels.