Scholarlink

A Doubly Efficient Private Information Retrieval (DEPIR) is defined as a Private Information Retrieval (PIR) scheme with both near-linear server-side preprocessing time and sublinear query time. For many years, it has been a strong open question to devise a DEPIR scheme from standard assumptions. Very recently, Lin et al. (STOC ’23) devised the first single-server DEPIR scheme from standard assumptions. However, their work left one major question open: can we build a DEPIR scheme in the multi-server setting, without relying on heavy cryptographic machinery? In this work, we discuss two different settings for multi-server DEPIR. In the non-colluding, non-communicating servers setting, we propose the first doubly efficient multi-server PIR scheme. Our scheme is information-theoretic. For a database of size \(N\) , our scheme allows servers to answer an infinite number of client queries in \(N^{o(1)}\) time, after a single preprocessing phase which takes \(N^{1+o(1)}\) time. Our result is only an \(N^{o(1)}\) factor from the lower bound proven by Persiano and Yeo (SODA ’22) for this setting. In addition, we devise a second information-theoretic PIR scheme in this setting which pushes the state of the art for the setting where the number of servers is more constrained. It achieves equally fast query times as our first scheme above, and a preprocessing time of \(N^{2+o(1)}\) . This scheme uses \(O(\log N)\) servers. Both schemes don’t require any cryptographic primitives. Furthermore, in the setting where the servers are additionally allowed to communicate and keep a global state (which is similarly required by PIR allowing database updates), we show a family of information-theoretic DEPIR schemes which achieve \(N\textsf {polylog}N\) preprocessing time, and \(\log ^3\,N\) communication and server time, for any number of servers \(k\) greater than three. We also discuss how introducing more servers or computational assumptions in this setting may improve concrete efficiency of the PIR. This setting of communicating servers requires online communication between servers to answer queries, in contrast to the standard multi-server PIR setting where servers only communicate to coordinate the database contents and do not communicate at query time.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Multi-server Doubly Efficient PIR in the Classical Model and Beyond

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Arthur Lazzaretti,
  • Zeyu Liu,
  • Ben Fisch,
  • Peihan Miao,
  • Charalampos Papamanthou

摘要

A Doubly Efficient Private Information Retrieval (DEPIR) is defined as a Private Information Retrieval (PIR) scheme with both near-linear server-side preprocessing time and sublinear query time. For many years, it has been a strong open question to devise a DEPIR scheme from standard assumptions. Very recently, Lin et al. (STOC ’23) devised the first single-server DEPIR scheme from standard assumptions. However, their work left one major question open: can we build a DEPIR scheme in the multi-server setting, without relying on heavy cryptographic machinery? In this work, we discuss two different settings for multi-server DEPIR. In the non-colluding, non-communicating servers setting, we propose the first doubly efficient multi-server PIR scheme. Our scheme is information-theoretic. For a database of size \(N\) , our scheme allows servers to answer an infinite number of client queries in \(N^{o(1)}\) time, after a single preprocessing phase which takes \(N^{1+o(1)}\) time. Our result is only an \(N^{o(1)}\) factor from the lower bound proven by Persiano and Yeo (SODA ’22) for this setting. In addition, we devise a second information-theoretic PIR scheme in this setting which pushes the state of the art for the setting where the number of servers is more constrained. It achieves equally fast query times as our first scheme above, and a preprocessing time of \(N^{2+o(1)}\) . This scheme uses \(O(\log N)\) servers. Both schemes don’t require any cryptographic primitives. Furthermore, in the setting where the servers are additionally allowed to communicate and keep a global state (which is similarly required by PIR allowing database updates), we show a family of information-theoretic DEPIR schemes which achieve \(N\textsf {polylog}N\) preprocessing time, and \(\log ^3\,N\) communication and server time, for any number of servers \(k\) greater than three. We also discuss how introducing more servers or computational assumptions in this setting may improve concrete efficiency of the PIR. This setting of communicating servers requires online communication between servers to answer queries, in contrast to the standard multi-server PIR setting where servers only communicate to coordinate the database contents and do not communicate at query time.