CS Paper Radar

Secure Multi-Access Coded Caching: A Lifting Approach

Han Fang, Qinyi Lu, Nan Liu, Wei Kang

cs.IT ·submitted 2026-10-04 11:34 UTC · v1
theory

Abstract

We construct secure cyclic multi-access coded caching schemes by re-encoding the caches of a secure single-access scheme and reusing its multicast message unchanged. For a library of $N$ files, each of $K$ users reads $L<K$ consecutive shared caches and must recover its requested file while learning no information about the other files. Starting from a parent scheme with a cyclic representation of its cached symbols, the transformation lets each access window recover the corresponding parent-cache symbols and, conditioned on them, learn nothing about the remaining symbols. A deterministic Pascal-window encoder handles symbols whose consecutive appearances span at least $L$ users. A randomized complement-dual encoder handles shorter spans. Over a suitable finite field, these encoders attain the exact minimum per-block storage for every input length in the block-separable, parent-preserving class. Applying the transformation to two secure single-access schemes gives an achievable memory-rate family for $N,K\ge2$ and $1\le L<K$, including the exact rate-one cache size $(N-1)(K-1)/L$. Using converse bounds for arbitrary secure multi-access schemes, we prove approximation guarantees for the achievable family and give a proof of the exact $L=K-1$ tradeoff.

Comment
48 pages, 2 figures. This paper was presented in part at the 2024 IEEE Information Theory Workshop(ITW)

Closest papers

Nearest neighbours by meaning across the whole index.

The Exact Optimal Delivery Scheme for the Cyclically $L$-Separated Placement in Multi-Access Coded Caching

cs.IT ·2026-11-16 ·Kai Wan, Huimei Wei, Minquan Cheng, Giuseppe Caire
similarity 0.72
Abstract

This paper investigates the $(K, L, M, N)$ multi-access coded caching (MACC) system introduced by Hachem et al. The system consists of a server storing $N$ equal-sized files, $K$ cache nodes, each with a storage capacity of $M$ files, and $K$ users, each accessing $L$ consecutive cache nodes in a cyclic wrap-around topology. The server transmits coded information to the users via an error-free capacitated broadcast channel, such that each user obtains its own requested file as a combination of the server transmission and the accessible caches' content. Our objective is to minimize the worst-case transmission load over all possible user demands. First, for the cyclically $L$-separated placement, we derive a new converse bound using the acyclic index coding bound. By carefully counting all valid cache supports, the proposed converse improves upon an existing bound for the same placement. We then develop a linear coded caching scheme based on a novel determinant-based interference alignment strategy, which achieves the new converse bound exactly. Exploiting the determinant structure of a random generating matrix (each of whose columns corresponds to one user), this scheme simultaneously aligns interference across all users into low-dimensional subspaces, while preserving the decodability of their desired packets. Furthermore, by averaging acyclic index coding bounds over cyclic user permutations, we derive a general converse bound applicable to arbitrary uncoded cache placements. By combining the proposed scheme with memory sharing, we demonstrate that the achievable transmission load is within a factor of two of the global bound under uncoded placement. Finally, theoretical and numerical comparisons demonstrate that the proposed scheme generally achieves a strictly lower load than existing schemes.

0.21

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

cs.IT ·2026-11-04 ·Han Fang, Nan Liu, Wei Kang
similarity 0.72
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.72
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

Cache-Aided Linear Function Computation

cs.IT ·2026-10-14 ·Xiaohong Cai, Ruze Zhang, Laigang Guo, Raymond W. Yeung
theory similarity 0.70
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

Heterogeneous Demand-Private Coded Caching: Exact Characterization for Two Users and Two Files

cs.IT ·2026-10-09 ·Tati V D N Eswar, Jithin Ravi
similarity 0.68
Abstract · 20pages

We consider the demand-private coded caching problem with heterogeneous file sizes and cache capacities, where each user must recover its requested file without learning any information about the demands of the other users. We first extend the virtual-user reduction technique to accommodate heterogeneous cache sizes, thereby enabling the construction of demand-private coded caching schemes from non-private schemes. Our main contribution is an exact characterization of the memory-rate trade-off for the fundamental setting of two users and two files with arbitrary file sizes and cache capacities. Specifically, we characterize the optimal trade-off through eight linear inequalities and establish achievability by constructing explicit coded caching schemes for the non-trivial corner points, followed by memory sharing. These constructions include novel asymmetric cache placement strategies tailored to heterogeneous file sizes and cache capacities. For the converse, we exploit the distributional equivalences induced by demand privacy to derive information-theoretic lower bounds that explicitly account for the underlying heterogeneity. Our results generalize the exact memory-rate trade-off characterization for the homogeneous demand-private coded caching setting with two users and two files, while quantifying the additional transmission cost imposed by demand privacy compared with the non-private heterogeneous setting.

0.15

Hotplug Coded Caching: Embedding the YMA and Interference Elimination Schemes via Reed--Muller Codes

cs.IT eess.SP ·2026-11-04 ·Daniela Tuninetti
similarity 0.66
Abstract · companion paper to arXiv:2611.03045

In the hotplug coded caching model, $K$ users fill their caches of size $M$ as a function of $N$ files, but only an unknown subset of $A<K$ users is active in the delivery phase. We recently showed that (i) under uncoded placement, offline users cause a strict load penalty at intermediate memory sizes, so that coded placement is needed; and (ii) for $AM\leq N$, every classical scheme with row-wise placement, including the scheme of Gomez-Vilardebo (GV), can be embedded in a Reed-Solomon code, which removes the penalty. In this note, we show that every point of the scheme of Yu, Maddah-Ali and Avestimehr (YMA) for a classical system with $A$ users is achievable in the hotplug model for every $K\geq A$. Each user is associated with a hyperplane and each file with a homogeneous polynomial; each user caches the restriction of the polynomial to its hyperplane, and the subfiles seen by the active users are the values of the polynomial at the points where their hyperplanes meet. This is a projective Reed-Muller code, which reduces to the Reed-Solomon code when each subfile is cached by one user. We then show, by an existence argument, that every classical scheme whose cache is a linear compression of the Maddah-Ali-Niesen cache and whose correctness holds for generic coefficients can also be embedded over a sufficiently large field; this includes the interference elimination (IE) schemes of Tian and Chen. These embeddings complement the Reed-Solomon one, which allows any row-wise placement and any delivery. Together with past work, our results show that every point attained by a GV, YMA or IE scheme ($N\leq A$ for IE), and every corner point of the linear tradeoff for $A=N=3$, is achievable in the hotplug model with a load that does not depend on $K$. Whether the optimal hotplug tradeoff depends only on $A$ remains open, but these results support a positive answer.

0.04

Secure D2D Coded Caching under Radius-Limited Connectivity via Lifting

cs.IT ·2026-10-04 ·Han Fang, Nan Liu, Wei Kang
theory similarity 0.65
Abstract · 17 pages, 2 figures

Secure device-to-device (D2D) caching requires users to generate delivery signals from their own caches and to recover their requested files without learning the other files. We construct schemes that meet both requirements when communication is limited to nearby users. The network consists of $K$ users on a cycle, a library of $N$ independent files, and a reception radius $r$. Delivery uses one round of noiseless orthogonal local broadcasts, with no server transmission. Each user's cache has capacity $M$ file units. An outer secret-sharing code assigns file shares to senders, and a secure local caching scheme at each sender delivers the requested shares. The cache budget includes the sender's library representation, random state, and delivery keys. We prove that each receiver's cache and all audible broadcasts jointly reveal no information about nonrequested files, despite the dependence between the outer shares. The converse counts transmissions crossing a contiguous user block and uses secrecy to remove one user's observation from the entropy bound. Let $h=2r$ and $K\ge h+1$. The private coded caching (PCC) instantiation attains the minimum peak sum load $K/h$ for every $M\ge Nh$ when $N>1$. For $N\ge K$, its memory-sharing envelope is within a factor $15$ of the optimum throughout $M\in[N/h+2,Nh]$. We also apply lifting without secrecy constraints, achieving the optimal load on $M\in[hN/(h+1),N]$ and a factor-$9/2$ guarantee on $M\in[N/(h+1),N]$ when $N\ge K$.

0.38

Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes

cs.IT ·2026-10-28 ·Ruho Kondo, Yota Maeda
similarity 0.61
Abstract · 13 pages, 5 figures,

Random access codes (RACs) encode a $q$-ary input string into fewer $q$-ary symbols while allowing any requested input symbol to be recovered with probability above the random-guessing value $1/q$. However, it remains unclear what asymptotic guarantees on compression and recovery probability should be required of RACs. We address this question by introducing the notion of asymptotically good RACs and give two polynomial-time constructions. First, an $[n,k,d]_q$ linear code with $d\ge2$, together with an encoder based on its orthogonal-array property, yields an $(n,n-k)_q$-RAC with worst-case decoding success probability \[ p_{\rm wc}=\frac{1}{q}+\left(1-\frac{1}{q}\right)\frac{d-2}{n}. \] These OA-RACs are asymptotically good whenever the underlying linear codes are, and Garcia--Stichtenoth algebraic-geometry codes give a concrete polynomial-time realization. Second, a direct-sum strategy using OA-RACs derived from $q$-ary Hamming codes and the trivial $(1,1)_q$-RAC yields asymptotically good RAC families at every prescribed RAC rate $R_{\rm RAC}=(n-k)/n\in(0,1)$. Numerical results demonstrate favorable finite-length performance of both constructions.

0.23