More efficient oblivious transfer and extensions for faster secure computation

More efficient oblivious transfer and extensions for faster secure computation

Gilad Asharov, Yehuda Lindell, Thomas Schneider, Michael Zohner
ACM CCS 2013 [pdf] [bibtex]

Several optimizations to the basic IKNP03 OT extension protocol are described:

Computational optimizations:

  • Instead of parallelizing the protocol by pipelining the different (not computationally symmetric) steps of the protocol, the large matrices of the OT extension protocol are divided into independent blocks and each thread carries out all steps of the protocol on one block.
  • In the IKNP protocol, the sender receives a large matrix row-wise but hashes it column-wise, requiring a matrix transposition. Surprisingly, this step accounted for 43% of the running time of the protocol. By simply using Eklundh's cache-aware transposition algorithm, performance of this step was increased by a factor of 9.

Protocol optimizations:

In many settings (e.g., using OT to transfer garbled wire labels), one or both of the sender's inputs to OT are chosen randomly. In these cases, the communication requirements of the protocol can be greatly improved. Quoting our summary of the basic IKNP03 protocol:

the sender encrypts the two messages ⚠ {$m_0, m_1$} under one-time pads with keys ⚠ {$H(i \| Q_{i,*})$} and ⚠ {$H(i \| Q_{i,*} \oplus s)$}, respectively, where ⚠ {$H$} is a random oracle.

When ⚠ {$m_0$} can be chosen random, we can simply set ⚠ {$m_0 := H(i \| Q_{i,*})$}, and now the first of these messages does not need to be sent (it would always be the all-zeroes string if sent). Similarly, we can set ⚠ {$m_1 := H(i \| Q_{i,*} \oplus s)$} when ⚠ {$m_1$} is allowed to be chosen randomly as well. When ⚠ {$H$} is a random oracle, this optimization is secure and results in the communication from sender to receiver being halved or even eliminated entirely when both strings can be chosen randomly. These optimizations are directly analogous to row reduction optimizations used in garbled circuits.

Categories:

OTExtension