Adaptive Oblivious Transfer or Giving Answers without Knowing the Questions

As recently realized, meta-data of communications are more important than the content itself. As a consequence, for privacy reasons, when one queries a database, nobody should learn the query, whereas the user would like to get the answer. Oblivious transfer (OT) protocols have been proposed by Rabin [Rab81] in 1981: the sender sends a message to the receiver with probability one half, while the sender remains oblivious as to whether or not the receiver received the message. It has thereafter been converted by Even et al. [EGL85] into the so-called 1-out-of-2 oblivious transfer, where the sender sends two messages, and the receiver chooses to receive one of them: the receiver learns nothing about the other one and the sender remains oblivious as to which message the receiver received. The natural 1-out-of-n extension provides both the notion of query secrecy and data secrecy, since the receiver gets one database element only without leaking any information about (1) which element has been asked to the server and (2) other elements of the database to the receiver. Private information retrieval (PIR) techniques [CKGS98] focus on the former point, but do not take care about the latter one, except the extension of symmetric PIR. In an adaptive oblivious transfer (AOT) protocol [NP99], a sender commits to a database of messages and then repeatedly interacts with a receiver in such a way that the receiver obtains one message per interaction of his choice (and nothing more) while the sender learns nothing about any of the choices. This is similar to 1-out-of-n OT, with n not known in advance, and queries are adaptive. In some sense, this is quite related to symmetric PIR. Goal of the Internship The goal is to study AOT protocols and get better constructions, in various directions, and namely, with a better security and/or a better efficiency. Expected Skills We are looking for candidates with good skills in algorithmics and complexity theory. Provable security for cryptographic protocols (as one can get in courses 2.12.1 and 2.30 of the MPRI) will be the basis of this internship