Polylogarithmic Single-Server Shuffle PIR with Negligible Security Error
Statement: AI-written, not yet formalized. Proof: open – no attempt yet.
In the shuffle model many clients send their PIR queries to a single server through an anonymous channel, so the server sees the whole multiset of queries but not who sent which. That alone buys something impossible in the standard model: a single-server PIR with sublinear communication and no computational assumption anywhere. The source’s security error, though, is only inverse-polynomial, and its own lower bound says that for a broad class of constructions it has to be. Whether polylogarithmic communication and negligible error can be had together, with only polynomially many honest queries, is the question it leaves open.
View PDF · LaTeX source · Formal statement — not yet formalized
The model (the source’s Definition 5.1). A single-server shuffle-model PIR over an alphabet \(\Sigma\) is a tuple \((\mathsf{Setup}, \mathsf{Query}, \mathsf{Answer}, \mathsf{Recon})\): the server deterministically encodes \(x \in \Sigma^n\) as \(P_x\); a client turns an index \(i\) into \(k\) sub-queries \(q_1, \dots, q_k\), each sent as its own anonymous message; the server answers each sub-query with the same algorithm; and the client reconstructs \(x_i\) from the \(k\) answers, with probability \(1\). For a shuffler \(\Pi = \{\Pi_c\}\) and a query count \(C^*\), let \(\widetilde D_{n,\Pi,C^*}(I)\) be the distribution of the shuffled concatenation of \(C^*\) clients’ sub-queries on index vector \(I\). The scheme is \((\Pi, C, \varepsilon)\)-secure if for every \(n\), every \(C^* \ge C(n)\) and all \(I, I'\), the statistical distance between \(\widetilde D_{n,\Pi,C^*}(I)\) and \(\widetilde D_{n,\Pi,C^*}(I')\) is at most \(\varepsilon(n)\).
Conjecture. There is such a protocol over \(\Sigma = \{0,1\}\), a polynomial \(C\), a negligible \(\varepsilon\) and a constant \(d\) with per-query communication at most \((\log n)^d\) that is \((\Pi, C, \varepsilon)\)-secure for the perfect shuffler.
How the source states it. Section 7, page 30: “The main technical question we leave open in this work is the possibility of obtaining similar results with negligible security error”; and, in the same paragraph, “We conjecture that polylogarithmic communication per client with negligible security can be achieved by instantiating both OPIR and IPIR with the Reed-Muller PIR construction with a polylogarithmic security threshold and a polylogarithmic communication complexity.” The restriction to polynomially many clients is the introduction’s, page 3: the paper discusses “whether negligible security is possible (with polynomially many clients) by using other protocols in the inner layer.”
The statement above is the existence claim, not the named route. The source’s own conjecture is stronger: it asserts that a specific instantiation works. Settling the existence claim by any construction resolves the open question the source poses; settling it via Reed–Muller in both layers additionally confirms the authors’ guess at how.
Why the polynomial query bound is the crux. Drop it and the statement is already known — the source reaches polylogarithmic communication with a \((\log n)\)-server CNF-based inner layer once the number of clients is \(n^{O(\log n)}\). Drop the polylogarithmic communication instead and it is known too, by the source’s Remark 11, at \(O(n/\log n)\) communication with super-linearly many clients.
Sources
- Ishai, Kelkar, Lee and Ma. Information-Theoretic Single-Server PIR in the Shuffle Model. IACR ePrint 2024/930. The source. Definition 5.1 is on page 15, Theorem 1.1 on page 2, Theorem 6.5 and the Reed–Muller remark on page 29, the open question in Section 7 on page 30.
- Ishai, Kushilevitz, Ostrovsky and Sahai. Cryptography from Anonymity. FOCS 2006. Introduces cryptography in the shuffle model.
- Dvir and Gopi. 2-Server PIR with Sub-Polynomial Communication. STOC 2015. The standard-model constant-server benchmark the source’s polylogarithmic variant is compared against.
- Lin, Mook and Wichs. Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE. STOC 2023. The standard-model doubly efficient PIR the source contrasts itself with; inherently computational.
View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized
Open, with the positive direction better signposted than the negative one.
Toward the construction. The source’s inner–outer paradigm composes two standard multi-server PIR schemes: the outer scheme’s sub-queries are spread across the shuffled messages and the inner scheme answers each. What has to be shown is that instantiating both layers with Reed–Muller PIR, at a polylogarithmic security threshold and polylogarithmic communication, gives negligible error at polynomially many queries. The two things to watch are whether the threshold can be kept polylogarithmic while the error goes negligible, and whether the message complexity stays inside the communication budget — the source counts anonymous messages separately from communication precisely because sending \(s\) one-bit messages is not the same as one \(s\)-bit message.
Toward the lower bound. Theorem 6.5 rules out negligible error for inner–outer constructions \(\mathsf{ShPIR}(\Phi, \Psi)\) in which \(\Psi\) is a constant-server additive PIR and the client count together with the numbers \(K_\Phi, K_\Psi\) of possible sub-query vectors are all polynomially bounded. A refutation would have to push that argument past additive inner layers — and the source explicitly flags instantiating the inner PIR with Reed–Muller as “an interesting open problem to consider”, because its bound says nothing there.
Checked against the literature, 2026-08-25. No proof, refutation or improvement found in the months since the ePrint. Targeted check, not an exhaustive sweep.
What the shuffler is doing. The source’s own framing is that shuffle-model PIR is a hybrid between the single- and multi-server models: the shuffler is a second “server” trusted not to collude, which holds no copy of the database and performs only database-irrelevant computation. That is why the model escapes the standard-model impossibility while remaining a plausible deployment — two servers holding the same database are hard to keep independent, one server plus a shuffler much less so.
Adversarial clients are free. The source’s model tolerates any number of clients colluding with the server, provided the honest-query bound is met; and because queries are anonymous, security depends on the total number of queries rather than the number of clients, so a fixed set of clients can pad with dummy queries to reach the bound. So the polynomial \(C\) in the statement is a bound on honest queries, not on distinct participants.
What a reviewer should be suspicious of, in order. First, whether the statement’s “per-query communication” is the source’s (client query plus server response for one query) and not an amortized figure — the source’s Remark 11 result is explicitly amortizable and this one is not stated that way. Second, whether the perfect shuffler is the right setting: the source handles imperfect shufflers in its Appendix B, and a construction that needs a perfect one is weaker than it looks. Third, whether Theorem 6.5’s hypotheses really are all four separate conditions, since a proof of the conjecture must violate at least one of them.