Study of the computational efficiency of single server private information retrieval

Thesis (M.S.)--Boston University PLEASE NOTE: Boston University Libraries did not receive an Authorization To Manage form for this thesis or dissertation. It is therefore not openly accessible, though it may be available by request. If you are the author or principal advisor of this work and would like to request open access for it, please contact us at open-help@bu.edu. Thank you.Private Information Retrieval (PIR) is a protocol for a client to retrieve information from a server without revealing anything about which item (s)he retrieved. It has numerous applications but its impracticality due to extremely poor performance or awkward assumptions about its usage prevent its uptake. This work provides a background on the topic of PIR performance, frames the problem of finding efficient PIR as the problem of finding a code with a local decoding property, shows existing families of locally decodable codes are not suitable, and lists some requirements that codes must have to produce secure PIR