Study Group on Oblivious Transfer

 

This week study group by Essam and Gareth was on Oblivious Transfer (OT), which is a fundamental primitive in cryptographic protocols. The problem is as follows: we have a sender S and a receiver R. Sender has N items, say M₁ , M₂ , ..., M_N. The receiver is interested to retrieve one of the items, say the item M_i, where the index i ∈ {1, ...., N}. Informally, any such OT protocol, denoted as OT$$₁^N, should satisfy the following two properties:

1. Sender's security (SS): The receiver should not learn anything about the item M_j where j ≠ i.
2. Receiver's security (RS): The sender should not learn about the index i.         

OT$$₁² is a special form of OT$$₁^N where S has only two items. The problem was first formulated by M. Rabin in his seminal work in 1981. Rabin's proposal was for the OT$$₁² (with a slight variation). This was followed by the work of Even et al., Brassard et al. and several other researchers and different variations of the problem, different notions of security and efficient solutions have been proposed over the past three decades. What makes OT so fundamental is that it is complete for any form of secure 2-party computation and in general for any secure n-party computation.

In the study group, we also discussed the adaptive variant of the OT, denoted by OT$$_k^N where the receiver can now retrieve k items out of the N items and that too adaptively. This means that the choice of the j^th item to retrieve may depend on the previous (j - 1) items which have been retrieved by the receiver. This primitive can be further generalized to OT$$_{k x U}^N, where now U denotes the number of  receivers in the system. In the study group, we discussed the simple case of U = 1, implying that we have only 1 receiver.

Adaptive OT finds motivation from database applications. For example, consider a large medical database, where a user might be interested to retrieve several records and his choice of records may depend upon the records retrieved by him earlier. Structurally, any OT$$_k^N protocol consists of the following two phases:

1. Initialization phase: this phase is invoked by the sender. Informally, here the sender does some form of commitment of his N inputs.
2. Transfer phase: in this phase S and R interacts where R retrieves an item of his choice. This transfer phase will be executed k times.

In the literature, different notions of the security for the OT protocols have been considered. They are as follows:

• Security in the presence of honest but curious adversary: here the sender's security (SS) and the receiver's security (RS) is guaranteed only in the presence of a passive adversary, who follows the protocol instruction but tries to gain extra information from the protocol transcript. For example, if the receiver is corrupted, then he will honestly follow the protocol, but at the same, would try to learn about the other items, in addition to the items retrieved by him. On the other hand, if the sender is honest, then he will honestly follow the protocol, but will try to learn about the items retrieved by the receiver.
• Security with half simulation: here the adversary can be actively corrupted, who can force the corrupted party (either the sender or the receiver) to deviate from the protocol in an arbitrary manner. In this model, the receiver's security (RS) is ensured using the standard indistinguishability based arguments. But the sender's security (SS) is proved by using the simulation based approach, where we compare the ideal OT primitive and the real world OT protocol and show that for every adversary who corrupts the receiver in the real protocol, there exists a simulator in the ideal OT functionality, who corrupts the receiver, such that the view of the adversary and the simulator are computationally indistinguishable. 
• Security with half simulation is good, but it does not capture all the corruption scenarios. For example, it may be possible that the sender aborts the transfer phase before the k executions of the transfer phase protocol, in a hope that he can retrieve information about the items retrieved by the sender. This is called selective abortion and this behavior by the sender is not captured by the notion of half simulation. To capture this, we go for security will full simulation, where we argue about both SS and RS using simulation based arguments. For this, we further enhance the ideal OT primitive and then the security is proved by showing that for every adversary in the real protocol (who corrupts the sender or the receiver), there exists a simulator in the ideal protocol, such that the view of the adversary and the simulator are computationally indistinguishable.

To get a feel of a  real implementation of the OT, Gareth presented the following simple OT$$₁² protocol due to Even et al.

• Setting: S has two items M₀ and M₁. R wants to retrieve the item M_b, where b ∈ {0, 1}.   
• Initialization phase (executed by the S): S generates an RSA key pair (N, e, d) and randomly generates x₀ and x₁ (corresponding to M₀ and M₁ respectively). S then sends the RSA public key e and the random x₀ and x₁  to the R.
• Transfer phase: 

        1. R picks a random k and blinds x_b  by computing

             v = (x_b + k^e) mod N.
         
           R then sends v to the S. In some sense, this k hides the choice of the item
           (of the) receiver from the sender.

        2. On receiving v, S prepares the mask for M₀ and M₁ by computing the
           following:

          k₀ = (v - x₀)^d mod N and k₁ = (v - x₁)^d mod N

          From the point of the view of the S, only one of the k₀ or k₁ will be equal
          to k. But S could not figure out this. S then masks the item M_i using
          the mask k_i as follows:

          c₁ = M₁  + k₁  and  c₂ = M₂  +  k₂

            S then sends c₁ and c₂ to the R.

       3. Since R knows the k, he can retrieve M_b by computing

           M_b = c_b  - k.

           R could not retrieve the other item M_1-b because he could not retrieve
           the mask k_1-b  from c_1-b

The above OT₁² protocol will be secure in the presence of an honest but curious adversary. Using this protocol as a black-box, we can design an OT₁^N protocol (proposed by Naor and Pinkas). The protocol was presented formally in the study group and I dont think that many people followed the protocol. To help them, I explain the idea of the protocol using concrete values.

Let N = 4 and hence S has items M_0, M_1, M₂ and M_3. The protocol assumes that N is a power of 2 and that is why I have selected N = 4. R will be interested to receive one out of the 4 items. Notice that the index of any item can be represented by 2 bits. For example, 3 = 11, 0 = 00 and so on. During the initialization phase, S will "some-how" encrypt all the items and will send the encrypted items to the R. The receiver will then "magically" retrieve the decryption key, corresponding to the item which we want to retrieve. Interestingly, this will be done in such a way that R will not learn the decryption keys corresponding to the other items. And at the same time, S will not learn which decryption keys are retrieved by the R. This can be viewed as some sort of "assisted decryption" service from the S. And this is the common principle underlying all the OT protocols.

In the current example, to do the encryption, S will select 4 PRF keys, namely
k_{0, 0,}  k_{0, 1,}   k_{1, 0}  and k_{1, 1} , for a PRF, say F. The interpretation is that the key
 k_{b, j} will be used for encrypting the item, whose index has bit b at position j in its binary representation, where b ∈ {0, 1} and j = 0, 1. This is demonstrated in the following table:

Item	Index	Binary Representation of the Index	Keys Used for Encrypting	Encryption of the Item
M0	0	00	k0, 0 and k0, 1	C0 = M0 ⊕ Fk0, 0 (0)⊕ Fk0, 1 (0)
M1	1	01	k1, 0 and k0, 1	C1 = M1 ⊕ Fk1, 0 (1)⊕ Fk0, 1 (1)
M2	2	10	k0, 0 and k1, 1	C2 = M2 ⊕ Fk0, 0 (2)⊕ Fk1, 1 (2)
M3	3	11	k1, 0 and k1, 1	C3 = M3 ⊕ Fk1, 0 (3)⊕ Fk1, 1 (3)

 During the initialization phase, S will send the cipher-texts C_0, C_1, C₂ and C₃ to the R. To retrieve an item, it is enough for the R to retrieve the keys, corresponding to the binary representation of the index of the item, which he wants to retrieve. Note that R needs to retrieve 2 PRF keys to retrieve an item and this will be done by invoking two instances of OT₁² protocol. The inputs for the first instance will be the PRF keys k_{0, 0} and k_{1, 0} while the input for the second instance will be the PRF keys k_{0, 1} and k_{1, 1.} 

Suppose R wants to retrieve the item M_2. Then it is enough for R to retrieve the keys k_{0, 0}  and k_{1, 1.} So from the first instance of the OT₁² protocol, R retrieves    the PRF key k_{0, 0}  and from the second instance of the OT₁² protocol, R retrieves  the PRF key k_{1, 1.} Now R can unmask C₂ and recover M_2.

On a high level, the receiver's security (RS) follows from the security of the underlying OT₁² protocols. The sender's security (SS) follows from the pseudo-randomness of the PRF, the security of the OT₁² protocols and the basic fact that any two indices differ in at least one position in their binary representation. So for every item other than the item retrieved by the R, there will be at least one PRF key, which will be unknown to the R.

It is easy to see that the complexity of the above protocol is very high. It requires N log N evaluation of PRFs in the initialization phase and log N invocations of the OT₁² protocols. Using more sophisticated primitives like blind signatures and variants of Elgamal encryption scheme, it is possible to design more efficient
OT_{k x U}^N   protocols, which was briefly discussed at the end of the study group.

An interesting problem is to design efficient UC-secure OT protocols based on static assumptions. There exist UC-secure OT protocols for certain settings, for example non-adaptive adversary, based on strong assumptions, etc. But getting an efficient UC secure protocol against an adaptive adversary, based on standard assumptions is an interesting problem.