Notation and Definitions

  • A 1-out-of-n OT protocol means the receiver get to query the sender \(\log (n)\) possible indexes.

  • If \(S\) is a set, \(x \xleftarrow{\$} S\) denotes sampling some element from \(S\) uniformly at random.

  • \(\mathbb{Z}_p^*\) denotes a multiplicative group of the integers modulo prime \(p\) (a cyclic group).

Oblivious Transfer

OT allows 2 parties to exchange information without revealing any auxiliary information required for the exchange. More specifically, if Alice has an index \(c \in \{1,...,n\}\) and Bob has some data \((x_1, ..., x_n)\), Alice can retrieve \(x_c\) without learning anything about any other \(x_i\) while Bob learns nothing about \(c\).

This may seem like magic, after all, how can Bob learn nothing about \(c\) if he has to send \(x_c\) to Alice? The key insight here is an OT protocol requires Bob to send Alice \((x_1,...,x_n)\) (otherwise Bob would know which data item Alice requested) while also requiring Alice only learns the contents of \(x_c\). In this framework, OT protocols have Bob send Alice \(\{E_{k_i}(x_i) | i \in \{1,..,n\}\}\) where Alice only posses the secret key for \(k_c\).

The Simplest Protocol for OT

Here we present the 1-out-of-2 version of the OT protocol from [1]:

Example 1. The Simplest Protocol for OT

  1. Bob

    • \(b \xleftarrow{\$} \mathbb{Z}^*_p\)

    • send Alice \(B = g^b\)

  2. Alice

    • \(a \xleftarrow{\$} \mathbb{Z}^*_p\)

    • \(A = cBg^a + (1-c)g^a\)

    • Send Bob \(A\)

  3. Bob

    • \(k_0 = A^b\), \(k_1 = (\tfrac{A}{B})^b\)

    • Send Alice \(e_o = E_{k_0}(M_0)\), \(e_1 = E_{k_1}(M_1)\)

  4. Alice

    • \(k_c = B^a\)

    • \(M_c = D_{k_c}(e_c)\)

The protocol is based off Diffie-Hellman Key Exchange, and assumes the Diffie–Hellman problem (DHP) and computational Diffie–Hellman (CDH) are hard. In the protocol, Alice and Bob first agree upon a group to operate on and a group generator \(g\). Bob (the sender) then sends Alice \(g^b\) and Alice will either send back \(g^{a+b}\) or \(g^{a}\) (depending on the choice of c). Since \(a\) is random and secret, Bob will not be able to distinguish between \(g^{a+b}\) and \(g^a\). Bob will then compute 2 symmetric keys, 1 of which Alice should be able to compute as well. There can be 2 possible configurations for the 2 symmetric keys, depending on which value of \(c\) Alice chose:

\(k_0^\alpha = g^{ab}\)
\(k_1^\alpha = g^{b(a-b)}\)
\(k_0^\beta = g^{b(a+b)}\)
\(k_1^\beta = g^{ab}\)

Bob then encrypts (think AES) \(M_i\) using the corresponding \(k_i\) and sends the 2 encrypted messages (\(e_0\), \(e_1\)) to Alice. From the 2 possible configurations for each of the 2 keys, Alice can only obtain 1 key regardless of the configuration:

\(k_c = B^a = g^{ab}\)

Thus we can see Alice can only compute the keys \(k_0^\alpha\) and \(k_1^\beta\) of Bobs, which are guaranteed to never be part of the same configuration. Finally, Alice can only decode message \(M_c\) as this is the only key she can compute.

References

[1] T. Chou, C. Orlandi, The simplest protocol for oblivious transfer, in: Progress in Cryptology–Latincrypt 2015: 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015, Proceedings 4, Springer, 2015: pp. 40–58.