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.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, 2020139 citations

Communication-efficient distributed oblivious transfer

Amos Beimel, Yeow Meng Chee, Huaxiong Wang +1 more

Journal of Computer and System SciencesFeb 27, 20127 citations

Efficient Oblivious Transfer Protocol Based on Bilinear Pairing

Zhenhua Chen

Oblivious Transfer(OT) protocol is an important primitive for designing cryptographic protocols.Designing OT protocol from bilinear pairing not only extends the bilinear pairing application but also increases the design technique of OT,which has important practical significance.This paper utilizes bilinear pairing to design a k-out-of-n OT protocol.The new protocol can protect both receiver’s privacy and sender’s privacy.The new protocol also can resist impersonation attacks,replay attacks and man-in-the-middle attacks.It can be used in an insecure channel,and the protocol has high efficiency.Oblivious Transfer(OT) protocol is an important primitive for designing cryptographic protocols.Designing OT protocol from bilinear pairing not only extends the bilinear pairing application but also increases the design technique of OT,which has important practical significance.This paper utilizes bilinear pairing to design a k-out-of-n OT protocol.The new protocol can protect both receiver’s privacy and sender’s privacy.The new protocol also can resist impersonation attacks,replay attacks and man-in-the-middle attacks.It can be used in an insecure channel,and the protocol has high efficiency.

Jisuanji gongchengJan 1, 20131 citation

An efficient quantum oblivious transfer protocol

Sushmita Sarkar, Vikas Srivastava, Tapaswini Mohanty +2 more

Cluster ComputingJul 8, 20245 citations

Efficient 1-Out-n Oblivious Transfer Schemes

Wen-Guey Tzeng

Lecture notes in computer scienceJan 1, 200286 citations

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.