CS Paper Radar

The Capacity of Private Information Retrieval from Coded Storage Systems with Colluding, Robust and Byzantine Servers

Rui Sun, Yiwei Zhang

cs.IT ·submitted 2026-10-27 15:30 UTC · v1

Abstract

We consider the problem of private information retrieval from MDS-coded databases with $T$ colluding servers, $U$ robust servers, and $B$ Byzantine servers, referred to as U-B-MDS-TPIR. In the U-B-MDS-TPIR setting, $M$ files are stored across $N$ servers, and in this paper each file is independently encoded using an $(N,K)$ GRS code. We characterize the capacity among linear, full support-rank U-B-MDS-TPIR schemes as $C=\frac{N-U-2B}{N-U}(1+\frac{K+T-1}{N-U-2B}+\cdots+(\frac{K+T-1}{N-U-2B})^{M-1})^{-1}$ when $N-U-2B\ge KT$. When $K=1$ or $T=1$, the same expression gives the capacity without the linearity and full support-rank restrictions. We further extend the construction to the retrieval of $P$ out of $M$ files. For $P \ge \frac{M}{2}$, the resulting multi-file scheme achieves capacity when $K=1$ or $T=1$.

Closest papers

Nearest neighbours by meaning across the whole index.

Bounds on the Service Rates of Linear Codes and their Connections to Combinatorial Designs

cs.IT ·2026-10-19 ·Monika Yadav, Priyanka Choudhary, Maheshanand Bhaintwal
theory similarity 0.64
Abstract

The service rate region of a distributed storage system describes the set of concurrent demand vectors that can be served without overloading any individual server, and is a fundamental measure of how effectively redundancy is used. In this paper, we investigate aggregate service rates in distributed data storage systems based on linear codes over arbitrary finite fields. We first derive an upper bound on the aggregate service rate for an arbitrary subset of $t$ data objects in terms of the dual distance and the sizes of their smallest recovery sets. For systematic generator matrices, this bound simplifies to an expression depending only on the code length, the dual distance, and the cardinality of the selected subset. This result extends existing bounds and provides a subset-wise formulation of the First Dual Distance Bound. We then establish conditions under which this upper bound is attained. We apply our results to several important families of linear codes, including MDS codes, Reed-Muller codes, constacyclic codes, and extended Golay codes, and obtain exact values of the maximum aggregate service rates for the corresponding subsets of data objects.

0.25

Doubly-Efficient Private Information Retrieval from Modular Forms

cs.CR math.NT ·2026-11-09 ·Alexandra Henzinger, Seyoon Ragavan
similarity 0.63
Abstract

We present new information-theoretic protocols for $s$-server, doubly-efficient private information retrieval (PIR) in sublinear server time and one extra bit of space on the servers, for every constant $s \geq 2$. On an $n$-bit database, each of the $s$ PIR servers first builds and stores a preprocessing data structure consisting of $n+1$ bits (which is unique to each server, and after which the server may discard the original database). Then, each server answers a PIR query in time $T_s(n)$, by reading at most $T_s$ bits of its data structure and sending them to the user. In the two server setting ($s=2$), our PIR protocols achieve $T_2 = n^{0.82}$, matching the server time of the state-of-the-art schemes of Henzinger and Ragavan (EUROCRYPT 2026) while shrinking their storage from $O(n\sqrt{\log n})$ to $n+1$ bits. With $s \geq 3$ servers, our PIR protocols retain the $n+1$ bits of storage and additionally improve on the server time of all prior information-theoretic $s$-server schemes with $n^{1+o(1)}$ storage: for example, achieving $T_3 = n^{0.74}$ and $T_{10} = n^{0.61}$ (previously $n^{0.79}$ and $n^{0.75}$). Asymptotically, as the server count $s$ grows, we shrink the number of servers required to achieve a given server-work exponent from $s^{3.9}$ to $s$. Our results draw inspiration from matching-vector techniques (Efremenko, STOC 2009), which we generalize to handle degree-two computations in the exponent. Using this generalization, we build doubly-efficient PIR from the new intermediate abstraction of Fourier-sparse cone-delta functions. Then, we construct such Fourier-sparse cone-delta functions via a connection to modular forms and complex analysis: if a Fourier-sparse cone-delta function does not exist, then there exists a modular form which has too many roots, contradicting the valence formula.

0.24

Optimal-Access Cooperative MSR Codes: Parity-Check Matrix Construction And a Unified Transformation

cs.IT ·2026-09-06 ·Yaqian Zhang, Jingke Xu, Ya-Feng Liu
theory similarity 0.61
Abstract

Cooperative MSR codes are a kind of storage codes which enable optimal-bandwidth repair of any $h\geq2$ node erasures in a cooperative way, while retaining the minimum storage as an $[n,k]$ MDS code. Each code coordinate (node) is assumed to store an array of $\ell$ symbols, where $\ell$ is termed as sub-packetization. To address the disk IO (input/output) capability, a cooperative MSR code is said to have optimal-access property, if during node repair, the amount of data accessed at each helper node meets a lower bound on this quantity. In this paper, we focus on reducing the sub-packetization level of optimal-access cooperative MSR codes. We propose new constructions of optimal-access cooperative MSR codes through two methods. At first, we propose a direct explicit construction by designing its parity-check matrix. Such parity-check matrix is built by repeatedly employing two crucial parity-check matrices as building blocks. Secondly, we propose a generic transformation framework. Starting from an arbitrary $[n+d-k,d]$ MDS scalar code, one can derive a final cooperative MSR code by systematically applying two basic transformations. Both approaches yield $(n,k,\ell=δ^m)$ optimal-access cooperative MSR codes with $δ=d-k+h$ and $m=\binom{n}{h}-\lfloor\frac{n}δ\rfloor(\binomδ{h}-1)$. Compared with the state of the art (with $\ell=δ^{\binom{n}{h}}$), the derived codes can reduce the sub-packetization $\ell$ by a fraction of $1/δ^{\lfloor\frac{n}δ\rfloor(\binomδ{h}-1)}$, where $δ=d-k+h$. Moreover, we also show that some previous code structures of optimal-access cooperative MSR codes and optimal-access MSR codes with $h=1$ are included as special cases of our transformation construction. At last, we note that all of the constructions are built over a finite field of linear size $\geq n+d-k$.

0.30

The Exact Memory-Rate Tradeoff for Three-User Secure Coded Caching

cs.IT ·2026-11-04 ·Han Fang, Nan Liu, Wei Kang
similarity 0.61
Abstract · 34 pages, 2 figures

We determine the exact zero-error memory-rate tradeoff for secure coded caching with three users and any number $N\ge2$ of independent files. Each user recovers its requested file, while its cache and the broadcast jointly reveal no information about the complete tuple of unrequested files. For $N\ge4$, two converse inequalities establish the optimality of the known achievable points and the memory-sharing segments between them. For $N=3$, two additional bounds identify a new corner at $(M,R)=(3/2,2)$, where memory and rate are measured in file units. An explicit linear code over $\mathbb{F}_3$ attains this corner and reduces the rate by one quarter of a file relative to memory sharing between the known points. The converse links the information held by cache pairs and triples to delivery under repeated and distinct requests. Its equality conditions guide the construction: users cancel the keys to recover their requested files, while uniform masking protects the complete tuple of unrequested files.

0.21

Order-Optimal Coded Caching With File and Demand Privacy

cs.IT ·2026-10-04 ·Han Fang, Nan Liu, Wei Kang
similarity 0.61
Abstract · 14 pages, 2 figures, 1 table

We study coded caching with joint file and demand privacy: each user recovers its requested file while learning nothing about the remaining files and the other users' requests jointly. Let $N$ and $K$ be the numbers of files and users, and let $M$ and $R$ denote the cache memory and delivery rate, both normalized by the file size. For every $N,K\ge2$ and every feasible cache size, we give a scheme whose worst-case delivery rate is at most $9/2$ times the optimum. To reduce the memory used for file shares, the scheme secret-shares $N-1$ differences relative to a reference file. Cached masks supply the correction needed to recover the requested file from its difference. For each integer $t\in\{0,\ldots,K-1\}$, the scheme achieves $M=1+(N-1)t/(K-t)$ and $R=K/(t+1)$. To lower-bound the delivery rate, we compare the joint cache entropy of user groups under alternative demand vectors, using one fixed user's privacy constraint. Two choices of groups determine the optimal delivery rate up to constants at the scale $\min\{K,1+(N-1)/(M-1)\}$ for $M>1$. At $M=1$, the exact optimum is $K$. A complementary bound on joint broadcast entropy gives the minimum memory for unit delivery rate, $1+(N-1)(K-1)$, and the exact tradeoff on an interval ending at that memory. All schemes and bounds apply to repeated as well as distinct requests.

0.59

Communication and Privacy Trade-Offs in Distributed Storage With Shared Secret Keys

cs.IT ·2026-10-29 ·Maryam Keshvari, Remi A. Chou
published similarity 0.61
Abstract · A preliminary version of this work was presented at the 2023 Allerton Conference on Communication, Control, and Computing

We study distributed storage over public communication channels where privacy is realized using shared secret keys. Specifically, a user wishes to store a file across $L$ servers such that any subset of at least $t$ servers can reconstruct the file, while any subset of at most $z$ colluding servers learns no more than a fraction $α$ of the file. Unlike classical secret-sharing models that assume secure communication channels between the user and each server, we consider a setting where all transmissions occur over a public channel and the user shares an individual secret key of length $n$ bits with each server. For a fixed key length $n$, we characterize the trade-off between the privacy leakage parameter $α$ and the maximum file size that can be securely stored. Additionally, we determine the minimum local randomness, public communication, and storage required to achieve this optimal trade-off.

0.27

Asymptotically unit-rate storage codes from binary BCH codes

cs.IT math.CO ·2026-10-01 ·Aryeh Lev Zabokritskiy
theory similarity 0.59
Abstract · 11 pages, no figures

A storage code on a graph assigns a symbol to each vertex so that the symbol can be recovered from its neighbors. We prove that the binary full-parity storage codes on triangle-free coset graphs of primitive BCH codes have rate tending to one for every fixed error-correction capability of at least two. The conclusion also holds for an increasing error budget under an explicit growth condition. The proof bounds the binary rank of convolution matrices associated with polynomial maps. Low coordinate degree forces cancellation in the polynomial representing the image, and a polynomial rank bound converts this cancellation into a quantitative estimate for the storage rate. For the double-error-correcting family over $\mathbb{F}_{2^m}$, we prove that the storage deficiency is $Θ(((1+\sqrt{5})/4)^m)$. This refinement follows from an exact Fibonacci formula for a polynomial coefficient rank and a matching exponential lower bound after finite-field evaluation.

0.12

Cache-Aided Linear Function Computation

cs.IT ·2026-10-14 ·Xiaohong Cai, Ruze Zhang, Laigang Guo, Raymond W. Yeung
theory similarity 0.59
Abstract · 11 pages, 2 figures. A shorter version has been submitted to the 2027 IEEE Information Theory Workshop (ITW)

We study cache-aided linear computation in distributed systems where each source generates and stores its own data. An external receiver requests a linear combination of these data, and the sources use information cached before the request is known to reduce the communication needed to recover the requested result. In our model, each of the $N$ sources stores its own independent file over a finite field and has an additional cache of normalized size $M$. The receiver must recover any requested linear combination with zero error from the messages sent by the sources over separate noiseless links. We establish a lower bound on the worst-case communication rate over any finite field by analyzing several requests under the same cache placement. This bound determines the optimal rate when no additional cache is available. For binary files, we propose parity-aided placement (PAP), a coded-placement scheme that combines cached parities with uncoded symbols. For every $N\geq3$, we characterize its communication rate for each request and optimize its placement parameters to obtain a closed-form worst-case rate. The resulting achievable rate meets the lower bound for $0\leq M\leq1/(2N-1)$ and $M\geq(N-1)/N$, establishing the optimal memory--rate tradeoff in these two ranges.

0.22