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: ia.cr/2020/924