Paper 2026/2395
The Price of Privacy: Randomness Complexity of Graph-Based Multi-Secret Sharing
, University of WarsawAbstract
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.
Note: Code and logs: https://github.com/pjmarszalik/price-of-privacy-code
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- secret sharingcorrelated secretsrandomness complexityinformation-theoretic security
- Contact author(s)
- pm448533 @ students mimuw edu pl
- History
- 2026-10-08: approved
- 2026-10-07: received
- See all versions
- Short URL
- https://ia.cr/2026/2395
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2395,
author = {Piotr Marszalik},
title = {The Price of Privacy: Randomness Complexity of Graph-Based Multi-Secret Sharing},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2395},
year = {2026},
url = {https://eprint.iacr.org/2026/2395}
}
