Paperlane

no. 5 · Friday 30 October 2026

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

Maryam Keshvari and Remi A. Chou

math.IT

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.

comments
A preliminary version of this work was presented at the 2023 Allerton Conference on Communication, Control, and Computing
fields
Information Theory
pdf ↗ page arXiv:2610.39112 ↗