← 研踪 PaperTrailarXiv:2611.07325 · v1
Functional Converses for Private Matrix-Product Retrieval under Library-Wide Decoder-Side Correlation
首次提交 2026-11-05 10:10
版本更新 2026-11-05 10:10
雷达观测 2026-11-06 10:04
摘要
We consider private retrieval of the matrix product $A^\top B^{(θ)}$ from replicated $P_c$-colluding servers when $B^{(\ell)}=A+N^{(\ell)}$, with the innovations mutually independent and independent of the user-held $A\in\mathbb{F}_q^{m\times 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^*\geq H(A^\top B^{(θ)}\mid A)/C_{\mathrm{PIR}}(N,P_c,L)-o(km)$, where $C_{\mathrm{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\geq H(G_m N^{(θ)})/C_{\mathrm{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_{\mathrm{PIR}}+o(m^2)$.
作者备注：36 pages, 4 tables
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-05 10:10 · 最新观测版本
Functional Converses for Private Matrix-Product Retrieval under Library-Wide Decoder-Side Correlation
We consider private retrieval of the matrix product $A^\top B^{(θ)}$ from replicated $P_c$-colluding servers when $B^{(\ell)}=A+N^{(\ell)}$, with the innovations mutually independent and independent of the user-held $A\in\mathbb{F}_q^{m\times 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^*\geq H(A^\top B^{(θ)}\mid A)/C_{\mathrm{PIR}}(N,P_c,L)-o(km)$, where $C_{\mathrm{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\geq H(G_m N^{(θ)})/C_{\mathrm{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_{\mathrm{PIR}}+o(m^2)$.
查看此版本解读 →查看此版本原文 ↗