The Bellare-Micali Oblivious Transfer

2022-05-03 by Alex Kampa

Oblivious transfer (OT) is a cryptographical primitive introduced by Michael Rabin in 1981. It is fundamental for secure multiparty computation. It can also be combined with Garbled Circuits to construct 2-party semi-honest secure function evaluation protocols, as shown in the seminal work of Yao.

A 1-2 oblivious transfer protocol can be described as follows. Bob has 2 messages \(m_0\) and \(m_1\) and Alice can retrieve one, and only one, of these messages. Bob should not learn which message Alice obtained. This can be generalised to 1-n (one out of n) and k-n (k out of n) oblivious transfer protocols.

In this post, we will stick with the 1-2 protocol, for which Bellare and Micali provided a simple and elegant construction in 1989.

The Bellare-Micali trick

We have a group \(G\) of prime order \(q\) and publicly known generator \(g\). As usual, the discrete log problem in \(G\) is assumed to be suitably hard. The OT protocol of Bellare and Micali relies on the following fact:

Given an element \(c \in G\) for which the discrete log is not known, it is impossible to find a pair \((k_0, k_1)\) such that \(k_0 k_1 = c\) while knowing the discrete logs of both \(k_0\) and \(k_1\). It is however easy to find such a pair so that the discrete log of one of the elements is known.

As any element of \(G\) can be seen as a public key, and therefore used for encrypting data, an OT protocol can be now constructed quite easily.

The Bellare-Micali OT protocol

The protocol works as follws:

(1) Bob selects a random \(c \in G\) and sends it to Alice. To do that, Bob could take some random \(r \in Z_q\) and set \(c = g^r\). However, the knowledge of \(r\) is actually not necessary. In some settings, such as a group of points on an elliptic curve, the random point could be chosen without any knowledge of its discrete log.

Note that \(c\) could also be a publicly known element for which no-one knows the discrete log. This would make this first step redundant.

(2) Alice generates two elements \(k_0, k_1 \in G\) such that \(k_0 k_1 = c\). Given that Alice does not know the discrete log of \(c\), the only way to achieve this is to select a random \(z \in Z_q\) and to set \(k_0 = g^z\) and then \(k_1 = c g^{-z}\). Note that Alice does not know the discrete log of \(k_1\). Alice now sends Bob one of the ordered pairs \((k_0, k_1)\) or \((k_1, k_0)\).

Note that Alice could have chosen some random \(k_0\) for which she does not know the discrete log. As she will, in general, be able to compute the inverse of \(k_0\), she can set \(k_1 = c k_0^{-1}\) to obtain the desired relation \(k_0 k_1 = c\). However, then she would not know the discrete log of any of the two points!

Also note that if Alice does not choose \(z\) randomly in step (2), she may leak information to Bob. For example, if she sent the pair \((c g^{-1}, g)\), Bob could easily find out that Alice knows the discrete log of the second point, and is therefore interested in message \(m_1\).

(3) Bob receives the pair \((k, k')\) and verifies that \(k k' = c\). If that is the case, he can be confident that Alice knows the discrete log of one, and only one, of these two points. However, if Alice has chosen \(z\) randomly, Bob will not know for which one of the two group elements Alice knows the discrete log.

Using the group elements \((k, k')\) as public keys, Bob generates the encryptions \(Enc(k, m_0)\) and \(Enc(k', m_1)\) and sends them to Alice. Here, \(Enc\) designates some suitable encryption protocol.

(4) Alice can now decrypt one (and only one) of these encrypted messages. If she sent \((k_0, k_1)\) in step (2), she will be able to decrypt the message \(m_0\) but not message \(m_1\). And if she sent \((k_1, k_0)\) in step (2), then she will be able to decrypt the message \(m_1\) but not message \(m_0\).

Conclusion

The Bellare-Micali oblivious transfer protocol can easily be extended to a 2-3 OT protocol, or more generally to a (n-1)-(n) protocol.

An extended abstract of the original paper can be found here, some of the notations are not the same as above though:

https://cseweb.ucsd.edu/~mihir/papers/niot.pdf

\(\mathrm{\blacksquare}\)