arxiv: 2605.09368 · v2 · submitted 2026-05-10 · 💻 cs.IT · math.IT

Recognition: 1 theorem link

· Lean Theorem

Secure and Private Structured-Subset Retrieval: Fundamental Limits and Achievable Schemes

Anoosheh Heidarzadeh, Maha Issa

Authors on Pith no claims yet

Pith reviewed 2026-05-13 07:34 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords structured-subset retrievalprivate information retrievalinformation theoretic securitynon-colluding serversshared randomnesssubpacketizationdemand family

0 comments

The pith

For any family of demand subsets, the maximum retrieval rate is 1-1/N with fixed randomness and subpacketization costs.

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

The paper introduces the Secure and Private Structured-Subset Retrieval problem, generalizing symmetric multi-message PIR to arbitrary families of possible demand subsets of size D. It establishes that the maximum achievable retrieval rate is always 1-1/N, independent of the specific family chosen. The minimum shared randomness to message size ratio needed is D/(N-1), and for balanced linear schemes the subpacketization level is (N-1)/gcd(D,N-1). These results are shown via a converse that works for arbitrary families and a single achievable scheme that applies to all families uniformly. This matters because it reveals that limiting the possible requests does not improve the fundamental efficiency limits in this privacy and security model.

Core claim

In SPSSR, for every candidate demand family, the maximum achievable retrieval rate equals 1-1/N. The minimum ratio of shared randomness size to message size to achieve this rate is D/(N-1). For balanced linear SPSSR schemes, the minimum required subpacketization level is (N-1)/gcd(D,N-1). Both the randomness ratio and subpacketization level are independent of the demand family. A single scheme achieves these bounds for every family.

What carries the argument

A uniform SPSSR scheme that works for any demand family and attains the optimal rate using shared randomness across non-colluding servers.

If this is right

The rate upper bound holds even for restricted demand families, not just the complete set of all size-D subsets.
One scheme suffices to achieve optimality no matter which family of subsets is considered.
The communication and storage overheads remain the same even when the user has fewer possible demands.
The construction improves subpacketization over known SMPIR schemes in some parameter regimes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Restricting the demand family does not yield better rates, suggesting the privacy constraint dominates.
The gcd-based subpacketization formula could reduce overhead in implementations with particular values of D and N.
The uniform scheme might simplify system design when the exact demand family is not known in advance.

Load-bearing premise

The N servers do not collude and the shared randomness is completely unknown to the user.

What would settle it

Demonstrating a scheme for some specific demand family that achieves a retrieval rate strictly greater than 1-1/N while preserving privacy from servers and security for the user would falsify the result.

read the original abstract

This work introduces the \emph{Secure and Private Structured-Subset Retrieval (SPSSR)} problem. In SPSSR, a user wishes to retrieve one subset from an arbitrary family of size-$D$ subsets from $K$ messages replicated across $N$ non-colluding servers that share randomness unknown to the user. The privacy requirement ensures that no server learns which subset is requested, while the security requirement ensures that the user learns nothing about the messages outside the requested subset. This generalizes Symmetric Multi-message Private Information Retrieval (SMPIR), where the candidate demand sets consist of all size-$D$ subsets. We show that, for every candidate demand family, the maximum achievable retrieval rate is equal to ${1-1/N}$. We also show that the minimum ratio between the size of the shared randomness and the message size required to achieve this rate is ${D/(N-1)}$, and that, for balanced linear SPSSR schemes, the minimum required subpacketization level is ${(N-1)/\gcd(D,N-1)}$; both quantities are independent of the demand family. Our converse proof for the maximum achievable retrieval rate applies to arbitrary demand families, unlike the existing proof for SMPIR, which is tailored to the full demand family. For achievability, we construct a single SPSSR scheme that applies uniformly to every demand family, achieves the optimal retrieval rate with the optimal shared-randomness ratio, and requires the optimal subpacketization level among balanced linear schemes. This subpacketization level is no larger than that of known SMPIR schemes in any parameter regime and is smaller in some regimes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a general converse for arbitrary demand families in structured subset retrieval plus one scheme that hits the optimal rate, randomness ratio, and subpacketization uniformly.

read the letter

The main thing to know is that the authors extend symmetric multi-message PIR to arbitrary families of D-subsets while proving a retrieval rate upper bound of 1-1/N that does not depend on the family being complete. They then give a single linear scheme that meets this rate, uses shared randomness of size D/(N-1) times the message size, and requires subpacketization (N-1)/gcd(D,N-1) for balanced cases, all independent of the specific family. That uniformity is the practical payoff. The converse being family-agnostic is a clear step beyond the SMPIR literature, which tailored its argument to the full set of subsets. The scheme also matches or beats known SMPIR subpacketization in the regimes they compare. The assumptions are the usual ones: non-colluding servers and shared randomness unknown to the user. If either fails the guarantees disappear, but that is standard for this line of work. The main limitation is that the abstract only states the existence of the proofs and construction; without the derivations it is hard to check for any looseness in the information-theoretic steps or whether the linear scheme handles every edge case cleanly. Still, the stated bounds look tight and the generalization is honest. This is for people working on information-theoretic PIR and restricted-access storage. A reader who cares about general query families or wants a single scheme that works across them will get direct value from the bounds and construction. It has enough substance to deserve a serious referee.

Referee Report

0 major / 2 minor

Summary. The manuscript introduces the Secure and Private Structured-Subset Retrieval (SPSSR) problem, generalizing Symmetric Multi-message Private Information Retrieval (SMPIR) to arbitrary families of D-subsets drawn from K messages replicated across N non-colluding servers that share randomness unknown to the user. It claims that the maximum achievable retrieval rate is 1-1/N for every candidate demand family, that the minimum shared-randomness-to-message-size ratio needed to attain this rate is D/(N-1), and that balanced linear SPSSR schemes require minimum subpacketization (N-1)/gcd(D,N-1). A converse proof applicable to arbitrary families and a single uniform linear construction achieving all three bounds are presented.

Significance. If the stated bounds and construction hold, the work supplies tight, family-independent information-theoretic limits for a broad class of private retrieval problems. The uniformity of the optimal parameters across all demand families of size D is a notable technical feature that simplifies scheme design relative to family-specific approaches and strengthens the generalization from SMPIR. The general converse, which does not rely on the demand family being the complete set of D-subsets, constitutes a clear advance over prior tailored arguments.

minor comments (2)

The term 'balanced linear SPSSR schemes' is used in the abstract and main claims without an explicit definition or reference to its precise meaning (e.g., whether it requires equal subpacket sizes across servers or a specific linearity condition); adding a short clarifying sentence or pointer to the relevant section would aid readability.
A small concrete example (e.g., N=3, D=2, K=4) illustrating how the uniform construction satisfies both privacy and security for a non-complete demand family would help readers verify the claimed independence from the specific family.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review and recommendation of minor revision. The referee's summary correctly captures the key contributions: the family-independent retrieval rate of 1-1/N, the shared-randomness ratio D/(N-1), and the subpacketization level (N-1)/gcd(D,N-1) for balanced linear schemes, along with the general converse and uniform construction.

Circularity Check

0 steps flagged

No significant circularity; bounds derived from standard information-theoretic arguments on the problem definition

full rationale

The paper establishes a general converse showing retrieval rate ≤ 1-1/N for arbitrary demand families of size D using standard mutual-information arguments on the non-colluding servers and shared randomness unknown to the user. Achievability is provided by an explicit single linear construction that simultaneously meets the rate, the shared-randomness ratio D/(N-1), and the subpacketization (N-1)/gcd(D,N-1) uniformly across all families. No equation reduces the claimed quantities to parameters defined by the result itself, no self-citation chain is load-bearing for the central claims, and the converse is stated to be independent of the specific family (unlike prior SMPIR proofs). The derivation is therefore self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the standard PIR modeling assumptions of non-colluding servers and private shared randomness; no new entities are postulated and no parameters are fitted to data.

axioms (1)

domain assumption The N servers are non-colluding and share randomness unknown to the user.
Explicitly stated in the problem definition in the abstract.

pith-pipeline@v0.9.0 · 5596 in / 1248 out tokens · 42307 ms · 2026-05-13T07:34:19.406787+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages · 1 internal anchor

[1]

The Capacity of Private Information Retrieval,

H. Sun and S. A. Jafar, “The Capacity of Private Information Retrieval,” IEEE Transactions on Information Theory, vol. 63, no. 7, pp. 4075– 4088, July 2017

work page 2017
[2]

Optimal Download Cost of Private Information Retrieval for Arbitrary Message Length,

——, “Optimal Download Cost of Private Information Retrieval for Arbitrary Message Length,”IEEE Transactions on Information F orensics and Security, vol. 12, no. 12, pp. 2920–2932, 2017

work page 2017
[3]

Multiround Private Information Retrieval: Capacity and Storage Overhead,

——, “Multiround Private Information Retrieval: Capacity and Storage Overhead,”IEEE Transactions on Information Theory, vol. 64, no. 8, pp. 5743–5754, 2018

work page 2018
[4]

Capacity-Achieving Private Information Retrieval Codes with Optimal Message Size and Upload Cost,

C. Tian, H. Sun, and J. Chen, “Capacity-Achieving Private Information Retrieval Codes with Optimal Message Size and Upload Cost,”IEEE Transactions on Information Theory, vol. 65, no. 11, pp. 7613–7627, 2019

work page 2019
[5]

Semantic Private Information Retrieval,

S. Vithana, K. Banawan, and S. Ulukus, “Semantic Private Information Retrieval,”IEEE Transactions on Information Theory, vol. 68, no. 4, pp. 2635–2652, 2022

work page 2022
[6]

Private Information Retrieval and Its Extensions: An Introduction, Open Problems, Future Directions,

S. Vithana, Z. Wang, and S. Ulukus, “Private Information Retrieval and Its Extensions: An Introduction, Open Problems, Future Directions,” IEEE BITS the Information Theory Magazine, vol. 3, no. 4, pp. 67– 85, 2023. 8

work page 2023
[7]

Private Retrieval, Computing, and Learning: Recent Progress and Future Challenges,

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 Communi- cations, vol. 40, no. 3, pp. 729–748, 2022

work page 2022
[8]

The Capacity of Symmetric Private Information Retrieval,

H. Sun and S. A. Jafar, “The Capacity of Symmetric Private Information Retrieval,”IEEE Transactions on Information Theory, vol. 65, no. 1, pp. 322–329, 2019

work page 2019
[9]

Symmetric Private Information Retrieval with User-Side Common Randomness,

Z. Wang and S. Ulukus, “Symmetric Private Information Retrieval with User-Side Common Randomness,” in2021 IEEE International Symposium on Information Theory (ISIT), 2021, pp. 2119–2124

work page 2021
[10]

Multi-Message Private Information Re- trieval: Capacity Results and Near-Optimal Schemes,

K. Banawan and S. Ulukus, “Multi-Message Private Information Re- trieval: Capacity Results and Near-Optimal Schemes,”IEEE Transac- tions on Information Theory, vol. 64, no. 10, pp. 6842–6862, Oct 2018

work page 2018
[11]

Multi-Message Private Information Retrieval: A Scalar Linear Solution,

N. Wang, A. Heidarzadeh, and A. Sprintson, “Multi-Message Private Information Retrieval: A Scalar Linear Solution,” in2022 58th Annual Allerton Conference on Communication, Control, and Computing (Aller- ton), 2022

work page 2022
[12]

A Linear Programming Approach to Private Information Retrieval,

A. Heidarzadeh, N. Wang, and A. Sprintson, “A Linear Programming Approach to Private Information Retrieval,” in2025 IEEE International Symposium on Information Theory (ISIT), 2025, pp. 1–6

work page 2025
[13]

A Low-Complexity Scheme for Multi-Message Private Information Retrieval,

N. Wang, A. Heidarzadeh, and A. Sprintson, “A Low-Complexity Scheme for Multi-Message Private Information Retrieval,” in2025 59th Annual Conference on Information Sciences and Systems (CISS), 2025

work page 2025
[14]

Leaky Multi- Message Private Information Retrieval with Differential Privacy Guar- antees,

A. Heidarzadeh, W. Zhao, C. Tian, and A. Sprintson, “Leaky Multi- Message Private Information Retrieval with Differential Privacy Guar- antees,” in2025 61st Allerton Conference on Communication, Control, and Computing Proceedings, 2025

work page 2025
[15]

Private Set Intersection: A Multi- Message Symmetric Private Information Retrieval Perspective,

Z. Wang, K. Banawan, and S. Ulukus, “Private Set Intersection: A Multi- Message Symmetric Private Information Retrieval Perspective,”IEEE Transactions on Information Theory, vol. 68, no. 3, pp. 2001–2019, 2022

work page 2001
[16]

Private Structured-Subset Retrieval

M. Issa and A. Heidarzadeh, “Private Structured-Subset Retrieval,” May 2026. [Online]. Available: https://arxiv.org/abs/2605.05160

work page internal anchor Pith review Pith/arXiv arXiv 2026
[17]

On the Subpacketization Level of the Banawan- Ulukus Multi-Message PIR Scheme,

A. Heidarzadeh, “On the Subpacketization Level of the Banawan- Ulukus Multi-Message PIR Scheme,” 2026. [Online]. Available: https://arxiv.org/abs/2602.09417

work page arXiv 2026
[18]

Single- Server Multi-Message Individually-Private Information Retrieval with Side Information,

A. Heidarzadeh, S. Kadhe, S. E. Rouayheb, and A. Sprintson, “Single- Server Multi-Message Individually-Private Information Retrieval with Side Information,” inIEEE International Symposium on Information Theory, July 2019, pp. 1042–1046

work page 2019
[19]

Single-Server Individually-Private Information Retrieval: A Combinatorial Approach,

A. Heidarzadeh and A. Sprintson, “Single-Server Individually-Private Information Retrieval: A Combinatorial Approach,” inIEEE Information Theory Workshop, 2021

work page 2021
[20]

The Linear Capacity of Single-Server Individually-Private Infor- mation Retrieval with Side Information,

——, “The Linear Capacity of Single-Server Individually-Private Infor- mation Retrieval with Side Information,” in2022 IEEE International Symposium on Information Theory (ISIT), 2022, pp. 2833–2838

work page 2022
[21]

Private Information Retrieval with Side Information,

S. Kadhe, B. Garcia, A. Heidarzadeh, S. El Rouayheb, and A. Sprintson, “Private Information Retrieval with Side Information,”IEEE Transac- tions on Information Theory, vol. 66, no. 4, pp. 2032–2043, 2020

work page 2032
[22]

Private Information Retrieval with Side Information: The Single Server Case,

S. Kadhe, B. Garcia, A. Heidarzadeh, S. E. Rouayheb, and A. Sprintson, “Private Information Retrieval with Side Information: The Single Server Case,” in55th Annual Allerton Conf. on Commun., Control, and Com- puting, Oct 2017, pp. 1099–1106

work page 2017
[23]

On the Capacity of Single-Server Multi-Message Private Information Retrieval with Side Information,

A. Heidarzadeh, S. Kadhe, B. Garcia, S. E. Rouayheb, and A. Sprintson, “On the Capacity of Single-Server Multi-Message Private Information Retrieval with Side Information,” in56th Annual Allerton Conf. on Commun., Control, and Computing, Oct 2018

work page 2018
[24]

Multi- Message Private Information Retrieval with Private Side Information,

S. P. Shariatpanahi, M. J. Siavoshani, and M. A. Maddah-Ali, “Multi- Message Private Information Retrieval with Private Side Information,” inIEEE Information Theory Workshop, 2018

work page 2018
[25]

Single-Server Multi-Message Private Information Retrieval with Side Information,

S. Li and M. Gastpar, “Single-Server Multi-Message Private Information Retrieval with Side Information,” in56th Annual Allerton Conf. on Commun., Control, and Computing, Oct 2018

work page 2018
[26]

Capacity of Single- Server Single-Message Private Information Retrieval with Coded Side Information,

A. Heidarzadeh, F. Kazemi, and A. Sprintson, “Capacity of Single- Server Single-Message Private Information Retrieval with Coded Side Information,” inIEEE Information Theory Workshop, Nov 2018

work page 2018
[27]

The Role of Coded Side Information in Single-Server Private In- formation Retrieval,

——, “The Role of Coded Side Information in Single-Server Private In- formation Retrieval,”IEEE Transactions on Information Theory, vol. 67, no. 1, pp. 25–44, 2021

work page 2021
[28]

Capacity of Single-Server Single-Message Private Information Retrieval with Private Coded Side Information,

——, “Capacity of Single-Server Single-Message Private Information Retrieval with Private Coded Side Information,” inIEEE International Symposium on Information Theory, July 2019, pp. 1662–1666

work page 2019
[29]

Multi- Server Private Information Retrieval with Coded Side Information,

F. Kazemi, E. Karimi, A. Heidarzadeh, and A. Sprintson, “Multi- Server Private Information Retrieval with Coded Side Information,” in Canadian Workshop on Information Theory, 2019

work page 2019
[30]

Private Information Retrieval with Private Coded Side Informa- tion: The Multi-Server Case,

——, “Private Information Retrieval with Private Coded Side Informa- tion: The Multi-Server Case,” in57th Annual Allerton Conference on Communication, Control, and Computing, 2019, pp. 1098–1104

work page 2019
[31]

A New Approach to Har- nessing Side Information in Multi-Server Private Information Retrieval,

N. Wang, A. Heidarzadeh, and A. Sprintson, “A New Approach to Har- nessing Side Information in Multi-Server Private Information Retrieval,” in2024 IEEE International Symposium on Information Theory (ISIT), 2024, pp. 2646–2651

work page 2024
[32]

Achieving Capacity of PIR with Private Side Information with Low Sub-packetization and without MDS Codes,

L. Erhili and A. Heidarzadeh, “Achieving Capacity of PIR with Private Side Information with Low Sub-packetization and without MDS Codes,” in2024 IEEE International Symposium on Information Theory (ISIT), 2024, pp. 2652–2657

work page 2024
[33]

The Capacity of Robust Private Information Retrieval with Colluding Databases,

H. Sun and S. A. Jafar, “The Capacity of Robust Private Information Retrieval with Colluding Databases,”IEEE Transactions on Information Theory, vol. 64, no. 4, pp. 2361–2370, 2018

work page 2018
[34]

The Capacity of Private Information Retrieval from Byzantine and Colluding Databases,

K. Banawan and S. Ulukus, “The Capacity of Private Information Retrieval from Byzantine and Colluding Databases,”IEEE Transactions on Information Theory, vol. 65, no. 2, pp. 1206–1219, 2019

work page 2019
[35]

The Optimal Sub-Packetization of Linear Capacity- Achieving PIR Schemes with Colluding Servers,

Z. Zhang and J. Xu, “The Optimal Sub-Packetization of Linear Capacity- Achieving PIR Schemes with Colluding Servers,”IEEE Transactions on Information Theory, vol. 65, no. 5, pp. 2723–2735, 2019

work page 2019
[36]

Secure Symmetric Private Information Retrieval from Colluding Databases with Adversaries,

Q. Wang and M. Skoglund, “Secure Symmetric Private Information Retrieval from Colluding Databases with Adversaries,” in2017 55th An- nual Allerton Conference on Communication, Control, and Computing (Allerton), 2017, pp. 1083–1090. 9

work page 2017