arxiv: 2605.05160 · v3 · submitted 2026-05-06 · 💻 cs.IT · math.IT

Recognition: no theorem link

Private Structured-Subset Retrieval

Maha Issa , Anoosheh Heidarzadeh

Authors on Pith no claims yet

Pith reviewed 2026-05-12 03:49 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords Private Structured-Subset RetrievalMulti-message Private Information RetrievalBalanced linear schemesSubpacketizationConverse boundsOptimization frameworkStructured demand families

0 comments

The pith

Restricting the user's possible demands to a known structured family allows private multi-message retrieval at higher rates or with smaller subpacketization than the unrestricted case.

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

The paper establishes that when the sets of messages a user might request are confined to a known structured collection, it becomes possible to design private retrieval schemes that outperform those built for completely arbitrary demands. Working within the class of balanced schemes that use only zero and one coefficients, the authors obtain upper bounds on the highest achievable retrieval rate and lower bounds on the storage expansion required to reach any given rate. They supply an optimization procedure that builds suitable schemes for any chosen demand family and that automatically improves performance once the family is smaller than the full set of combinations. This matters because many practical retrieval tasks have natural restrictions on which message groups are requested together, so the extra knowledge can be turned into lower communication and storage costs while privacy is preserved.

Core claim

The authors formulate the Private Structured-Subset Retrieval problem in which a user retrieves D messages from K messages replicated across N non-colluding servers and the demand is known to belong to a prescribed structured family of D-subsets. For the class of balanced {0,1}-linear schemes they derive converse bounds on the maximum retrieval rate and on the minimum subpacketization needed for any target rate. They also present an optimization framework that constructs such schemes for an arbitrary structured family, recovering the best known balanced linear multi-message PIR constructions when the family is the complete set and strictly improving rate or subpacketization when the familyis

What carries the argument

The optimization-based framework that constructs balanced {0,1}-linear retrieval schemes for any given structured demand family, allowing explicit trade-offs between retrieval rate and subpacketization level.

If this is right

When the demand family is the complete set of all D-subsets the framework reproduces the strongest known balanced linear multi-message PIR constructions.
For any proper subset family the same framework produces at least one scheme whose retrieval rate exceeds the multi-message PIR rate or whose subpacketization is smaller than the multi-message PIR subpacketization for identical N, K, D.
The derived converse bounds give the highest rate attainable by any balanced {0,1}-linear scheme at a prescribed subpacketization level.
The framework extends without modification to contiguous-demand families and yields rate-optimal schemes that impose no field-size restrictions.

Where Pith is reading between the lines

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

Applications whose natural queries consist of contiguous blocks or other correlated groups could adopt the structured schemes to reduce communication and storage while keeping the same privacy guarantee.
The bounds obtained here provide concrete targets that future nonlinear or multi-round protocols could attempt to beat for the same structured families.
The optimization method can be applied to other families with combinatorial structure, such as fixed-weight or geometrically constrained subsets, to quantify possible further gains.

Load-bearing premise

The user's demand is known in advance to belong to a fixed structured family of D-subsets rather than ranging over all possible D-subsets.

What would settle it

A specific structured family of D-subsets and concrete values of N, K, D for which every balanced {0,1}-linear scheme achieves no higher retrieval rate and no smaller subpacketization than the best known multi-message PIR scheme for the same parameters.

read the original abstract

We introduce the \emph{Private Structured-Subset Retrieval (PSSR)} problem, where a user retrieves $D$ messages from a database of $K$ messages replicated across $N$ non-colluding servers, and the demand is restricted to a known structured family of $D$-subsets. This formulation generalizes Multi-message Private Information Retrieval (MPIR) and captures settings where the demand space is constrained by application-specific structure. Focusing on balanced ${\{0,1\}}$-linear schemes, a class that includes several best-known MPIR schemes, we derive converse bounds on the maximum retrieval rate and minimum subpacketization level required to achieve any given rate. We also develop an optimization-based framework to construct schemes for general structured demand families, providing flexibility in optimizing the retrieval rate or the subpacketization level. When specialized to the full demand family, this framework recovers known balanced $\{0,1\}$-linear MPIR constructions; for more restricted demand families, it can exploit the demand structure to increase the retrieval rate, reduce the subpacketization level, or both. We demonstrate this through a structured-demand example in which the proposed PSSR scheme simultaneously achieves a higher rate and requires a smaller subpacketization than the best-known MPIR scheme for the same parameters $N$, $K$, and $D$. Our parallel work on contiguous-demand families further illustrates the scope of this framework by yielding rate-optimal schemes with substantially smaller subpacketization and no field-size restrictions, improving upon MPIR-based schemes.

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

Restricting demands to structured families lets PSSR beat MPIR on rate and subpacketization in some cases via an optimization framework.

read the letter

The main takeaway is that this paper shows how restricting the user's possible demands to a structured family can lead to better private retrieval schemes than treating all demands equally, at least for certain linear schemes. They define the Private Structured-Subset Retrieval problem and focus on balanced {0,1}-linear schemes. The authors derive converse bounds for the maximum rate and minimum subpacketization needed. They also give an optimization framework to construct schemes for any given structured family. When the family is all possible demands, it matches known MPIR results. For a specific structured example, their scheme gets a higher rate and smaller subpacketization than the top MPIR scheme with the same N, K, D. The work does well by providing a general way to handle structure and by demonstrating an actual improvement in one case. The parallel results on contiguous demands suggest the approach can yield rate-optimal schemes with much less subpacketization and no field size limits. On the downside, the gains are illustrated with just one example, so it's not yet clear how broadly the structure helps or by how much. The optimization framework is described at a high level, and I'd want to see how practical it is to run for bigger problems. Since they limit to linear schemes, the converse bounds apply only there, which is fine but leaves room for better nonlinear schemes. This is targeted at people in the PIR and private retrieval community. Readers interested in extending MPIR to application-specific structures will find it relevant. It has enough substance with new bounds, a construction method, and a performance gain to merit a full peer review. I recommend sending it to referees. The central claims hold up based on the recovery of prior results and the example improvement.

Referee Report

0 major / 3 minor

Summary. The paper introduces the Private Structured-Subset Retrieval (PSSR) problem, a generalization of Multi-message Private Information Retrieval (MPIR) in which the user's demand is restricted to a known structured family of D-subsets drawn from a database of K messages replicated across N non-colluding servers. Focusing on balanced {0,1}-linear schemes, the authors derive converse bounds on the maximum retrieval rate and the minimum subpacketization level needed to achieve a given rate. They also present an optimization-based framework for constructing schemes that can exploit the demand structure to improve rate, reduce subpacketization, or both; the framework recovers known balanced {0,1}-linear MPIR schemes when the demand family is the full set of all D-subsets, and an explicit structured-demand example is given in which the PSSR scheme simultaneously exceeds the rate and lowers the subpacketization of the best-known MPIR scheme for the same N, K, D.

Significance. If the converse bounds are tight and the optimization framework produces valid, explicit schemes, the work offers a principled way to obtain efficiency gains over standard MPIR when application-specific structure is present in the demand set. The recovery of prior MPIR constructions as a special case and the concrete example of simultaneous rate and subpacketization improvement provide concrete evidence that the framework is not merely formal but can be instantiated to outperform existing schemes. These contributions are potentially useful for private retrieval in domains (e.g., contiguous or patterned queries) where the demand family is known a priori.

minor comments (3)

[Abstract] The abstract states that the PSSR scheme 'simultaneously achieves a higher rate and requires a smaller subpacketization than the best-known MPIR scheme for the same parameters N, K, and D,' but does not name the concrete values of N, K, D or the precise structure of the demand family. Adding these parameters (even parenthetically) would allow readers to immediately gauge the magnitude of the improvement.
The manuscript refers to 'our parallel work on contiguous-demand families' that yields rate-optimal schemes with smaller subpacketization. If this parallel manuscript is already public or submitted, a citation should be added; if it is not yet available, a brief parenthetical note clarifying its status would avoid reader confusion.
Notation for the structured demand family (e.g., how the family is formally denoted and how the optimization variables encode membership in the family) should be introduced with a short dedicated paragraph or table early in the technical development so that the subsequent optimization program is immediately readable.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our work on Private Structured-Subset Retrieval, as well as for recognizing its significance in generalizing MPIR, deriving converse bounds, and providing a flexible optimization framework that recovers known schemes and can outperform them under structured demands. The recommendation for minor revision is noted; we will make any necessary minor adjustments in the revised version.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper defines PSSR as a generalization of MPIR with structured demand families, derives information-theoretic converse bounds on rate and subpacketization for balanced {0,1}-linear schemes, and introduces an optimization framework for explicit constructions. Specializing the framework to the full demand family recovers prior MPIR schemes as a special case for validation, but the core results (converses and constructions) are developed independently from first principles and do not reduce to fitted inputs, self-definitions, or load-bearing self-citations. No equations or steps in the provided description equate outputs to inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The central claims rest on standard domain assumptions from PIR literature plus the new restriction to structured demand families; no free parameters or invented entities are explicitly introduced in the abstract.

axioms (3)

domain assumption N non-colluding servers hold replicas of the K-message database
Standard PIR setup stated in the abstract.
domain assumption Demand restricted to a known structured family of D-subsets
Core of the new PSSR problem definition.
domain assumption Schemes are balanced {0,1}-linear
Focus of the converse bounds and framework.

pith-pipeline@v0.9.0 · 5566 in / 1345 out tokens · 60018 ms · 2026-05-12T03:49:08.138355+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Secure and Private Structured-Subset Retrieval: Fundamental Limits and Achievable Schemes
cs.IT 2026-05 accept novelty 8.0

For any family of size-D subsets, the optimal SPSSR retrieval rate is 1-1/N, achieved with shared-randomness ratio D/(N-1) and subpacketization level (N-1)/gcd(D,N-1) for balanced linear schemes.
Secure and Private Structured-Subset Retrieval: Fundamental Limits and Achievable Schemes
cs.IT 2026-05 unverdicted novelty 7.0

For any demand family in SPSSR, the maximum retrieval rate is 1-1/N, achieved with shared-randomness ratio D/(N-1) and subpacketization (N-1)/gcd(D,N-1) for balanced linear schemes.
Private Contiguous-Block Retrieval
cs.IT 2026-05 unverdicted novelty 6.0

PCBR achieves the optimal MPIR retrieval rate with substantially lower subpacketization by restricting demands to contiguous blocks and constructing explicit balanced linear schemes.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · cited by 2 Pith papers · 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 Forensics 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

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]

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
[9]

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
[10]

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
[11]

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
[12]

Private Contiguous-Block Retrieval

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

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

The Asymptotic Capacity of Private Search,

Z. Chen, Z. Wang, and S. A. Jafar, “The Asymptotic Capacity of Private Search,”IEEE Transactions on Information Theory, vol. 66, no. 8, pp. 4709–4721, 2020

work page 2020
[14]

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
[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 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
[17]

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
[18]

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
[19]

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
[20]

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
[21]

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
[22]

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
[23]

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
[24]

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
[25]

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
[26]

The Capacity of T-Private Infor- mation Retrieval with Private Side Information,

Z. Chen, Z. Wang, and S. A. Jafar, “The Capacity of T-Private Infor- mation Retrieval with Private Side Information,”IEEE Transactions on Information Theory, vol. 66, no. 8, pp. 4761–4773, 2020

work page 2020
[27]

Converse for Multi-Server Single-Message PIR with Side Information,

S. Li and M. Gastpar, “Converse for Multi-Server Single-Message PIR with Side Information,” in54th Annual Conference on Information Sciences and Systems, 2020, pp. 1–6

work page 2020
[28]

On the Existence of XOR-Based Codes for Private Information Retrieval with Private Side Information,

M. Krishnan K. H. and J. Harshan, “On the Existence of XOR-Based Codes for Private Information Retrieval with Private Side Information,” Entropy, vol. 23, no. 10, 2021

work page 2021
[29]

On Single Server Private Information Retrieval With Private Coded Side Information,

Y . Lu and S. A. Jafar, “On Single Server Private Information Retrieval With Private Coded Side Information,”IEEE Transactions on Informa- tion Theory, vol. 69, no. 5, pp. 3263–3284, 2023

work page 2023
[30]

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
[31]

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
[32]

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
[33]

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
[34]

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. 16

work page 2022