Extending Oblivious Transfers Efficiently
Yuval Ishai, Joe Kilian, Kobbi Nissim, Erez Petrank
CRYPTO 2003 [pdf] [bibtex]
Introduces the concept of OT extension. It is well known that oblivious transfer (OT) cannot be based on symmetric-key primitives alone (in a black-box way). Hence OT protocols necessarily rely on expensive public-key operations. OT extension is a method for obtaining a large number of effective OTs using only a small number of "base" OTs (depending only on the security parameter) plus symmetric-key operations, minimizing the cost of OT in an amortized sense.
The protocol achieves ⚠️{$n$}
instances of 1-out-of-2, ⚠️{$\ell$}
-bit string OT, using only ⚠️{$k$}
instances of 1-out-of-2, ⚠️{$n$}
-bit string OT, where ⚠️{$k$}
is the security parameter. Note that it is trivial to extend the bit length of an OT by transfering (via a base OT) a length-⚠️{$k$}
seed to a PRG and masking a longer message with the PRG output (this variant of OT extension is due to Beaver). Hence, the important parameter is that a small, fixed number ⚠️{$k$}
of OTs is extended to an arbitrarily larger number ⚠️{$n$}
of OTs.
- The receiver chooses a random
⚠️{$n \times k$}
matrix⚠️{$T$}
of bits and a string⚠️{$r \in \{0,1\}^n$}
denoting his choice bits in the⚠️{$n$}
logical OTs. The sender chooses random string⚠️{$s \in \{0,1\}^k$}
. - Let
⚠️{$T_{*,j}$}
denote the⚠️{$j$}
th column of⚠️{$T$}
(an⚠️{$n$}
-bit string). The parties use the base OTs (in the opposite direction!), with the receiver providing messages⚠️{$T_{*,j}$}
and⚠️{$T_{*,j} \oplus r$}
, and the sender providing choice bit⚠️{$s_j$}
. - Let
⚠️{$Q$}
denote the matrix that the sender receives from these base OTs (received column-wise). Let⚠️{$Q_{i,*}$}
denote the⚠️{$i$}
th row of⚠️{$Q$}
. The important part of the protocol is that⚠️{$Q_{i,*}$}
is either⚠️{$T_{i,*}$}
or⚠️{$T_{i,*} \oplus s$}
, depending on the receiver's choice bit⚠️{$r_i$}
. - To execute the
⚠️{$i$}
th logical OT, 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. Exactly one of these masks is⚠️{$H(i\|T_{i,*})$}
, according to the receiver's choice bit, so the receiver can unmask his desired message. The other mask is⚠️{$H(i\| T_{i,*} \oplus s)$}
, where⚠️{$s$}
is unknown to the receiver.
Note that, besides the base OTs, the only other operations are calls to the random oracle ⚠️{$H$}
. The protocol is secure against semi-honest adversaries. A cut-and-choose technique can be used to provide security in the malicious setting.
For simplicity, the hash function ⚠️{$H$}
is assumed to be a random oracle. More concretely, the protocol requires that the joint distribution of
⚠️{$t_1,t_2,...,t_n$}
and ⚠️{$H(1\|t_1\oplus s),H(2\|t_2\oplus s),...,H(n\|t_n\oplus s) $}
be psuedorandom where ⚠️{$s$}
is unknown. This security property is called correlation-robustness.
Other links:
Categories:
- Home page
- All papers, by:
- .. category
- .. author names
- .. publication date
- .. recently added
- .. recently updated
- Glossary
- About
- Just getting started in MPC?
- Guidelines
- Todo List
Search Papers
Bibliography Categories