A.E.: Generalizing pir for practical private retrieval of public data

Abstract. Private retrieval of public data is useful when a client wants to query a public data service without revealing the query to the server. Computational Private Information Retrieval (cPIR) achieves complete privacy for clients, but is deemed impractical since it involves expen-sive computation on all the data on the server. Besides, it is inflexible if the server wants to charge the client based on the service data that is exposed. k-Anonymity, on the other hand, is flexible and cheap for anonymizing the querying process, but is vulnerable to privacy and se-curity threats. We propose a practical and flexible approach for the pri-vate retrieval of public data called Bounding-Box PIR (bbPIR). Using bbPIR, a client specifies both privacy requirements and a service charge budget. The server satisfies the client’s requirements, and achieves overall good performance in computation and communication. bbPIR generalizes cPIR and k-Anonymity in that the bounding box can include as much as all the data on the server or as little as just k data items. The efficiency of bbPIR compared to cPIR and the effectiveness of bbPIR compared to k-Anonymity are verified in extensive experimental evaluations.