CS Paper Radar

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

Maryam Keshvari, Remi A. Chou

cs.IT ·submitted 2026-10-29 00:52 UTC · v1
published

Abstract

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.

Comment
A preliminary version of this work was presented at the 2023 Allerton Conference on Communication, Control, and Computing

Closest papers

Nearest neighbours by meaning across the whole index.

Order-Optimal Coded Caching With File and Demand Privacy

cs.IT ·2026-10-04 ·Han Fang, Nan Liu, Wei Kang
similarity 0.70
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.58

Secure D2D Coded Caching under Radius-Limited Connectivity via Lifting

cs.IT ·2026-10-04 ·Han Fang, Nan Liu, Wei Kang
theory similarity 0.68
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

Two-Stage Secret Sharing

cs.IT ·2026-11-12 ·Mizuki Murata, Mamoru Shibata
theory similarity 0.68
Abstract

We give an information-theoretic formulation of two-stage secret sharing for situations in which secret information becomes available progressively. In the proposed model, shares for an initial part of the secret are distributed before the remaining part becomes available, and additional shares are distributed to new participants after the remaining part becomes available, without updating the shares already distributed and without using any additional information other than shares. To characterize this setting, we propose the notion of a two-stage access structure and provide its characterization. We further quantify the amount of information about the first-stage secret that the dealer must retain between the two distribution stages, derive a universal lower bound, and present a construction that achieves this bound for every two-stage access structure. We also position advance sharing as a special case of the proposed model and give its characterization and a related construction in classical information-theoretic secret sharing.

0.18

The Price of Privacy: Randomness Complexity of Graph-Based Multi-Secret Sharing

cs.IT cs.CR ·2026-10-07 ·Piotr Marszalik
code/data similarity 0.66
Abstract · 12 pages, 4 figures, including an appendix with proofs. Code: https://github.com/pjmarszalik/price-of-privacy-code

We study the randomness required to share possibly correlated secret bits among parties connected by a graph. A dealer places shares on the edges so that each party can recover its own secret from its incident shares and learn nothing about the others beyond what its own secret reveals. Anilkumar et al. completely determined the minimum randomness required for three binary secrets. We extend this study to four secrets and obtain results for arbitrary numbers of secrets on general graphs. For four parties on a complete graph, we determine the minimum number of random states for every set of permitted secret combinations: the possible values are one, two, three and four. We also characterize when one random bit suffices on an arbitrary graph.

0.39

Weak Private Information Retrieval for Graph-based Storage under $ε$-privacy

cs.IT ·2026-10-14 ·Jayesh Seshadri, Prasad Krishnan
theory similarity 0.65
Abstract

The problem of Private Information Retrieval (PIR) across graph-based replicated systems has seen a surge of interest in recent literature. In such systems, servers are modeled as the vertices of a graph, and each file is represented by an edge connecting the pair of servers that store it. While previous research on Graph-PIR (G-PIR) has focused mostly on perfect information-theoretic privacy, relaxing this constraint has the potential for significantly higher retrieval rates. In this work, we consider the setting of Graph-based Weak Private Information Retrieval (G-WPIR), under an $ε$-privacy metric. We adapt an existing G-WPIR scheme for arbitrary graphs to analyze its performance under the $ε$-privacy metric. Additionally, we establish a lower bound on the expected download cost for arbitrary graphs under the $ε$-privacy metric and derive from it an explicit rate upper bound for complete graphs. Finally, we show the achievable rate-privacy trade-offs for two specific graph classes---complete graphs and complete bipartite graphs.

0.11

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

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

Local Leakage Resilience of Shamir Secret Sharing: Below Half Threshold Rate

cs.CR ·2026-10-13 ·Hai H. Nguyen
theory similarity 0.64
Abstract

We study the local leakage resilience of Shamir secret sharing, where an adversary leaks a bounded number of bits from every share. For $n$ parties and reconstruction threshold $k$ over a prime field $\mathbb{F}_p$ with $p>n$, we prove the following. (1) There is an absolute constant $c_{\mathrm{bh}}<1/2$ such that, for $k\ge c_{\mathrm{bh}}n$, Shamir sharing is resilient to arbitrary one-bit leakage from every share. The best previous threshold was $0.668n$. (2) For every fixed $0<δ<1/2$ and $k\ge(1/2+δ)n$, Shamir sharing is resilient to $\left\lfloor\fracδ{24}\log_2 n\right\rfloor$ bits of arbitrary local leakage per share. By a recent attack, this number of bits is optimal up to a constant factor depending on $δ$. (3) For every fixed threshold rate $c>0$ and $k\ge cn$, Shamir sharing is resilient to quadratic-residue leakage and to almost all local leakage functions of up to $η_c\log_2 p$ bits, for a constant $η_c>0$. All three results follow from one analytic framework, which we develop for generalized Reed--Solomon codes: local leakage from a uniform codeword is statistically close to the same leakage from independent uniform field elements. The framework expresses the leakage distance as the norm of a function on the leakage outputs. The Efron--Stein decomposition splits this function into orthogonal components indexed by supports of dual codewords. Two tools bound the components: list recovery of the dual code, which is ordinary list decoding for one-bit leakage, and a generalized von Neumann inequality for MDS systems of linear forms that retains linearly many Gowers norms. The first tool gives the result above half, the second gives the constant-rate result, and applying both to different ranges of supports in the same decomposition gives the result below half.

0.15

Physalia: Redistribution-Resistant Content Protection for Decentralized Storage

cs.CR ·2026-09-23 ·Giacomo Giuliari, Karl Wüst
similarity 0.64
Abstract

In decentralized storage systems, access control is often implemented by encrypting the data before upload and sharing the decryption key with authorized parties. A leaked key, however, makes the data publicly accessible, which lowers the barrier to content piracy below that of traditional systems, where piracy requires redistributing the full data. We present Physalia, an end-to-end access-control system for decentralized storage that secret-shares the data itself, instead of just the key, across multiple servers. Leaking the data then requires transmitting it in full: We formalize this intuition and introduce the redistribution bandwidth an adversary must pay to leak protected content and show that Physalia raises it to the size of the data. Sharing across untrusted servers requires robustness against corrupted shares. We develop a robustness transform that turns any computational secret sharing scheme into a robust one and which is of independent interest. In contrast to existing schemes that rely on error correction, it uses signatures with ephemeral keys and adds only constant-size metadata per share. We show that this transform is secure and evaluate Physalia end-to-end on the Walrus decentralized storage system with an on-chain access policy.

0.28