The Price of Privacy: Randomness Complexity of Graph-Based Multi-Secret Sharing
Abstract
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.
Related
- Cryptanalysis of a Class of Ideal Secret Sharing Schemes Based on the CRT for Polynomial Rings
- Communication and Privacy Trade-Offs in Distributed Storage With Shared Secret Keys
- Differentially Private Distributed Optimization via the Intrinsic Randomness of Zeroth-Order Estimators: Sampling Geometry, Convergence, and Privacy Guarantees
- Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection
- Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy
BibTeX
@misc{marszalik2026price,
title = {{The Price of Privacy: Randomness Complexity of Graph-Based Multi-Secret Sharing}},
author = {Piotr Marszalik},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10002},
eprint = {2610.10002},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10002},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Price of Privacy: Randomness Complexity of Graph-Based Multi-Secret Sharing
AU - Piotr Marszalik
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10002
UR - https://arxiv.org/abs/2610.10002
AB - 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.
ER -