You are looking at a specific version 20140117:101312 of this paper. See the latest version.

Paper 2014/044

rPIR: Ramp Secret Sharing based Communication Efficient Private Information Retrieval

Lichun Li and Michael Militzer and Anwitaman Datta

Abstract

Even as data and analytics driven applications are becoming increasingly popular, retrieving data from shared databases poses a threat to the privacy of their users. For example, investors/patients retrieving records about interested stocks/diseases from a stock/medical database leaks sensitive information to the database server. PIR (Private Information Retrieval) is a promising security primitive to protect the privacy of users' interests. PIR allows the retrieval of a data record from a database without letting the database server know which record is being retrieved. The privacy guarantees could either be information theoretic or computational. Ever since the first PIR schemes were proposed, a lot of work has been done to reduce the communication cost in the information-theoretic settings - particularly the question communication cost, i.e., the traffic from the user to the database server. The answer communication cost (the traffic from the database server to the user) has however barely been improved. When question communication cost is much lower than the record length, reducing question communication cost has marginal benefit on lowering overall communication cost. In contrast, reducing answer cost becomes very important. In this paper we propose ramp secret sharing based mechanisms that reduce the answer communication cost in information-theoretic PIR. We have designed four information-theoretic PIR schemes, using three ramp secret sharing approaches, achieving answer communication cost close to the cost of non-private information retrieval. Evaluation shows that our PIR schemes can achieve lower communication cost and the same level of privacy compared with existing schemes. Our PIR schemes' usages are demonstrated for realistic settings of outsourced data sharing and P2P content delivery scenarios. Thus, our approach makes PIR a viable communication efficient technique to protect user interest privacy.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Private Information RetrievalSecret Sharing
Contact author(s)
lilichun @ gmail com
History
2014-01-17: received
Short URL
https://ia.cr/2014/044
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.