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 15x, 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 9x 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 / correlated oblivious transfer, secure computation Original Publication (with minor differences): 2020 ACM SIGSAC Conference on Computer and Communications Security (CCS'20)