טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentGilboa Niv
SubjectTopics in Private Information Retrieval
DepartmentDepartment of Computer Science
Supervisor Mr. Ben-Zion Chor


Abstract

In the problem of Private Information Retrieval (PIR) a user queries a database in order to retrieve one of n data items, while hiding the identity of the retrieved item from the database administrator. In the last few years extensive research has been conducted on PIR and related problems derived from it.

This dissertation consists of three works that are motivated by PIR or similar problems. The first work introduces the concept of computationally private information retrieval (CPIR). In such a scheme, a user’s privacy is maintained as long as computational resources at the disposal of an adversary are bounded. The main advantage of the CPIR schemes we introduce over information-theoretically private schemes is a significantly lower communication overhead per query.

The second work introduces the notion of Private Information Retrieval by Keywords.  In this setting the database model is more realistic than in PIR. Instead of containing a sequence of n bits, which are retrieved by their index, it is made up of n keywords. The user holds a keyword and retrieves its database index in a private manner, without revealing the identity of that keyword. We show several solutions for this problem, based on PIR protocols.

The third work presents a protocol for two parties to generate RSA keys jointly and privately. In other words, each of the parties holds the public key, and has a share of the private key. The two parties can cooperate and use the private key for signatures or decryption. However, each party can gain no information on the other’s share or on the private key as a whole.