Optimality of Cube-Root Communication for Two-Server Arithmetic PIR
Statement: AI-written, not yet formalized. Proof: open – no attempt yet.
An arithmetic PIR scheme treats the database as a vector of field elements and makes only black-box use of the field: query generation, answering and decoding are arithmetic circuits that must work for whichever field an adversary picks. The source’s main result is negative — with one server, arithmetic PIR cannot beat trivial download — but with two servers the classical cube-root schemes do arithmetize. The best binary two-server schemes reach \(n^{o(1)}\), and they run on matching vectors and rings with zero divisors, structures no field-agnostic scheme can appeal to. Whether the arithmetic setting is genuinely stuck at the cube root is unknown.
View PDF · LaTeX source · Formal statement — not yet formalized
The object. A two-server PIR scheme \((\mathsf{Query}, \mathsf{Ans}, \mathsf{Dec})\) is arithmetic if all three algorithms are arithmetic circuits over a generic field \(\mathbb{F}\) with black-box access to it, so that correctness and privacy hold for every \(\mathbb{F}\); it has finite degree if it uses no division or zero-check gates. Privacy is information-theoretic: each server’s query distribution is identical for all indices.
Conjecture. Determine whether the \(O(n^{1/3})\) communication of the arithmetized classical schemes is optimal, by resolving either: (a) there is a two-server arithmetic PIR with perfect information-theoretic security and finite degree whose total communication is \(o(n^{1/3})\) field elements; or (b) every such scheme has total communication \(\Omega(n^{1/3})\).
The equivalent linear-algebraic form (the source’s Theorem 5.3). Clause (a) holds with communication \(O(\ell(n))\) if and only if, for every sufficiently large field \(\mathbb{F}\), there exist \(n\) pairs of distributions \((A_1,B_1), \dots, (A_n,B_n)\) over \(O(\ell(n)) \times n\) matrices such that the rows of \((A_i,B_i)\) jointly span the unit vector \(e_i\); for all \(i,j\) the marginals \(A_i\) and \(A_j\) are identical, and likewise \(B_i\) and \(B_j\); and \((A_i,B_i)\) can be sampled in two steps — a short description \((q_1,q_2)\) of \(O(\ell)\) field elements sampled by a circuit \(S^{\mathbb{F}}_i\), then the matrices computed from it by a deterministic extraction procedure \(E^{\mathbb{F}}\) independent of \(i\), both circuits having black-box field access and no division or zero-check gates.
How the source states it. Page 5: “At present, it is unknown whether one can improve upon the \(O(n^{1/3})\) communication bound, let alone achieve sub-polynomial communication, in the arithmetic setting. We view this as an intriguing open question.” And, in its abstract, of the \(O(n^{1/3})\) result: “The optimality of this result remains an interesting open question.”
Perfect security and finite degree are load-bearing. Theorem 5.3 is stated there, where the equivalence is clean; the source records that it extends — statistical privacy corresponds to relaxing the marginal condition to statistical indistinguishability, statistical correctness to letting the spanning condition fail with negligible probability, and its Remark 5.4 partially handles division and zero-check gates. A scheme beating \(n^{1/3}\) only with imperfect security resolves the corresponding relaxed statement and should be reported as such.
A Boolean database changes the question. The source notes that if the database is restricted to a subset of the field — \(\{0,1\}\), say — linearity is cheap: the matching-vector scheme of Dvir and Gopi gives a two-server PIR whose answer algorithm is linear over a small field such as \(\mathbb{F}_3\) while the database is Boolean, with a non-linear decoder. A scheme of that shape does not resolve this statement.
Sources
- Applebaum, Ishai and Shechter. On Arithmetic Private Information Retrieval: Why Code-Based PIR (Usually) Fails. IACR ePrint 2026/1224. The source. The open question and Informal Theorem 1.4 are on page 5, Theorem 5.3 on page 19, and the arithmetized Woodruff–Yekhanin scheme in Section 5.2, page 20.
- Applebaum, Avron and Brzuska. Arithmetic Cryptography. Journal of the ACM 64(2):10:1–10:74, 2017. The arithmetic-cryptography framework the source adapts to PIR.
- Woodruff and Yekhanin. A Geometric Approach to Information-Theoretic Private Information Retrieval. CCC 2005. The scheme the source arithmetizes explicitly, reaching \(O(n^{1/3})\).
- Dvir and Gopi. 2-Server PIR with Sub-Polynomial Communication. STOC 2015. The matching-vector scheme achieving \(n^{o(1)}\) over the binary field, which the source states it does not know how to arithmetize.
- Razborov and Yekhanin. An \(\Omega(n^{1/3})\) Lower Bound for Bilinear Group Based Private Information Retrieval. Theory of Computing 3(1):221–238, 2007. The lower bound known for the strictly more restricted bilinear two-server setting.
View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized
Open in both directions, with the source having done the reduction work.
What is achieved, and how. The source arithmetizes Woodruff–Yekhanin explicitly: with \(m = O(n^{1/3})\) variables, the degree-\(3\) polynomial \(F_x(z) = \sum_{i<j<k} x_{i,j,k}z_iz_jz_k\), queries \(e_{i,j,k} + \lambda_s v\) for distinct nonzero \(\lambda_1,\lambda_2\), and answers consisting of \(F_x\) together with its \(m\) partial derivatives, recovered by Hermite interpolation. Query and answer are each \(O(m)\) field elements, everything is arithmetic, and both the answer and the decoder are linear.
Toward an improvement. The best binary schemes reach \(n^{o(1)}\) via the matching-vectors framework, which “does not appear to be field independent” — it needs rings with zero divisors. So an improvement has to find some other algebraic structure that survives an adversarial choice of field. Theorem 5.3 says exactly what such a structure would have to look like, in terms of matrix distributions.
Toward a lower bound. Two-server linear PIR has been studied, and it remains open whether such schemes over the binary field can be ruled out at \(O(\log n)\) communication. What the source’s equivalence adds is that the linear scheme it produces is field-agnostic (its clause on the two-step sampling), which it suggests “may make it more amenable to lower-bound techniques”. A strong \(\Omega(n^{1/3})\) bound is known for the strictly more restricted bilinear setting.
Checked against the literature, 2026-08-25. No proof, refutation or improvement found. Targeted check on a recent ePrint, not an exhaustive sweep.
Why the arithmetic model, and why it is bad news for code-based PIR. Every proposed code-based PIR scheme happens to be arithmetic, which is the source’s motivation. Its main theorem then says no single-server arithmetic PIR can have the server communicate less than \(n\) field elements — and it breaks the recent code-based candidates in minutes for all suggested parameters. The moral it draws is that security in this space inherently requires non-arithmetic operations whose degree scales with the field, as in lattice- or group-based PIR.
Where the model is escapable. Two relaxations work. With two servers and computational security, arithmetizing the distributed-point-function construction gives \(O(n^\varepsilon)\) communication from an arithmetic PRG (and \(\mathrm{polylog}(n)\) under sub-exponential security). With one server and a client secret key, arithmetic LPN gives an arithmetic sk-PIR at \(O(n^\varepsilon)\), with encoded-database length \((1+\varepsilon)n\) under LSN. This statement is about neither: it is the information-theoretic two-server case.
What a reviewer should be suspicious of, in order. First, whether a claimed improvement’s algorithms are field-agnostic in the source’s sense — correctness and privacy for an arbitrary adversarial choice of field, not for one field of the designer’s choosing. Second, whether the database is a vector of field elements with linearity over the same field, since restricting it to \(\{0,1\}\) makes linear answering cheap. Third, whether “finite degree” holds, i.e. no division or zero-check gates, since Theorem 5.3’s clean form assumes it.