Paper 2023/1510

Towards Practical Doubly-Efficient Private Information Retrieval

Hiroki Okada, KDDI Research (Japan)
Rachel Player, Royal Holloway University of London
Simon Pohmann, Royal Holloway University of London
Christian Weinert, Royal Holloway University of London

Private information retrieval (PIR) protocols allow clients to access database entries without revealing the queried indices. They have many real-world applications, including privately querying patent-, compromised credential-, and contact databases. While existing PIR protocols that have been implemented perform reasonably well in practice, they all have suboptimal asymptotic complexities. A line of work has explored so-called doubly-efficient PIR (DEPIR), which refers to single-server PIR protocols with optimal asymptotic complexities. Recently, Lin, Mook, and Wichs (STOC 2023) presented the first protocol that completely satisfies the DEPIR constraints and can be rigorously proven secure. Unfortunately, their proposal is purely theoretical in nature. It is even speculated that such protocols are completely impractical, and hence no implementation of any DEPIR protocol exists. In this work, we challenge this assumption. We propose several optimizations for the protocol of Lin, Mook, and Wichs that improve both asymptotic and concrete running times, as well as storage requirements, by orders of magnitude. Furthermore, we implement the resulting protocol and show that for batch queries it outperforms state-of-the-art protocols.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. Financial Cryptography and Data Security 2024
Contact author(s)
Simon Pohmann 2022 @ live rhul ac uk
2024-01-12: last of 2 revisions
2023-10-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hiroki Okada and Rachel Player and Simon Pohmann and Christian Weinert},
      title = {Towards Practical Doubly-Efficient Private Information Retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1510},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.