Cryptology ePrint Archive: Report 2020/924

Ferret: Fast Extension for coRRElated oT with small communication

Kang Yang and Chenkai Weng and Xiao Lan and Jiang Zhang and Xiao Wang

Abstract: 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. 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:

- 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 COTs.

- 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 $1-3$ nanoseconds slower for each COT.

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

With this new record of efficiency for generating COT correlations, we anticipate new protocol designs and optimizations will flourish on top of our protocol.

Category / Keywords: cryptographic protocols / vector OLE, secure computation

Date: received 24 Jul 2020

Contact author: wangxiao at cs northwestern edu

Available format(s): PDF | BibTeX Citation

Version: 20200726:062703 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]