| 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 valued, and learnsRd.
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 sendsx0 = B0 ⊕ Reandx1 = B1 ⊕ R(!e).
Consider the four cases for (c, d) (neither of which are known to A) and e (which A does know):
(0, 0), 0: B gets B0 ⊕ R0 and B1 ⊕ R1. Since they already know R0, they can figure out B0 (which is Bc), but they can’t figure out B1 because they never learned R1.(0, 1), 1: B gets B0 ⊕ R1 and B1 ⊕ R0. Since they already know R1, they can figure out B0, but they can’t figure out B1 because they never learned R0.(1, 0), 1: B gets B0 ⊕ R1 and B1 ⊕ R0. Since they already know R0, they can figure out B1, but they can’t figure out B0 because they never learned R1.(1, 1), 0: B gets B0 ⊕ R0 and B1 ⊕ R1. Since they already know R1, they can figure out B1, but they can’t figure out B0 because they never learned R0.This gets used by a variety of later works, including the recent “basically free IF” paper.