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

In the study group, we also discussed the adaptive variant of the OT, denoted by OT$$

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$$

v = (x

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

following:

k

From the point of the view of the S, only one of the k

to k. But S could not figure out this. S then masks the item M

the mask k

c

3. Since R knows the k, he can retrieve M

M

R could not retrieve the other item M

the mask k

The above OT

Let N = 4 and hence S has items M

In the current example, to do the encryption, S will select 4 PRF keys, namely

k

k

Suppose R wants to retrieve the item M

On a high level, the receiver's security (RS) follows from the security of the underlying OT

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

OT

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 }, M_{2 }, ..., 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$$_{1}^{N}, should satisfy the following two properties:- Sender's security (SS): The receiver should not learn anything about the item M
_{j }where j ≠ i. - Receiver's security (RS): The sender should not learn about the index i.

_{1}^{2}is a special form of OT$$_{1}^{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$$_{1}^{2}(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:- Initialization phase: this phase is invoked by the sender. Informally, here the sender does some form of commitment of his N inputs.
- 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.

- 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.

_{1}^{2}protocol due to Even et al.- Setting: S has two items M
_{0}and M_{1}. 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
_{0}and x_{1 }(corresponding to M_{0}and M_{1}respectively). S then sends the RSA public key e and the random x_{0}and x_{1}to the R. - Transfer phase:

_{b}by computingv = (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

_{0}and M_{1}by computing thefollowing:

k

_{0}= (v - x_{0}_{})^{d}mod N and k_{1}= (v - x_{1})^{d}mod NFrom the point of the view of the S, only one of the k

_{0}or k_{1}will be equalto k. But S could not figure out this. S then masks the item M

_{i}usingthe mask k

_{i}as follows:c

_{1}= M_{1 }+ k_{1 }and c_{2}= M_{2 }+ k_{2}_{ }S then sends c_{1}and c_{2}to the R.3. Since R knows the k, he can retrieve M

_{b}by computingM

_{b}= c_{b }- k.R could not retrieve the other item M

_{1-b }because he could not retrievethe mask k

_{1-b}from c_{1-b}The above OT

_{1}^{2 }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_{1}^{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_{2 }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 keyk

_{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 |

M_{0} |
0 | 00 | k_{0, 0} and k_{0, 1} |
C_{0} = M_{0} ⊕ F_{k0, 0 }(0_{})⊕ F_{k0, 1 }(0_{}) |

M_{1} |
1 | 01 | k_{1, 0} and k_{0, 1} |
C_{1} = M_{1} ⊕ F_{k1, 0 }(1_{})⊕ F_{k0, 1 }(1_{}) |

M_{2} |
2 | 10 | k_{0, 0} and k_{1, 1} |
C_{2} = M_{2} ⊕ F_{k0, 0 }(2_{})⊕ F_{k1, 1 }(2_{}) |

M_{3} |
3 | 11 | k_{1, 0} and k_{1, 1} |
C_{3} = M_{3} ⊕ F_{k1, 0 }(3_{})⊕ F_{k1, 1 }(3_{}) |

_{ }During the initialization phase, S will send the cipher-texts C_{0, }C_{1, }C_{2 }and C_{3 }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_{1}^{2 }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_{1}^{2 }protocol, R retrieves the PRF key k_{0, 0}_{ }and from the second instance of the OT_{1}^{2 }protocol, R retrieves the PRF key k_{1, 1}_{. }Now R can unmask C_{2}and recover M_{2.}On a high level, the receiver's security (RS) follows from the security of the underlying OT

_{1}^{2 }protocols. The sender's security (SS) follows from the pseudo-randomness of the PRF, the security of the OT_{1}^{2 }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

_{1}^{2 }protocols. Using more sophisticated primitives like blind signatures and variants of Elgamal encryption scheme, it is possible to design more efficientOT

_{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.

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

ReplyDeleteWhile 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:

http://www.cs.toronto.edu/~vinodv/OT.pdf

This comment has been removed by the author.

DeleteYes, 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.

DeleteI 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...

Delete