Pith. sign in

REVIEW 2 major objections 5 minor 14 references

The Capacity of Semantic Private Information Retrieval with Colluding Servers

T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that the capacity of semantic private information retrieval with $T$ colluding servers is $\mathbb{E}[L]/\left(L_1+\frac{T}{N}L_2+\cdots+\left(\frac{T}{N}\right)^{K-1}L_K\right)$, and gives a scheme that attains it.

desk verdict A natural capacity extension with a solid converse but an under-proved achievability step; worth refereeing despite the integrality gap. read the letter →

arxiv 2507.15818 v1 pith:2KCAR3QS submitted 2025-07-21 cs.IT cs.CRcs.NIeess.SPmath.IT

Mohamed Nomeir , Alptug Aytekin , Sennur Ulukus This is my paper · ORCID
classification cs.ITcs.CRcs.NIeess.SPmath.IT MSC 94A1594A62
keywords privateinformationretrievalsemanticPIRcolludingserverscapacityinformation-theoreticprivacydownloadcostMDScodesTPIR
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies private information retrieval when messages have different lengths and different retrieval probabilities (semantic PIR) and when any $T$ of the $N$ servers may collude to identify the requested message (Sem-TPIR). It proves the exact capacity: the best possible ratio of average retrieved message length to downloaded symbols is $\mathbb{E}[L]$ divided by $L_1+\frac{T}{N}L_2+\cdots+\left(\frac{T}{N}\right)^{K-1}L_K$, where messages are ordered longest to shortest. This generalizes the classical TPIR capacity, recovered when all lengths and priors are equal, and the no-collusion semantic PIR capacity, recovered at $T=1$. The paper also shows the capacity can exceed ordinary PIR capacity when message lengths and priors are skewed, and it constructs a scheme that reaches the bound.

What carries the argument

The load-bearing identity is the rate formula $C=\mathbb{E}[L]/\left(L_1+\frac{T}{N}L_2+\cdots+\left(\frac{T}{N}\right)^{K-1}L_K\right)$. The mechanism that achieves it is a triangular matrix $V$ (equation (26)) with diagonal entries $N^i/T^{i-1}$ and off-diagonal entries $(N-T)N^{j-1}/T^{j-1}$ for $i<j$; it maps the scheme's per-round symbol counts $\nu_1,\ldots,\nu_K$ to the message sub-packet lengths $U_1,\ldots,U_K$. Inverting $V$ gives the $\nu_i$ in terms of the $L_i$, scaled by $\alpha=\gcd(L_{[K]},M_{[K]})$ so that the counts are integers. Privacy is maintained by applying the same MDS code and fresh random invertible matrices to interference symbols in each $s$-sum phase, so every $T$-server subset observes equivalent distributions for all possible requested indices.

What would settle it

For the small case $N=3$, $T=2$, $K=2$, $L_1=2$, $L_2=1$, $p_1=p_2=1/2$, the claimed capacity is $\frac{3/2}{2+2/3}=9/16$; an exhaustive search over all finite query-answer protocols that finds any scheme with rate above $9/16$ would refute the upper bound, while showing that the proposed scheme's required $\nu_i$ are fractional for these lengths would expose the achievability gap.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for $N$ servers, any $T<N$ colluding servers, $K$ messages with lengths $L_1\ge\cdots\ge L_K$ and retrieval priors $p_i$, the capacity of semantic TPIR is $C=\mathbb{E}[L]/\left(L_1+\frac{T}{N}L_2+\cdots+\left(\frac{T}{N}\right)^{K-1}L_K\right)$. The upper bound is proved by a converse using Han's inequality and an induction over permutations of messages, showing that any private scheme must spend at least $\sum_i (T/N)^{i-1}L_i$ downloads on average. The achievability scheme downloads singleton symbols and $s$-linear combinations of symbols from $s$ distinct messages, encoded with MDS codes and randomized by invertible linear maps, so that any $T$ colluding servers see the same distribution for every possible requested message. The formula reduces to the known TPIR capacity when lengths and priors are uniform, and to the no-collusion semantic PIR capacity when $T=1$.

Load-bearing premise

The achievability side assumes that after sub-packetizing the messages, every download count in the scheme is a positive whole number and that finite-field MDS codes of exactly those dimensions exist; for arbitrary message lengths neither is guaranteed by the paper.

Editorial extensions

If this is right

  • No scheme can beat the rate $\mathbb{E}[L]/\sum_{i=1}^K (T/N)^{i-1}L_i$, and the paper's scheme attains it, so the capacity of semantic TPIR is exactly that quantity.
  • With equal lengths and uniform priors the formula collapses to the classical TPIR capacity $(1+\frac{T}{N}+\cdots+(\frac{T}{N})^{K-1})^{-1}$.
  • With $T=1$ it collapses to the no-collusion semantic PIR capacity $\mathbb{E}[L]/(L_1+\frac{1}{N}L_2+\cdots+\frac{1}{N^{K-1}}L_K)$.
  • Semantic TPIR can beat ordinary PIR capacity: for $N=10$, $T=2$, $K=2$, $L_1=1000$, $L_2=100$, $p_1=0.99$, the capacity is about $0.9716$, exceeding the classical PIR capacity of about $0.9081$.
  • Because longer messages receive larger weights in the denominator, reducing the length of the longest messages (or making lengths more equal) improves the capacity the most.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The achievability proof requires every $((N-T)/T)^{s-1}\nu_i$ and the MDS dimensions to be positive integers; for arbitrary message lengths this is only demonstrated under the normalization $L_i=\beta_i N^K$. I infer that a block-scaling argument on repeated message sets would close this gap, so the formula is likely the true capacity for all finite lengths even though the literal proof leaves the
  • The priors enter the capacity only through the average length $\mathbb{E}[L]$, so the detailed popularity distribution does not affect the achievable download efficiency; only the average message size matters.
  • Since the formula depends on $N$ and $T$ only through the ratio $T/N$, configurations with the same ratio have the same capacity, and the semantic problem inherits the effective-servers reduction familiar from classical TPIR; a similar symmetrization may extend the result to arbitrary collusion patterns.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies semantic private information retrieval (Sem-PIR) with T colluding servers. Messages have arbitrary integer lengths L1 >= L2 >= ... >= LK and non-uniform retrieval probabilities p_i. The main result, Theorem 1, states that the capacity is E[L] / (L1 + (T/N)L2 + ... + (T/N)^{K-1} LK). The proof consists of a converse based on Han's inequality and an MDS-based achievability scheme that downloads singletons and s-sum combinations; two numerical examples are provided, and corollaries recover or compare with classical TPIR and Sem-PIR capacities. The paper claims that this exact formula holds for all parameter values.

Significance. If correct, the capacity formula is a clean unification of known results: setting T=1 gives the Sem-PIR capacity of [13], and setting equal lengths and uniform priors gives the classical TPIR capacity (1 + T/N + ... + (T/N)^{K-1})^{-1}. The semantic model's prediction that unequal message lengths and non-uniform priors can improve download efficiency is practically relevant, and the corollaries provide useful comparisons. The converse appears independent of the achievability construction, and Example 1 backs the formula with explicit arithmetic. The main caveat is that the achievability proof, as written, does not cover all integer message lengths because of an integrality and MDS-existence gap; the result is therefore currently a conditional exact-capacity theorem, though a repair by block scaling seems plausible.

major comments (2)
  1. [Section V, Eqs. (25)-(27), Remark 3] The achievability scheme is not fully specified for arbitrary integer message lengths. The construction requires nu = (1/alpha) V^{-1} L to be a vector of positive integers and requires every ((N-T)/T)^{s-1} nu_k used in the s-sum steps to be an integer, so that Step 1 and Step 2 can be implemented with whole symbols. Remark 3 proves positivity and integrality only after imposing the normalization L_i = beta_i N^K, a condition not stated in Theorem 1. For example, with N=2, T=1, K=2, and L1=L2=1, we have V^{-1}L = (1/4, 1/4); since alpha must divide both message lengths, alpha=1 is forced, and the scheme would require downloading nu1=nu2=1/4 symbols per server in Step 1. Thus the stated construction does not literally achieve the claimed exact capacity for all parameter values. A block-scaling or padding argument, or an explicit asymptotic statement, is needed to complete the proof; the converse appears independent of this gap.
  2. [Section V, Steps 1 and 2] The scheme invokes MDS codes MDS_{a x b} for many values of a and b, but it never specifies the finite field size or proves that all required MDS codes and the random invertible matrices S_i exist over a common field. Since the code dimensions grow with powers of (N-T)/T and with the nu_i, the proof should state a sufficient condition, for example a field of size at least the largest code dimension, or cite an explicit MDS construction that covers the required parameters. This is a repairable gap, but as written the achievability claim is incomplete.
minor comments (5)
  1. [Section VI-B, Example 2] The retrieval probabilities p_i are not specified in Example 2, so E[L] is undefined and the claimed rate equality cannot be verified numerically. Please state p_i or clarify that the rate expression is formal in E[L].
  2. [Section V, Eq. (27)] The notation alpha = gcd(L[K], M([K])) is undefined. It should say the gcd of the entries of the vectors L and M, and it should be clarified over which integers the gcd is taken after normalization.
  3. [Section VII, Eq. (61)] There is a stray unmatched bracket in the tuple (S1([beta1], :]), ...); the expression should be corrected to (S1([beta1], :), ..., SK([betaK], :)).
  4. [Section VIII, Eq. (74)] The phrase 'since the proof is symmetric over i and j' is slightly misleading because the roles of the desired and the interfering message are not fully symmetric in the derivation; the conclusion is correct, but the wording should be adjusted.
  5. [Theorem 1 and examples] The capacity notation is used inconsistently: Theorem 1 writes the full argument list, while the examples write CSem-TPIR(4,3,3) or CSem-TPIR(8,2,4) without the lengths and priors. Please make the notation uniform.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the capacity formula is proved by an independent converse plus an explicitly counted scheme; the same-group citation [13] is non-load-bearing, and the Remark 3 integrality gap (L_i = beta_i N^K) is a correctness concern rather than a self-referential step.

full rationale

The derivation chain is self-contained and not circular. The converse (Section VIII) upper-bounds the rate using only Han's inequality (restated as Lemma 1), Lemma 2, and the privacy constraints; the chain in Eqs. (75)-(83) yields N*H_T >= L1 + (T/N)L2 + ... + (T/N)^{K-1}L_K by maximizing over message permutations, with no appeal to the capacity formula. The achievability scheme (Section V) is a concrete protocol whose download tally is counted honestly: Eq. (20) gives D = sum (N^i/T^{i-1}) nu_i, Eq. (24) gives the symbols of the requested message, and the identities alpha*U = L and alpha*D = L1 + (T/N)L2 + ... + (T/N)^{K-1}L_K follow from U = V*nu and nu = (1/alpha)V^{-1}L in Eqs. (25)-(33); Example 1 confirms the physical download count per server (81 = 324/4). This is a scheme designed to hit the claimed rate, not the rate assumed as an input, and the matching converse is independent content. The T=1 special case of Theorem 1 is derived within the paper by setting T=1, so the citation of [13] (Vithana-Banawan-Ulukus, same group) for the no-collusion Sem-PIR capacity is contextual and non-load-bearing; it appears only in the introduction and in Corollaries 1-2 comparisons. Per the reviewing rule, I flag one non-circular defect: Remark 3 (Eq. 35) proves integrality of the s-sum counts only after imposing L_i = beta_i * N^K, a restriction not stated in Theorem 1. For N=2, T=1, K=2, L1=L2=1, nu = (1/4, 1/4) for any alpha dividing both message lengths, so Step 1's requirement of downloading nu_i symbols per server cannot be executed; the achievable scheme as written does not run for arbitrary lengths. This is a correctness/overstatement gap (a block-scaling or padding argument would plausibly repair it), not a circular step, since neither the converse nor the scheme reintroduces the claimed capacity as an input. Overall score 2: the only self-referential element is the minor, non-load-bearing citation of the authors' own [13].

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The derivation rests on the standard PIR system model, MDS code existence, Han's inequality, and one cited distributional lemma. There are no empirical free parameters or newly postulated physical entities. The only ad hoc element is the beta_i N^K normalization used for integrality in the achievability argument.

assumptions (8)
  • domain assumption Message symbols are generated independently and uniformly at random, giving H(W_i) = L_i.
    Used in Section II, Eq. (1), as the standard PIR message model.
  • domain assumption The user has no prior knowledge of message contents, so I(W1,...,WK; Q) = 0.
    Eq. (2) in Section II; standard PIR assumption.
  • domain assumption Servers are honest but curious, and each answer is a deterministic function of the queries and messages.
    Eq. (5) in Section II; standard PIR model.
  • domain assumption Privacy requires exact zero mutual information between the request index and any T-subset of queries.
    Eqs. (3)-(4) in Section II; defines the T-colluding privacy requirement.
  • standard math Existence of MDS codes with the dimensions used in Steps 1 and 2 of the scheme over a sufficiently large finite field.
    Invoked in Section V for the MDS_Nu and MDS_s-sum encodings; the paper does not specify the field size.
  • standard math Han's inequality for average entropies of T-subsets.
    Lemma 1 in Section VIII; used in the converse proof.
  • standard math The distributional equivalence of random linear transformations and MDS-coded interference, restated as Corollary 5 from [3, Lemma 1].
    Used in Section VII for the privacy proof; cited rather than reproved.
  • ad hoc to paper Message lengths can be normalized so that L_i = beta_i N^K for integers beta_i.
    Introduced in Remark 3 to prove that the s-sum parameters are positive integers; common rescaling preserves the capacity, but the paper does not explicitly justify this normalization for arbitrary lengths.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Capacity of Semantic Private Information Retrieval with Colluding Servers." pith.science (2026). https://pith.science/paper/2KCAR3QS

@misc{pith2026250715818,
  author       = {Pith},
  title        = {Pith review of: The Capacity of Semantic Private Information Retrieval with Colluding Servers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2KCAR3QS}},
  note         = {Machine review of arXiv:2507.15818}
}
abstract

We study the problem of semantic private information retrieval (Sem-PIR) with $T$ colluding servers (Sem-TPIR), i.e., servers that collectively share user queries. In Sem-TPIR, the message sizes are different, and message retrieval probabilities by any user are not uniform. This is a generalization of the classical PIR problem where the message sizes are equal and message retrieval probabilities are identical. The earlier work on Sem-PIR considered the case of no collusions, i.e., the collusion parameter of $T=1$. In this paper, we consider the general problem for arbitrary $T < N$. We find an upper bound on the retrieval rate and design a scheme that achieves this rate, i.e., we derive the exact capacity of Sem-TPIR.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 13 canonical work pages

  1. [13]

    Vithana, K

    S. Vithana, K. Banawan, and S. Ulukus. Semantic private information retrieval. IEEE Trans. Info. Theory , 68(4):2635–2652, December 2021

    work page 2021

  2. [1]

    B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan. Private information retrieval. Jour. of the ACM , 45(6):965–981, November 1998

    work page 1998

  3. [2]

    Sun and S

    H. Sun and S. A. Jafar. The capacity of private information retrieval. IEEE Trans. Info. Theory , 63(7):4075–4088, July 2017

    work page 2017

  4. [3]

    Sun and S

    H. Sun and S. A. Jafar. The capacity of robust private information re- trieval with colluding databases. IEEE Trans. Info. Theory, 64(4):2361– 2370, April 2018

    work page 2018

  5. [4]

    X. Yao, N. Liu, and W. Kang. The capacity of private information retrieval under arbitrary collusion patterns for replicated databases. IEEE Trans. Info. Theory , 67(10):6841–6855, July 2021

    work page 2021

  6. [5]

    Banawan and S

    K. Banawan and S. Ulukus. Private information retrieval through wiretap channel II: Privacy meets security. IEEE Trans. Info. Theory , 66(7):4129–4149, February 2020

    work page 2020

  7. [6]

    Banawan and S

    K. Banawan and S. Ulukus. The capacity of private information retrieval from coded databases. IEEE Trans. Info. Theory , 64(3):1945–1956, January 2018

    work page 1945

  8. [7]

    Makkonen, D

    O. Makkonen, D. Karpuk, and C. Hollanti. Secret sharing for secure and private information retrieval: A construction using algebraic geometry codes. 2024. Available online at arxiv:2408.00542

    arXiv 2024

Show all 14 references
  1. [8]

    Banawan and S

    K. Banawan and S. Ulukus. The capacity of private information retrieval from Byzantine and colluding databases. IEEE Trans. Info. Theory , 65(2):1206–1219, September 2018

    2018

  2. [9]

    Sun and S

    H. Sun and S. A. Jafar. The capacity of symmetric private information retrieval. IEEE Trans. Info. Theory , 65(1):322–329, June 2018

    2018

  3. [10]

    C. Tian, H. Sun, and J. Chen. Capacity-achieving private information retrieval codes with optimal message size and upload cost. IEEE Trans. Info. Theory, 65(11):7613–7627, November 2019

    2019

  4. [11]

    Wang and S

    Z. Wang and S. Ulukus. Symmetric private information retrieval at the private information retrieval rate. IEEE Jour. on Selected Areas in Info. Theory, 3(2):350–361, June 2022

    2022

  5. [12]

    Ulukus, S

    S. Ulukus, S. Avestimehr, M. Gastpar, S. A. Jafar, R. Tandon, and C. Tian. Private retrieval, computing, and learning: Recent progress and future challenges. IEEE Journal on Selected Areas in Communications , 40(3):729–748, March 2022

    2022

  6. [14]

    T. M. Cover and J. A. Thomas. Elements of information theory . John Wiley & Sons, 1999

    1999

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.