Friday, February 24, 2012

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 M1 , M2 , ..., MN. The receiver is interested to retrieve one of the items, say the item Mi, where the index i ∈ {1, ...., N}. Informally, any such OT protocol, denoted as OT1N, should satisfy the following two properties:

  1. Sender's security (SS): The receiver should not learn anything about the item Mj where j ≠ i.
  2. Receiver's security (RS): The sender should not learn about the index i.         
OT12 is a special form of OT1N 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 OT12 (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 OTkN where the receiver can now retrieve k items out of the N items and that too adaptively. This means that the choice of the jth 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 OTk x UN, 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 OTkN 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 OT12 protocol due to Even et al.

  • Setting: S has two items M0 and M1. R wants to retrieve the item Mb, where b ∈ {0, 1}.   
  • Initialization phase (executed by the S): S generates an RSA key pair (N, e, d) and randomly generates x0 and x1 (corresponding to M0 and M1 respectively). S then sends the RSA public key e and the random x0 and x1  to the R.
  • Transfer phase: 
        1. R picks a random k and blinds xb  by computing

             v = (xb + ke) 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 M0 and M1 by computing the

          k0 = (v - x0)d mod N and k1 = (v - x1)d mod N

          From the point of the view of the S, only one of the k0 or k1 will be equal
          to k. But S could not figure out this. S then masks the item Mi using
          the mask ki as follows:

          c1 = M+ kand  c2 = M+  k2

            S then sends c1 and c2 to the R.

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

           Mb = c- k.

           R could not retrieve the other item M1-b because he could not retrieve
           the mask k1-b  from c1-b

The above OT12 protocol will be secure in the presence of an honest but curious adversary. Using this protocol as a black-box, we can design an OT1N 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 M0, M1, M2 and M3. 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
k0, 0,  k0, 1,   k1, 0  and k1, 1 , for a PRF, say F. The interpretation is that the key
 kb, 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 C0, C1, C2 and C3 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 OT12 protocol. The inputs for the first instance will be the PRF keys k0, 0 and k1, 0 while the input for the second instance will be the PRF keys k0, 1 and k1, 1. 

Suppose R wants to retrieve the item M2. Then it is enough for R to retrieve the keys k0, 0  and k1, 1. So from the first instance of the OT12 protocol, R retrieves    the PRF key k0, 0  and from the second instance of the OT12 protocol, R retrieves  the PRF key k1, 1. Now R can unmask C2 and recover M2.

On a high level, the receiver's security (RS) follows from the security of the underlying OT12 protocols. The sender's security (SS) follows from the pseudo-randomness of the PRF, the security of the OT12 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 OT12 protocols. Using more sophisticated primitives like blind signatures and variants of Elgamal encryption scheme, it is possible to design more efficient
OTk x UN   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.


  1. "An interesting open problem is to design efficient UC-secure OT protocols."

    While I agree that there's lots of work to be done here, it's not completely open. There have been at least a couple of papers on this (including one of my own, though it used a specific setting and some strong assumptions). The problem here is that the /efficient/ NIZKs we have are restricted to certain types of statement, and engineering around that requires some work. Also, in the non-adaptive setting Peikert, Vaikunathan and Waters have a very efficient DDH-based construction based on 'message-lossy' public keys:

    1. This comment has been removed by the author.

    2. Yes, I agree with Essam. I should have said that the open problem is to design efficient UC secure OT protocols based on static assumptions. Because indeed there are special settings where we can design UC secure OT protocols. I will change the last paragraph. Thanks to Matthew and Essam.

    3. I agree that the open problem is to design an efficient adaptive protocol that is both UC secure and based on standard static assumption rather than dynamic ones...