Technical Program

Paper Detail

Paper Title Private Proximity Retrieval
Paper IdentifierTH3.R3.2
Authors Tuvi Etzion, Technion - Israel Institute of Technology, Israel; Oliver Gnilke, Aalborg Universiy, Denmark; David Karpuk, Universidad de los Andes, Colombia; Eitan Yaakobi, Yiwei Zhang, Technion - Israel Institute of Technology, Israel
Session Private Information Retrieval IV
Location Monge, Level 3
Session Time Thursday, 11 July, 14:30 - 16:10
Presentation Time Thursday, 11 July, 14:50 - 15:10
Manuscript  Click here to download the manuscript
Abstract A private proximity retrieval (PPR) scheme is a protocol which allows a user to retrieve the identities of all records in a database that are within some distance r from the user's record x. The user's privacy at each server is given by the fraction of the record x that is kept private. The distortion of a PPR scheme measures how accurately the user can calculate the identities of the desired files. We assume that each server stores a copy of the database. This paper studies protocols that offer trade-offs between perfect privacy and low computational complexity and storage. In this paper, this study is initiated. The work focuses on the case when the records are binary vectors together with the Hamming distance. In particular, for a given privacy level, we investigate the minimum number of servers that guarantee a prescribed distortion value. The collusions of pairs of servers as well as other distance measures are investigated.