Functional Converses for Private Matrix-Product Retrieval under Library-Wide Decoder-Side Correlation
Abstract
We consider private retrieval of the matrix product A⊤ B(θ) from replicated Pc-colluding servers when B(ℓ)=A+N(ℓ), with the innovations mutually independent and independent of the user-held A∈𝔽qm× m. The servers store the full library, correlated with A, which changes both the communication problem and the security definition: a secrecy condition including the stored library cannot hold, as the library itself partly reveals A. We therefore measure only additional leakage and require index privacy conditioned on A; both reduce to classical notions under independence. For A of rank k<m we prove, with no structural hypothesis on the map, D*≥ H(A⊤ B(θ)| A)/CPIR(N,Pc,L)−o(km), where CPIR(N,Pc,L) is the replicated Pc-colluding private-information-retrieval capacity. The proof rests on a colluding converse for servers storing arbitrary refinements of the demanded messages, whose answers need not be measurable functions of the functional-message library, and a privacy-transfer characterization. Publishing a canonical row-space representative makes the bound achievable for arbitrary independent and identically distributed innovations under a public-setup measure. Under a strengthened observational model (exact correctness, common conditional library support, and full-transcript security), concealment forces D≥ H(Gm N(θ))/CPIR, where Gm spans the linear join of all row spaces in the support of the operand distribution; this extends to vanishing error under a simultaneous-decodability assumption. In the full-rank case product recovery reduces to innovation recovery: D*=H(N(θ))/CPIR+o(m2).
Related
- The Capacity of Private Information Retrieval from Coded Storage Systems with Colluding, Robust and Byzantine Servers
- Weak Private Information Retrieval for Graph-based Storage under ε-privacy
- Quantum Private Information Retrieval on Forests
- Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results
- Local Private Information Retrieval for Graph-Based Replicated Systems
BibTeX
@misc{aliasgari2026functional,
title = {{Functional Converses for Private Matrix-Product Retrieval under Library-Wide Decoder-Side Correlation}},
author = {Malihe Aliasgari and Yousef Nejatbakhsh},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07325},
eprint = {2611.07325},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07325},
}
RIS
TY - UNPB
TI - Functional Converses for Private Matrix-Product Retrieval under Library-Wide Decoder-Side Correlation
AU - Malihe Aliasgari
AU - Yousef Nejatbakhsh
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07325
UR - https://arxiv.org/abs/2611.07325
AB - We consider private retrieval of the matrix product A^⊤ B^(θ) from replicated P_c-colluding servers when B^(ℓ)=A+N^(ℓ), with the innovations mutually independent and independent of the user-held A∈𝔽_q^m× m. The servers store the full library, correlated with A, which changes both the communication problem and the security definition: a secrecy condition including the stored library cannot hold, as the library itself partly reveals A. We therefore measure only additional leakage and require index privacy conditioned on A; both reduce to classical notions under independence. For A of rank k<m we prove, with no structural hypothesis on the map, D^*≥ H(A^⊤ B^(θ)| A)/C_PIR(N,P_c,L)−o(km), where C_PIR(N,P_c,L) is the replicated P_c-colluding private-information-retrieval capacity. The proof rests on a colluding converse for servers storing arbitrary refinements of the demanded messages, whose answers need not be measurable functions of the functional-message library, and a privacy-transfer characterization. Publishing a canonical row-space representative makes the bound achievable for arbitrary independent and identically distributed innovations under a public-setup measure. Under a strengthened observational model (exact correctness, common conditional library support, and full-transcript security), concealment forces D≥ H(G_m N^(θ))/C_PIR, where G_m spans the linear join of all row spaces in the support of the operand distribution; this extends to vanishing error under a simultaneous-decodability assumption. In the full-rank case product recovery reduces to innovation recovery: D^*=H(N^(θ))/C_PIR+o(m^2).
ER -