๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Protecting Data Privacy in Private Information Retrieval Schemes

โœ Scribed by Yael Gertner; Yuval Ishai; Eyal Kushilevitz; Tal Malkin


Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
292 KB
Volume
60
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

โœฆ Synopsis


Private information retrieval (PIR) schemes allow a user to retrieve the i th bit of an n-bit data string x, replicated in k 2 databases (in the informationtheoretic setting) or in k 1 databases (in the computational setting), while keeping the value of i private. The main cost measure for such a scheme is its communication complexity. In this paper we introduce a model of symmetrically-private information retrieval (SPIR), where the privacy of the data, as well as the privacy of the user, is guaranteed. That is, in every invocation of a SPIR protocol, the user learns only a single physical bit of x and no other information about the data. Previously known PIR schemes severely fail to meet this goal. We show how to transform PIR schemes into SPIR schemes (with information-theoretic privacy), paying a constant factor in communication complexity. To this end, we introduce and utilize a new cryptographic primitive, called conditional disclosure of secrets, which we believe may be a useful building block for the design of other cryptographic protocols. In particular, we get a k-database SPIR scheme of complexity O(n 1ร‚(2k&1) ) for every constant k 2 and an O(log n)-database SPIR scheme of complexity O(log 2 n } log log n). All our schemes require only a single


๐Ÿ“œ SIMILAR VOLUMES


Bridging social and private interactions
โœ Eric M. Meyers ๐Ÿ“‚ Article ๐Ÿ“… 2008 ๐Ÿ› Wiley (John Wiley & Sons) ๐ŸŒ English โš– 63 KB

## Abstract Until recently, most models of information seeking and retrieval did not take into account other searchers or peers in the social/organizational environment (Wilson, 1999). Donald Case's (2007) survey of research on information seeking, needs and behavior further illustrates this omissi