Đang chuẩn bị liên kết để tải về tài liệu:
Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval

Designers still have the option of three-tier or n-tier application designs; but, they now have the two-tier option again. The sim- plicity of two-tier client/server is attractive, but security issues (databases have huge attack surfaces) may cause many designers to want three-tier server architectures with the web server in the demilitarized zone (DMZ). It is likely that web services will be the way we federate heteroge- neous database systems. . | Replication Is Not Needed Single Database Computationally-Private Information Retrieval extended abstract Eyal Kushilevitz Technion Rafail Ostrovskyt Bellcore Abstract We establish the following quite unexpected result replication of data for the computational Private Information Retrieval problem is not necessary. More specifically based on the quadratic resid-uosity assumption we present a single database computationally-private information-retrieval scheme with O ne communication complexity for any e 0. 1 Introduction 1.1 Problem statement and History Private Information Retrieval PIR schemes allow a user to retrieve information from a database while maintaining the privacy of the queries from the database. More formally we view the data as an n-bit string X from which the user wishes to obtain the bit Xi while keeping the index i private from the database. The notion of PIR schemes was introduced by Chor Goldreich Kushilevitz and Sudan CGKS-95 in an information theoretic setting. This Dept. of Computer Science Technion Haifa Israel email eyalk@cs.technion.ac.il http www.cs.technion.ac.il evalk Part of this research was done while visiting DIMACS center at Rutgers University. Supported by MANLAM Fund 120-857 and by the Fund for Promotion of Research at the Technion. ÍBell Communications Research MCC 1C-365B 445 South Street Morristown New Jersey 07960-6438. e-mail rafail@bellcore.com. means that the queries asked by the user give no information whatsoever about i. In this setting they proved the following results Every information theoretic PIR scheme with a single-database requires Q n bits of communication this matches the trivial upper bound in which the user just asks for a copy of the entire database in order to hide which particular bit it is interested in . A way to get around the above impossibility result so as to reduce the communication complexity to be sub-linear in n is by assuming that the data is replicated in several sites which are assumed not .