DROPS

Document

DOI: 10.4230/LIPIcs.ITC.2024.6

Information-Theoretic Single-Server PIR in the Shuffle Model

Authors: Yuval Ishai, Mahimna Kelkar, Daniel Lee, and Yiping Ma

Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)

Abstract

We revisit the problem of private information retrieval (PIR) in the shuffle model, where queries can be made anonymously by multiple clients. We present the first single-server PIR protocol in this model that has sublinear per-client communication and information-theoretic security. Moreover, following one-time preprocessing on the server side, our protocol only requires sublinear per-client computation. Concretely, for every γ > 0, the protocol has O(n^{γ}) communication and computation costs per (stateless) client, with 1/poly(n) statistical security, assuming that a size-n database is simultaneously accessed by poly(n) clients. This should be contrasted with the recent breakthrough result of Lin, Mook, and Wichs (STOC 2023) on doubly efficient PIR in the standard model, which is (inherently) limited to computational security.

Cite as

Yuval Ishai, Mahimna Kelkar, Daniel Lee, and Yiping Ma. Information-Theoretic Single-Server PIR in the Shuffle Model. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ishai_et_al:LIPIcs.ITC.2024.6,
  author =	{Ishai, Yuval and Kelkar, Mahimna and Lee, Daniel and Ma, Yiping},
  title =	{{Information-Theoretic Single-Server PIR in the Shuffle Model}},
  booktitle =	{5th Conference on Information-Theoretic Cryptography (ITC 2024)},
  pages =	{6:1--6:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-333-1},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{304},
  editor =	{Aggarwal, Divesh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.6},
  URN =		{urn:nbn:de:0030-drops-205142},
  doi =		{10.4230/LIPIcs.ITC.2024.6},
  annote =	{Keywords: Private information retrieval, Shuffle model}
}

Search Results

Documents authored by Lee, Daniel

Information-Theoretic Single-Server PIR in the Shuffle Model

Abstract

Cite as

Thanks for your feedback!

Could not send message