pith. machine review for the scientific record. sign in

arxiv: 2605.05169 · v2 · submitted 2026-05-06 · 💻 cs.IT · math.IT

Recognition: unknown

Private Contiguous-Block Retrieval

Maha Issa , Anoosheh Heidarzadeh
Authors on Pith no claims yet

Pith reviewed 2026-05-08 15:50 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords private contiguous-block retrievalprivate information retrievalsubpacketization levelretrieval ratelinear schemescontiguous blocksmulti-server PIRinformation theoretic privacy
0
0 comments X

The pith

A scheme for private contiguous-block retrieval achieves optimal rate with subpacketization matching the derived lower bound over broad parameters.

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

The paper introduces Private Contiguous-Block Retrieval, in which a user downloads a contiguous block of D messages chosen from K total messages replicated across N non-colluding servers while keeping the block identity hidden from every server. This models ordered data in storage and streaming applications. For the class of balanced {0,1}-linear schemes the authors prove an upper bound on retrieval rate, a lower bound on the subpacketization level needed to reach that rate, and an explicit construction attaining both bounds for many parameter values. The achievable rate equals the best known upper bound from general multi-message PIR, yet the new construction requires substantially smaller subpacketization by using the contiguity constraint. A reader would care because the result shows that restricting the demand set to contiguous blocks can improve a key efficiency metric without sacrificing rate.

Core claim

The paper establishes an upper bound on the achievable retrieval rate for all problem parameters under balanced {0,1}-linear schemes. It derives a lower bound on the subpacketization level required by any scheme that meets this rate upper bound. It then constructs a rate-optimal scheme whose subpacketization level exactly matches the lower bound for a broad range of parameters. Although the optimal rate coincides with the best-known converse bound for unrestricted multi-message PIR, the construction exploits the contiguous-block structure to achieve that rate with far less subpacketization than existing MPIR schemes.

What carries the argument

The explicit rate-optimal balanced {0,1}-linear scheme that exploits contiguous demands to meet both the rate upper bound and the subpacketization lower bound simultaneously.

If this is right

  • The retrieval rate is bounded from above for every parameter set in the balanced linear class.
  • Any rate-optimal scheme in this class must meet the derived subpacketization lower bound.
  • Explicit constructions exist that simultaneously attain the rate upper bound and the subpacketization lower bound for many N, K, D.
  • General multi-message PIR schemes can require larger subpacketization even when they achieve the same rate that PCBR admits.

Where Pith is reading between the lines

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

  • Restricting the demand family to contiguous blocks can improve subpacketization without changing the optimal rate.
  • Whether non-linear or unbalanced schemes can further reduce subpacketization remains open.
  • Storage and streaming systems that access data sequentially could adopt the construction to lower communication cost while preserving privacy.

Load-bearing premise

The analysis and construction apply only inside the class of balanced {0,1}-linear schemes.

What would settle it

For concrete parameters such as N=4, K=6, D=3, exhibit a balanced {0,1}-linear scheme that achieves the claimed rate upper bound yet uses subpacketization strictly below the paper's lower bound.

read the original abstract

We introduce the \emph{Private Contiguous-Block Retrieval (PCBR)} problem, where a user retrieves a block of $D$ messages with contiguous indices from $K$ replicated messages stored across $N$ non-colluding servers, while hiding the identity of the requested block from each server. This problem is motivated by storage and streaming systems where files are split into ordered segments. Unlike multi-message Private Information Retrieval (MPIR), where any $D$-subset may be requested, PCBR restricts the demand family to contiguous blocks. This relaxation raises a natural question: Can this structure be exploited to improve retrieval efficiency? We answer this question for balanced $\{0,1\}$-linear schemes. We establish an upper bound on the achievable retrieval rate for all problem parameters, derive a lower bound on the subpacketization level required by any scheme achieving the rate upper bound, and construct a rate-optimal scheme whose subpacketization level matches the lower bound for a broad range of problem parameters. Although the optimal PCBR rate coincides with the best-known MPIR rate converse bound, existing MPIR schemes can be suboptimal for PCBR and can require a much larger subpacketization level. In contrast, our scheme exploits the contiguous-block structure to achieve the optimal rate with reduced subpacketization.

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.

Referee Report

0 major / 3 minor

Summary. The paper introduces the Private Contiguous-Block Retrieval (PCBR) problem, a structured variant of multi-message PIR in which the user retrieves a block of D contiguous messages from K replicated messages stored across N non-colluding servers while concealing the block's starting index. Restricting attention to balanced {0,1}-linear schemes, the authors derive a rate upper bound that holds for all parameters, a matching lower bound on the subpacketization level required to achieve this rate, and an explicit construction that simultaneously meets the rate upper bound and the subpacketization lower bound for a broad range of parameters. They observe that the optimal PCBR rate equals the best-known MPIR converse bound, yet existing MPIR schemes are often suboptimal for PCBR in subpacketization cost; the new construction exploits the contiguous-block structure to reduce subpacketization.

Significance. If the stated bounds and construction are correct, the work demonstrates that the contiguous-block restriction can be leveraged to obtain private retrieval schemes with substantially lower subpacketization than general MPIR while preserving the same rate. This is practically relevant for ordered-data applications such as distributed video streaming. The explicit matching of rate and subpacketization bounds inside the balanced {0,1}-linear class, together with a concrete construction, constitutes a solid technical contribution; the authors correctly limit optimality claims to this class and do not assert results outside it.

minor comments (3)
  1. [Abstract] Abstract: the phrase 'a broad range of problem parameters' for which the construction matches the bounds is left unspecified; stating the precise conditions on K, N, D (e.g., in terms of divisibility or inequalities) already in the abstract would improve immediate readability.
  2. [§2] §2 (Definitions): the formal definition of a 'balanced {0,1}-linear scheme' should be accompanied by an explicit equation or matrix representation that makes the balance and {0,1} constraints unambiguous before the rate and subpacketization analyses begin.
  3. [Introduction / Abstract] The comparison paragraph in the abstract and introduction asserts that 'existing MPIR schemes can be suboptimal for PCBR and can require a much larger subpacketization level'; a single concrete numerical example (with specific K, N, D values) illustrating the subpacketization gap would strengthen this claim without lengthening the text.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and constructive review of our manuscript on Private Contiguous-Block Retrieval. We appreciate the recognition of the practical relevance for ordered-data applications and the technical contribution of matching rate and subpacketization bounds within the balanced {0,1}-linear class. The recommendation for minor revision is noted.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation begins from the newly defined PCBR demand family (contiguous blocks only) and the restriction to balanced {0,1}-linear schemes. The rate upper bound is obtained directly from the problem constraints and information-theoretic arguments on this family; the subpacketization lower bound follows from the same constraints; and the matching construction is exhibited explicitly for the stated parameter range. No step equates a claimed result to a fitted parameter, renames a prior result, or reduces the central claim to a self-citation chain. The paper explicitly limits its optimality statements to the considered class and contrasts its subpacketization with existing MPIR schemes without relying on unverified self-references for the core bounds.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard assumptions of linear coding over finite fields and non-colluding servers; no free parameters or invented entities are introduced beyond the new problem definition.

axioms (2)
  • domain assumption Schemes are balanced {0,1}-linear
    Explicitly stated restriction on the class of schemes considered for the bounds and construction.
  • standard math Servers are non-colluding
    Standard assumption in multi-server PIR models.

pith-pipeline@v0.9.0 · 5522 in / 1196 out tokens · 32701 ms · 2026-05-08T15:50:26.283725+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

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

  1. Private Structured-Subset Retrieval

    cs.IT 2026-05 unverdicted novelty 6.0

    PSSR generalizes PIR and MPIR by restricting demands to structured D-subsets, yielding tighter converse bounds and higher achievable rates via an optimization framework for many families.

  2. Private Structured-Subset Retrieval

    cs.IT 2026-05 unverdicted novelty 6.0

    PSSR generalizes MPIR to structured demand families, derives converse bounds on rate and subpacketization, and provides an optimization framework that recovers known MPIR schemes while improving on them for restricted...

Reference graph

Works this paper leans on

14 extracted references · 2 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [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

    2017

  2. [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

    2017

  3. [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

    2018

  4. [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

    2019

  5. [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

    2022

  6. [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

    2023

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

    2022

  8. [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

    2018

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

    2022

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

    2025

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

    2025

  12. [12]

    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

    2025

  13. [13]

    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

  14. [14]

    Private Structured-Subset Retrieval

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

    work page internal anchor Pith review Pith/arXiv arXiv 2026