Minicrypt PIR for Big Batches

Nico Döttling; Jesko Dujmovic; Julian Loss; Maciej Obremski

Paper 2025/317

Minicrypt PIR for Big Batches

Nico Döttling

, Helmholtz Center for Information Security

Jesko Dujmovic

, Helmholtz Center for Information Security

Julian Loss

, Helmholtz Center for Information Security

Maciej Obremski

, National University of Singapore

Abstract

We present PIR protocols for offline/online two-server setting where a client $C$ wants to privately retrieve a batch of entries from database of size $N$ by interacting with a servers . The client has interacted with a server ahead of time, not colluding with . We present simple protocols based on one-way functions that substantially improve on the query complexity or runtime over existing works. Concrete instantiations of our general paradigm lead to batch PIR protocols with the following parameters: - A protocol for batches of , where , and each spend a total of work and exchange bits of communication. This yields an amortized complexity of work and communication per query in the batch. - A more balanced protocol for batches of size in which spends a total of work, and spend work, and the total communication is of size . Our protocols have immediate applications such as Private Set Intersection (PSI) in the two-server setting with preprocessing and unbalanced set sizes.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: PIR Private Information Retrieval offline/online minicrypt one-way functions batch
Contact author(s): doettling @ cispa de
jesko dujmovic @ cispa de
loss @ cispa de
obremski math @ gmail com
History: 2025-02-21: approved; 2025-02-21: received; See all versions
Short URL: https://ia.cr/2025/317
License: CC BY

BibTeX

@misc{cryptoeprint:2025/317,
      author = {Nico Döttling and Jesko Dujmovic and Julian Loss and Maciej Obremski},
      title = {Minicrypt {PIR} for Big Batches},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/317},
      year = {2025},
      url = {https://eprint.iacr.org/2025/317}
}