Paper 2023/1619

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

Shuaishuai Li, Zhongguancun Laboratory
Weiran Liu, Alibaba Group (China)
Liqiang Peng, Alibaba Group (China)
Cong Zhang, Institute for Advanced Study, BNRist, Tsinghua University
Xinwei Gao, Alibaba Group (China)
Aiping Liang, Alibaba Group (China)
Lei Zhang, Alibaba Group (China)
Dongdai Lin, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences
Yuan Hong, University of Connecticut

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.

Available format(s)
Cryptographic protocols
Publication info
Private Information Retrieval
Contact author(s)
genielss @ yeah net
weiran lwr @ alibaba-inc com
plq270998 @ alibaba-inc com
zhangcong @ mail tsinghua edu cn
xinwei gao 7 @ gmail com
ailing lap @ alibaba-inc com
zongchao zl @ taobao com
ddlin @ iie ac cn
yuan hong @ uconn edu
2024-03-03: last of 3 revisions
2023-10-19: received
See all versions
Short URL
No rights reserved


      author = {Shuaishuai Li and Weiran Liu and Liqiang Peng and Cong Zhang and Xinwei Gao and Aiping Liang and Lei Zhang and Dongdai Lin and Yuan Hong},
      title = {Pai: Private Retrieval with Constant Online Time, Communication, and Client-Side Storage for Data Marketplace},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1619},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.