Cryptology ePrint Archive: Report 2019/1159

Efficient Two-Round OT Extension and Silent Non-Interactive Secure Computation

Elette Boyle and Geoffroy Couteau and Niv Gilboa and Yuval Ishai and Lisa Kohl and Peter Rindal and Peter Scholl

Abstract: We consider the problem of securely generating useful instances of two-party correlations, such as many independent copies of a random oblivious transfer (OT) correlation, using a small amount of communication. This problem is motivated by the goal of secure computation with silent preprocessing, where a low-communication input-independent setup, followed by local ("silent") computation, enables a lightweight "non-cryptographic" online phase once the inputs are known.

Recent works of Boyle et al. (CCS 2018, Crypto 2019) achieve this goal with good concrete efficiency for useful kinds of two-party correlations, including OT correlations, under different variants of the Learning Parity with Noise (LPN) assumption, and using a small number of "base" oblivious transfers. The protocols of Boyle et al. have several limitations. First, they require a large number of communication rounds. Second, they are only secure against semi-honest parties. Finally, their concrete efficiency estimates are not backed by an actual implementation. In this work we address these limitations, making three main contributions:

- Eliminating interaction. Under the same assumption, we obtain the first concretely efficient 2-round protocols for generating useful correlations, including OT correlations, in the semi-honest security model. This implies the first efficient 2-round OT extension protocol of any kind and, more generally, protocols for non-interactive secure computation (NISC) that are concretely efficient and have the silent preprocessing feature.

- Malicious security. We provide security against malicious parties (in the random oracle model) without additional interaction and with only a modest concrete overhead; prior to our work, no similar protocols were known with any number of rounds.

- Implementation. Finally, we implemented, optimized, and benchmarked our 2-round OT extension protocol, demonstrating that it offers a more attractive alternative to the OT extension protocol of Ishai et al. (Crypto 2003) in many realistic settings.

Category / Keywords: cryptographic protocols / Secure computation, oblivious transfer, pseudorandom correlation generator

Original Publication (with major differences): ACM Conference on Computer and Communications Security (CCS '19)

Date: received 6 Oct 2019

Contact author: peter scholl at cs au dk

Available format(s): PDF | BibTeX Citation

Version: 20191007:082546 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]