Paper 2023/1619

Pai: Private Retrieval with Constant Online Time, Communication, and Client-Side Storage for Data Marketplace

Abstract

Data marketplace is a critical platform for trading high-quality and private-domain data. A basic functionality in the data marketplace is that a data seller (as a server) owns a private key-value database and provides private query services to data buyers (as clients). This relates to Private Information Retrieval (PIR) by Keyword with symmetric privacy, abbreviated to KSPIR. In the context of PIR, Client-preprocessing PIR supports fast online retrievals by introducing a one-time, query-independent offline phase with linear offline communication, promising for deployment in the data marketplace. However, there are remaining challenges. First, the client-side storage and the online costs are still relatively large. Second, current implementations only consider public array databases (cannot handle private or key-valued databases). Third, existing solutions are somewhat intricate for non-expert PIR developers. To address these significant deficiencies, we propose a novel client-preprocessing PIR framework Pai, which only requires constant online time, communication, and client-side storage. Building upon Pai,we present its KSPIR variant PaiKSPIR.We also explore an alternative variant of KSPIR named Chargeable KSPIR (CKSPIR) for the data marketplace application where the server seeks payment from the client for retrieval. We have undertaken comprehensive implementations and conducted extensive experiments for Pai. The online query time is only about 1ms with 1KB communication overhead for large key-value databases (e.g., $n = 2^{24}$). Given the superior online time and storage, our protocol is well-suited in the data marketplace for even real-time key-value retrievals.