A survey of single-database private information retrieval: techniques and applications <s> Introduction <s> Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the theoretical treatment it deserves. In this paper, we provide theoretical treatment of software protection. We reduce the problem of software protection to the problem of efficient simulation on oblivious RAM. A machine is oblivious if thhe sequence in which it accesses memory locations is equivalent for any two inputs with the same running time. For example, an oblivious Turing Machine is one for which the movement of the heads on the tapes is identical for each computation. (Thus, the movement is independent of the actual input.) What is the slowdown in the running time of a machine, if it is required to be oblivious? In 1979, Pippenger and Fischer showed how a two-tape oblivious Turing Machine can simulate, on-line, a one-tape Turing Machine, with a logarithmic slowdown in the running time. We show an analogous result for the random-access machine (RAM) model of computation. In particular, we show how to do an on-line simulation of an arbitrary RAM by a probabilistic oblivious RAM with a polylogaithmic slowdown in the running time. On the other hand, we show that a logarithmic slowdown is a lower bound. <s> BIB001 </s> A survey of single-database private information retrieval: techniques and applications <s> Introduction <s> Searchable symmetric encryption SSE allows a party to outsource the storage of his data to another party in a private manner, while maintaining the ability to selectively search over it. This problem has been the focus of active research and several security definitions and constructions have been proposed. In this paper we begin by reviewing existing notions of security and propose new and stronger security definitions. We then present two constructions that we show secure under our new definitions. Interestingly, in addition to satisfying stronger security guarantees, our constructions are more efficient than all previous constructions.Further, prior work on SSE only considered the setting where only the owner of the data is capable of submitting search queries. We consider the natural extension where an arbitrary group of parties other than the owner can submit search queries. We formally define SSE in this multi-user setting, and present an efficient construction. <s> BIB002
A Single-Database Private Information Retrieval (PIR) scheme is a game between two players: a user and a database. The database holds some public data (for concreteness, an n-bit string). The user wishes to retrieve some item from the database (such as the ith bit) without revealing to the database which item was queried (i.e., i remains hidden). We stress that in this model the database data is public (such as stock quotes) but centrally located; the user, without a local copy, must send a request to retrieve some part of the central data 1 . A naive solution is to have the user download the entire database, which of course preserves privacy. However, the total communication complexity in this solution, measured as the number of bits transmitted between the user and the database is n. Private Information Retrieval protocols allow the user to retrieve data from a public database with communication strictly smaller than n, i.e., with smaller communication then just downloading the entire database. Supported in part by IBM Faculty Award, Xerox Innovation Group Award, NSF Cybertrust grant no. 0430254 and U.C. MICRO grant. Supported in part by NSF grant no. 0430254, and U.C. Presidential Fellowship. 1 PIR should not be confused with a private-key searching on encrypted data problem, where user uploads his own encrypted data to a remote database and wants to privately search over that encrypted data without reveling any information to the database. For this model, see the discussion in BIB002 BIB001 and references therein.