Abstract Private information retrieval (PIR) is one of the promising techniques to preserve user privacy in the presence of trusted-but-curious servers. The information theoretically private query construction assures the highest user privacy over curious and unbounded computation servers. Therefore, the need for information-theoretic private retrieval was fulfilled by various schemes in a variety of PIR settings. But, there is a lack of efficient encryption switching scheme which supports efficient switching between information-theoretic to/from computationally bounded PIRs. We propose a combination of new bit connection methods called rail-shape and signal-shape and new quadratic residuosity assumption based family of trapdoor functions for generic single database private block retrieval (PBR). The main goal of this work is to show that the possibility of mapping from computationally bounded privacy to information theoretic privacy or vice-versa in a single database setting using newly constructed bit connection and trapdoor function combinations. Notably, the proposed schemes are single round, memoryless and plain database schemes (at their basic constructions).
Abstract Private information retrieval (PIR) is one of the promising techniques to preserve user privacy in the presence of trusted-but-curious servers. The information theoretically private query construction assures the highest user privacy over curious and unbounded computation servers. Therefore, the need for information-theoretic private retrieval was fulfilled by various schemes in a variety of PIR settings. But, there is a lack of efficient encryption switching scheme which supports efficient switching between information-theoretic to/from computationally bounded PIRs. We propose a combination of new bit connection methods called rail-shape and signal-shape and new quadratic residuosity assumption based family of trapdoor functions for generic single database private block retrieval (PBR). The main goal of this work is to show that the possibility of mapping from computationally bounded privacy to information theoretic privacy or vice-versa in a single database setting using newly constructed bit connection and trapdoor function combinations. Notably, the proposed schemes are single round, memoryless and plain database schemes (at their basic constructions).
Private Information Retrieval (PIR) protocols allow a user to read information from a database without revealing to the server storing the database which information he has read.Kushilevitz and Ostrovsky [23] construct, based on the quadratic residuosity assumption, a single-server PIR protc-co1 with small communication complexity.Cachin, Micali, and Stadler [6] present a single-server PIR protocol with a smaller communication complexity, based an the (new) *hiding assumption.A major question, addressed in the present work, is what assumption is the minimal assumption necessary for the construction of single-server private information retrieval protocols with small communication complexity.We prove that if there is a (O-error) PIR protocol in which the server sends less than n bits then one-way functions exist (where n is the number of bits in the database).That is, even saving one bit compared to the naive protocol, in which the entire database is sent, already requires one-way functions.The same result holds (but requires more work) even if we allow the retrieval to fail with probability of at most 1/(8n).Moreover, similar tcomputer science
We study the communication complexity of single-server Private Information Retrieval (PIR) protocolsthat are based on fundamental cryptographic primitives in a black-box manner. In this setting, we establish a tight lower bound on the number of bits communicated by the server in any polynomially-preservingconstruction that relies on trapdoor permutations. More specifically, our main result states that in such constructions \\Omega (n) bits must be communicated by the server, where n is the size of the server's database,and this improves the \\Omega (n / log n) lower bound due to Haitner, Hoch, Reingold and Segev (FOCS '07).Therefore, in the setting under consideration, the naive solution in which the user downloads the entire database turns out to be optimal up to constant multiplicative factors. We note that the lower boundwe establish holds for the most generic form of trapdoor permutations, including in particular enhanced trapdoor permutations.Technically speaking, this paper consists of two main contributions from which our lower bound is obtained. First, we derive a tight lower bound on the number of bits communicated by the sender duringthe commit stage of any black-box construction of a statistically-hiding bit-commitment scheme from a family of trapdoor permutations. This lower bound asymptotically matches the upper bound provided bythe scheme of Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). Second, we improve the e fficiencyof the reduction of statistically-hiding commitment schemes to low-communication single-server PIR, due to Beimel, Ishai, Kushilevitz and Malkin (STOC '99). In particular, we present a reduction that essentiallypreserves the communication complexity of the underlying single-server PIR protocol.
Abstract. In this paper we present a single-round, single-server symmetrically private information retrieval scheme, in which privacy of user follows from intractability of the quadratic residuacity problem and the privacy of the database follows from the XOR assumption for quadratic residues introduced in this paper. The communication complexity of the proposed scheme for retrieving one bit can be made O(n ɛ), for any ɛ>0, where n is the number of bits in the database. We extend the protocol to a block retrieval scheme which is specially efficient when the number of records in the database is equal to the size of each record.
The Private Information Retrieval protocol(PIR) is an important secure multi-party computation protocol.In PIR,a user can perform a query from a database without revealing his private information;meanwhile the privacy of the database will be protected,too.This paper proposes a new scheme in which we apply cryptographic technology on the auxiliary random servers protocol to solve the problem of PIR.This scheme is efficient in computational complexity and doesn't increase the cost of communication.It is very practical and can retrieve a block of bits.Detailed analysis of security,computational complexity and communicational complexity to the scheme is also given in this paper.
Private information retrieval (PIR) is an important protocol in cryptographic community to ensure privacy of the user when retrieving information from untrusted databases. In a variation to this problem, symmetric private information retrieval (SPIR) is a protocol which ensures the privacy of user as well as databases. A major drawback for the majority of existing works on information theoretic PIR and SPIR is that they focus on scenarios where all databases store the entire data set (i.e. replicated databases). The goal of this thesis is to present PIR and SPIR schemes for storage constrained databases. For both PIR and SPIR, we present a systematic approach to utilize storage constrained databases. The technical contribution involves two main parts: (a) a careful storage scheme to split and store messages across databases; and (b) construction of information theoretic PIR and SPIR schemes from such databases. We also compare our results to the fully replicated scenario, as well as compare the differences between the communication overhead of PIR and SPIR schemes.
Single-server private information retrieval (PIR) schemes are known to require linear query time. Recent works circumvent these classical lower bounds by leveraging preprocessing to answer queries in sublinear time. We prove computation lower bounds for PIR with preprocessing schemes making blackbox usage of any cryptography (such as random oracles or virtual blackbox obfuscation). If the client stores s bits about an n-bit database, then answering k=Ω(s) queries requires either Ω(n/s) amortized online communication or Ω(n/s) amortized server cryptographic operations. This is tight, as known constructions match either bound while outperforming the other. Our lower bound is unconditional and allows arbitrary query protocols, weakened privacy, and server-side database encodings (including doubly efficient PIR) whenever the encoding is independent of the blackbox cryptography. Previous bounds were only known conditionally and for restricted classes of preprocessing, e.g., under non-encoding assumptions. Our framework also yields Ω(n/s) communication lower bounds for schemes with o(n/s) server cryptographic operations, communication-determined server cryptography, or perfect privacy in the idealized model. Finally, we prove lower bounds for symmetric PIR with client preprocessing in the random oracle model and give a matching construction using only one-way functions in the online phase.