Geoffroy Couteau
CNRS, IRIF, Université Paris Cité

Lalita Devadas
MIT

Srinivas Devadas
MIT

Alexander Koch
CNRS, IRIF, Université Paris Cité

Sacha Servan-Schreiber
MIT

Keywords:

Abstract

Oblivious Transfer (OT) is at the heart of secure computation and is a foundation for many applications in cryptography. Over two decades of work have led to extremely efficient protocols for evaluating OT instances in the preprocessing model, through a paradigm called OT extension. A few OT instances generated in an offline phase can be used to perform many OTs in an online phase efficiently, i.e., with very low communication and computational overheads.

Specifically, traditional OT extension protocols use a small number of “base” OTs, generated using any black-box OT protocol, and convert them into many OT instances using only lightweight symmetric-key primitives. Recently, a new paradigm of OT with a public-key setup has emerged, which replaces the base OTs with a non-interactive setup: Using only the public key of the other party, two parties can efficiently compute a virtually unbounded number of OT instances on-the-fly.

In this paper, we put forth a novel framework for OT extension with a public-key setup and concretely efficient instantiations. An implementation of our framework is 30–100× faster when compared to the previous state-of-the-art public-key OT protocols, and remains competitive even when compared to OT protocols that do not offer a public-key setup. Additionally, our instantiations result in the first public-key schemes with plausible post-quantum security.

In summary, this paper contributes:

- QuietOT: A framework for OT extension with a public-key setup that uses fast, symmetric- key primitives to generate OT instances following a one-time public-key setup, and offering additional features such as precomputability.

- A public-key setup for QuietOT from the RingLWE assumption, resulting in the first post- quantum construction of OT extension with a public-key setup.

- An optimized, open-source implementation of our construction that can generate up to 1M OT extensions per second on commodity hardware. In contrast, the state-of-the-art public-key OT protocol is limited to approximately 20K OTs per second.

- The first formal treatment of the security of OT with a public-key setup in a multi-party setting, which addresses several subtleties that were overlooked in prior work.