Irving Street Functionality

This is supposed to be a blog.

recent posts
posted 03 Feb, 2021

Precomputing Oblivious Transfer; Donald Beaver; 1995

author Donald Beaver
title Precomputing Oblivious Transfer
howpublished Advances in Cryptology - CRYPT0 ’95, LNCS 963, pp. 97-109
year 1995
where Penn State University, University Park, PA

A lot’s changed in 25 years. The paper’s entirely readable in a modern context, but everything from the class of applications in which the author is interested, to the choice of fonts, reminds the reader of this foreign context. The paper is short, and half of it is just laying out the theoretical framework within which it’s going to describe it’s contribution.

The lasting contribution that’s of interest to my work is the ability to do most of the heavy lifting of a 1-of-2 OT in advance (that is, before either party has decided on their inputs to the “real” oblivious transfer). This has obvious performance implications for, for example, GMW circuit execution. (Actually realizing a total speed boost may not be trivial though.)


A and B perform normal oblivious transfer with random inputs.

A generates random values (R0, R1), and knows them.
B generates random value d, and learns Rd.

Then at runtime, when A knows the real values (B0, B1) and B knows the real choice c, the oblivious transfer can be completed with only three more bits being communicated.

B sends e = c ⊕ d.
A sends x0 = B0 ⊕ Re and x1 = B1 ⊕ R(!e).

Consider the four cases for (c, d) (neither of which are known to A) and e (which A does know):

This gets used by a variety of later works, including the recent “basically free IF” paper.