tailieunhanh - Single-Database Private Information Retrieval with Constant Communication Rate

The hardness result for selecting an optimal index configuration was shown by Shapiro [60]. Therefore, the challenge was similar to that in the area of query optimization – identifying the right set of heuristics to guide the selection of physical design. One set of papers advocated an approach based on rule-based expert systems. The rules took into account query structures as well as statistical profiles and were “stand-alone” applications that recommended indexes. A tool such as DEC RdbExpert falls in this category. Rozen and Shasha [56] also used an external cost model but their cost model was similar to that. | Single-Database Private Information Retrieval with Constant Communication Rate Craig Gentry and Zulfikar Ramzan DoCoMo Communications Laboratories USA Inc. cgentry ramzan @ Abstract. We present a single-database private information retrieval PIR scheme with communication complexity O k d where k log n is a security parameter that depends on the database size n and d is the bit-length of the retrieved database block. This communication complexity is better asymptotically than previous single-database PIR schemes. The scheme also gives improved performance for practical parameter settings whether the user is retrieving a single bit or very large blocks. For large blocks our scheme achieves a constant rate . even when the user-side communication is very low . two 1024-bit numbers . Our scheme and security analysis is presented using general groups with hidden smooth subgroups the scheme can be instantiated using composite moduli in which case the security of our scheme is based on a simple variant of the A-liidiiig assumption by Cachin Micali and Stadler 2 . 1 Introduction Problem Statement and Background. Private Information Retrieval PIR schemes allow a user to retrieve the ith bit of an n-bit database without revealing to the database the value of i. The trivial solution is for the user to retrieve the entire database but this approach may incur enormous communication costs. A good PIR scheme on the other hand should have considerably lower certainly sub-linear communication complexity. Private Block Retrieval PBR is a natural and more practical extension of PIR in which instead of retrieving only a single bit the user retrieves a d-bit block that begins at index i. PIR and PBR have been studied extensively here we only mention the work most relevant to us. The notion of PIR was introduced by Chor et al. 5 who focused on the information-theoretic case where one requires that the user s query give absolutely no information about i. They .