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
## 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