NDLI: Share Conversion and Private Information Retrieval

Content Provider	IEEE Xplore Digital Library
Author	Beimel, A. Ishai, Y. Kushilevitz, E. Orlov, I.
Copyright Year	2012
Abstract	An information-theoretic {\em private information retrieval} (PIR) protocol allows a client to retrieve the $i$-th bit of a database, held by two or more servers, without revealing information about $i$ to any individual server. Information-theoretic PIR protocols are closely related to {\em locally decodable codes} (LDCs), which are error correcting codes that can simultaneously offer a high level of robustness and sub linear-time decoding of each bit of the encoded message. Recent breakthrough results of Yekhanin (STOC 2007) and Efremenko (STOC 2009) have led to a dramatic improvement in the asymptotic complexity of PIR and LDC. We suggest a new ``cryptographic'' perspective on these recent constructions, which is based on a general notion of {\em share conversion} in secret-sharing schemes that may be of independent interest. Our new perspective gives rise to a clean framework which unifies previous constructions and generalizes them in several directions. In a nutshell, we use the following two-step approach: (1) apply {\em share conversion} to get a low-communication secure multiparty computation protocol $\cal P$ for a nontrivial class $\cal F$ of low-depth circuits, (2) use a lower bound on the {\em VC dimension} of $\cal F$ to get a good PIR protocol from $\cal P$. Our framework reduces the task of designing good PIR protocols to that of finding powerful forms of share conversion which support circuit classes of a high VC dimension. Motivated by this framework, we study the general power of share conversion and obtain both positive and negative results. Our positive results improve the concrete complexity of PIR even for very feasible real-life parameters. They also lead to some improvements in the asymptotic complexity of the best previous PIR and LDC constructions. For 3-server PIR, we improve the asymptotic communication complexity from $O(2^{146\sqrt{\log n\log\log n}})$ to $O(2^{6\sqrt{\log n\log\log n}})$ bits, where $n$ is the database size. Our negative results on share conversion establish some limitations on the power of our approach.
Starting Page	258
Ending Page	268
File Size	384639
Page Count	11
File Format	PDF
ISBN	9781467316637
ISSN	10930159
e-ISBN	9780769547084
DOI	10.1109/CCC.2012.23
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-06-26
Publisher Place	Portugal
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Protocols Servers Complexity theory Logic gates Vectors Additives Databases VC dimension private information retrieval locally decodable codes secret-sharing secure multiparty computation constant-depth circuits matching vectors
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

On the hardness of information-theoretic multiparty computation (2004)

Function Secret Sharing: Improvements and Extensions

An effective private data storage and retrieval system using secret sharing scheme based on secure multi-party computation

Information sharing across private databases: Secure union revisited (2011)

Information sharing across private databases: Secure union revisited (2011)

Lower bounds for linear locally decodable codes and private information retrieval

Multiparty Computations --- Information-Theoretically Secure Against an Adaptive Adversary (2001)

On Codes, Matroids, and Secure Multiparty Computation From Linear Secret-Sharing Schemes

On Share Conversions for Private Information Retrieval

Share Conversion and Private Information Retrieval

Similar Documents

On the hardness of information-theoretic multiparty computation (2004)

Function Secret Sharing: Improvements and Extensions

An effective private data storage and retrieval system using secret sharing scheme based on secure multi-party computation

Information sharing across private databases: Secure union revisited (2011)

Information sharing across private databases: Secure union revisited (2011)

Lower bounds for linear locally decodable codes and private information retrieval

Multiparty Computations --- Information-Theoretically Secure Against an Adaptive Adversary (2001)

On Codes, Matroids, and Secure Multiparty Computation From Linear Secret-Sharing Schemes

On Share Conversions for Private Information Retrieval

Share Conversion and Private Information Retrieval