NDLI: Breaking the O(n/sup 1/(2k-1)/) barrier for information-theoretic Private Information Retrieval

Content Provider	IEEE Xplore Digital Library
Author	Beimel, A. Ishai, Y. Kushilevitz, E. Raymond, J.-F.
Copyright Year	2002
Description	Author affiliation: CS Dept., Ben-Gurion Univ., Beer Sheva, Israel (Beimel, A.)
Abstract	Private information retrieval (PIR) protocols allow a user to retrieve a data item from a database while hiding the identity of the item being retrieved. Specifically, in information-theoretic, k-server PIR protocols the database is replicated among k servers, and each server learns nothing about the item the user retrieves. The cost of such protocols is measured by the communication complexity of retrieving one out of n bits of data. For any fixed k, the complexity of the best protocols prior to our work was O(n/sup 1/2k-1/). Since then several methods were developed in an attempt to beat this bound, but all these methods yielded the same asymptotic bound. In this paper, this barrier is finally broken and the complexity of information-theoretic k-server PIR is improved to n/sup O(log log k/k log k)/. The new PIR protocols can also be used to construct k-query binary locally decodable codes of length exp(n/sup O(log log k/k log k)/), compared to exp(n/sup 1/k-1/) in previous constructions. The improvements presented in this paper apply even for small values of k: the PIR protocols are more efficient than previous ones for every k/spl ges/3, and the locally decodable codes are shorter for every k/spl ges/4.
Sponsorship	IEEE Comput. Soc. Tech. Committee on Maht. Found. Comput. (TCMF) ACM/SIGACT
Starting Page	261
Ending Page	270
File Size	441653
Page Count	10
File Format	PDF
ISBN	0769518222
ISSN	02725428
DOI	10.1109/SFCS.2002.1181949
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2002-11-19
Publisher Place	Canada
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Information retrieval Databases Decoding Complexity theory Access protocols Scholarships Upper bound
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in