A survey of single-database private information retrieval: techniques and applications <s> Connections: PIR and Complexity Theory <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> Connections: PIR and Complexity Theory <s> We initiate the study of compression that preserves the solution to an instance of a problem rather than preserving the instance itself. Our focus is on the compressibility of NP decision problems. We consider NP problems that have long instances but relatively short witnesses. The question is, can one efficiently compress an instance and store a shorter representation that maintains the information of whether the original input is in the language or not. We want the length of the compressed instance to be polynomial in the length of the witness rather than the length of original input. Such compression enables to succinctly store instances until a future setting will allow solving them, either via a technological or algorithmic breakthrough or simply until enough time has elapsed. We give a new classification of NP with respect to compression. This classification forms a stratification of NP that we call the VC hierarchy. The hierarchy is based on a new type of reduction called W-reduction and there are compression-complete problems for each class. Our motivation for studying this issue stems from the vast cryptographic implications compressibility has. For example, we say that SAT is compressible if there exists a polynomial p(middot, middot) so that given a formula consisting of m clauses over n variables it is possible to come up with an equivalent (w.r.t satisfiability) formula of size at most p(n, log m). Then given a compression algorithm for SAT we provide a construction of collision resistant hash functions from any one-way function. This task was shown to be impossible via black-box reductions (D. Simon, 1998), and indeed the construction presented is inherently non-black-box. Another application of SAT compressibility is a cryptanalytic result concerning the limitation of everlasting security in the bounded storage model when mixed with (time) complexity based cryptography. In addition, we study an approach to constructing an oblivious transfer protocol from any one-way function. This approach is based on compression for SAT that also has a property that we call witness retrievability. However, we mange to prove severe limitations on the ability to achieve witness retrievable compression of SAT <s> BIB002 </s> A survey of single-database private information retrieval: techniques and applications <s> Connections: PIR and Complexity Theory <s> Let \Lambda : {0, 1}^n ? {0, 1}^m \to {0, 1} be a Boolean formula of size d, or more generally, an arithmetic circuit of degree d, known to both Alice and Bob, and let y \in {0, 1}^m be an input known only to Alice. Assume that Alice and Bob interacted in the past in a preamble phase (that is, applied a preamble protocol that depends only on the parameters, and not on \Lambda, y). We show that Alice can (non-interactively) commit to y, by a message of size poly(m, log d), and later on prove to Bob any N statements of the form \Lambda(x_1, y) = z_1, . . . , \Lambda(x_{N}, y) = z_N by a (computationally sound) non-interactive zero-knowledge proof of size poly(d, logN). (Note the logarithmic dependence on N). We give many applications and motivations for this result. In particular, assuming that Alice and Bob applied in the past the (poly-logarithmic size) preamble protocol: 1. Given a CNF formula \Psi(w_1, . . . , w_m ) of size N, Alice can prove the satisfiability of \Psi by a (computationally sound) non-interactive zero-knowledge proof of size poly(m). That is, the size of the proof depends only on the size of the witness and not on the size of the formula. 2. Given a language L in the class LOGSNP and an input x \in {0,|1}^n , Alice can prove the membership x \in L by a (computationally sound) non-interactive zero-knowledge proof of size polylogn. 3. Alice can commit to a Boolean formula y of size m, by a message of size poly(m), and later on prove to Bob any N statements of the form y(x_1 ) = z_1 , . . . , y(x_N ) = z_N by a (computationally sound) non-interactive zero-knowledge proof of size poly(m, logN). Our cryptographic assumptions include the existence of a poly-logarithmic Symmetric-Private-Information- Retrieval (SPIR) scheme, as defined in [4], and the existence of commitment schemes, secure against circuits of size exponential in the security parameter. <s> BIB003
Dziembowski and Maurer have shown the danger of mixing computational and information-theoretic assumptions in the bounded-storage model. The key tool to demonstrate an attack was a computationally-private PIR protocol  . The compressibility of NP languages was shown by Harnick and Naor to be intimately connected to computational PIR BIB002 . In particular, what they show that if certain NP language is compressible, then one can construct a single-database PIR protocol (and a collisionresistant hash function) that can be built (in a non-black-box way) based on any oneway function. Naor and Nissim [28] have shown how to use computational PIR (and Oblivious RAMs BIB001 ) to construct communication-efficient secure function evaluation protocols. There is an interesting connection between zero-knowledge arguments and SingleDatabase PIR. In particular, Tauman-Kalai and Raz have shown (for a certain restricted class) an extremely efficient zero-knowledge argument (with pre-processing) assuming Single-Database PIR protocols BIB003 . Another framework of constructing efficient PIR protocols is with the help of additional servers, such that even if some of the servers leak information to the database, the overall privacy is maintained  . The technique of  is also used to achieve PIR combiners  , where given several PIR implementations, if some are faulty, they can still be combined into one non-faulty PIR.